writerしてました。
Div2Medium
1mm進めるジャンプとBmm進めるジャンプを合計T回やってちょうどDmm進めるか。
式にすると、
x+By = D x+y = T
いろいろ気をつけながら数学すると解ける。けど、わりとそういう解法はコーナーケースにハマったりしやすいので、二分探索もおすすめ。
Div2Hard
AとBをマージした文字列になるようにSの?を埋めよ。複数ある場合は辞書順最小。
解法１：一文字ずつAから順番に試し、それ以降が条件を満たせるかを毎回チェックする。チェックパートはDP[i][j]=A[i]まで、B[j]までを使って適切に埋めることが出来るか。
解法２：DP[i][j] = A[i]まで、B[j]までを使った時にできる辞書順最小の文字列
Div1Easy
モンテカルロ君の初期サイズは分からない。最終的なサイズとしてあり得ないものは何通りか。
いろいろやり方はありそうですが、楽そうなのを２つ。
解法１：setで「その時点で作れないもの」のリストを更新しながら舐める。
解法２：「作れないもの」も「意味のある初期サイズ」も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を各回で１番目に取る、最初のM個のGを各回で２番目に取る、次のM個のRを各回で３番目に取る...」としてよいことが証明できるので、それを利用して少し考えるとこの条件になります。
これそんなに簡単なんですか・・・(出題側は難しいと思っていた)。
Med > Hardらしいです。すみませんでしたっm(_ _)m
面白そうなゲーム見つけたので許して下さい。
