結果
100+100+100=300pt
1stタイ
問題
A Furniture: グリッドグラフの頂点が関節点か判定して、そうでないならそれを削除するクエリを処理する問題。できるだけ左下を通るようなパスとできるだけ右上を通るようなパスを管理すると、dfsの計算時間が償却されてO(HW)で解ける。難易度10
B Monochrome: 白と黒がN個ずつ並んだ円環で、白と黒をペアにして交差数を最大化する問題。白と黒の順序は崩さずいくつかずらしたものの中に最適解があって、最適なずれの位置は二分探索で求める。時間O(Nlog^2N)で解ける。難易度11
C Power: 木の最適化問題。木DPをすると解ける。難易度8
経過
時間は分の一の位を四捨五入していることがある
13:03-(0+0+0=0)
コンテスト開始
Aを読む。
読解verifyのため小課題1の5点を取る。
13:10-(5+0+0=5)
小課題2が95点で、取った方が良さそうなのでこれを考える。
一般のDAGに拡張して考えると到底解けなさそうに見えたので、グリッドグラフの優位性を考えると、グリッドグラフが持っている「左下に行けば行くほど左下に行きやすい」という性質が使えることに気づく。
この手のオリジナル感のある問題は下手に実装すると合わないので、丁寧に方針を固めてから実装し、100点を取る。
14:20-(100+0+0=100)
Bを読む。特定の二つの区間の関係を考察し、最適解の形を限定する。行き過ぎた限定をした解法を提出し、0点。verifyのため小課題1の全探索を書き、4点を取る。
15:20-(100+4+0=104)
4点の解法によるジャッジを作り、0点の解法の穴を発見する。
小課題2のためO(N^3)のDPを書くが、書いている途中で持つべき状態量が不十分だと分かる。
行き詰まったのでCに移る。
15:30-(100+4+0=104)
Cを読む。愚直に木DPを書くと、100点が得られた。
15:50-(100+4+100=204)
Bに戻る。小課題2のためのDPに最適解の形の限定を利用することを考えると、区切りの場所を一箇所決めればBITを使って解けることが分かる。O(N^2logN)の解法を提出し、35点を取る。
16:50-(100+35+100=235)
区切りの場所ごとに決まった値の最大値を求める問題なので、単調性や凸性を利用することを考える。実験をすると、f(k+1)-f(k)がk=[1,n)の範囲で++...++--..--のようになっていることが分かる。二分探索でその境界を求めるO(Nlog^2N)の解法を提出すると、100点が得られた。
17:10-(100+100+100=300)
18:03-(100+100+100=300)
コンテスト終了。
感想
満点が取れて嬉しい。
