競プロ
PAST 第二回を、答えを知っている状態で通した。ダラダラやっていて + 実装が迷走して M にかなり時間をかけてしまった。
第二回日本最強プログラマー学生選手権: 解いている途中。
- F: 配列に対する二分探索、部分配列の rotation, 部分配列の和の計算ができればよいので、二分探索木を実装すれば通りそうなのはわかるが、実装する元気が起きない。これが本当に想定解法なのか?
- G: 行列木定理を使うという話が当時あったので、それを思い出して解いた。
- H なもりグラフなのでサイクルをちょうど 1 個もつ。サイクルの弧のどちらかを使わなければならないという制約があるときに使う辺の個数を最小化するという問題になるはずなので、「ある点から反時計回りに連続で使うとした時、最小何個でカバーできる?」という問題になりそうな気がしたが、使う辺の集合が単一の区間とならない可能性もある。
「使わない 1 辺を固定したらそれぞれの弧についてどちらを使うか決まるので、それらの最小値をとる」というのはできるかもしれない。何個必要かの計算はインクリメンタルにやる必要があるのかな?
