307.1

古き良き時代のSRM...ってこともないか。

250

隣接要素のスワップがN回まで許可されている状況で、辞書順でもっとも大きい配列を作れ、という問題。

先頭から後ろN個以内で最大のものを先頭に持ってきて、移動した回数Nを減らす。先頭は固定して以下順番に繰り返す。

500

電車の上を進行方向に向かって移動する。車両ごとに休憩できる地点があって、それ以外の場所にいるときに橋を通過することはできない。橋の座標が与えられるので、橋をいくつかこえるか、先頭につくかしたら降りるとき、最初に降りることのできる場所の座標を答えよ、という問題。

橋の間隔を求めて、そこで何両分移動できるかを計算する。電車の先頭についたら降りるし、そうでなければ指定された橋の位置になるはず。

longが出てきてdoubleにするときに注意しないと精度が足りなかった。

1000

コインの山が与えられるので、二つの山を一つにするか、一つの山を二つにするという処理を繰り返して、終了状態を作る。このときの最小回数を答えよ、という問題。

初期状態と終了状態が同じコインの数でないならまずできない。それ以外は可能。

初期状態と終了状態から二部グラフ作って、最大流流して、閉路潰したときに、二部グラフ間に使う枝数x2から二部グラフのノード数を引いてやれば良さそう。後でちゃんとやる。