TopCoder SRM練習 - SRM 525 DIV 2 Easy/Medium

次回のSRMで復帰予定なのでそろそろ感覚取り戻していくべく練習。
以前とは違ってSRM同様75分の中で解くのを重視。

今回やったのはSRM 525 Div 2

まずはEasy問題。

(0, 0) - (N-1, 1) の 2 x N な通路中を(0, 0)からスタートして(N-1, 0)まで到達出来るかどうかを判定して返せ

という問題。で、条件としては「1点以上を共有しているマスには移動できる」の中で制約に「Wとマークされているマスは水浸しで通れない」ってのがある。
少し図に書いて考えてみると
□□
□□
ok
□■
■□
ok
■□
□■
ok
□■
□■
ng
■□
■□
ng
ということで、縦にFが2つ並んでいるものを除けば良いということになる。で、これはうっかり忘れてたのだけれどゴール地点がW(水浸し)ならそもそも到達不可能として弾かなきゃいけない。後から問題の制約条件読むと「道の最初と最後は水浸しじゃない」と明記されてたので救われた形。

public class RainyRoad {
 public String isReachable(String[] road) {
  int width = road[0].length();
  for (int i = 0; i < (width - 1); i++) {
   if (
     (road[0].charAt(i) == 'W' && road[1].charAt(i) == 'W') ||
     (road[0].charAt(i + 1) == 'W' && road[1].charAt(i + 1) == 'W')
     ) {
    return "NO";
   }
  }
  return "YES";
 }
}

コードはこのとおり。無駄に2列ずつやってるのは、最初のうち問題を読み間違って「上下左右にしか動けない」と勘違いしてた状態で書いたコードの残骸(非効率だけど間違いではない)が含まれるから。システムテスト通ってスコアは212.31 / 250。

続いてMedium問題。
読んだ瞬間には「うわ、GDD DevQuiz系?」と探索アルゴリズムに弱いのを思い出したけど、まずはしばしごにょごにょ考えた。
問題をざっくり訳すと

指定サイズ(1辺は1-30マス)の盤面のいくつかのマスにコインが置かれてる。このとき、コイン群を盤面全体に対して上下左右いずれかに動かし、盤面の端から適当な数のコインを落として指定された(K枚)のコインのみを盤面に残すための最短手数を返せ

というもの。
単純に考えると1回のオペレーションで4通り、探索すると最大30x2=60手なので2^120ぐらい読む必要がある。これは2秒の制限中では明らかに無理。
ということでしばらく図を眺めてごにょごにょと考え「移動順はともかく、元盤面の中でサブの盤面を定義してその中にK枚のコインが残るようなケースのうち最も手数の少ないものを探しだす」んだと思いついた(ちょい遅かった)。
こうすると始点と終点の選び方で30^4、選んだエリアの中に含まれるコインの枚数を数えるのに最大30^2(実際はサブセットに限定される分、もうちょい小さい)の計30^6、ループは7億回ちょいとなって2秒制限の中ではやばい感じがするけどひとまず実装してみた。
ちなみに実装中に考えていたループ回数の低減策は「指定エリアに含まれるコイン枚数を辞書として持つ」で、計算量的には30^4+30^2と相当効くはず30^4+30^4となって半分程度に出来る(辞書の辿り方によってはむしろ悪化する)。ただ、その分81万要素を保持する必要が出てくるので変なパックするとメモリ足りなくなる(64MBしか使えないらしい)。まあこのあたりは一旦HashMapあたりで作って不足するならcharの配列あたりに落としていけばいいかなと。
で、そんなことをほんのり考えつつひとまず書いたナイーブな実装がこれ。

public class DropCoins {
 public int getMinimum(String[] board, int K) {
  int min = 9999;
  int width = board[0].length();
  int height = board.length;
  for (int i = 0; i < width; i++) {
   for (int j = 0; j < height; j++) {
    for (int k = i; k < width; k++) {
     for (int l = j; l < height; l++) {
      // (i, j) -> (k, l)
      int tmpCnt = 0;
      for (int m = j; m <= l; m++) {
       for (int n = i; n <= k; n++) {
        if (board[m].charAt(n) == 'o') {
         tmpCnt++;
        }
       }
      }
      if (tmpCnt == K) {
       int left = i;
       int top = j;
       int right = width - k - 1;
       int bottom = height - l - 1;
       int steps = 0;
       if (left < right) {
        steps += left * 2 + right;
       }
       else {
        steps += left + right * 2;
       }
       if (top < bottom) {
        steps += top * 2 + bottom;
       }
       else {
        steps += top + bottom * 2;
       }
       if (steps < min) {
        min = steps;
       }
      }
     }
    }
   }
  }
  return (min == 9999 ? -1 : min);
 }
}

時間切れになるかなーと思いつつシステムテスト(この適当さがあんまり良くないんだけど)走らせたところ、最も時間のかかるケースで411msかかりつつも時間内に処理出来てパス。スコアは265.44 / 600。
例によって道筋が立ってからはほとんど一本道でいけたけど危なくてしょうがない。
tmpCntのカウント中にカウントがKを超えた場合には途中で諦めるというのも手なんだけど、そのぶん分岐が増えるわけで微妙。

Hard問題は開いてないし当分開かないでいいと思う。