ICPCに初めて参加

競技プログラミングをちゃんと始めたのは1年の頃からです。当時工房などにも参加しておらず周りに知り合いがいなかったので去年は出れませんでしたが、今年は参加することができました。 誘った時点で茶コーダーだったのに一緒に出てくれたnonoさんとreinさんには感謝しています。

当日まで

チームしてこれといった準備はほとんどできませんでした。 模擬国内には参加しましたが、各自オンラインでの参加だったので殆ど考察を相談したりすること等はなく、チームとしての練習はほとんどできませんでした。 Atcoderのレートが自分だけ他2人より圧倒的に低かったので本番までにICPCの過去問埋めをするというよりかはとにかく基礎力を上げるために普段よりABCのCとD問題の精進を頑張りました。VLLの映像制作とシンセのライブとICPCの時期が重なったので結構忙しかったです。

当日

リハーサルが15時までとのことだったので14時半ごろにCEDに向かいましたが、授業で使ってるようだったので入れませんでした。代わりに隣の部屋に入り自分のノートPCでリハーサルに参加し提出の練習をしました。この辺は模擬国内と全く同じだったので苦労することはなかったです。参加してよかった。 CEDのキーボードの配置がキモイ(Ctrlの位置とか)ので自分のキーボードを持参しました。日本語配列のキーボードにUS配列のキーキャップを取り付けてたので書いてあるキーと実際のキーが違い、 チームメイトに困惑されました。来年はちゃんとしたキーボードを持っていこうと思います。

本番

模擬国内通り自分がA問題をまずやろうとし、問題文を開く。やるだけの問題だけど1と2の処理めんどくさいなーと思ってたら後ろで見てたnonoさんに1と2に13たして後でmod13とれば良いと 言われ賢いなと思いつつ実装。緊張もあってタイプミスが多かった。サンプルがあったので提出しAC。 印刷された問題が届いた頃、reinさんがBの実装,nonoさんがCの考察をし,僕がDの考察を始める。数分後BがAC。

しばらくし、nonoさんがC問題が沼っぽいと言っていたので3人でCの考察を始める。制約が小さいので愚直なやり方でも通りそうだけど実装がよくわからず、焦っていたところreinさんがdpで解ける と解法を思いついたみたいなので解法を聞くが、理解できなかった。よくわからないけど実装してもらい、AC。ここまで30分でとりあえず悪くなさそうなペースで一旦緊張が解ける。

Dの考察を始める。頭であれこれ考えても進展がなさそうだったので自分が初項1-5のときの数列を20項目くらいまで書き出して実験してみる。暫く考えると、初項がそれ以降に初めて出現する前と後で 規則性が変わることに気付いたので2人に共有。

十数分後にnonoさんが初項が初めて出現した後とさらに初項sがs回出現するまでとそのあとの2段階に規則性が変わることに気付いたらしく聞いてみる。この時点で最後の規則性以外は一般化できていたので 最後の部分の規則性が一般化できれば計算で任意の項が求められるので規則性を考えるが、わからない。 数分後nonoさんがなんとなくわかったらしいので実装を開始、解けることを信じてreinさんと僕でEの考察を始める。 実装を終え、テストケースもあってたので提出しAC。nonoさんは数学系の問題に強いのでありがたい。

Eの考察を3人で始める。一旦初手はジェムが1つ以上含まれている瓶の中で最も安いものを選ぶのがよさそうだが、その後ジェム付きのを連鎖的に買うorジェムが含まれていない瓶で高いものを選ぶの2択をどのように決めればいいか分からず、詰まる。 reinさんが答えの金額で二分探索し、判定の際はとりあえず最初はジェム付き&&最安の瓶を買い、次にジェムが多いものから選んで～～という解法を思いついたらしく聞くが、いまいち理解できなかった。とりあえずPCは空いてるので実装してもらいつつ、引き続き考察を進める。 1,20分後にnonoさんがreinさんの方針だとWAになりそうなケースを見つけ、2人で議論が始まる。自分がついていけなかったので1人で考察を進める。 2人が話し合っている間よさそうな方針が思いつく。ジェムの個数によって最善な買い方が複雑になりそうなので、一旦ジェムの総和を求め、ジェムの有無にかかわらず価格でソートする。ジェムの総和だけ 価格の高い順に瓶を消去し、残りはジェムが0個の瓶がN-(ジェムの個数+1(最初にジェム付きの瓶を買う))あるのでそれを買えばいいのではと思いつく。 reinさんが実装に詰まってそうだったので席を変わってもらい、実装。 実装中にnonoさんが僕とはアプローチの仕方が異なるが同じっぽい解法を思いつく。解法を聞いている間に自分の実装ができたのでサンプルを通す。あってたので提出し、AC。

この時点で残り1時間。難易度を考慮すると解けても1問っぽいので3人でFの考察をする。早々にnonoさんが座標圧縮とダイクストラ法で解けそうと言っていたので実装してもらう。 競プロ力が低すぎて自分はそもそもダイクストラ法を書けないので投了し、残りのG,Hの問題文を読み何とか解けそうなのがないか探してみる。reinさんからHは浮き輪の個数,棒の数の制約的に 浮き輪を移動するロジックさえ考えればシュミレーションしても間に合いそうだということを聞き、考える。が、思いつかない。 残り30分になったところでnonoさんのF問題の実装が重く、残り時間的に終わらなさそうなのでH問題に掛けることにする。reinさんがそれっぽい解法を思いついたみたいなので実装してもらう。 FとHの問題とにらめっこするが、方針が思いつかない。2時間以上何かに集中し続けるというのは2年前の大学入試以来であり、集中力も切れてくる。 reinさんの実装も間に合わず、結果5完で終了。

この手ごたえだと6完以上はしてないと予選突破は厳しそうだな～と思いつつ順位表を見ると、なんと5完に弊学4チームが固まっていた。 しかもその4チームの中で一番下、一番上のチームとは14分差。ノーペナだったので自分の考察+実装があと14分早ければ間に合っていたと考えると非常に悔しい結果になった。

おわりに

考察部分は比較的頑張れたものの、実装力や後半のアルゴリズムの知識がなかったり、基礎的な競プロ力が不足しているのを改めて実感させられました。 来年までにはもっと精進をし、少なくとも入水はしてリベンジしたいと思います。