本戦
A, B, C, D, E
パパパッと解く もちろん後半に比べると簡単ではあるんだけども、C,D,Eは自明ではなかった
D問題imosで解けなかったのダメかもしれない(StarrySkyTree並感)
E問題は面白かった
F
1時間ぐらい使う。無理。
G
O(N4)はすぐに思いつく。ウンウン考えてたら天啓が降ってきてO(N3)になる。やったぜ
H
読んだ感じ区間を適当にsortしたのちにSegTreeで処理するタイプの問題っぽいなと思う
区間を適当にsortしたのちSegTreeで処理したら解けた
I
木+データ構造やんけ、これは勝ったな(確信)
ウンウン考えてたらUTPC2013の支配と友好っぽいことをすればいいと気づく
あんまりデータ構造要素はなかったけど面白い
F
再び戻る
ぐるっと回るのはたかだか2周でいいというところまではわかっていて、ウンウン考える
式をウンウンいじったらいつの間にか辺を使う回数の式が出ていた。常勝
J
- 読む
- 無理
- 終了
エキシビジョン
- Bでライブラリ貼るだけと信じてやまなかったのでBから読む
- 線をつなぐ?これはLink-Cut Tree待ったなしですね
無 慈 悲 な 1 0 億 7
Aを読む
- オッフローじゃ〜ん
- 部分点はさすがに自明だったのでとりあえず0点回避に向けて動くことにする
- 自明だけども実装が重い、けど20点を取る
- 満点は流し戻し的なことをするのかなぁと思う
ちなみに会場からSCCという単語が聞こえてきていた。耳栓をしていてもマイクを使って発言されるとどうしようもない
Bを考える
- お絵描きして色々調べる
- 結構形の制約は厳しいことがわかる
いややっぱり無理じゃない?
Aを考える
- 残余グラフでの連結性だけ調べればよくて、結局フローを流すのは最初だけで良いことがわかる
場合分けして、なんかSCCとか使ったら解けた。
Bを考える
- サイクルがあるなら必ず長さ4のサイクルがあることに気づく
- でも全然解けなかった。終了。