チームSpirytusとして出場し、4完1ペナの109位で競技を終えました。
チームメンバーは緑/緑/茶と高くはないものの、adhokな問題に(比較的)強いメンバーもいるということでギリギリで予選突破できる可能性があると思っていましたが、流石に現実は甘くないらしいです。
競技前
競技前はライブラリやテンプレの準備に走っていました。今年はライブラリの利用に関する制限が甘くなったこと、そして国内予選模擬でmod998が問われる問題が出たことから、ac-libraryを使えるようにしたりなどバタバタとしていました。他にもいろいろな事情により焦っていたというのもあります。
競技
競技は謎のデカ教室が使えました。ウヒョー。
Aのガヤ(?)とB・Dの考察と実装を担当しました。私は普段のコンテストではRustを使っていますが、ICPCではRustで提出できないのでC++で書いていました。また、英字配列のキーボードをメインで使っているのですがチームメンバーの2人が日本語配列を使っているということでちょっと慣れない環境でのコーディングをしていました。
A - おやつは 300 円以内
Aは早ときの得意なメンバーが居るので、丸投げしてました。初動すぐに問題文を印刷したものが届けられるわけではなく暇なので 、「普通に前から見ていって超えなかったら足さないでよくね？」と口出しをしていました。コーディングに移るタイミングで問題文をBの方にスクロールしてもらって、Bを読む。
B - 追い抜き
自分の担当です。愚直なシミュレーションで、追い越しが何回起こったかを数えれば良さそうですが、はじめの「まだ先行しているのがどちらか決まっていない状態」をどう表現するかを考えていて沼ってしまいました。最終的には0/1/2でAが勝っている/Bが勝っている/まだどちらも先行していないの三状態を変数で持つ実装にしましたが、この変数の型をintではなくboolにしてプチバグらせ。結局10分ちょっとをかけて正答しました。
C - ハチの巣距離
自分がBを解いてる間に「解けたわ！」ということらしいので丸投げ。多分自分だったら沼にハマるタイプの問題なので、さくっと通してくれて助かりました。
D - だんごむしではないむし
自分の担当です(というか、典型そのままという感じの問題なので「俺通すからほか見といて」という感じ)。やることは座標(a, b)から向いている方向にある壁のうち最も手前のものを二分探索してそこまでの距離を取ってあげるか、壁がないならその処理をすればよいです。今思えば実装をもっと簡単にできると思っていて、
右・上と左・下の操作はまとめて実装できた
壁がないときの処理を場合分けしたが、制約上十分に大きいinfを配列に加えておけば場合分けが要らなくなる
無限にぐるぐるするパターンがあるので、二回同じ場所にたどり着いた場合はスキップしないといけないのに全然気付いておらず、実行が終わらない
の3点はかなり反省かなぁと言う感じです。実際には4方向・壁の発見有無で8パターンの場合分けを書いて時間をかけてしまい、更に実装等複雑にしすぎたために変数や添字のミスが多発し、しばらくC++を書いていなかったためにlower_boundを始めとする標準ライブラリの使い方すら忘れていてメンバーに聞きながら実装したことで、結局Cの正答を得たあとすぐに実装をもらったのにもかかわらず、1時間40分(+1ペナ)でなんとか答えにたどり着きました。
以降の問題について、メンバーは自分がDで沼にハマっている間に「Eの構築がヤバい」という結論に至っていたようで、Fに取り組んでいました。Dで正答を得た直後、Fは「進行方向にボールがあるかをlogぐらいで判定できたら解ける」とのこと。一旦落ち着いて菓子パーティーを挟んでから(？)45°回転する座標変換を思いつたのでそれを伝えて、自分はEを解いていました。この時点で確か残り1時間ぐらい。
かなり近しいところにはたどり着いていた気はするものの、細部まで詰めきれず、Fの方は実装が厳しいということで、多分嘘解法のEを実装し、ちゃんと嘘でその時には残り3分。間に合いませんでした。
競技終了後・感想
競技終了後は適当に同じ教室てやっていたメンツと解法を伝え合ったり、普通に雑談していたりしました。
自分たちのチームはいろいろな事情が重なり合ってなかなか練習ができていない中ではあったものの、最善を尽くしたとは思っています。自分個人としても去年は1問も実装できずチームとしても2完で終わってしまったところから、今年は4完できて嬉しい...反面、Dをもっと早く実装してE, Fの考察と実装に力を使えただろという思いもあり、かなり悔しい結果でもあります。EなんかはARC-Bで出てきそうな構築問題っぽさがあり、精進の足りなさを実感しました。
ということで、悔しさを吐き出すための振り返りでした。ここまでお付き合いいただきありがとうございます。来年は勝ちます。