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」を使わせてもらいました。

bloggerに移動してきたよ

多分VALUE DOMAIN系(というかCore Servers)を有効に使うことはこの先無さそうだなぁと思い、移動しました。

コンテンツはかなり古くなったものばかりなので、一新しちゃいましょうっと。

--
古いコンテンツもある程度参照していただいてるようなので、見えるようにします。
旧サーバへのログイン方法を思い出すまでしばらくお待ちください。。
--
その後、http://www.muo.jp/android/ などでアクセスされた際には http://old.muo.jp/android/ などへリダイレクトするよう設定しました。比較的直接リンクされてる場合にはうまくいくと思います。