ACM-ICPC 2017 国内予選 参加記

ACM-ICPC 2017 国内予選に参加しました。

RiPProとしては「4,3回生チーム」「2回生チーム」「1回生チーム」の3チーム参加してました。

メンバーは「ixmel, T.M, noy72」。

昨年、一昨年はSIMritとしてでていたが、チームの一人が競プロ離れしたため一人swapしSIMnitと変名して参加。チーム名後ろ3文字はメンバーのIDの頭文字。

 

結果: 4完 29位 学内1位なので通るかと (追記:通りました！！)

 

作戦を立てる時間は楽しいので作戦は今までで一番細かく立てた。以下

  • ixmelが実装担当、T.Mは考察担当、noy君はテンプレ写経と構文解析と考察担当
  • T.Mとnoy君が考察しixmelに伝えixmelが実装、の流れ
  • 提出の際全員でチェック(提出ミスはしたくない
  • バグるorWAったときは誤読、認識の差異、実装ミスなどの可能性が高いため2人に実装方法を伝える(よくここでバグった理由が判明する
  • コンテスト開始直後noy君がテンプレ写経、その間2人でABの実装方法を考える
  • ixmelがABを実装、T.Mとnoy君がCの考察
  • ixmelがCを実装、T.Mとnoy君がDの考察
  • ...
  • noy君の手が空いたらFとかGとか読む(幾何問題あればワンチャンなので

 

コンテスト開始前

テンションが上がってくる

F5アタックしながら待機

 

コンテスト開始

ページ読み込み？が始まってオッとなるが読み込みが長い。

気を抜いてマウスから手を放した直後表示されてアッ。

印刷クエリ投げてる間にT.MがAを解き終えてた(はや。

noy君がテンプレ写経してる間にBをめんどいやつだなーと思いながら実装方法を相談する。

写経し終わったっぽいのでAとBを通す。(A.9:50 B.25:45)

 

Cの解法を教えてもらい通す。(C.36:45)

NAISTのyazatenプロ,yurahunaプロチームには勝ちたい気持ちがあって、この時点で勝っていたので喜ぶ。

 

Dの解法が2人から降ってこなかったのでDの考察に加わる。

D、フローはダメ、制約より同じのを消してったら√n種類に収まるかなー(嘘かつ嘘解法)などいろいろ考える(T.M迷走

nが小さいと全探だよなーmが小さいとbitでいけるなーとT.Mが思いつたっぽいので実装しD AC(D.77:45)

ここまで0WAなので予選突破ほぼ確チャンとなりT.Mが滑る椅子を使い躍る

 

Gをフローで解けるのでは(ソースから左上と右下へ容量2、左下と右上からシンクへ容量2の辺を張る)と考えるが実装し終わってサンプルが合わず噓解法と判明。捨てる。

 

Eに手を付ける。

Eは入力が16文字までなので答えとなる長さ最短な式には変数が4つまでしかないことから全探する解法でいく。

前日あたりに「2分探索」という言葉が脳にinputされていたため、多少遅くてもいいやというノリがあって前計算でいけることに気づかない。

列挙する部分はできたので、構文解析担当のnoy君にバトンタッチ。この時点で順位表見ると1回生チームが2回生チームにペナルティ100差で勝っていてあまりにも僅差で感動。

残り約10分に実装が終わりサンプルを通すが一つだけ合わず。否定がかかる順序やらが怪しいが時間切れ。

 

コンテスト終了

菓子パ。

 

https://twitter.com/wk1080id/status/885827579751444481

感想

模擬含め5完したことがないのでしたかった。来年こそは。