読者です 読者をやめる 読者になる 読者になる

SRM615

topcoder

writerしてました。

Div2Easy

モンテカルロ君は同じサイズのgelに重なると合体するらしいです。
元ネタはまあアレですね。
設定はDiv1のと似てますが、こちらはシミュレーションするだけ。

Div2Medium

1mm進めるジャンプとBmm進めるジャンプを合計T回やってちょうどDmm進めるか。
式にすると、

x+By = D
x+y = T

いろいろ気をつけながら数学すると解ける。けど、わりとそういう解法はコーナーケースにハマったりしやすいので、二分探索もおすすめ。

Div2Hard

AとBをマージした文字列になるようにSの?を埋めよ。複数ある場合は辞書順最小。
解法1:一文字ずつAから順番に試し、それ以降が条件を満たせるかを毎回チェックする。チェックパートはDP[i][j]=A[i]まで、B[j]までを使って適切に埋めることが出来るか。
解法2:DP[i][j] = A[i]まで、B[j]までを使った時にできる辞書順最小の文字列

Div1Easy

モンテカルロ君の初期サイズは分からない。最終的なサイズとしてあり得ないものは何通りか。
いろいろやり方はありそうですが、楽そうなのを2つ。
解法1:setで「その時点で作れないもの」のリストを更新しながら舐める。
解法2:「作れないもの」も「意味のある初期サイズ」もXに含まれる数字のみなので、Xに含まれる数字の集合から作れるものをremoveしていく。こちらもsetを使いたくなる。

Div1Medium

重み付き無向グラフで長さがちょうどLのS-Tパスは存在するか。
Sについてる適当な辺を取ってきてその重みをWとする。すると、長さXのパスがあるときにX+2kWも作ることが出来る。つまり、mod 2Wごとに最短路を求め、dist[L mod 2W] <= L であればいい。これは実は必要十分条件になっています。
めっちゃ既出臭漂う問題だけど、りんごさんは見たことが無いらしいので大丈夫ぽい?

Div1Hard

R,G,B,Wからなる文字列が与えられる。Wを塗る方法であって、そこから同じ長さのRGRG...をM回取ったときにBしか残らないような塗り方は何通りか。(説明雑いっすね)
正しい塗り方の条件は、
(ア) RとGの個数の合計が2Mの倍数
(イ) どの時点においても、0 <= Rの個数-Gの個数 <= M
これが分かればDPの漸化式は自明。
(イ)に関しては、「最初のM個のRを各回で1番目に取る、最初のM個のGを各回で2番目に取る、次のM個のRを各回で3番目に取る...」としてよいことが証明できるので、それを利用して少し考えるとこの条件になります。

これそんなに簡単なんですか・・・(出題側は難しいと思っていた)。
Med > Hardらしいです。すみませんでしたっm(_ _)m
面白そうなゲーム見つけたので許して下さい。