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:
開いてない