heno239’s blog

まとめたいことをまとめる

ICPC 2023 Asia Yokohama Regional スタッフ参加記

  • 前書き

こんにちは、heno239です。

 

今回はICPC 2023 Asia Yokohama Regional にスタッフとして参加してきました。

私自身は去年まで選手側としてこの大会に出場していたのですが、参加資格がなくなり、かつコーチの資格もないため、このような形で参加することになりました。

 

大会のスタッフ側がどんな感じなのかあまり知れ渡っていない(実際自分も全然どんな感じなのか知らなかった)気がしているので、この記事では

  1. スタッフの仕事内容(自分の場合)
  2. どういう点が楽しかったか/面白かったか/お得だったか

について書き、スタッフ側で参加することにも興味を持っていただけたら嬉しいなと思っています。

 

  • 参加することになった経緯

10月半ばごろにJAGの方からスタッフのお誘いをいただきました。当時の予定では11月10日~11月18日にICPC WFでエジプトに行く予定だった*1ので、「体調が崩れてなければ行きます」みたいな微妙な返事をした記憶があります。

 

そうして何日か経った後にエジプト行きが延期されたので、心置きなくスタッフ参加できるようになりました。延期でキャンセルした飛行機のキャンセル料がどうなるか分からず不安になったり、いつまで経っても選手を引退できなくてなんだこれとなったり、逆に横浜大会はのびのび参加できるなと安心したりして、とても複雑な気持ちになりながら日々を過ごしていました。

 

スタッフとしての仕事は11月24日に現地に行くまで特に無かったので、それまでは普通に過ごしていました。

 

また、スタッフ参加にあたって、交通費全額支給と宿泊場所の提供、(これは後ほど知りますが)食事or食費の支給があり、金銭面では全く困ることが無い*2ように設計されていました。

学生運営のイベントスタッフしか経験したことが無かった自分にとっては、かなり待遇が良いんだなと感じました。

 

  • スタッフ1日目(大会0日目)

11時集合で、この日は主に会場の設営を行いました。

何もない空間から全てを配置していくのかと身構えていたのですが、到着時には既に机やPCは並べられていました。以下に時系列順で行った仕事を書きます。

----------------------------------------------------------------------------------------------

  • 各机のPCにつなげられるように電源を引く

この仕事は、会場にいくつかあるコンセントと机を頂点として、以下の制約を満たすように辺を貼ってグラフを作る仕事でした:

  1. 各机について、同じ連結成分内にちょうど1つコンセントがある
  2. 連結成分のサイズに上限がある
  3. 通路を跨ぐような辺の数をできるだけ小さくする

ホワイトボードを使ってこの問題が解かれ、その通りに皆で全身を使って実装しました。

  • 前項で貼った辺を強くする

養生テープを用いて、各辺が人間の足によって破壊されないように固定・保護しました。

  • ネットワークケーブルを引く

こちらはどれをどのように繋げるかについて全て指示されていたので、その通りに実装していました。

  • ネットワークケーブルも強くする

養生テープを用いて、各ケーブルが人間の足によって破壊されないように固定・保護しました。

  • 机の上にあらゆるものを置いていく

スタッフで分担して、

で机の上に置いてあるものを順次運んでいきました。自分は主に計算用紙を配っていました。

  • 椅子の設置

ナイスな椅子を運んで設置していきました。

  • コンテストのリハーサルのリハーサル

PCの環境やコンテストのジャッジシステムが想定外の挙動をしないことを確認するため、皆でリハーサルのリハーサルが行われました。

「あらゆる手段を用いてできるだけインターネットにアクセスしようとしてみてください」という指示があったりして面白かったです。

 

----------------------------------------------------------------------------------------------

このように仕事を行っていたのですが、全てが順調で、特に焦ったり困ったりすることが無くて精神的には楽でした。(肉体的には疲れましたが)

最後は仕事がなくなって暇になったので、できるだけ風船を膨らませて会場に飾り付けていく、ということをしていました。

あまりにも風船を膨らませるのが下手すぎて、beetさんに「風船膨らませたことないんですか？」と指摘されてしまいました。

 

また、準備中にもスタッフ用のSnack Areaがあって、いつでもお菓子を食べたり飲み物を食べたりできるようになっており、休憩しやすかったのがかなり嬉しかったです。

 

昼食/夕食も食費をいただけるとのことだったので、美味しい食事をすることができました。(参照:

hackmd.io

)

 

  • スタッフ2日目(大会1日目)

9時集合で、この日は13時から続々と選手たちが入場してきます。

午前中は前日に引き続き、電源やネットワークがうっかり破壊されないように辺の強化を行っていました。

 

選手が入場してからは、主に会場の案内や、会場を巡回して困っているチームがあったら助けに行く、ということが仕事になりました。

この際、念のためコンテスト終了までは選手らとの交流は控えましょうという指示があったので、あまり喋らないように気を付けていました。

 

開会式の後にリハーサルコンテストがありました。

選手たちにとってのコンテストのリハーサルですが、スタッフにとてもコンテストのリハーサルになっており、コンテスト中の主な仕事である「プリンターの前で待機して印刷物が出てきたら適切なチームのもとに持っていく」と「会場を巡回して怪しい動きをしている人がいないか監視する」を行っていました。

特に印刷物に関しては、あるチームが印刷したものを別のチームに誤配してしまうとコンテストの公平性が大きく損なわれる事態になりかねないので、緊張感のある仕事になっていました。(仕組み自体も間違いが無いか入念にチェックするような仕組みになっていました。)

 

余談ですが、「ファーストプリント賞」という賞を裏で勝手に作り、1番最初に印刷したチームをこっそり賞賛していました。

 

こうして無事リハーサルは終わり、スタッフ2日目/大会1日目も無事に終わりました。

 

  • スタッフ3日目(大会2日目)

8時過ぎ集合で、この日は8時半から続々と選手たちが入場してきます。

この日の仕事はリハーサルの日と同様なのですが、リハーサルよりも厳重に様々なことをチェックする必要があり、コンテスト開始まで会場を歩き回っていました。

 

そしてコンテストの開始時間を迎えました。

今日の仕事はリハーサル通り「印刷物の配達」「会場の徘徊(昼食のゴミ回収含む)」となっており、また「大会配信への出演」もすることになりました。

 

最初のうちはどのチームもほとんど印刷をしないので結構時間に余裕がありましたが、問題は閲覧できない状況にありました。

しばらくしてスタッフ側も問題文が閲覧できるようになり、いつの間にかスタッフ待機椅子が問題文で埋まっていました。問題文を手に取らないと座れないシステム   

 

JAGの人たちで手分けして問題を解いて大会配信に役立てよう、という感じになり、問題を見ていきました。この時点ではABDFあたりがACが出ていた記憶があります。

とりあえず自分は最初の方にあってまだ解かれていない、数え上げのC問題を解くことにしました。

それで「解けたと思ったら解けていなかった」を何度も繰り返すうちに、他のJAGの人たちによってC問題以外の解法が出てしまいました。(1発で最難問を引いてしまった...)

結局時間をかけて解けたのですが、その間は印刷等の仕事を他の人たちに押し付ける形になってしまったので、申し訳なかったです。

 

C問題を解いた後は主に印刷物の配達を行い、時々順位表を見てはあれやこれや他の人と予想する、ということを行っていました。

また、最後の方に大会配信にも出演し、去年までのICPCの経験や、凍結している順位表を見てあれやこれや述べたり、を行っていました。

 

こうしてコンテストが終わり、解説・表彰式・閉会式・懇親会が行われました。

コンテスト終了後は特に仕事もなく、イベントを楽しんでいました。

ドーナツ配布に関してスタッフ側にもドーナツがたくさん置かれていたのですが、「毎年大量に余る」という噂を信じてたくさん食べたら割とすぐなくなってしまって申し訳ない気持ちになりました。

 

懇親会について、去年よりも会場が一回り大きく、また食べ物/飲み物が提供されるようになっており、やっぱりこんな感じで豪華に懇親会すると楽しくて良いなあという気持ちになりました。

 

こうして懇親会も終わり、自分も帰路につきました。

 

  •  終わりに

今までずっと選手側として参加してきた大会に、今回スタッフとして参加することになり、とても新鮮な気持ちになったのと同時に、少しだけでも恩返しできたのかなと思いました。

 

一方で、まだ自分は選手だという強い意識があり、コンテストの問題セットに正面から向き合えなかったり、強いチームを見て焦燥感を覚えたりと、モヤモヤした部分は正直あります。(どうしようもないことですが)

 

とはいえ、スタッフとしてとても良い環境の中で大会に貢献し、コンテストに熱心に取り組む選手たちを支えることができたり、また逆にその姿からモチベーションを得られたのはとても良かったなと達成感や満足感があります。とても良い環境を整えてくださった運営の方々には感謝しかありません。

 

来年も是非何らかの形で参加できたらいいなと思っています。ここまで読んでくださりありがとうございました。

 

  • おまけ

最後に会場の風船を割っていく音が、打ち上げ花火をしている音に聞こえて、とても良かった。

 

*1:スタッフの日程は11月24日~11月26日

*2:むしろ美味しいものが無料でかなり食べられる

AtCoder World Tour Finals 2022 参加記

  • まえがき

heno239です。今回はAtCoder World Tour Finals(以下略称としてWFと書きます)に選手として参加してきました。

大会中の大体の経緯はTwitter(あるいはX)に書いてきましたが、あらためてここに記事として書いていきたいと思います。

 

  • 2021年 参加権取得

2021年12月4日のAGC056の結果を経てWFへの参加権を得ました。

https://clist.by/standings/atcoder-race-ranking-2021-26421821/

しかし、この時は情勢的にWFが延期され続けており、本当に開催されるのか、開催されるとして一体何年後になるのか、という不安があり、あまり現実味がないまま年月が過ぎ去っていきました。

 

  • 2023年 開催決定

2022年後半あたりからオンサイトコンテストが復活し始め、ずっと頭に残っていたWFもそろそろ動かないかなと思っていたところ、ついに開催されると発表が出ました。

atcoder.jp

(実はこの発表より少し前から通過者には連絡が来ており、開催されるぞー！！とtwitterで大騒ぎしたかったのですが、内々での連絡内容を大公表するのはまずいなあと思い黙っていました。)

全ての通過者が参加できるようにかなり早い段階から日程アンケートが行われたりしていて、めちゃくちゃ配慮されてるんだなあと少し感動していました。

 

飛行機やVISAの問題など諸々の質問がメールで一斉送信されてくるのですが、毎回「私は日本人です」と返答することになり、ちょっと滑稽で面白かったです。

 

  • day 0 (コンテストday1前日)

この日はコンテストday1の前日で、主にhotelに移動する日でした。

他の参加者と会うこともなく、主に本番に向けて英気を養っていました。

泊まった部屋が32Fで、自身の過去最記録を更新しました。

  • day 1

11時間ほど眠り、朝9時に朝食に行きました。

ビュッフェ形式で、自分の考える最強の朝食を作り上げることができるので嬉しかったです。

 

11時頃からhotel→コンテスト会場の移動となっており、割と距離があって大変でした。

この時点ではまだ名札が無かったので、maspyさん達と会話しているうちにAtCoderのスタッフ勢に紛れこみ、スタッフになりきっていました。途中で渋谷スクランブル交差点の観光コーナーが始まったのは面白かったです。(海外勢どんな気持ちで見てたんだろう)

 

着いてからコンテスト開始まで1時間ぐらい余裕はあったので、会場で昼食をとったりし、コンテストに向けて集中を高めていきました。

 

Contest day1中にとった戦略を以下に書きます。

  1. とりあえず景気付けにA問題を考える。順位表を見ていると結構FAが早かったので、そのまま取り組み、AC。
  2. B問題からE問題までの問題のジャンルを見る。B構築、C数え上げ、D最適化、E数え上げ。自分はかなり数え上げに自信があるので、Cぐらいは解けないとこのWFで勝負にすらならないだろうと思い、Cを選択して一点集中する。
  3. コンテスト開始3時間時点で大体解けた気持ちになっていたが、微妙に計算量が悪くて定数倍改良を要求されたり、実装に細かなミスがあって時間を食われたりして、結果的に残り30分ぐらいでようやく通る。
  4. 30分しかないので、閃きさえすればすぐ解けそうなBに挑むが、間に合わず。

結果的に7位につくことができ、1位の5000点(凄すぎる)を除けばまだ十分day2で逆転できるなあという感じになりました。

 

コンテスト後にtwitterを見たところ、コンテスト参加者の異常行動が結構すごいと話題になっていましたが、そんなことになっていたとは全然気づきませんでした。(一番前の席だったからかな)

 

結構疲れたので、帰ってたくさん寝ました。あまり記憶が無いです。

 

  • day2

10時間ほど眠り、朝9時に朝食に行きました。

この朝もあまり記憶が無いです。とにかくday2で逆転したいという気持ちで一杯でした。

唯一残っている記憶は、この日も渋谷スクランブルエッグ交差点の観光があり、日本の素晴らしい文化「天丼」を海外の皆様にお伝え出来たことかなと思います。

 

Contest day2中にとった戦略を以下に書きます。

  1. 今日は全ての問題の配点が異常な上に、day1で少しビハインドを背負っているので、A問題で景気付けなどということは考えず、最初からA~E問題を見てみる。
  2. Aゲーム?、B数え上げ、C最適化、D数え上げ、Eゲーム。day1と同じ要領で、自分はB問題ぐらいは通さないと話にならないと思い、B問題を選択して一点集中する。
  3. B問題をFAでき、結構希望が見える。この時点での順位表がこちら

  5. ここから仮にA問題を通して4501点になったとしても、3001点勢が1人でも1500点↑を通したり、あるいは2502/2501点勢が一人でも2000点↑を通した時点で捲られてしまうので、A問題を通す価値は無いと判断。
  6. CDEのうち自分をここまで支えてきた"数え上げ"であるD問題に挑むが、解けない。
  7. 残り1時間時点で、あまりにも順位表が動かない様子を見て異常を察知した自分は、4501点でも3位に入れるのではないかと思い直し、慌ててA問題を考える。
  8. それっぽい解法を考え実装までしたが、サンプルが合わないまま終了。

結果的にday1終了時点と同じ7位になりました。3位に入るのもかなり現実味を帯びていたので悔しかったですが、このメンバーの中で7位に入れたのはかなり健闘できたのかなと思っています。

一方で、1位や2位との差はあまりにも大きくて、まだまだ高みがあるんだなあと思い知らされました。この2つの問題セットを作成できるmaroonさんもめちゃくちゃ凄いなと思い知らされました。

 

コンテスト後、懇親会があり、卓球やダーツ、テーブルサッカー、ビリヤードが遊べる会場に行きました。

自分は

  • 卓球: それなりにやったことがある
  • ダーツ: ゲームの中でしかやったことがない
  • テーブルサッカー: めっちゃやったことがある
  • ビリヤード: ほんのちょっとだけやったことがある

という感じで、主に卓球とテーブルサッカーをしていました。

chokudaiさんとバトルし、卓球ではボコボコにした(要出典)んですが、ダーツではボコボコにされました。(実際に僕に向かってダーツを投げられたという意味ではないです)

海外勢の数人とも卓球やテーブルサッカーで勝負して、とても楽しかったです。(卓球うまい人多くてすごい)

 

懇親会ではしゃぎすぎた結果、半分死にながらhotelに戻ることになりました。

hotelに着き、ここで正式にWF終了、解散となりました。

 

  • day3

起床後にhotelの朝食に行くと、海外勢が何人かいて余韻を感じました。

 

  • 終わりに

並みいるLegend達の実在を確認できてとても感動しました。そのうち何人かとは挨拶したり懇親会でゲームしたりでき、とても良い経験になりました。

 

英語をちゃんと話せたらもっとちゃんと交流できたんじゃないかなあという気持ちはあり、頑張っていかないと...という感じです。

 

コンテスト自体も、day1はB問題、day2はA問題が、AC数が多いのに自分が通していない問題で、5時間じゃ全然足りなかったんだなあ、あるいは自分がまだまだ頭の回転速度が足りていないんだなあ、と痛感しました。この辺りはもっと練習を積むことでもっと成長できるなあと思い、今後もより頑張っていきたいと思わせられました。

 

コンテスト後に、WFについての実況や、更には自分についての実況等をしているツイートをたくさん見て、とても楽しかったです。特にday2は、「day1で思ったより見られていたし、最後まで諦めた姿は見せず本気で頑張ろう」という気持ちになりました。ありがとうございました。

 

今年度もWFに通過できそうなので、これからもまた頑張ります。

ここまで読んでいただきありがとうございました。

 

  • おまけ

エレベーターで遊ぶのはやめた方がいいです

yukicoder No.540 格子点と経路 上界について

この記事では、

No.540 格子点と経路 - yukicoder

において、最大値と一致する上界をどう与えるかについて書きます。

実際の構成方法については他の記事を参考にしてください。

  • 前提として

まず、y座標が0であるような横線はw個あります。

このうち、答えにカウントできるのは最大でもceil(w/2)個しかありません。(頂点を共有する横線同士を両方カウントできないことから来ています。)

この事実を頻繁に使用します。

  • wまたはhが偶数の時

wを偶数とします。(wが奇数の時はhとwを入れ替えてください。)

この時、カウントできる横線の個数は(w/2)*(h+1)個です。

横線の前後にできるだけ縦線を入れることを考えると、上界として(w/2)*(h+1)*2+1が与えられます。

h=wの時は縦線も横線と同じ個数しか存在しないので、さらに良い上界として(w/2)*(h+1)*2が与えられます。

  • wもhも奇数の時

上界として(h+1)*(w+1)-min(h,w)が与えられることを以下で書きます。

各y座標について、「良い横線の状態」を「(w+1)/2の横線をカウントする状態」として定義します。「良い縦線の状態」についても同様に定義します。

 

とりあえず、あるjが存在して、y座標として2*jと2*j+1がともに「良い横線の状態」であったとします。

この時、x座標として2*i,2*i+1をともに「良い縦線の状態」にしてしまうと、(2*i,2*j),(2*i,2*j+1),(2*i+1,2*j),(2*i+1,2*j+1)で四角形ができてしまい、破綻します。

したがって「良い縦線の状態」となるx座標は(w+1)/2個しか存在せず、カウントできる縦線の個数は(h+1)*(w+1)/2-(w+1)/2個で抑えられます。この縦線の前後に横線を入れることを考えても、最大値は((h+1)*(w+1)/2-(w+1)/2)*2+1=(h+1)*(w+1)-wで抑えられることが分かります。

 

次に、どのjについてもy座標として2*jと2*j+1のいずれかが「良い横線の状態」ではなかったとします。

この時はカウントできる横線の個数が(h+1)*(w+1)/2-(h+1)/2で抑えられるため、最大値を(h+1)*(w+1)-hで抑えることができます。

 

これらを組み合わせると、最大値を(h+1)*(w+1)-min(h,w)で抑えられることが分かります。

ICPC 2021 Asia Yokohama Regional 参加記

  • まえがき

皆さんこんにちは、heno239です。

今回は 

ICPC 2021 Asia Yokohama Regional

にチーム「Heno World」で参加しました。

チームメンバーはheno239・yamunaku・moririn2528の3人で、去年とチーム名もメンバーも同じです。

わざわざ集まるのが面倒だった昨今の情勢を鑑みて、3人とも別の部屋からオンラインで出場することになりました。

 

  • 1日目(コンテスト前日)

この日は13:00からコンテストの参加受付がありました。

13時前にチームメンバーが全員集まったので安心感がありました。(色々あって受付は13:30ぐらいになりました)

13:50ぐらいから開会式があり、開会しました。

 

14:10から、本番と同じ環境を用いたpractice contestがありました。

コンテスト時間は2時間で、問題は去年の問題がそのまま使われていました。

去年の僕がE,F,H,I問題を実装していたので、practiceではそれ以外のA,B,C,D,G,J,KのうちA,B,C,J,Kを腕慣らしで通しました。1年経ってたのに全部解法を覚えていて、やっぱり印象に強く残るコンテストなんだなあと実感しました。

 

また、practice contestでは「assertがちゃんとRE返してくれるか」や「無限ループするとREになるか」や「bitsetの_first_bitが使えるか」や「美味しいカレーの作り方を書いたらACになるか」*1等、様々なことを確認しました。

 

practice contestが終わったあと、軽い質問時間がありました。

そこで「submissionした後にどのソースコードを提出したかを確認する方法はありますか？」という質問がありました。(submitはローカルファイルを選んで提出する形だったので、誤提出が起きやすかった、という事情がありました)

この質問に対する回答が「あると思うんだけど現状ない」みたいな感じで、結局翌日に「ある」になりました。

(去年は結局なかった(し、誰も指摘しなかった)ので、変わったのすごい)

 

参考資料(?)↓

 

質問時間が終わるとその日のプログラムは終わりで、あとは「ちゃんと早く寝る」だけになりました。

コンテストに向けて3日前ぐらいから23時寝7時起きみたいな生活をしていたので、その日も無事21時に寝ることができました。

 

  • 2日目(コンテスト当日)

朝3時に起きて、その後眠れませんでした。今もまだ眠れていないので1週間ずっと徹夜しています。

8時頃にはチームメンバー全員の起床が確認でき、いよいよ本番を待つこととなりました。

 

そして9:10からコンテストは始まりました。

 

  • コンテスト中

  1. チームメイト2人にAとBを任せて*2、自分はC以降の問題文を読む。
  2. まずKを読み、「時間をかければ解けるけどすぐには解けなさそう、順位表で他のチーム解かれてたらやろうかな」と思いパス
  3. やっぱり去年と同様にmod 998244353みたいなことが書いてある問題からやろうと思いなおし、問題文を"mod"があるかどうかで枝刈り探索していくと、G問題「mod 10^9+7」に到達。
  4. 問題を読むと一瞬で解法が浮かんだので実装するも、WA。(それなりに実装量もあるので実装ミスかな)と思い、小さいケースを手で作って試していると、考察ミスが発覚(自分の子が親で自分の親が子になるやつ)。修正してAC(FA)。
  5. チームメイトの様子を見ているとAがACされ、BでWAが出て苦戦している様子。Bを手伝いに行き実装すると、自分もWAが出て頭を抱える。結局3人とも誤読していることを発見し、修正してAC。
  6. この時点で開始1時間ほどで、順位表を見るとJが通されている。そこで自分がJに行き、チームメイトに他の問題を探ってもらう形に。
  7. Jで「overflow事故」「場合分け書き忘れ」「提出ファイル間違える」「ジャッジミス」の4連コンボが決まり、4ペナ出しつつなんとかAC。今になって思うと、早く解かなきゃ、とかなり焦っていた気がする(特に提出ファイル間違いについては・・・)
  8. Jで苦しんでいる間にC問題とD問題をチームメイトがそれぞれやってくれていたので、他の問題を見る。各問題の所感は、E問題:存在を忘れてた、F問題:ちょっと考えたけど分からない、そもそもTL:30sがやばすぎるので近寄りたくない、H問題:誤差の制約をどう使うか分からない、I問題:頑張れば解けそう、K問題:頑張れば解けそう、といった感じ。
  9. 上記の中からK問題を選び、突撃。この間にDはACされ、CはWAが出る。C問題のWAの原因特定も手伝いつつK問題を考える形に。
  10. 結局K問題に進展はなく、C問題は僕なしで通る。チームメイトありがとう・・・
  11. 3人そろったところで問題を見直し、自分もK問題の考察からI問題の考察に移行する。
  12. チームメイトとグラフのお絵描きをしながらI問題の考察をし、かなり順調にいって考察が完成する。そのまま実装し、AC(FA)を勝ち取る。この時点で7完がHeno Worldのみとなり、単独一位に浮上する。(そしてこの時点でほぼ2位に入るだろうと思っていた。)
  13. 相変わらずE問題の存在は忘れているしF問題はTL:30s,H問題は誤差で近づきたくないので、K問題に突撃。そのまま適当な嘘をいくつか投げて撃沈。(実はコンテスト後に誤読が発覚)。

そしてコンテストが終わりました。順位表は終了1時間前の状態のまま凍結されており、その時点ではUT a.k.a. Isには確実に負け、tonosamaやTLE_workには2問通されていると負ける、他のチームには大体勝ち、という状況でした。

 

特にtonosamaが怖かったので、ドキドキしながらYesNo(順位表開示イベント)を迎えました。

 

  • コンテスト後

まず問題の解説とスポンサー企業の紹介がありました。

問題の解説では、ヤバいと思って避けたF問題が実は解法から見ると普通の問題だったり、H問題の解説に驚いたり、K問題の解法になるほどと思ったりしたり、E問題の解法にうわあとなったりしました。特にF問題についてはACが出なかったことが驚くべきものでした(TLが30sというだけで全チームが避けた結果、こうなっているのだろうと思います。)

 

その後いよいよYesNoがありました。

YesNoの結果2位が確定し、例年通りであればほぼ確実にWorld Finalへの参加が決まりました。とても嬉しかったのを覚えています。

f:id:heno239:20220323192456p:plain

 

表彰式ではインタビューみたいなものがあったのですが、コメント内容はちゃんと準備したのに名乗るのを忘れてしまいました。その後に1位のUT a.k.a. Isの方々か素晴らしいインタビューをしていったので、社会性の違いを見せつけられる結果となってしまいました*3。

 

その後、gatherにてオンライン懇親会が行われており、渾身の懇親をしました。20:00ぐらいに眠気に勝てなくなり、そこで僕のICPC 2021 Asia Yokohama Regionalは幕を閉じることとなりました。

  • あとがき

結果として2位をとり、おそらくWorld Finalへ行きます。

これでWorld Finalは3回目であり、World Finalの参加回数の上限規定に引っかかるため、来年はICPCに出られません。

結局、ICPC Asia Yokohama Regionalは3度参加し、そのうち2回がオンラインになってしまいました。ここ2年横浜の現地で他のチームの方々と交流できなかったのがとても心残りです。

World Finalも、

World Final 2019:オンラインで既に開催された

World Final 2020:今年11月に開催が予定されていて、どうなるか(オンラインになるかとか)が分からない

World Final 2021(今回の):どうなるか何も分からない

という感じで、かなり不明瞭な感じになっています。

 

2位をとった安堵の先にも後にも不安だらけですが、World Finalでも結果を残せるように頑張っていきたいです。

ICPC運営の皆さん、他のチームの皆さん、また特にチームメイトの2人へ、ありがとうございました。

 

  • おまけ

うまい棒ではずれを引いたので今回はおまけはありません。

*1:なりませんでした

*2:コンテストはA,B問題が簡単な2問と公表されており、それ以外の問題は難易度がランダムだった

*3:Give me sociability

AOJ 2597 Color the Map Extreme

  • まえがき

解説PDFが閲覧できなくなっていたのと、ネットに自分の解法が落ちてなさそうだったので書きました。

 

  • 問題概要

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2597

 

  • 解法

とりあえずグラフを作る。4色定理があるので答えは4以下。

 

答えが1かどうか→グラフに辺があるかどうか

答えが2かどうか→グラフが二部グラフかどうか

 

なので、答えが3かどうかを調べる。

 

まず、色1,2,3があったときに、色3となる頂点が全て決まっている場合、これは残りの頂点を2色で塗る問題に帰着される。

 

そこで問題となるのが色3となる頂点の決め方に2^N通りあること。少し考えると、色3となる頂点の集合は極大独立集合であると仮定してよい。

 

ところでグラフの極大独立集合は O(1.618^N) で列挙できる。

具体的には、頂点を1から順に見ていったときに、次数0の頂点は独立集合に加えるしかないし、次数1以上の頂点はそれを独立集合に加えると頂点N-2以下のグラフとなるので、計算量がフィボナッチ数で抑えられる。

 

したがってO(N^2*1.618^N)でこの問題は解くことができる。

このままだと少し遅いので、お好みの枝刈りをどうぞ

(私の場合は、答えが3かどうかの判定の直前に次数2以下の頂点を順次削除しました。)

 

  • 実装

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=6161908#1

AOJ 1340 Directional Resemblance

  • まえがき

初見でかなり混乱したので書きました

そんなに厳密な説明じゃないです(覚え書き程度です)

 

  • 問題内容

N個の3次元ベクトルが与えられる。

これらのベクトルは全てx軸方向、y軸方向、z軸方向に正である。

ベクトルのうち2つをとったとき、なす角の最小値と、最小値になるようなindexのpairを求めよ。

 

  • 解法

問題を言い換えます。

 

まず、各ベクトルを、「原点を中心とする半径1の球の表面」に射影します。

(前述でベクトルv_iを点p_iに射影したとします。)

そうすると、2つのベクトルv_i,v_jのなす角の大きさは、点p_i,点p_jを最短距離で結ぶ球の弧の長さと比例します。さらにこの値は、点p_iと点p_jのユークリッド距離に比例します(最重要)。

 

結局、「球面上にN個の点が与えられるので、ユークリッド距離が最短の2点を求める」問題に言い換えられました。

 

あとは、最近点対(参照: https://compro.tsutaj.com//archive/190207_divcon.pdf )と同様にやります。具体的には、(z軸のことを忘れて)上のスライドのp37のように各点についてスリットを考え、この点とスリット内にある点それぞれについて、(z軸のことを思い出して)3次元空間上の距離を求めます。

「x,yの値が近いがzの値が違う点がめちゃくちゃある」みたいなときに計算量が崩壊しそうですが、「点が球面上にある」という条件が効いて(?)十分高速に動きました。

 

  • 実装

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=6148187#1

 

  • おわりに

なにかあれば↓にお願いします。

twitter.com

Educational Codeforces Round 15 F. T-Shirts

  • まえがき

解説が無かったので、正解につながるキーワードを書いておきます。

(解説と呼べるほど丁寧には書いてありません)

  • 問題概要

https://codeforces.com/contest/702/problem/F

問題を言い換えると、結局長さnの数列aがあって、クエリxに対して

int cnt=0;

for(int i=0;i<n;i++){

  if(x>=a[i])x-=a[i],cnt++;

}

return cnt;

をする問題。

  • キーワード

この問題を解くにあたってのキーワードは、「xの値を高速にx/2未満にする」です。

 

  • 解法の概要

いま、数列中での現在地iと現在のクエリの値xがあります。

2^k<=x<2^(k+1)を満たす整数kを用意します。

ここから、O(logN)でiの値を進めてxの値を2^k未満にします。

このとき、次の2パターンがあります。

  1. aの値が2^k以上のものを1つ以上とる
  2. aの値が2^k未満のものだけでxの値が2^k未満になる。

一旦1.のパターンがおこり得ないとすると、2.のパターンはあらかじめ各0<=k<20に対して値が2^k未満のものだけの数列を作っておくと、累積和を良い感じに二分探索することで、iをどこまで進めるとxが2^k未満になるか分かります。

逆に2.のパターンがおこり得ないとすると、1.のパターンはこれもあらかじめ各0<=k<20に対してb_i=(2^k<=a_iかつa_i<2^(k+1)のときは0<=j<iでa_j<2^kを満たすものの総和+a_i、そうでない時は2^100)という数列を用意しておくと、「整数le,supに対し、j>=leかつb_j<=supを満たすjの最小値」を求める話になります。

 

そこで、2つのパターンのうち行き先が近い方に行くことで、iの値を進めてかつxの値を2^k未満にすることができます。

 

  • 計算量

Aを数列aの最大値として、O(NlogA+QlogNlogA)

  • 関連問題

Codeforces Global Round 14 I. Phoenix and Diamonds

https://codeforces.com/contest/1515/problem/I

この問題に個数と個数の変更クエリがついて複雑になった問題。

逆にいえば複雑になっただけなので、ほとんど同じ解法でものすごく頑張ると解けます。

  • あとがき

かなり雑に書いたので、何かあれば 

https://twitter.com/heno_code

まで気軽にご連絡ください。