結果
35+0+15=50pt
日程内9位(unique)
累計8位(unique)
A:ヒストグラムの木の問題、難易度12(?)
B:なもりグラフでクエリに答える、難易度12(?)
C:木の辺を彩色して根に案内する、難易度10
経過
□9:00(0+0+0=0pt)
コンテスト開始
Aを眺める
走査方向を高さの昇順に取ると良いことがわかる
うまく扱うと木になりそうだということがわかるが、O(N^2)のDPでA-1,A-2を通しておく
□10:00(35+0+0=35pt)
A-満点を木DPで解くことを考える
実装して何回か提出するがWA
ある区間の星によって孫以下の区間が分断されるケースを見落としていることに気づく
難しい問題であることがわかるので、別の問題に移る
□11:15(35+0+0=35pt)
Bを読む
危険なデータ構造と場合分けを求めているような見た目をしていて、小課題の点数も低いので考えないことにする
□11:16(35+0+0=35pt)
Cを眺める
C-1,C-3の値が3までの木のケースを実装する
入力形式を誤認していたところを修正する
□11:43(35+0+4=39pt)
C-2,C-4の一般グラフのケースを考える
根への単なる到達を達成する解法をdfs木で実装し、サンプルが合わなかったため、最短路での到達が求められているということを理解する
BFS木を書いて追加の11点を得る
□12:09(35+0+15=50pt)
C-満点を考える
パスのサブタスクを考え、どの点から見ても左右非対称な6文字の2進文字列を見つける
ウニのサブタスクを考え、次数が3以上の頂点では根に近い辺だけが別の色だとわかる
丁寧にレジュメを書いて実装するが、WA
□13:22(35+0+15=50pt)
直前の辺と頂点の扱いの周辺で条件式や応答形式などの間違いがあった
提出&assertなどのデバッグをするが、0点のまま競技が終了する
□14:00(35+0+15=50pt)
考察
求められていることを確認して、正しいコードを書こうという姿勢が必要