Codeforces 50A - A. Domino piling

50A - A. Domino piling

M x N サイズのボードに 2 x 1 サイズのドミノを出来るだけ沢山敷き詰める問題。ボードに配置可能なドミノの個数を出力する。

制約:
1 <= M, N <= 16

ボードのサイズが偶数であれば、隙間なくドミノを敷き詰められます。なので、まず偶数サイズのボードに隙間なくドミノを敷き詰めます。もしボードのサイズが奇数であれば、その残りの 1 行にドミノを敷き詰めていきます。

下の図は、5 x 5 サイズのボードです。赤線で囲ったのが偶数サイズのボードです。

calc :: Int -> Int -> Int
calc w h = (w' * h' `div` 2) + a + b
  where
    w' = w - (w `mod` 2)
    h' = h - (h `mod` 2)
    a  = if w /= w' then h' `div` 2 else 0
    b  = if h /= h' then w' `div` 2 else 0

main = do s <- getLine
          let [w, h] = map read $ words s :: [Int]
          print $ calc w h

もっと短く書けそうな気もしますが…。

上の図はProcessingで書きました。以下がそのコードです。

// -*- mode: Java -*-

final int SIZE = 40; // rectのサイズ

void setup() {
    size(600, 600);
}

void draw() {
    background(255);
    stroke(0);
    strokeWeight(1);
    
    final int x = 100, y = 100;
    final int rows = 5, cols = 5;
    // ボード描画
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if ((i+j) % 2 == 0) noFill(); else fill(0);
            rect(x+j*SIZE, y+i*SIZE, SIZE, SIZE);
        }
    }

    stroke(255, 0, 0);
    strokeWeight(3);
    noFill();
    rect(x, y, 4*SIZE, 4*SIZE);

    // ドミノ描画
    noStroke();
    fill(183, 177, 177);
    for (int i = 0; i < rows-1; i += 2) {
        for (int j = 0; j < cols-1; j++) {
            rect(x+10+j*SIZE, y+10+i*SIZE, SIZE-20, SIZE*2-20);
        }
    }

    fill(102, 224, 247);
    rect(x+10+4*SIZE, y+10+0*SIZE, SIZE-20, SIZE*2-20);
    rect(x+10+4*SIZE, y+10+2*SIZE, SIZE-20, SIZE*2-20);
    rect(x+10+0*SIZE, y+10+4*SIZE, SIZE*2-20, SIZE-20);
    rect(x+10+2*SIZE, y+10+4*SIZE, SIZE*2-20, SIZE-20);
}