矮小

井の中の蛙

CODE THANKS FESTIVAL 2014 B日程 D,E問題

D 足ゲーム

矢印が判定エァリアに重なるタァーイミングでパァーノゥを踏むゲェーイム.パーノゥはN枚あってプレイ時間はT秒.i個目のパーノゥにはA_i秒間隔で矢印が降ってくる.パーノゥ1枚につき足を1本割り当てた時,最大で同時に何本の足が必要になるかを求める.以上,問題設定の拡大解釈版でした.

解法:最も多い公倍数が出現する頻度を答える

import std.stdio;
import std.algorithm;
import std.range;
import std.string;
import std.conv;
import std.numeric;

void main() {
    int n, t;
    readf("%d %d\n", &n, &t);
    int[] a;
    for (int i = 0; i < n; i++) {
        a ~= readln.chomp.to!int;
    }

    int[] ldcary;
    foreach (e; a) {
        for (int i = 1; ; i++) {
            if (e * i > t)
                break;
            ldcary ~= e * i;
        }
    }

    auto countary = ldcary.sort.group;
    int maxcount = 0;
    foreach (tup; countary) {
        maxcount = max(tup[1], maxcount);
    }

    maxcount.writeln;
}

int ldc(int a, int b) {
    return a * b / gcd(a, b);
}

各パネルの公倍数を持った配列を作ってその中で最も多い頻度のものをカウントして出力,という流れにしたけどちょっとストレートにやりすぎてごちゃごちゃになってしまった.逆に,サイズがT+1の配列を作って,インデックスが倍数の時にインクリメントして,その配列の中で一番大きい値を出力するというのが想定解だったっぽい.いま想定解で提出したら30msでした.はい.想定解は以下の通り.

import std.stdio;
import std.algorithm;
import std.range;
import std.string;
import std.conv;

void main() {
    int n, t;
    readf("%d %d\n", &n, &t);

    int[] a;
    for (int i = 0; i < n; i++) {
        a ~= readln.chomp.to!int;
    }

    int[] countary = new int[t + 1];
    foreach (e; a) {
        for (int i = 1; i <= t / e ; i++) {
            countary[e * i]++;
        }
    }

    countary.minPos!("a > b")[0].writeln;
}

~=は配列に要素を追加する演算子.ついでに~で配列同士を結合できます.

E マスゲーム

盤面上の黒いグリッドだけを通ってスタートからゴールまで行けるかどうかを確かめる.

解法:僕は(たぶん)幅優先探索で解きました.

import std.stdio;
import std.algorithm;
import std.range;
import std.string;
import std.conv;

void main() {
    int r, c;
    readf("%d %d\n", &r, &c);

    bool[][] field;
    for (int i = 0; i <= r + 1; i++) {
        bool[] f;
        for (int j = 0; j <= c + 1; j++) {
            f ~= false;
        }
        field ~= f;
    }

    bool[][] checked;
    for (int i = 0; i <= r + 1; i++) {
        bool[] f;
        for (int j = 0; j <= c + 1; j++) {
            f ~= false;
        }
        checked ~= f;
    }

    int rs, cs;
    readf("%d %d\n", &rs, &cs);
    int rg, cg;
    readf("%d %d\n", &rg, &cg);
    int n = readln.chomp.to!int;
    for (int i = 0; i < n; i++) {
        int ri, ci, hi, wi;
        readf("%d %d %d %d\n", &ri, &ci, &hi, &wi);
        for (int j = ri; j < ri + hi; j++) {
            for (int k = ci; k < ci + wi; k++) {
                field[j][k] = true;
            }
        }
    }

    bool result = false;
    int[][] queue;
    queue ~= [rs, cs];
    while (!queue.empty) {
        int[] current = queue[0];
        queue.popFront;
        int r_cur = current[0];
        int c_cur = current[1];

        // 黒い
        if (field[r_cur][c_cur]) {
            // ゴール
            if (r_cur == rg && c_cur == cg) {
                result = true;
                break;
            }

            if (checked[r_cur][c_cur])
                continue;
            // チェックを付ける
            checked[r_cur][c_cur] = true;
            if (field[r_cur - 1][c_cur])
                queue ~= [r_cur - 1, c_cur];
            if (field[r_cur + 1][c_cur])
                queue ~= [r_cur + 1, c_cur];
            if (field[r_cur][c_cur - 1])
                queue ~= [r_cur, c_cur - 1];
            if (field[r_cur][c_cur + 1])
                queue ~= [r_cur, c_cur + 1];
        }
    }

    writeln(result ? "YES" : "NO");
}

そもそもスタートとゴールが白いマスである可能性に気をつける必要がある.ということで出だしから黒いマスのみを対象に処理することにした.というか黒いマスだけ処理するならエンキューする時にわざわざ黒いかどうかチェックする必要はないじゃないかと今更思ったので変更して提出したらちょっと速くなった.↑が45ms,↓が38msでした.

import std.stdio;
import std.algorithm;
import std.range;
import std.string;
import std.conv;

void main() {
    int r, c;
    readf("%d %d\n", &r, &c);

    bool[][] field = new bool[][](r + 2, c + 2);
    bool[][] checked = new bool[][](r + 2, c + 2);

    int rs, cs;
    readf("%d %d\n", &rs, &cs);
    int rg, cg;
    readf("%d %d\n", &rg, &cg);
    int n = readln.chomp.to!int;
    for (int i = 0; i < n; i++) {
        int ri, ci, hi, wi;
        readf("%d %d %d %d\n", &ri, &ci, &hi, &wi);
        for (int j = ri; j < ri + hi; j++) {
            for (int k = ci; k < ci + wi; k++) {
                field[j][k] = true;
            }
        }
    }

    bool result = false;
    int[][] queue;
    queue ~= [rs, cs];
    while (!queue.empty) {
        int[] current = queue[0];
        queue.popFront;
        int r_cur = current[0];
        int c_cur = current[1];

        // 黒い
        if (field[r_cur][c_cur]) {
            // ゴール
            if (r_cur == rg && c_cur == cg) {
                result = true;
                break;
            }

            if (checked[r_cur][c_cur])
                continue;
            // チェックを付ける
            checked[r_cur][c_cur] = true;

            // 周りのマスをキューに追加
            queue ~= [r_cur - 1, c_cur];
            queue ~= [r_cur + 1, c_cur];
            queue ~= [r_cur, c_cur - 1];
            queue ~= [r_cur, c_cur + 1];
        }
    }

    writeln(result ? "YES" : "NO");
}

D言語でキューとスタックの操作を実現するには~popFront()popBack()を使います(というか僕は使ってます).具体的にはエンキュー・プッシュが~,デキューがary[0]を取り出した後ary.popFront,ポップがary[$-1]を取り出した後ary.popBack(添字を書く場所では$はその配列の長さに変換される.n..mは[n,m)).何でこうしないといけないのかというとpopFrontpopBackも値を返してくれないvoid関数だからです.どうしてかは忘れた.確か公式サイトに書いてあった気がする.あとはstd.containerとかも使うのかもしれない.今やってみたら使えなかったのでよく分かりません.

ところでnew hoge[][](r + 2, c + 2)みたいにすれば実行時に配列の大きさを決められるというのをarukukaさんのコードを見て初めて知ったんだけどこれってどこで調べればいいんだろう…….