294.1

SRM

250が一番扱いに困るかも知れない。こういうのを一発で通すルーチンがちゃんと書けない...。

250

カードを半分の山に分けて、指定された山からK枚とり、その山がなくなるまで、逆の山から交互に1枚ずつとる。残ったK枚のカードをとる、というような感じでカードを並び替える。この操作を指定された手順で行ったとき、最初に一番下にあったカードはどこにあるか答えよ、という問題。


カードの位置がどこか、で場合分けして、次にどこに行くか、を計算するのがメイン。この処理をどうやって綺麗に書くか、という問題。条件分岐をたくさん書くと絶対間違えると思いつつ、条件分岐を羅列してみたら、案の定動かないものができてしまった。


単純にシミュレーションを回してやるのが正解っぽい。i番目のカードがどこに行くかをmove[i]としてやれば良い。

int move[] = new int[n * 2];
int p = 0;
int a = 0;
int b = n;
for(int i=0; i<k; ++i) { move[a++] = p++; }
for(int i=k; i<n; ++i) {
  move[b++] = p++;
  move[a++] = p++;
}
for(int i=0; i<k; ++i) { move[b++] = p++; }

コードで書くとこんな感じ。aは最初の山の先頭へのポインタで、bは別の山の先頭へのポインタ。書いてある通りに実装するのがいいんだろうなぁ、と思いつつ、O(N)じゃなくてO(1)で書こうとしたくなる。間に合うケースで無駄に最適化するとバグを埋め込むので注意が必要、という典型的な問題だろうと思う。

500

与えられた文字列を前半分とする回文のうち、辞書にある単語の結合でできるものから、辞書順で最初のものを答えよ、という問題。


まず辞書をソートしてやって、回文の先頭から順にマッチするものをチェックしていけば良い。単純にやると終わらないので、チェックした回文の部分文字列と、マッチした辞書の語のペアをメモしておく。回文は2通り作り方があるので、両方について求めると同時に、どちらが辞書順に先かを検討する。同じ回文については、辞書をソートすることでちゃんと辞書順で先のものが先に出てくるようになる。

1000

N桁の数字を決定することを考える。ランダムに数字が与えらるので、未決定の桁について割り当てる。このとき最終的に出来上がる数の期待値を求めよ、という問題。初期状態として、部分的に決定された状態で与えられる。


K個の空きがある状態で次にどこに数字を割り当てるか、を考えれば良い。これはDPでできる。K-1個の空きがある状態で、各桁の期待値が決定できているとすると、その期待値よりも大きい数字が与えられるならば、その桁よりも上の桁に持っていくし、そうでなければ下の桁に入れる。これを0から9までチェックしてやれば良くて、後は上から順に埋めていくだけ。既に決まっている桁については何も考えなくて良い。