2/1
CEOIの問題は良いのが多いですね。
PKU 3652
やるだけ。
PKU 3653
だいくすとら。
PKU 3654
やるだけ。
PKU 2452
solve(a, b) を S[a..b] におけるこの問題の解を求める関数とすると、solve(a, b)は以下のような実装になる。
0. b >= a なら -1 を返す
1. S[a..b] 中の最大値 S[maxi] を求める
2. S[a..b] 中の最小値 S[mini] を求める
3. max{ maxi-mini, solve(a, mini-1), solve(maxi+1, b) } を返す
ここで最大値、最小値を効率よく求めるためにRMQを使ってやるとよい。
PKU 1934
LCSを求めるDPに＋αしたようなもの。
DPの表の上で A[i] == B[j] となるような (i, j) の位置を頂点として、 dp[i][j] + 1 == dp[i'][j'] かつ i < i' かつ j < j' の場合にのみ (i, j) → (i', j') の有向辺が存在するようなグラフを考える。
そのグラフ上で dp[x][y] が A, B のLCSと等しくなるような頂点 (x, y) までの経路を辿るとよい。
PKU 2274
まず全体の追い越し回数を求める。
V[i] > V[j] なら i はいつか必ず j を追い越すということに注目すると、全体の追い越し回数は V[1..N] をバブルソートした時の交換回数となる。これはマージソートっぽい感じで求めてもいいし、0 < V[x] < 100 だからBinary Indexed Treeを使っても良い。結局 O(N log N)。
次に最初の10000回の追い越しを求める。
基本的な考え方としては追い越しのイベントをヒープに入れて、その追い越しが起きる時間が早い方から取り出して行く方法。i が j を追い越す(i < j)とすると、それ以前に i < x < j なる x を i は追い越しているはずである。なのでとりあえず i が i+1 を追い越すようなイベントだけを最初はヒープに入れておく。
i が j を追い越すイベントがヒープから取り出されたとき、まずそれを表示する。そして今度は i が i+1 を追い越すイベント、 j-1 が j を追い越すイベントをそれぞれヒープに入れる。これでO(N + P log N)。ただしP = min{10000, 全体の追い越し回数}。
PKU 1920
まずどこに移せばよいかは、最初に円盤N(いちばんでかいやつ)があるところで決定。
count(n, dst) を 1..n の円盤を棒dstに移すのに必要な移動回数を表すものとする。これは次のように実装できる。
0. n < 1なら0を返す。
1. nが既にdstにあるなら count(n-1, dst) を返す。
2. nがある棒でもなく、dstでもない棒を作業棒とする。
3. count(n-1, 作業棒) + 2n-1 を返す。
最後にcount(n-1, 作業棒) + 2n-1 を返せばよいのは次の理由による。
まず、1..n-1 の円盤を作業棒に移すと n の円盤は1回の移動で dst へ移すことができる。またこのとき、作業棒には 1..n-1 の円盤が全てあるので、これを dst へ移すのに必要な移動回数は 2n-1-1 回となる。
