7完 92:25 84位
2連続2桁でいいかんじ
発想+感想中心でCから書きます
C Rotated Colored Subsequence
よくあるやつ、各文字ごとにみればOK
左シフトと右シフト間違えて時間ロス...
(AC 18:39)
D LOWER
更新するやつ典型その1「最後だけわかればいい」
前からみて解いたんですが、「文字の変更」「大文字・小文字の変更」の2つが最後にいつ起こったか管理しておけば解けます
「大文字・小文字の変更」がそもそもない場合がコーナーになるかもなので注意
実装としてはそんなに変わらないと思うんですが、
更新するやつ典型その2「後ろから確定させる」
を使っても解けますね
(AC 29:12)
E Roulettes
期待値DPの鉄則「ゴールから考える」
これに尽きます
とりあえず期待値DPをすると考えると、
dp[i] := 今のポイントがiのとき、Mポイント以上になるために必要な金額の期待値
と定義したくなります
遷移を考えてみます
ルーレットのどの目が出るかはわからないので、「どのルーレットを使うのが最善か？」を考えることになります
そうすると、あるルーレットを使った時の期待値を遷移先から計算できます
たとえば、1と3が出るルーレットなら
dp[i] = (dp[i + 1] / 2 + dp[i + 3] / 2) + Ci
になります
このdp[i]が最小になるルーレットを見つけてあげればよいです
ここまでできれば水diffくらいあると思うんですが、今回は0が入っているのでもう少し複雑になります
たとえば、0と3が出るルーレットなら先ほどの例と同様に
dp[i] = (dp[i + 0] / 2 + dp[i + 3] / 2) + Ci
になるんですが、dp[i+0] つまり dp[i]がわかっていないので右辺が計算できません
このように両辺にdp[i]が出てくる場合は、典型処理としてdp[i]を移項させます
dp[i] - dp[i]/2 = dp[i+3] / 2 + Ci
1/2 dp[i] = dp[i+3] / 2 + Ci
dp[i] = 2(dp[i+3] / 2 + Ci)
と式変形することができるので、これで求めることができます
(AC 41:18)
F A Certain Game
むずかしかった...
解説にある通り「Union Find の過程をマージする木」を使うと簡単な問題に帰着できるのですが、思いつかなかったので自分なりの解法を書きます
まず、操作をかみ砕くと
「大きさaの連結成分に含まれる各頂点にa/a+bを足す、bも同様」
ということになります
各頂点にそのまま足していくと2乗のオーダーになってしまうので回避する方法を考えます
発想としては、逆から見てあげることで「それぞれに足す」というのを「結んだ2つの頂点に足す」に簡略化できるかな～という感じです
まず、辺をマージするときにそれぞれの代表元を記録しておき、UnionFindでマージします
これを逆にたどることで各頂点に足すべき値を伝播させていきます
具体例をだすと
1-2, 2-3と結ぶ場合には
・代表元1, 2にそれぞれ 1/2, 1/2を足す -> マージした後の代表元は1(になったとする)
・代表元1, 3にそれぞれ 2/3, 1/3を足す -> マージした後の代表元は3(になったとする)
を逆からたどります
dp[i] := その時点での頂点iの答えと定義します
・dp[1], dp[3]にそれぞれ 2/3, 1/3を足す
・dp[1], dp[2]にそれぞれ 1/2, 1/2を足す、さらにdp[2]には本来足すべきだった2/3(=1/2を足す前のdp[1])を足す
というような操作をしました
解説よりは複雑ですが、実質的にやっていることは同じになっているはずです
Submission #44525435 - AtCoder Beginner Contest 314
(AC 71:24)
G Amulets
単純なところから考えていきます
K=0はさすがに自明なので、K=1を考えます
モンスターiを倒せるかどうかは、1~iまでのモンスターの体力をタイプごとにわけて、
「1~iまでのモンスターの体力の総和」- 「最大となるタイプの体力の総和」がHより大きくなるかを判定すればわかります
つまり、i番目までに登場したモンスターで「それぞれのタイプの体力の総和」がわかれば、その最大値を引けばいいことになります
これはvectorなどを使えばO(N)でできそうですが、Kが大きくなった場合を考えていきます
結局、i番目までに登場したモンスターで「体力の総和が大きいタイプ上位K個」がわかれば、その和を計算することで判定することができます
これはmultisetなどを使って実装できます
上位K個を入れるmultiset A, 下位M-K個を入れるmultiset Bを用意しておいて、それぞれのモンスターに対して該当するタイプを更新していけばよいです
これで、Kを固定したバージョンが解けるのですが、ほぼ同じでK = 0, 1, ... , Mが解けます
もしK個で無理になったら、そのときに上位K個のmultisetを上位K+1個に変更していきます
倒せるモンスターの数には単調性があるので、K個で突破できるものはK+1個でも突破できて、ダメになったところから考え始めるとしても問題ありません
(AC 92:25)
総括
F完全に忘れていた典型だった
