たまにはと思って、Dから解いてみた
6完 59:19 + 1ペナで86位、こどふぉ勢がいないので順位は高いけど立ち回りがびみょい
A Edge Checker 2
ある程度慣れてる人ならAなんだけど、グラフ初見の人はたいへんそう
二分木なので親が子/2か？で判定できる
(AC 20:48)
B Longest Uncommon Prefix
SiがS[1~i]かと思ってあせるけど、そんなものBに出るわけないのでよくみるとS[i]だった
内容としては愚直にチェックすればOK
(AC 24:09)
C abc285_brutmhyhiizp
逆の操作はABC-Cで既出
26進法だと思って計算すればいい、
(AC 27:18)
D Change Username
ちょっと頑張ろうかなと思って早めに解いたけど、noimiさんが早すぎた
サンプルのダメな例みると、明らかに有向グラフがループしてるので、どうせ強連結成分があるかどうかだと思う
あとはACLのSCC使えばおわり
(AC 4:42)
E Work or Rest
ちょっと考察したけど、単純な形に帰着できていい気持ち
1つの平日の塊の長さをXとすると、その塊における生産性は簡単に計算できます(A[i/2]の和)
1つ平日の塊を追加するには、1つ休日を配置する必要があります
また、平日の塊のそれぞれの長さが決まって、休日を含めてN日以内におさまることがわかれば、それを満たす平日・休日の置き方は存在します(もしあまったら休日にすればいいです)
こう考えると、i日使うと生産性がPi得ることができるという条件がN個与えられ、sum(i) = Nとなるときの生産性を最大化する問題になります
これは重みi, 価値Piの個数制限なしナップサック問題だと考えられます
よって、dp[i][j] := 重みiまで考えて、現在の重みの総和がjのときの価値の最大値
と定義してdp[N][N]を求めればよいです
(AC 18:49)
F Substring of Sorted String
まず思うこととして、アルファベットが26文字しかないのでS[l:r]の中に「隣り合う文字が異なる箇所」が26個以上あれば必ず条件を満たしません
つまり、「隣り合う文字が異なる箇所」に着目すれば各クエリに対して26回以内のチェックで判定ができそうです
ということで、「隣り合う文字が異なる箇所」を管理することにしましょう
次に異なる場所がどこにあるか？が知りたい + クエリによって変化するのでsetで管理することにします
クエリ1は簡単で、両隣をみてあげて異なっているか更新すればよいです(同じになったらerase, 違ったらinsert)
クエリ2が本番になります
解説ではセグメント木を使っていますが、そうでない方法で書きます
まず、Sに含まれる各文字の個数を管理しておきます(vectorなどで管理して、クエリ1でも更新します)
次に、S[L:R]の中に各文字がどのくらいあるか調べましょう
Lを徐々に右に進めていく要領で確認できます(以下説明)
Lより右で最も近い「隣り合う文字が異なる箇所」をsetに対する二分探索で求めます
違う文字になる位置がyとすると、L-y個のS[L]が存在します
ここで、L = yに進め、同様の操作を繰り返します(この操作回数は文字の種類数で抑えられます)
このときにS[L] < S[y]である必要があり、そうでないならNoです
これでS[L:R]での各文字数がわかりました
あとは、足りていない文字が存在していないか確認すればよいです
S[L] ~ S[R]の間(S[L], S[R]は含まない)で、全体の文字数>S[L:R]中の文字数となる場所があればNo、そうでなければYesです
これで各クエリにO(σ logN)で答えることができてACとなります
(AC 59:19)
G Tatami
Hanjoじゃないんだな～
できる手法としてはDPかフローかなと思います
ただ、Hanjo 2でも Wがかなり小さい値だったので、これをDPでやるにはきついんだろうなと思います
フローかな？と思っていい性質を探すと(これはもっと早く気付くべきなんですが)、グリッドなので二部グラフであり、フローが使いやすそうだと思います
ざっくり考えると、1じゃない隣り合うマスに対して(i+jが偶数) -> (i+jが奇数)に辺をはって、最大流を解けばいいんですが、「ここには絶対流さないといけない！」というところがあります
「ここには絶対流さないといけない！」ところのコストを低くして、最小費用流にすればいいのでは？と思って書いたのですが、そういえば最小費用流はおおよそ流量×辺の数だけかかるので、TLEでした...
解説をみたんですが、最小流量制限つきってありましたね
勉強になります
(AC --:--)
総括
FでS[l:r] = T[l:r]だと思ってロスしたのかなしい
