GCJ 2011 Qualification Round

今年は普通な問題しか出ていないというか、やさしめ。終わる前から通ったりとか。

A

ロボットが2つあり、それらが行動したログが与えられるので、かかった最小時間を答えよ、という問題。

片方のロボットが行動するとき、自分が前にした行動からその動作にかかる時間と、もう一方のロボットの直前の行動との時間の大きい方を選択しないとログ順にならないというのを気を付けて実装するだけ。

B

ある文字列について、隣接する二文字が特定の文字からなれば他の文字に変換し、特定の二文字を含んでいればすべて削除するという処理を先頭から順番に行う。最終的に残る文字列を答えよ、という問題。

やるだけ。

C

整数配列が与えられるので、xorで合算した結果が等しくなるように二つに分割した後、大きい方の合計値を答えよ、という問題。

xorで合算した結果が等しくなるということは、全部をxorで合算したら0になるということ。二つに分割しないといけないので、一番小さい値とその他に分けるだけ。

D

整数配列が与えられる。配列のうち、任意のK個を選択して、ランダムに並び替える、という操作を何回やればソートできるか答えよ、という問題。

A枚のカードをランダムに並び替えると、それぞれのカードについて、目的の位置に移動する確率は1/Aなので、目的の位置に移動するカードの枚数の期待値は1枚。なのでA回やればA枚が目的の位置に移動する。なので整数配列のうち、ソートした結果と位置が違う枚数と同じ回数だけやれば良い。