2017 ICPC国内予選
参加しました。
チーム名はIQ94(由来は1994年生まれだから)
チームメンバー hyksm ホハム(mtsd) polyomino
でした。
始まる前のチームとしての作戦は以下の通り。
hyksm : (重そうな)実装担当
polyomino : 考察+実装
mtsd : 考察
要するに(私は使い物にならないので) hyksmとpolyominoで交互にコーディングしていこうという話でした。
各人の適正を考えるとこうするしかないという感じでした。
(要するに僕は考察でどうにか成果を出せということ)
では実際。
スタート直後、印刷をpolyominoが、hyksmがA問題をそのまま解き始める。
polyominoの印刷スピードは最速感があった。
最初の問題の割り振りは以下のようになった。
B問題:polyomino
C問題:mtsd
読んでるうちにAを通す。polyominoがBを解き始める。hyksmにC問題の概要を伝えると、「もっと後ろを解いて」とのこと。
とりあえず、全体の問題を流し読みして、F問題のような話は数学の問題として見たことがあったので自分が解きにいかないとという気持ちになる。
B問題polyominoが実装で微妙に詰まったらしく、hyksmにコーダー交代。先にCを解いてそのままBを解くという流れに。
その間にD,E,Fを2人で考えることに。
DはXORをとって0になるような選び方の最大値だよなぁと思ったがよくわからない。制約どうやって使うんだ?多分DPでしょ?ナップザック問題だけどbitDPは無理だな??と分からない。
Eは論理変数も少ないし、文の長さが十分短いので全部先に列挙させればいいな、構文解析やればいいなという感じに。
A~Cを解いたhyksmと、polyominoがEをどっちが書くか相談。hyksmに一任。
あとの二人はDとFを考える。
Fは0-indexで始めると絶対見通しがいいと思って図をひたすら書く。一回折り曲げた後は重なった部分は同一視して~~とかいろいろ考えるも泥沼にはまっていく。2^3のパターンとかを書き始めるが、これで本当に分かるのか?と悩み始めツライ感じに。延々1時間半は悩む。
(shurikenがこうすりゃいいんじゃん!みたいなことを言っているのが聞こえてさらに心がやられる)
hyksmがEを通し、DとFをチーム全員で考え始める。とりあえずそれっぽいことをhyksmに適当に言ったら、(たぶん関係なく)hyksmが4分割すれば行けそう!と言い始めそのままコーディングへ。
polyominoとDを考え始める。2部グラフでどうにかする?無理そう、流石にDじゃでないだろみたいな感じでやっぱDP系か~という感じに。変数としてpair<それまでの選んだ個数、XORした値>みたいなものを考えるんかなぁ~という話になり、もしかしてsetにバンバン追加してけばいいんじゃね!?という感じに。適当な(嘘)計算量解析によりなんか行けそう!とか適当に言ってみる。とりあえず紙コーディング。
ここらへんで上位陣が全部東大でひえぇ~~~~って思う。
F上手く行かないということになり、コードを印刷して、デバッグへ。その間にDを書き始める(残り30分切っていた)。
ついに僕がコーディングすることに。10行くらい書いたところでpolyominoが印刷から帰ってきたので交代。ペアコーディングに。一通り書ききって動かしたら止まらない。setの追加の位置がダメ→修正→string用に書いたXORがおかしい→修正→サンプル通る!
ギリギリのケースで間に合うか不安になるもとりあえずテストケースを投げる。やはり時間がかなりかかって焦る。
hyksmがFを修正しながら、後でDの答えが返ってくるのを待つ(残り15分くらい)。
D1個目通る!D2個目へ。hyksm怒涛のF修正!
D2個目もプログラムが終了!提出!Congratulation!!(2:50:59)
残り10分、Fの修正を見守る。なんかオーバーフローが起きている→1<<n を(ll)1 << n に修正→サンプルあってる!
テストケースを落として提出!Correct!もう一個提出!Congratulation!!(2:56:50)
終了~
結果 6完 11位(学内順位7/10) (学内予選酷すぎる)
shurikenチームはおめでとうございます。
結果、完全にhyksm様様でした。
F、チーム作戦的にも問題的にも自分が解けないといけない問題だったのにやらかしてしまって本当に悲しい。焦ってもいいことはないね。算数勢辞めます。
来年はhyksm神がいないので、もっと研鑽を積んで実装の鬼になろう(か他のプロを呼んできたい)と思います。
おまけ。
家に帰って最初にやったこと。
う~んw終わり!w