はじめに
バチャを走りました．Dまでの4完，517位相当
コンテスト後にEも通しました
とても楽しいセットだったので記録を残します
A. Creating a Character
問題
キャラを作ります．初期のstrengthはstrでintelligenceはintです．今experience pointをexp点持っています．これを1使うとstrかintを1上げれます．最終的にstr>intとなるようにポイントを全部振るようなパターン数は何通りですか．
解法
strに振るポイントをaとすると，intに振られるポイントはexp-aであり，ここからaの下限が求まります．a>(exp-(str-int))/2です．これを使って解けます．Aにしては難しくないですか．
B. Zmei Gorynich
問題
HPがxの敵を殺したいです．n個の行動の選択しがあって，好きな順で好きなだけ行えます．i番目の行動を選ぶと，敵にダメージdiだけ与え，そののち敵はhiだけ回復します．最短何回の行動で敵を殺せますか？殺せないなら-1．
解法
とりあえずdi-hiの値が大きいやつで最初はHPを削り，そしてとどめをhiに関係なくdiが大きい行動でやるとよいことは明らかです．これは二分探索がやりやすそうです．二分探索で殺せる最小の行動回数を探索しました．check(m)をm回の行動で殺せるか，にし，m-1回di-hiが最大の行動をし，1回diが最大のでダメージを与え，合計ダメージがxを超えるかで判定してあげるとできました．
今書いてて気づいたんですが，別にceil( (x-max(di) ) / max(di-hi))でよくないですか？
頭ついてなかった...
C. The Number Of Substrings
問題
01の文字列が与えられます．連続な部分文字列の長さとその部分文字列を2進数としてみたときの値が一致する部分文字列を数え上げてください．
解法
こういう条件を満たす部分列を数え上げるみたいなのはABCでよく見る気がします．最近特に．
しかしそのような問題と違い，今回は単純なしゃくとりなどはできないことがわかります．そしてコンテスト中はSuffix Arrayの上での二分探索を使いACしました．自分のSuffix Arrayは二分探索を実装していなかったのでライブラリを窃盗しました...
Suffix順に並んだ配列で，どこからどこまで接頭辞が同じかを二分探索で求めることができるのでこのような問題を殴ることができますね
codeforces.com
D. Coloring Edges
問題
n頂点m辺の有向グラフが与えられます．どのサイクルも一色だけで塗られていることのないように塗るには最低何色いりますか？塗り方の復元もしてください．
解法
超いい問題だった．感動した．この問題をみんなが楽しめば世界から戦争はなくなる．
まず，DAGなら1色で彩色可能なのは明らかです．だってサイクルがないのですから．
そして問題文の雰囲気的に強連結成分分解をします．そうすると強連結成分ごとに問題を解けばいいことが分かります．強連結成分同士をつなぐような辺はテキトーに1で塗っておきましょう．
では，強連結成分をどのように彩色すればよいかを考えます．結果からいうと，強連結成分の頂点を一列に並べ，左から右へ行くような辺を色1で塗り，右から左へ行くような辺を色2で塗るのが一種の最適な彩色方法です．
このようにすると色1だけのサイクル，色2だけのサイクルは絶対にできません．
じゃあどのように実装するかですが，dfsをし，頂点の訪問順ordを記録しておき，同じ強連結成分内でord[from]<ord[to]なら色1をそれ以外なら2を割り当てることで先述の彩色を実現できました．
これ楽しいですね．最近lowlinkとか二重辺連結成分とかグラフまわりを色々勉強してたおかげで解法がすぐみえて楽しかったです．まぁグラフが連結とは限らないことを忘れて1点からしかdfsしないで30分くらい溶かしたのですが...
E. Sum Queries?
問題
とても長いので省略
解法
セグ木以外何もみえない...
2個より多くでサブセットを作っても得しないし，同じ桁が0じゃない2つでサブセットを作れるので，2個でサブセットを作りたい．
桁ごとにセグ木持って，セグ木の値はa[i]の桁が0ならINF，それ以外ならa[i]をもって最小値と二番目に小さい値を持つようなセグ木で桁ごとにしばく
神に祈りながらセグ木を10本持ちます...
祈りは通じました．
おわりに
楽しい...楽しくない？楽しいです．
Fはみていません(猛省)
