結果
本番まで
メンバーの一人はキャンパスが違うということもあって特にチームで練習するということはなく、各個人で勝手に精進を重ねる程度。僕はARCの3問目を埋めていっていた。一応予選時からレートは+150くらい。まだ闇雲にでも解けば上がる段階ではある。
リハーサルではCLionでちゃんとコーディングできることを確認する作業をメインに。日頃はVisual Studioを使っていてIDEを使えないとデバッグがまともにできない人間なのでCLionが使えるのはとても有難かった。しかしUS配列のキーボードに慣れていなくて、コーディングしづらいことにここに来て気づいたのはひどかった。US配列しかないことは事前に告知されていたけど、その影響度合いを舐めていた。大反省。
本番
あまり作戦もなく3人でA問題から見ていって後は流れでという感じ。
開始してすぐは緊張気味で、A問題の解法がパッとは思い浮かばず、メンバーが思いついたらしいので任せる。しかし微妙に詰まったようで、そこで別のメンバーが「数字以外は大きな定数をかければ単純なソートだけで済む」という実装を提案してくれたので僕が代わって書いてAC。ここでそんなに詰まらなかったのが精神的には良かったかもしれない。
B問題に行くけどさっぱりわからなくてかなり時間が経つ。チームメンバーはC問題とか他の問題を見たりしていたようだけど僕はずっとB問題にかじりついていた。いろいろ考えていたらvector<map<int, int>>を使って「dp[i][j] =i番目まで見たときに公差jである部分列の最大長」というのが思いついたけど出してもTLE。で
が通らないのは厳しいなぁと思いつつ、検証するために手元で
のサンプルをランダム生成してジャッジのオプション通りにコンパイルして実行してみたところ10秒はいかないくらいだったので高速化で通せそうだと考えた。しかし
cinをscanfにしたりmapをunordered_mapに替えたりしたけどTLEは消えず。ここらへんで2時間以上経過していて1完で終わってしまうのかなぁと冷えかかっていた。
根本的に間違っていると判断して一から考え直して、(はソート済みとして)頂点
から頂点
へ
のコストを持ったエッジを張ってダイクストラ法みたいなことを考えて適当に実装したらなんか行けそうだったので出したら通った。後から冷静に考えるとグラフどうこうは全く意味がなく、小さい公差で最後まで行ったらそれ以上調べないとか、途中でぴったりな数字がなかったら終わりみたいな枝刈りを入れたのが重要だったようだ。計算量が見積もりが下手なので正当な解法なのかどうかが未だにわからない……。
ほぼ同時にチームメンバーがC問題を通してくれたので3完できて少し安心する。順位表を見たり二人から話を聞いてG問題がいけそうという感じだったのでG問題を見る。ぱっと見で転倒数だったのであるびん君に転倒数のライブラリを写してもらいながら問題を考えていたところ、セグメント木を持って小さい方の数から左右の端の近い方に投げつけていけば解けそうだと思いつく。実装をしていたら同じ数字が複数あったときの処理に少し悩んだが、セグメント木をもう一つ用意して順番を決定するということをやって無理やり通した。これは完全に無駄なことをやっていて普通に1回で良かったんだけど本番中解いていたときは頭がおかしかった。
Gを通したところで残り40分以下しかなくて、DとかKが簡単そうだということでDを見たけどさっぱり思いつかなかった。残り数分とかになってからは完全に反省会モードへ。目標としていた4完ができて良かった。しかし後から振り返るとACした問題でも提出したコードがひどくて、これは実装力不足と言うべきなのか考察力不足と言うべきなのか。もっと精進したい。
終わりに
3日目の企業見学なども含めて学びの多い大会だった。年齢制限があるので僕は今回が最初で最後になってしまうけど、後輩の活躍に期待。
