読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

RUPC 2015 Day1 参加記

立命館大学競技プログラミング合宿2015の初日、立命館大学セット
同じ大学の後輩と2人でチームを組んだ ( 折角の合宿なのだから他大学の人と組めという話だが、積極的にチーム編成に参加していかなかった結果 )
コンテスト中の流れは以下の通り

開始 自分がA, 後輩がB問題を読む

いまいち問題概要が掴めない
なんとなく解釈ができたしサンプルもあうようなので実装開始

14:45 実装できた、サンプルも一致 問題概要完全に掴めてないがチームメイトは後輩なので気軽にsubmit -> WA
悲しみと申し訳なさと後悔が押し寄せる

パスの間に他のチームの人がいたらそれってパスできてないのでは、とふと思う
連続する2つの記録において~とあるしそれっぽい
修正、サンプルは一致

14:49 とりあえずsubmit -> AC
後輩がBとCを書けると言っているので後の問題を読む
後輩がBの実装を開始する

幾何っぽいのがあるので読んでみる
解けなさそう、

木に対するクエリ処理の問題がある、HeavyLightDecompositionと遅延評価すれば解ける?
なんて考えながらも実装量やばそうなのでこれも避ける

Eがdijkstraするだけっぽい
Dを軽く読んでおく

15:15 後輩がBをsubmit -> RE
他の問題も読んだしEも書けるのでBをデバッグする

メモリが足りていないことに気がつく
配列の0を1つ増す

15:18 Bをsubmit -> MLE
10^6の配列を3つとってるだけなのに何故??
一つ配列を消せるということなんので消す

15:18 Bを再度submit -> MLE
少し動揺
後輩から0が多すぎないかと指摘される
10^6の配列を確保したつもりが10^7の配列を確保していた

15:20 後輩がこれで絶対Bは通る、間違えないと断言 Bをsubmit -> WA
動揺

ある部分を別のループでやると答えが変わる?かも?と言われたのでその通りに変更
それっぽい感じになった

15:25 Bをsubmit -> AC 安心

後輩がCを実装

15:37 Cをsubmit -> WA
一緒にデバッグ

UnionFindTreeの初期化をしていないことに気がつく、修正

15:40 C submit -> AC

自分がEの実装を始める、後輩にはGかDのどちらかを考えてもらう

14:00頃 Eの実装が終わる
サンプルチェックするが2番目だけなぜか合わない
小さなケースでチェックするがうまくいく
後輩も呼んで2人でデバッグ

どうみても良さそうにしか見えない、辛さが増す

16:30 最小値を保存して置く配列の要素で、初期状態以外で最小値が0となるものが存在している
明らかに初期化ミス
初期化のループの範囲が間違っていることが判明、修正

16:35 E submit -> AC 初期化ミスで1時間潰したショックは大きい

F,Gは残り時間から考えても無理なので2人でDを考える
全探索コードを書いて色々調べたり全体から重複している部分を消す方法などを考える
40人以上通しているのにさっぱり分からなくて悲しい気持ちになる

コンテスト終了


感想 :
デバッグ力、DP力が足りていないと痛感
後輩とのチームだったので楽しくできた