ICPC Bangkok Regional参加記(コンテスト編)
コンテスト編以外は後日書きます。
コンテスト
- ぼくが環境を構築する。ctrl:nocapsにする。設定から画面スプリットのショートカットを変更、マウススクロールの方向を変更、.vimrcの作成、.bashrcにg++のエイリアスを追記、geditのタブ幅等の変更、テンプレートの入力、テスト用プログラムの作成をする
- けんしん、荻野が問題を読んでいく
- 準備が終わってもまだ解ける問題はなさそう
- 荻野がDの解法を教えてくれるのでDを書く。WA
- 誤差かと思って精度を改善するもWAが続く
- けんしんからFはやるだけだと聞くのでFを書く。WA
- 並列でデバッグしつつ、ぼくがI, J, Kあたりを読んでいく
- 1時間弱経つのに1問も正解できないのでさすがにジャッジおかしくないかと思ってジャッジが間違っていないかclarする。正常だと言われる(ちなみにスコアボードは1:12まで機能していなくて何も見れなかった)
- スコアボードが突如現れて、しかもなぜかrandomizedされていなく(予告ではrandomized)、Mがかなり解かれているので荻野が読む。
- なんかFがリジャッジされてACになった。けんしんが発狂。ジャッジ間違ってたやんけ
- KがLCAやるだけだったのでけんしんに場合分けを任せつつ、ぼくがライブラリを写経する
- Kが通る
- 荻野がMの解法を伝えてくれる。75次方程式の係数の漸化式を伝えてくれたので実装する。ちょっとバグったけど案外すぐ通る。
- Dのデバッグを詰めなきゃいけなくなってきたのでDを荻野が詰める。Iをけんしんが考察してくれていて、遅延セグ木で頑張ればできることがわかる。
- Hを読んでみるとかなり数学的には簡単だったのでやることを整理する
- D、素数列挙が足りなかっただけだったので書いて出す。やっとAC。この時点で4完
- Hをそのまま実装するもWA。というかd.dddE+dddのフォーマットで出力するのがだるすぎた。printfの仕様を完全理解していなかったのでlog10とかexp10とか使って自分で切り出した。しかし冷静に愚直にやると精度がやばいことに気づく。とりあえず保留
- ぼくがHを解いている間に荻野がBできたかもしれないと言い出す。
- 荻野にJのペル方程式についての知見を質問されたがあいにく荻野のサブセットしか知識がなかったので困った
- Aで調和級数みたいなO(MlogM)を書いたらTL2秒で手元2.1秒で落ちたのでかなり困る。けんしんがいろいろ改善してくれて最初にO(N^2)前計算をすることによって諸々が軽くなって通る。
- この辺でラスト1時間になり、B, H, Iがキューに溜まっている状態で、2問通せればいいねみたいな話をした。
- 荻野にグレイコードの構築ができるかと聞かれてかなり困ったが(かなり昔にwikipediaを読んだことがある)、なんか天啓が降ってきてi ^ (i >> 1)思い出した。
- H, Iが進まないので荻野にBを譲ったらいつの間にか通っていた。やばい。
- 残り15分ぐらいになった。Hは浮動小数点演算の精度をうんぬんするのではなく、もっと数学的にうまく処理できることに気づいたけどさすがに間に合わない
- Iもさすがに間に合わないけどぼーっとするのもあれなのでけんしんがIを実装する
- コンテスト終了。あ〜となる
感想
- 最初の1,2時間がほぼ虚無だったのでかなり痛手を負った
- キューに2問溜まったまま終了したのはもしかして初めてだったかもしれない。プログラミングコンテストは実装コンテストであることを痛感した。
- printfで異常scientific表記を要求されるのはバンコクの過去問にもあったのでちゃんと予習しておくべきだった(過去問のやつだと困らなかったんですが)。ちなみにC/C++のリファレンスは用意されているがごく一部だけでiomanipなどはなかった。
- 問題はたしかに教育的な問題も多くて楽しかった
- ワクワクコンテストということで諸々で批判されているがなんか強いチームはやっぱり強いしあんまり関係なさそう、という気持ちになった。
ワクワク要素まとめ(公式)
運営の謝罪 pic.twitter.com/q1YYgyke0m
— Joe@ICPC Bangkok Regional (@xuzijian629) November 3, 2019