ICPC参加記
自己紹介
東京理科大学のチームOSMAです。読み方はオスマです。 去年まではja君と別のチームで出てたのですが、今年は野田キャンパスの白椿さんを誘ってチームを結成しました。 白椿さんは横浜に出場するのは2回目で僕とja君は初です。
- srtubaki
- atcoder青色 知識が豊富 実装が早い MA学科
- pres1dent
- atcoder水色 グラフやクエリの問題が得意 OS学科
- ja14378
- atcoder水色 数学系の問題が得意 OS学科
コンテスト開始まで
起床に成功し朝ごはんを食べました、ちょっと量が少なめだったけど大会中の昼食に期待してホテルを後にしました。
会場に到着し、駆けつけてくれたコーチのヘキサさんに挨拶をしたり、記念撮影をして入場しました。 写像12相の記事を印刷してきてくれて渡してくれました。本当にありがたかったです。
入場してからはリュックや電子端末ををビニール袋に入れたり、ライブラリをファイルから取り出したりと、何だかんだ準備をしていたら開始まで残り２分になっており、あっという間に始まりました。
本番
リハーサルではもたついてしまったので、素早く封筒を開封し、パソコンの環境を整え、サンプルの入力をja君に変わってもらいます。 （終わってから知ったのですがサンプルってダウンロードできたんですね）
Bの考察をします。早く解かないとという焦りから問題文を流し読みしてしまい、最も小さいものを出力するという条件を見落としていました。白椿さんがAを通してくれた(0:18)ので、実装をしました。
結局実装もバグらせて、嘘解法のため２ペナしてしまいました(0:40ぐらい?)。冷静ではなかったのでデバッグをja君に変わってもらいました。解法が思いついてから実装するまでは紙でコーディングをしていたのですが、もっと条件やサンプルを確認すれば良かったとめちゃくちゃ後悔しました。
Eが解かれていたので読んでみるとdfsでできそうとわかったので白椿さんに問題と解法を伝えて実装してもらいます。 もう自分では実装なんてする気になれず、実装の強いチームメイトがいるのは本当にありがたかったです。 Bはプリントデバッグに交代です。
解かれていたKを読んだのですが、誤読して変数mとnを逆だと思っていて、愚直が通るとかbitset高速化とか嘘解法を生やしていました。白椿さんがEを無事通して(1:19)くれたので、Kの嘘解法を共有すると、サンプルが合わないことを指摘され、嘘に気づきます。もしかしたら英語を読むのが下手くそなのかもしれません。いや日本語でもよく誤読してるから関係ないか。 その後、二人で考察を進め、大体の方針が立ち、残りを白椿さんが考察&実装をしてくれました。
実装が終わり提出するとWAが出てしまいます。 話を聞いて条件を整理すると、2つの会議に出席できる人数が多いほど良いという条件が抜けていることが判明… ２人で考察をしていた時に抜け落ちてしまっていました… 反省を生かして、条件が抜け落ちないように問題文をja君とあらかじめ読み合わせ、問題文にメモまで書いてあるのですが、解法を思いついた時には忘れていてしまったのです。馬鹿すぎる〜〜〜。
そして再提出するとまたWAでした。 Bで２ペナをすでに出してしまっているのでむしろ開き直っており、デバッグすれば絶対通るよ的なことを言った気がします。 そんなことをしている間にja君のデバッグが終了し、再実装して無事ACを取ってくれました(1:27)。本当にありがとう…。
その後、順位表の情報により、ja君がCを読解し解けそうということを共有してくれます。 問題概要を聞くと、割とすぐ解法と証明のようなものが思い付きました。 証明のようなものは、あとで整理してみると主客転倒の式変形で正しいのですが、その時点ではだいぶ直感的で自信がありませんでした。しかし、PCが空いていたので、解法を伝え実装してもらいます。
その後、Kの問題文を読むと2つの日付はdistinctという部分があり念の為確認すると、WAの原因になっていそうでした。 原因がわかったとはいえ修正するのは大変そうでした。
この時点で自分達が解いていない問題の中ではKやIがかなり解かれていて、Iは解かなければいけない問題だと思い諦めずに粘りました。Iはセグ木やMoのような考え方では全然歯が立ちませんでした。想定解はセグ木の二分探索なのですが。 結局クエリを先読みし座標順に処理することを考え、単調性を保持しながら値を更新することで、計算量を減らすことができました。
考察している途中でja君がCの実装で寄与を求める部分で苦戦していたので、実装を交代しCを通しました。(2:56) その後Kのデバッグを白椿さんがやりきり、こちらもACが出ました。(3:00) 自分は無限にIの考察をしていて行き詰まっていましたが、そんな時でもチームメンバーがACを取ってくれるのがチーム戦のいいところだと思いました。
Iの解法はチームメイトに話したりして正当性には自信がありましたが、Bの実装で2ペナもしてしまったので、実装はやりたくありませんでした。しかし、そこまで自信があるなら自分で実装するのがいい的なことを言われてしまい、Iの実装をやることになりました。蓋を開けてみると、データ構造が不要で場合分けなどもシンプルだったので実装はそこまで苦労せず無事ACを取ることができました。(3:44)（本大会１番の偉いポイント）
残り2時間ほどで6完しており、ペナが多いことを考えるとplayoffに進出するためにはあと２問解く必要がありそうです。 この時点ではまだ希望はギリギリあるかなという気持ちでした。 少なくともDは解く必要があると判断し、Dにで3人取り組むことにしました。
チームで少しずつ考察を出し合い、少しずつ考察は進んでいきますが、本質的な数え上げに帰着できず、ただ時間が過ぎ去っていきました。結論から言うと２時間以上取り組んでいましたが、競技中に正解することはできず、終了五分前ほどに、白椿さんが正しい解法を思い付いてはいたのですが、実装は間に合いませんでした。
最終的には６完で、凍結前順位は26位で最終的な順位は32位でした。最後の数時間で１問も解けず悔しかったです。 そして、Dやその他の問題を時間内に解いている上位チームとの実力の差を痛感しました。 playoffに進出できなかったのは残念ですが、そもそも４年目にして最終年でようやく横浜に参加できたので、この場にいるだけで嬉しかったです。
解説会 & 懇親会
解説会ではGの解説が面白かったです。また、目を通さなかった問題が結構あったので、ちょっと後悔しました。
懇親会ではkotatsugameさんにお会いしAA Quineの話をしました。AAに埋め込んだチーム情報などに気づいてくれていて嬉しかったです。また、「チーム紹介スライドに何で実行エラーのリンク載せたんですか」と聞かれてしまいました。直前までpaizaで実行確認をしていたのですが、コードを共有すると編集できてしまう問題があり、直前にideoneに提出して「なんか動いてそう」と思ってしまいました（実行結果ぐらいちゃんと確認してくれ…）。ICPCのTwitterにもスライド付きで写真が載ってしまっていて困っています…。ICPCの関係者には申し訳ありません。ideoneの実行環境ではevalがdangerousという理由で実行エラーになるので、他の実行環境を教えてもらいました。 あとで、AA Quineの記事を書く予定なのでその際にきちんと動くリンクを用意しようと思います。
あとハイパーロボット対戦が楽しかったです。４連勝ぐらいしてシールをたくさんもらいました。 他にもいろんな人と話せて良かったです。懇親会は会場全体が盛り上がっていて楽しかったです。
おわりに
良い子のみんなは問題文を正確に読もう！
ICPC2024 国内予選 参加記
(敬称略)
当日まで
去年はhexa0611, pres1dent, ja14378でチームを組んでいたのですが、hexa0611の参加資格がなくなってしまったので、新しくチームメンバーを探しました。去年チームを募集のツイートを見てDMしてくれたsrtubaki（その時点ではもうチームが結成されており１年前は組めず）を誘ってチームが無事結成されました。
チームを結成してすぐにオンラインで自己紹介をかねて話しました。その際に、事前準備ありへのルールに変更されたことを受けて、レートが一番高いsrtubakiのPCで出たほうがよさそうとか、当日は神楽坂のキャンパスで出ようなどの話になりました。
応用数学研究部というサークルの部長をしており、部内でチーム組をしたり、監督員+コーチとの連絡、教室の手配など様々なことをしました。大変でした。
また、借りられた教室はプリンターがある建物から遠いので、自宅からプリンターを運びました。
模擬国内
神楽坂の教室に集まって参加しました。模擬国内ではBを3ペナした挙句実装が無理すぎて投げ出したりしました。自分の環境をカスタマイズしすぎているのとUSキーボードを普段使っているのもあって、慣れない環境で実装するのは向いてないと思い（去年の反省もあり）、本番は実装しないことを決めました。
当日
11時ごろ会場に着いて机の移動や立ち入り禁止の紙を貼ったりしました。
リハーサルもしました。
11時30ごろに監督員と印刷の確認をしました。思ったよりプリンターの性能が良くて安心しました。
コンテスト
序盤
A: srtubaki, B: pres1dent, ja14378を担当することにし、モニターの片方ずつに写して読みました。Aがすぐに解けたようで、実装が始まりました。
Bの問題はシンプルでしたが、並走するところの処理がよくわからずフリーズしていたところ、ja14378がどちらがリードしているかの情報をもてば解けると主張していました。
そうこうしているとAの実装が終わり無事ACを取りました！ナイス！
B 実装のお手伝い
ここでja14378に実装を交代します。僕は隣で見守る役をやります。
問題文の印刷がちょうどCまで届いたぐらいだったので、srtubakiがC, Dに移りました。
僕は問題を読みながらオーバーフローしないかとか細かいところを確認していました。
実装が終わったところ実行するとサンプルが合わなそうです。ここで、与えられる情報が差分だということを指摘しました。若干パニクっていたので具体的にどこをどう直せば良いのかを共有して無事AC。ガッツポーズ。
一旦順位表を確認し、心を落ち着けたりして、srtubakiに進捗を聞くとC, Dが解けておりすぐに実装できるようでした。
速すぎる...。
実装が上手いことは知っていたので、C, Dは任せてE問題を見ることにしました。
E 考察
E問題は左端と右端が一致する場合は簡単に構築でき、そうでない場合に構築できるのかが問題でした。左端と右端が一致しない場合でも構築できそうな気がしたので、手を動かしながら、構築できるケースを作ろうと試みます。手を動かしているうちに、右端と同じ要素がないと構築不可能ということがわかり、左端についても同じことが言えそうでした。
（この辺りでCが通っていた気がします。）
つまり、b ... a ... b ... aのようになっていることが必要条件だというところまでわかりました。逆にそのようなケースで構築できるのかというパズルを考えることにしました。途中でDがバグっていて辛そうなので、様子を聞いてみると移動距離:dの値が想定外の挙動をしていました。ただ話を聞いていただけですが、勝手にバグが解消されていき、あとはなんとかなりそうというところまで行ったので、Eに戻りました。
パズルの続きを考えていたところ、Dが無事通っていました。天才すぎる！
srtubakiの手が空いたので、問題の概要を共有しました。
パズルがもう少しでできそうなので、少し時間を欲しいと言い、パズルの続きをやりました。しばらく考えるとパズルが解け、一般の形でも構築できそうだという直感がありました。解法を共有したところ、きちんと証明になっていることが確かめられました。
E 実装
どちらが実装するかという話になり、国内模擬の反省を踏まえて僕は実装しないと決めていたので、C, Dを立て続けに実装していて疲れていそうでしたが実装を引き受けてもらいました（鬼畜）。とはいえ、少しは役に立つべきだと思ったので、隣で実装の方針を立てていました。おおまかな流れを伝えているだけで、細かい処理を丁寧にバグなく実装していて呆気に取られました。
数字を真ん中に配置するために、最初は上にずらしながら、次に左にずらしながらといったように配置していくことを提案したのですが、添え字の処理が大変で途方に暮れていたところ、srtubakiが盤面を回転させれば一方向だけの処理で済むという天才的アイデアを思いつき、高速に実装することができました。
全てを実装し終え、サンプルが合ったので提出をしました。正直上手く行きすぎていて、提出前は異様な興奮状態でした。提出したところCongratulationsと表示され（静かに）大はしゃぎしました。
順位表をみると15位ぐらいでした。（たぶん）
この時点で、理科大のICPC事情を考えると国内予選突破をほぼ確信しましたが、続きの問題を解くことにしました。順位表をみるとF, Gが同じぐらい解かれているので両方に目を通し、解けそうな方に取り組むことにしました。
しばらく考えるとsrtubakiがFは実装が大変だが、計算量的には間に合う解法があると主張し、実装を始めました。2人はGを考えて欲しいと言われたので、Gを考えることにしました。
G 考察
Gは正直どこから手をつけていいのかわかりませんでした。
かなり時間が経った頃、ja14378が筋の良い解法を思いつき、長さが奇数の場合は解けていそうでした。長さが偶数の場合、偶数の項があれば奇数のケースに帰着できるとか色々考えました。
結局、終了10分前ぐらいに解法としてまとまりましたが、とても実装は間に合わなそうでした。Fはどうだったか聞くと、実装の方針があまり良くなかったのか（?）こちらも間に合いそうにはありませんでした。
順位表を確認すると理科大の2位チームが追い上げてきていて、もう一問解かれたら抜かれるなあと焦っていましたが、順位的に2位通過もできそうだったので安心しました。
結果
最終的に29位大学内1位を取ることができました。
ここまで上手く行ったのは初めてで、今まで参加したコンテストの中で一番楽しかった気がします。
4年目にしてようやくアジア地区予選にいけることになったので（おそらく）、残り5ヶ月精進を頑張りたいです。
おまけ
サークルから5チーム出ていたので、みんなでモスバーガーを買ってきて打ち上げをしました。先輩からピザの差し入れもいただきました。
楽しかったです。
（食べたあとは、もちろんきれいに掃除しました）
ICPC 国内予選 2022 参加記
ICPC国内予選にチームSOSOS*1で参加して予選敗退しました。
チームメンバーはpres1dent、ja14378、sdr8でした。
予選前
アルゴリズムの勉強会*2とか模擬国内に参加したりをしました。直前に中間考査が生えたりしたのもあって、チーム戦はほとんどできませんでした。
コロナの関係で教室を借りるのが大変でした。部長ありがとう。。
本番前
16:00まで４限があったので結構ギリギリでした。ちなみにこの４限ではアイスを３回もご馳走になっていて神！この日は暑くなかったのでありませんでした（悲しい）。
教室についてからは違法滞在してる人を追い出したり、立ち入り禁止の張り紙をしたりしていたら残り５分とかで焦りました。
本番
作戦としてはA:sdr8、B:ja14378、C:pres1dent 担当という感じでした。困ったら言ってね〜とか話していたら始まりました。今年もサイトが重くなることを予想してましたが、すんなり入れてまずはいいスタート。
Cを読む。割と読みやすくてすぐ理解できる。
気持ち的には働くのをできるだけ連続させて、休むのを小分けにすれば良さそう。
働くのを分ける場合は一つにまとめて、休むのを分けるのときは等しく分配すればよさそうなので、何個分けるかについて全探索で実装する。
実装半ばでAを実装していたsdr8くんからhelp。テストケースがデカすぎて貼り付けでトラブってるらしい。*3提出を一通り肩代わりしてAC。Bに向かってもらう。
Cの実装に戻る。Nが0,1のコーナーケースをしっかり処理してAC。順調に２完できてテンションが上がる。
Bはシミュレーションの実装問題で、実装に時間がかかりそうだとうことで引き受ける。setのvectorで実装すると良さそうという話を聞きそのまま実装。次のプレイヤーを決めるパートに苦労しながらも、素直なループで解決しAC。
結構順位が高くて（３０位ぐらいだったと思う。ほんとか？）ワンチャンありそうで盛り上がる。この時点で数分差で学内２位だったのでもう１問は通さないとという話になる。
実装してる間にDとEを読んでもらったので聞く。DはDPぽいけど状態が爆発しそうでどこから手をつけていいかわからず。Eも制約が小さい以外はやばそうという話をしていた。１０分ぐらい順位表を眺めたり、チームで考察をして、Dに行くことにきめる。
僕はSの存在を忘れていて、Tだけなら逆からシミュレーションしてけば良くね？という方針が生える。*4
しかし、Sについてどうしたもんかと１時間ぐらいみんなで考察するがこれと言って解ける感じがしない。やはり、必要条件で絞るのが良さそうということで、実装しながら詰める。この時点で理科大の一位チームがDを通していてペナの関係であと30分ぐらいしかなくつらい。
分割した列についての情報は何を持てばいいかとかでだいぶグダるが、４０分ぐらいガチャガチャやってると条件が降ってきて解ける。
ギリギリでデバッグが終わって提出しACを得る。
結果
４４位大学内２位で進出ならず。
結構悔しかった。
コンテスト後
Twitterを眺めたり、東大やべーという話をしたりしてた。
有限幾何学の課題を出して、帰った。今度打ち上げにも行こうと思う。
最後に
去年に引き続き今年もコーチを引き受けてくれた教授と教室貸出でお世話になった部長に感謝です。
去年チームを組んだチームメイトにも感謝してます。
来年こそはアジア出たいぜ！
