ICPC2018 国内予選参加記
ICPC2018に出たら参加記を書く文化なので。
時系列順に並べていきます。
12:40
大学に到着。皆居たので、まずは環境の確認
プリンターが動かないなどトラブル発生だが、その後解決
13:00
まずは他の人が動作確認でI問題を解いていたので、待機
他の2人はC++を用いるのに対し、私はJavaを使うつもりだったのでJ問題は解く
……が問題発生、eclipseが動かず
一旦修正を頼んで生協に飲み物などを買いに行く
暫くしてみてみたら動いたので通してAC
暇なので持ち物確認を行う
自分の持ち物:
- ホワイトボードx2
- ホワイトボードマーカー 7色
- ホワイトボード消し
- 鉛筆やシャーペン、消しゴムなどの筆記用具・文房具類(例: 穴あけパンチx2)
- ノートx1
- A4用紙x30
- ダイス 4面x1 6面x127 8面x1 10面x74 20面x1 30面x1
- ダイスカップ及びダイストレイ
- トランプ
- 500mlミルクティーx3
- お菓子x4
ここで、方眼式の紙があるとDPや幾何の問題で楽と判断、印刷して6枚確保
15:00
M問題に挑むもめっちゃ誤読してたらしく、サンプルのみ通るソースコードでWA量産
どの順番でも土産屋回れると思ってた……
16:00
準備
16:30
まずは人数分の問題を印刷、問題を見ていく
A問題は平均値なので簡単、担当に10^9までしか出ないからオーバーフローしないと伝える
B問題は折り紙、東工大絶対許早苗
C問題を見て累積和を脳内に構築、連続した列なのを見て尺取り法と判断
脳内デバッグするも尺取り法で間違いなさそうなので実装を検討
なお数学的解法の存在も気付いたが式構築に時間掛かるので却下
16:34
A問題AC
C問題をと見積もったので時間掛かりそう、交代して先に挑む
ソースコードはさくっと書けたがメモリ不足、long[1000000001]をint[1000000001]にしたら動いたので実行
サンプルACだったので待機
17:04
C問題AC
0WAだと時間ペナないしこれはいけるんじゃないかという話をしつつD問題の相談を受ける
全探索だとだから無理ではないかという話をしたが、片側決め打つともう片側が決まるのでではないかという話に
適度に枝刈すれば間に合うよね、ということで書いてもらう
その間に自分は他の問題を確認、E問題をチェック
5分ほど考えるが良い実装が思いつかないのでF問題見る、が無理そうなのでGを見る
構文解析だが()内から順に解けば良いのではと考えてみる
考えると、()については内部を解いた式の答え+()を全部解いた後の外部の式の答えが全体の答えになるので、まずは()のない式を検討
この時+と*しかないので単調増加なことから尺取り法が可能だと分かり、ということは左から解けるのでO(s)じゃんと判断
18:15
D問題AC
G問題が解けそうということと方針を伝えてから、いまだ解けてないB問題のヘルプに回る
添え字とか確認しつつコードをリファクタリング、サンプル通ったので投げるもWA
折った状態を表示するデバッグコードを用意してWAしたデータ1と見比べると、変な折り方してるのがあったので修正して投げるもWA
後は迷走、そのままサンプル絶対ACするWAコードを量産するにとどまり
19:30
終了、お疲れさまでした(ACDの3完)
69位で、自分の上に4完の同大学チームがいるので予選落ちが確定。なんでBバグらせたんだマジで
そのまま食事行って解散、B問題で死ぬとは思ってなかったので悲しみ