コンテストページ
解法
✔A - Creating a Character
強さの方に振る分を x とすると、0 <= x <= exp です。 さらに賢さよりも強さの方が上という条件から x に下限条件が付きます。
✔B - Zmei Gorynich
最後は最も強い攻撃で倒しますから、まずはそれを計算です。 それで倒せたら、ヨシ、ダメならその前にも攻撃が必要です。 弱体化は、差し引きダメージの最大のものです。 先程倒せなくて、かつこれが 0 以下なときには NG です。
✔C - The Number Of Good Substrings
1, 10 以外は 0 始まりですから、初めて出る 1 を全探索です。 a[ 右端 + 1 ] = そこから左に伸ばせる 0 の数 を前計算です。 順番に右に伸ばしていきましょう。すぐに値のほうが n を超えるので間に合います。
✔D - Coloring Edges
DAG ならば 1 色でよいです。 そうでないときには頂点番号が増えるものと減るもので色分けをすればよいです。 DAG 判定は、各点から DFS です。 行きがけに 1 にして、帰りがけに 2 にします。 2 はスルー、1 は DAG ではありません。
✔E - Sum Queries?
balanced である条件は、被っている桁がないことです。 被っている桁がなければ明らかに balanced なのですが、逆が難しいです。 被っていても繰り上がれば大丈夫に見えますが、ダメです。 まず、繰り上がって新しい桁が出来るのはアウトです。 したがって、繰り上がっては来るけれどそこから再び繰り上がることがない桁が存在します。 その桁がダメな桁です。
実装です。 桁ごとにセグメント木です。その桁が立っていたらその数を、なかったら空欄 0 です。 トップ 2 を管理するセグツリーをしましょう。 (x0,x1),(y0,y1) -> (max(x0,y0),max(min(x0,y0),x1,y1))です。
✖F - Forced Online Queries Problem
これは難しいです。Dynamic Connecivity と呼ばれるものでしょうか。 Link-Cut で解けるかなと思ったのですが、それは森でないときつそうです。 Wikipedia にページがありますね。 難しそうなので断念をしてしまいました。
それはさておき、Link-Cut も、いつかは素で書けるようになりたいものですね。
感想
B と C が丘って本当ですか！？ C のほうがかなり込み入っているイメージなのですが、どちらも 1600 のようです。
