【AtCoder 反省会】AtCoder Beginner Contest 422

今回の成績

A,B,C 正答

A問題

自分の回答

static void impl()
{
    str input;
    cin >> input;

    str s0 = input.substr(0, 1);
    str s2 = input.substr(2, 1);
    int i = stoi(s0);
    int j = stoi(s2);

    int next_i = 0;
    int next_j = 0;

    if (j == 8)
    {
        next_i = i + 1;
        next_j = 1;
    }
    else
    {
        next_i = i;
        next_j = j + 1;
    }

    cout << next_i << "-" << next_j << endl;
}

振り返り

無事一発正解。
「4-3」みたいな入力値から整数に変換するところで、若干詰まった。
今回はscanfの方を使えば良かった。

int i, j;
scanf("%d-%d", &i, &j);

B問題

自分の回答

static void impl()
{
    const vec<pair<int, int>> d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    int H, W;
    cin >> H >> W;
    vec<str> S(H);
    FOR(i, H)
    cin >> S[i];

    for (int i = 1; i <= H; ++i)
    {
        for (int j = 1; j <= W; ++j)
        {
            if (S[i - 1][j - 1] == '.')
                continue;

            int cnt = 0;
            for (const auto &p : d)
            {
                int ni = i + p.first;
                int nj = j + p.second;
                if (ni < 1 || ni > H || nj < 1 || nj > W)
                    continue;
                if (S[ni - 1][nj - 1] == '#')
                    ++cnt;
            }

            if (!(cnt == 2 || cnt == 4))
            {
                cout << "No" << endl;
                return;
            }
        }
    }
    cout << "Yes" << endl;
}

振り返り

無事一発正解。
盤のサイズが小さいので、愚直な全探索で上手くいった。
解説にあった番兵 (sentinel)がいいアイディアだった。一回り大きい白塗りエリアを用意すれば、範囲外チェックをしなくて良い、という感じ。

C問題

簡単かと思いきや、結構沼ってしまった。

沼っていた時の自分の回答

static void impl()
{
    ull T;
    cin >> T;
    while (T--)
    {
        ull a, b, c;
        cin >> a >> b >> c;

        // 最大でも、これが限界
        ull max_amount = min(a, c);
        // 残りは全てbにあげる
        b += (a - max_amount);
        b += (c - max_amount);

        cout << min(max_amount, b) << "\n";
    }
}

間違っていたところ

色々入力値を変えて試して、次のようなケースで上手くいかないことが分かった。
具体的には、「Bが最小 かつ A+C-B >= 3」の場合。
A,Cのみで構築する分が、正しく計算できていなかった。

14 5 14
自分のコードの出力：5
正しい　　　　出力：11

最終回答(正答)

このコードで正答。
解説ではもう少し洗練されたコードだった。

static void impl()
{
    int T;
    cin >> T;

    FOR(i, T)
    {
        int a, b, c;
        cin >> a >> b >> c;

        // 最低保証
        int min_amount = min({a, b, c});
        a -= min_amount;
        b -= min_amount;
        c -= min_amount;

        // a,cのみで構築する分
        int additional_amount = 0;
        if (b == 0)
        {
            additional_amount = (a + c) / 3;
            additional_amount = min({additional_amount, a, c});
        }

        cout << min_amount + additional_amount << "\n";
    }
}

D問題

A,B,C問題が終わり、残り20分ほど。
D問題に狙いを定める。

自分の回答(正答ではない)

static void impl()
{
    int N, K;
    cin >> N >> K;

    int len = (1 << N);
    int base = K / len; // 各項の最小値
    int left = K % len; // 追加で分配するべき個数

    while (left >= len)
    {
        base++;
        left -= len;
    }

    vec<int> A(len, base);

    // leftを分配
    if (left > 1)
    {
        int sep = (len - left) / (left - 1); // 分配しない間隔
        for (int i = 0; i < len; i += (sep + 1))
        {
            A[i]++;
        }
    }
    else if (left == 1)
    {
        A[0]++;
    }
    else
    {
        cout << 0 << "\n";
        FOR(i, len)
        {
            cout << base << " ";
        }
        cout << "\n";
        return;
    }

    cout << 1 << "\n";
    for (const int a : A)
    {
        cout << a << " ";
    }
    cout << "\n";
}

振り返り

出力するX(アンバランスさ)の値が0または1しかあり得ない、という点はあっていた。
ただし、1の場合に、端数を数列の各項にどう分配するか、が出来なかった。
解説のアルゴリズム（数列Aを圧縮する手順を逆順に再現）はやっぱりスマートで、言われればなるほどな、という感じ。
sounansyaさんの解説がシンプルすぎてビビった。

E問題

確率的に試行するというのが、目から鱗。
素数判定で使われるヤツと似ていると思う。

F問題

ダイクストラ法を使うのかな〜、ということだけ分かった。
いつか解けるようになりたい。

G問題

無理。

まとめ

それなりに解けて満足。
次回も頑張ろう！