速解きをしただけの人、Ex詰めるべきだった
42:13 + 1ペナ 6完 162位
A "atcoder".substr()
言われてみるとタイトルに答えが書いてある
意識してなかったですが、substr()を使って書きました
(AC 1:08)
B Nice Grid
端からの最短距離で色が決まっていることが分かります
一瞬多点BFSしようかと思ったけど、冷静になると端からの距離を計算してそのminをとればよいことに気づきます
あとは偶奇を求めるだけ
(AC 5:45)
C Matrix Reducing
ひさしぶりにbit全探索きましたね
Cに出るけどdiffが高くなると評判のやつです
制約が小さいので、とりのぞくところを決め打って一致するか見ればよいです
ざっくりみて2^10 x 2^10ですが、h2,w2と一致しない時は無視できるのでかなり高速に動きます
(AC 12:58)
D "redocta".swap(i,i+1)
これも非常に典型的な転倒数を求める問題です(ソート回数=転倒数)
もう少し列が長いとBITなどを用いたO(NlogN)の解法が必要になりますが、今回は愚直にチェックしてあげればよいです
具体的には与えられた文字列に対する位置を2つ決めて、その位置がもとの"atcoder"で逆転していないか確かめればよいです
(AC 15:40)
E Blackout 2
このあたりからちょっと難しめになってきます
まず、こういう「辺を切る」操作はかなり扱いづらいので、「逆からみる」とうまくいくことが多いです
この典型はABCに限っても何回も出ています
出題例：
ABC229-E Graph Destruction
ABC120-E Decayed Bridges
とりあえず逆からみることにして、「今発電所とつながっている都市の数」をどうカウントするか考えます
解説のように超頂点をつくるときれいに書けますが、そこまで考えられなくても頑張ると解けます
計算するのに必要なものは
「そのグループは発電所とつながっているか？」
「そのグループには何個都市があるか？」
の2つです
これがわかれば、新しく発電所を含むグループとつなげるときに、都市の個数を加えてあげればいいことになります
これを配列などで管理してみましょう
どっちでもやることは同じなので、「そのグループには何個都市があるか？」について考えてみます
もし、そもそも同じグループにいるなら新たに考える必要はありません
2点u,vが違うグループにいるなら、新しくできるグループの個数は
(uを含むグループの都市の数) + (vを含むグループの都市の数)
になります
では、(uを含むグループの都市の数) をどう計算すればよいでしょうか？
グループをくっつけたときに、そのグループに含まれる都市すべての値を更新することでも計算できますが、最悪の場合O(N^2)の計算量になります
そこで、UnionFindにあるleaderなど、グループを代表する頂点だけ更新するようにします
そうすると1回の更新で1つの値しか変化しないので十分高速になります
発電所があるか否か？も同様に管理すればよいです
(AC 31:48)
F Monochromatic Path
制約を読むとかなり大きいので、できることが限られてきます
今回「右か下にしか動けない」という条件があるので、1度通り過ぎた行や列に戻ってくることはありません(ので、その場所以前の情報を考慮する必要はありません)
また、今いる位置が0なのか1なのか？は「その行の反転回数 + その列の反転回数」にのみ依存します
よって、必要な情報は[今のマス目はどこか][その行は反転したか][その列は反転したか]の3つになります
ということでこれらを素直にDPに落とし込んでいきます
dp[i][j][k][l] = マス(i,j)にいて、行が反転(k=0,1)、列が反転(l=0,1)しているときの最小費用
とDPを定義すると、
新しく移動するときに色が異なるかどうかを確認して、違うなら進む先の行or列の色を反転させる必要があるので、そのぶんのコストを加えるとすることで遷移できます
(AC 42:13)
G String Fair
大胆予想！！最適な文字列は3文字以下かINFとしたら嘘でした
最短経路、文字列だとよくあるパターンなのに出てこなかったの反省
総括
いいところF
