【AtCoder 反省会】AtCoder Beginner Contest 424

コンテストサイト
前回の結果

今回の結果

A,B 正答
C問題が、簡単と思いきや難しかった。

A

最初 cnt >= 2 だと勘違いしていた。
cnt >= 1 に変えてACしたが、よく考えると (a==b)||(b==c)||(c==a) でよかった。

static void impl()
{
    int a, b, c;
    cin >> a >> b >> c;

    int cnt = 0;
    if (a == b)
        cnt++;
    if (b == c)
        cnt++;
    if (c == a)
        cnt++;

    if (cnt >= 1)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

B

解説通りの模範回答だった。
自分でもよく書けたと思う。

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

    // Q人の人、それぞれの正解数 (max : M)
    vec<int> Q(N, 0);

    vec<int> finished;
    finished.reserve(N);

    while (K--)
    {
        int A, B;
        cin >> A >> B;

        if (++Q[A - 1] >= M)
        {
            finished.push_back(A);
        }
    }

    for (int i : finished)
    {
        out << i << ' ';
    }
}

C (最終結果 不正解)

なぜか通らないな〜、と思っていると、質問のところで
「スキルは好きな順序で習得することができます。」
という回答があった。えッ、それは話が変わってくるのでは…？？

↓↓ 不正解のコード

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

    int cnt = 0;

    // 1-indexed
    // 習得済みスキル
    vec<bool> acquired(N + 1, false);

    // 入力メモ
    vec<int> A(N + 1);
    vec<int> B(N + 1);
    FOR1(i, N)
    {
        int a, b;
        cin >> a >> b;
        A[i] = a;
        B[i] = b;

        if (a == 0 && b == 0)
        {
            acquired[i] = true;
            ++cnt;
        }
    }

    // 新規取得
    FOR1(i, N)
    {
        if (acquired[i])
            continue;

        int a = A[i];
        int b = B[i];

        if (acquired[a] ^ acquired[b])
        {
            acquired[i] = true;
            ++cnt;
        }
    }

    out << cnt << endl;
}

試行錯誤

結局回答は諦めたが、「こうすればいいのか？」と考えていた方針は合っていた。
（具体的には、遷移グラフを構築してのBFS/DFS。）
ただ、自分で書けるかは別の話で、結局のところ書けなかった。
まあ最近はAIもあるので、方針立てが出来るならひとまず及第点か？

D （最終結果 実行時間超過）

実験の結果、2x2の黒ブロックに分割する時、その最大値を求めれば良い 気がした。
説明とかは出来ないが、不正解にはならなかったので、考え方は合っているっぽい。
ただ、どうしても実行時間を短縮することが出来ず、敢えなく撃沈。

解説がムズかった。

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

    while (T--)
    {
        int H, W;
        cin >> H >> W;

        int black_count = 0;

        vec<str> grid(H);
        for (str &g : grid)
        {
            cin >> g;

            for (char c : g)
            {
                if (c == '#')
                    black_count++;
            }
        }

        // 2x2の黒ブロックに分割する時、その最大値を求めれば良い

        // 2x2の組み合わせを全列挙
        vec<arr<pr<int, int>, 4>> blocks;
        blocks.reserve(H * W);
        FOR(y, H - 1)
        FOR(x, W - 1)
        {
            if (grid[y][x] == '.' || grid[y][x + 1] == '.' || grid[y + 1][x] == '.' || grid[y + 1][x + 1] == '.')
                continue;

            arr<pr<int, int>, 4> block =
                {
                    make_pair(y, x),
                    make_pair(y, x + 1),
                    make_pair(y + 1, x),
                    make_pair(y + 1, x + 1),
                };
            blocks.push_back(block);
        }

        int max_cnt = -1;

        sort(all(blocks));
        do
        {
            // ブロックの取り出し方を全列挙

            vec<str> grid_copy = grid;
            int cnt = 0;
            for (const arr<pr<int, int>, 4> &block : blocks)
            {
                bool can_take = true;
                for (const pr<int, int> &p : block)
                {
                    if (grid_copy[p.first][p.second] == '.')
                    {
                        can_take = false;
                        break;
                    }
                }
                if (can_take)
                {
                    cnt++;
                    for (const pr<int, int> &p : block)
                    {
                        grid_copy[p.first][p.second] = '.';
                    }
                }
            }

            max_cnt = max(max_cnt, cnt);

        } while (next_permutation(all(blocks)));

        out << max_cnt << "\n";
    }
}

E

この解説の方針 を採用したら、解けていたかも？

F

一瞬簡単かも、と思って作ってみたコード↓↓。
普通に間違いで、実行時間的にも論外。

static void impl()
{
    long N, Q;
    cin >> N >> Q;

    // 1-indexed
    // i個目の点が結線されたか
    vec<bool> used(N + 1, false);

    while (Q--)
    {
        long A, B;
        cin >> A >> B;

        if (A > B)
            swap(A, B);

        // A < B

        bool can = true;
        for (long i = A + 1; i != B; ++i)
            if (used[i])
            {
                can = false;
                break;
            }

        if (can)
        {
            out << "Yes\n";
            used[A] = true;
            used[B] = true;
            continue;
        }
        else
        {
            can = true;
            for (long i = B /* B+1 */; i != A; i = (i + 1) % N)
            {
                if (used[i])
                {
                    can = false;
                    break;
                }
            }

            if (can)
            {
                out << "Yes\n";
                used[A] = true;
                used[B] = true;
                continue;
            }
            else
            {
                out << "No\n";
                continue;
            }
        }
    }
}

G

なるほど、動的計画法を使うんですね〜、という感想。

総括

今回はC問題から難しかった。（というより、問題文が分かりにくかった。）
配列を 1-indexed にしてみて使い勝手が良かったので、次回からも採用しようと思う。
次回も頑張ろう！