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問題は開いてないし当分開かないでいいと思う。

TopCoder SRM練習 - SRM 511 DIV2 Easy

今日もちょいちょいと。
GameOfLifeDivTwo

・ライフゲームの変形版
・ドットが円形に並んでる
・状態Tでの各ポイントの生存状態は、その前(T-1)で自身プラスマイナス1つの計3つのうち2つ以上が生存していた(=>true)か否か(=>false)で決まる

ということで愚直に端っこをループさせてこういうふうに解いた。計算量的には、-1にあたる場所とNにあたる場所をもうちょい特殊に扱って毎回境界外をつなぐ処理を行わないようにすれば減らせそう。まあ、Top Submission見てもこんな感じ。途中喋りながらやってたというのはあるけど、さらっと書いてから配列のコピーで微妙にハマりprintfデバッグ繰り返した結果159.31。うーん、イマイチ。正答率91%、平均点183。

public class GameOfLifeDivTwo {

 public String theSimulation(String init, int T) {
  int setLen = init.length();
  boolean stateList[] = new boolean[setLen];
  boolean stateTmpList[] = new boolean[setLen];
  for (int i = 0; i < setLen; i++) {
   stateList[i] = init.charAt(i) == '1';
  }
  for (int i = 0; i < T; i++) {
   for (int j = 0; j < setLen; j++) {
    int liveCnt = 0;
    int nextIdx = j + 1;
    if (nextIdx == setLen) {
     nextIdx = 0;
    }
    if (stateList[nextIdx] == true) {
     liveCnt++;
    }
    int prevIdx = j - 1;
    if (prevIdx == -1) {
     prevIdx = setLen - 1;
    }
    if (stateList[prevIdx] == true) {
     liveCnt++;
    }
    if (stateList[j] == true) {
     liveCnt++;
    }
    stateTmpList[j] = 2 <= liveCnt;
   }
   for (int k = 0; k < setLen; k++) {
    stateList[k] = stateTmpList[k];
   }
  }
  String retStr = "";
  for (int i = 0; i < setLen; i++) {
   retStr = retStr.concat(stateList[i] == true ? "1" : "0");
  }
  return retStr;
 }

}

TopCoder SRM練習 - SRM 450 DIV1 Easy

昨日に続いて、少しずつやる。
今日やったのはOrdered Nim。

・AliceとBobの2人がゲームをしてる
・複数のヒープ(インデックスが振られている)のうち1つから、1つ以上の石を交互に取り出す
・あるヒープから石を取り出せる条件は、そいつよりインデックスの小さなヒープが全て空の場合だけ
・最初に取り出すのはAlice
・各ヒープに入ってる石の数は10億個以下
・お互いが最も効率的にゲームをプレイする場合、勝つのはAliceかBobか返せ

先日落としたトラウマ化しつつある問題と少々似てるところがある。いくつかケースを紙に書いてみて
・Aliceが必ず勝てる場合以外は、Bobが必ず勝てる(直感的にこうだけど未証明)
・n-1番目へたどり着いたら全部取って勝てるので、n-2(境界注意)までが勝負
・"Aliceが勝つかどうか"をn-2番目のヒープから逆順でたどって検証していけばよさげ
・あるヒープに石が最初から1個しかなければ、勝者判定をひっくり返す
・あるヒープに石が最初2個以上あれば、その次(ループ上はひとつ前)のヒープにある石が1個であれば勝者判定をひっくり返し、2個以上であればAliceの勝ち判定とする(総取りか1つ残すかのどちらかで、Bobに不利条件を押し付けられるから)
とたどり着いた。

テストケースを自前で増やしてやばそうなパターンを拾えるようにしたけれど、それでも抜けがあって一度failed system test。その後訂正し再提出して75.0pt(実際だったら0pt)。なかなか凹みますな。avg=205 / 正答率74%。この回なら文句なしに落ちてる。

public class OrderedNim {

 public String winner(int[] layout) {
  String ALICE = "Alice";
  String BOB = "Bob";
  if (layout.length == 1) {
   return ALICE;
  }

  boolean aliceWins = true;
  boolean oneStoneFollows = false;
  for (int i = layout.length - 2; 0 <= i; i--) {
   if (oneStoneFollows == true) {
    if (layout[i] == 1) {
     aliceWins = !aliceWins;
    }
    else {
     aliceWins = true;
     oneStoneFollows = false;
    }
   }
   else {
    if (layout[i] == 1) {
     aliceWins = !aliceWins;
     oneStoneFollows = true;
    }
   }
  }
  return aliceWins ? ALICE : BOB;
 }

}

"both players play optimally"な問題はまあまあ苦手だなぁ。

TopCoder SRM練習 - SRM 450 DIV2 Easy

簡単な問題でもいいので、出来るだけ毎日解くキャンペーン中。
今回やったのはStrangeComputer

・指定位置のメモリを書き換えると、そこから右(概念的に)が全て指定した値でフィルされてしまう、変なコンピュータが与えられてる
・入力(文字列)で指定されたメモリ状態にするための最短手数を返せ
・なお、初期状態は0埋めされてる

public class StrangeComputer {

 public int setMemory(String mem) {
  char prevChar = '0';
  int opCnt = 0;
  for (int i = 0; i < mem.length(); i++) {
   if (mem.charAt(i) != prevChar) {
    opCnt++;
    prevChar = mem.charAt(i);
   }
  }
  return opCnt;
 }

}

こんだけ。同じ値が連続すれば、その分は前オペレーションで指定済みとなるので手数増やさずに設定したことに出来る。230.98、passed system test。平均スコアが213.15で正答率93%なのでこんなもん。

SRM 507 DIV1

DIV1昇格後初のSRM。気付いたら2ヶ月ぶりで結構焦る。あっちこっち出かけたり飲みに行ったりしてたらこんなに空いてた。
差し当たりはDIV2と同様、easyを確実に取るのを目標にしつつアリ本などで勉強、過去問やる方針。

easy:
立方体の塗り分け。
複数の色が与えられてそれらで立方体を塗り分けることが出来るか否かを返す。
隣接する面は同じ色で塗っちゃダメ。つまり向かい合う面を同じ色で塗れたら必要な色数を1つ減らせる。
けど当然3色より小さな色数で塗り分けるのはムリなので一応弾いておく。

実装も単純で、与えられた色をどんどんMapに放りこんで(それぞれの数も大事なのでMap)、2つ以上見つかった
色の数を使って塗り分けに必要な色数を減らす。最後に、必要な色数<=見つかった色数かどうかを判定して返す。

import java.util.HashMap;

public class CubeStickers {

    public String isPossible(String[] sticker) {
        HashMap<String, Integer> mapping = new HashMap<String, Integer>();
        for (String target : sticker) {
            mapping.put(target, mapping.containsKey(target) ? (mapping.get(target) + 1) : 1);
        }
        int colorsNeeded = 6;
        for (int cnt : mapping.values()) {
            if (2 <= cnt) {
                colorsNeeded--;
            }
            if (colorsNeeded == 3) {
                break;
            }
        }
        return colorsNeeded <= mapping.size() ? "YES" : "NO";
    }
}

medium: 指定された立方体群(片方は1x1x1、もう片方はLxLxL)を敷き詰めるのに必要な直方体の最小体積を求める。 立てた方針は 1.Nb個の各辺Lな立方体を詰め込むのに最小限必要な領域(領域1)を調べる 2.前述の領域にNs個の各辺1な立方体を、領域1の空き空間に詰め込む→埋めきったらここで終了 3.Nb個の立方体とNs個の立方体の体積を一緒くたにして立方体にしてみる→埋められたらここで終了 4.(2)で埋めて残った分を、面積が最小となる方向に辺を伸ばすのに使って直方体つくる →終了 どのように組めば体積が最小となると言えるのか、をちゃんと検討する余裕が無かったのでこう適当な感じ。 立方体作ってちょいちょい拡張すればいいんじゃないかとなんとなく浮かんだ策で進めてみたけど 案の定うまくいかない。 なかなかやけっぱちなコードである。

public class CubePacking {

    public int getMinimumVolume(int Ns, int Nb, int L) {
        int x, y, z;
        int startSize = (int)Math.floor(Math.pow(Nb, 1.0 / 3.0));
        System.out.println("start=" + startSize);
        x = y = z = startSize;
        int bRemain = (int)(Nb - Math.pow(startSize, 3));
        System.out.println("bre=" + bRemain);
        while (0 < bRemain) {
            int px = y * z;
            int py = z * x;
            int pz = x * y;
            if (px <= py && px <= pz) {
                x++;
                bRemain -= y * z;
            }
            else if (py <= px && py <= pz) {
                y++;
                bRemain -= z * x;
            }
            else if (pz <= px && pz <= py) {
                z++;
                bRemain -= x * y;
            }
        }
        System.out.println("x=" + x + ", y=" + y + ", z=" + z);
        // fill vacant area first
        int sRemain = Ns + bRemain * (L * L * L);
        if (sRemain <= 0) {
            System.out.println("----");
            return x * y * z * L * L * L;
        }
        int sPointSize = (int)Math.floor(Math.pow(Ns + Nb * L * L * L, 1.0 / 3.0));
        int tx = x * L;
        int ty = y * L;
        int tz = z * L;
        sRemain -= sPointSize * sPointSize * sPointSize - (tx * ty * tz);
        if (sRemain <= 0) {
            System.out.println("----");
            return sPointSize * sPointSize * sPointSize;
        }
        System.out.println("point size=" + sPointSize);
        tx = ty = tz = sPointSize;
        while (0 < sRemain) {
            int px = ty * tz;
            int py = tz * tx;
            int pz = tx * ty;
            if (px <= py && px <= pz) {
                tx++;
                sRemain -= ty * tz;
            }
            else if (py <= px && py <= pz) {
                ty++;
                sRemain -= tz * tx;
            }
            else if (pz <= px && pz <= py) {
                tz++;
                sRemain -= tx * ty;
            }
        }
        System.out.println("tx=" + tx + ", ty=" + ty + ", tz=" + tz);
        System.out.println("----");
        return tx * ty * tz;
    }

}

hard:
開いてない

SRM 406 DIV1 easy

過去問の記録を書いていったら多少成長するかなとか。

今日やったのはこれ。
http://www.topcoder.com/stat?c=problem_statement&pm=8784&rd=12178

まず、ワンコは全然関係無いのでスルー。ある数値群で50を作れるのがポイントかなーとか思ったけど順列の組み合わせはたかだか5万程度(8要素しか無いから)なので全部ナイーブに見ちゃえ。

import java.util.Arrays;
import java.util.Enumeration;
import java.util.HashSet;
import java.util.Iterator;


public class SymmetricPie {
    public class Permutation implements Iterable<int[]> {
        private final int size;

        /**
         * <p>順列を表すクラスのコンストラクタ。反復子が返す配列の要素数を指定する。
         * @param size 順列の要素数（10程度が妥当な最大値）
         * @throws IllegalArgumentException 引数（順列の要素数）が0以下の場合
         */
        public Permutation(int size) {
            if (size <= 0) throw new IllegalArgumentException();
            this.size = size;
        }

        public Iterator<int[]> iterator() {
            return new Iter(size);
        }

        private class Iter implements Iterator<int[]> {
            private final int[] source;
            private boolean isFirst = true;

            private Iter(int size) {
                source = new int[size];
                for(int i = 0; i < size; ++i) {
                    source[i] = i;
                }
            }

            /**
             * <p>反復子がまだ順列を返しうるか調べる。
             * 本メソッドは{@link Iter#next()}呼び出し前に必ず1回ずつ実行する必要がある。
             * @return 順列が存在する場合はtrue
             */
            public boolean hasNext() {
                if (isFirst) {
                    isFirst = false;
                    return true;
                }

                int n = source.length;
                for (int i = n - 1; i > 0; i--) {
                    if (source[i - 1] < source[i]) {
                        int j = n;
                        while (source[i - 1] >= source[--j]);
                        swap(source, i - 1, j);
                        reverse(source, i, n);
                        return true;
                    }
                }
                reverse(source, 0, n);
                return false;
            }

            /**
             * <p>次の順列を表すint型配列を返す。
             * <p>このメソッドが返す参照は常に同じ配列に対する参照である。
             * このため配列の要素を変更したり次回の{@link Iter#next()}呼び出し後も参照する場合は、
             * クラスの呼び出し側が配列のクローンを生成して利用する必要がある。
             * @return 順列を表すint型配列
             */
            public int[] next() {
                return source;
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }

            private void swap(int[] is, int i, int j) {
                int t = is[i];
                is[i] = is[j];
                is[j] = t;
            }

            private void reverse(int[] is, int s, int t) {
                while (s < --t) swap(is, s++, t);
            }
        }
    }

    public int getLines(int[] dogs) {
        int cnt = dogs.length;
        int maxLines = 0;
        Permutation permutations = new Permutation(cnt);
        int[] combi = new int[cnt];
        int l = 0;
        for (int[] permutation : permutations) {
            for (int k = 0; k < permutation.length; k++) {
                combi[k] = dogs[permutation[k]];
            }
            HashSet<Integer> combiSet = new HashSet<Integer>();
            int total = 0;
            int lines = 0;
            for (int j = 0; j < cnt; j++) {
                total += combi[j];
                if (total == 100) {
                    break;
                }
                if (total == 50) {
                    lines++;
                }
                if (combiSet.contains(total - 50)) {
                    lines++;
                }
                combiSet.add(total);
            }
            
            if (maxLines < lines) {
                maxLines = lines;
            }
            l++;
        }
        return maxLines;
    }

}

==
permutationsのロジックを思いつかずにハマった。ちゃんと身につけるToDo行き。

今回は http://topcoder.g.hatena.ne.jp/eller/20090831/1251723649 の「IterableなJava版next_permutation」を使わせてもらいました。