208.1

SRM

面倒なセット...。

250

二次元配列が与えられるので、各列の最大値のうち最小のものと、各行の最小値のうち最大のものを答えよという問題。


もしかしたら逆かも知れないけれど、実装あるのみ。

500

NxNの盤面にN個のクイーンを置く。規則にしたがってクイーンを移動させて、各クイーンが進行を阻害しないようにするために必要なステップ数を答えよという問題。


ひたすら長い英語は無視してサンプルを見つつ実装。ただし、最後に一意に定まる時は乱数ルーチンを呼ばないことに注意する必要がある。

1000

二次元ボード上を左上から右下まで3回移動する。移動は右か下のどちらかを常に選択する。初めて特定の場所に到達したとき、そこに記されている点を得ることができる。このとき最大の得られるスコアを答えよという問題。


単純なDP。ただし盤面を45度傾けた状態で処理をする必要がある。

  int score[w][h];
  int newScore[w][w+h-1]; // fill -INF
  for(int i=0; i<w; ++i) {
    for(int j=0; j<h; ++j) {
      newScore[i][i+j-1] = score[i][j];
    }
  }

この変換をした上でDPすると多分綺麗に書けるんだと思う。後は3つのパスを同時に検査するので、各点がx,y,zの位置にあるとしてやれば良い。O((w+h)*w^3)で、wとhは50程度。


DPテーブルの初期値をそれなりに大きいマイナスの値にしておかないと、初めて代入されるのかどうかの判定をやらないといけない。Javaだとboolean配列を作ればfalseで埋まっているので、それをみて新規の値なのかどうかを判定すればいいのかも知れないけれど、不真面目に0かどうかで判定したらたまたま0になるケースで失敗した。