情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

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問題をO(b)と見積もったので時間掛かりそう、交代して先に挑む
ソースコードはさくっと書けたがメモリ不足、long[1000000001]をint[1000000001]にしたら動いたので実行
サンプルACだったので待機

17:04

C問題AC
0WAだと時間ペナないしこれはいけるんじゃないかという話をしつつD問題の相談を受ける
全探索だと2^{72}だから無理ではないかという話をしたが、片側決め打つともう片側が決まるので2^{36}ではないかという話に
適度に枝刈すれば間に合うよね、ということで書いてもらう
その間に自分は他の問題を確認、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問題で死ぬとは思ってなかったので悲しみ

反省

穴あけパンチを持ち込んでいたのでB問題のシミュレーションが楽だったのは良点
だが紙が手軽に折れないので、折りやすい紙があると良いかもしれない
反省点として、B問題を解くと決めたならコーディングしていない最後の1人に紙を量産してもらうべきだった
あとは糖分が足りない、ミルクティーに入れる砂糖を用意すべき 午後の紅茶は甘さが足りないんだよ!
他人のコードのリファクタリングも困難なので、書き直しした方が良かったというのもあるかも
というか変数名が敵だった