Educational Codeforces Round 25

• https://codeforces.com/contest/825

A. Binary Protocol

$0$ の間にある $1$ の個数を数えます．

• https://codeforces.com/contest/825/submission/187400518

B. Five-In-a-Row

すべての連続 $5$ 文字を列挙します．

• https://codeforces.com/contest/825/submission/187400379

C. Multi-judge Solving

昇順にソートして，基準に足りていなかったら外部で解くということにします．

• https://codeforces.com/contest/825/submission/187400139

D. Suitable Replacement

例えば二分探索で目標個数を決めて，不足分を貪欲にとっていきます．

• https://codeforces.com/contest/825/submission/187398867

E. Minimal Labels

入次数が $0$ で最小インデックスの頂点に最小ラベルを割り当てることを繰り返します．

• https://codeforces.com/contest/825/submission/187398169

F. String Compression

自然に $O(N^2)$ 遷移の dp があります．同じ区間に対する遷移を最小周期に対してしか行わないように注意して実装すればよいです．

• https://codeforces.com/contest/825/submission/186268669

G. Tree Queries

黒い点全体（およびそれにクエリ点を追加したもの）の steiner tree 上の頂点 min を求めよということになります．

集合 $S=\{v_1,v_2,\dots ,v_n\}$ の steiner tree は，これら $n$ 頂点が dfs in order 順にソートされているとき，パス $v_i{v}_{i+1}$ の和集合になります（$v_{n+1}=v_1$ とする）．各辺を $2$ 回ずつ通ることが分かるからです．

クエリ処理．黒い点が増える一方（incremental）なので比較的易しいです．点の追加によって和集合をとるべき新たなパスを検出し，そのパス上の点の min で ans を更新すればよいです．

• https://codeforces.com/contest/825/submission/185245133