ICPC2019国内予選参加記チームWEloveSAINO
C問題の良い実装が思いつかずにA,B2完をした榊です。
初めてICPCに出た感想を記します。
ICPC前日
必死こいてライブラリを作る。
模擬国内で4,50分溶けてしまったEOF対策をする。(意味なかったけど!!)
ネットから使用方法が簡単なライブラリをコピペしてくる。(意味なかったけど!!)
念のため幾何用のライブラリをコピペする。(意味なかったけど!!)
大体1問は文字列操作、構文解析があるので文字列用のライブラリを作る。(意味なかったけど!!)
ICPC当日
まず、先輩方にリアルで顔を合わせて(ツイッター上でやりとりはしていた)、「女装してくるのを期待してたのに...」とか、「3完くらいしてね?」とか煽られる。(その先輩のチームは本番楽しそうでした(後日談))
時間になったら問題を見て、A,Bの解法を出す。
(ここまで10分、なおこの時点でのAは嘘解法,BはBFSとi,jのマンハッタン距離の2通りの解法が出ていた)
メンバーの1人は開始から2時間30分くらいずっとCの考察をしていました。
→C,Dを見る、厳しそう。Cは実装出来るか怪しい。
→A,Bとりあえず解いておくか。
→Visual Studioがバグる。
→2,30分後
→正しく実装しなおす。→合ってた。1完。
→Bを書く。実装が弱いので当然マンハッタンで解く。→合ってた。2完。
→Cの実装が重くて(実装が苦手)Dへ逃げようとした。
→貪欲を書く。通らない。それはそう。DPなので。→いっぱい時間溶ける。
→やっぱりC問題やるしかない！！
→まず、結果的にm個の分銅で作れる重さを全て列挙する。
→バグる。
→long long のmapで書いたら3*10^16くらい?の意味わからない値が混じってる…→絶対値がクソでかい値だけ省けばいいんじゃね？？
→なぜか列挙は出来てるっぽい。チームメンバーにバカと天才は紙一重みたいなことを言われつつ、答えの場合分けに入る。
→分銅であり得る値は列挙しているので、その値と一致していない薬品の数を数える。
→全部一致していれば当然0
→何個か残っているケースを考える。
→1個余ってるのは流石に簡単なので、複数余っている場合を考えた。以下多分嘘解法。
→(ここで、薬品と列挙した分銅を事前にソートしておいて、その差をとったvector配列を用意。)
→(vector配列と一致している範囲が存在するかを判定し、あれば差を取って出力。)
→バグらせた。そもそも解法が正しいかもわからない。
→バグ埋小宮になった。死亡。ここでタイムオーバー。
D問題がDPだとサンプルの最後でちゃんと見抜いていても、多分C問題の実装は無限に時間がかかったし、多分嘘なので詰んでいた感がすごいです。
今後の精進について
効率的な実装を身につけ、思いつけるようにする。
ICPCのD問題は大体DPなので、DPの漸化式を出す精進をする。
4完すればアジア予選行けそうなので頑張ります!!
