ARC 172

Tue, Jul 1, 2025

A. Chocolate

https://atcoder.jp/contests/arc172/tasks/arc172_a

自力 AC. 解説と解き方が違うが多分問題ないと思う。

1辺が大きいピースから切り出していく。下図のうち 1 の部分が切り出す部分とする。切り出した後 2, 3, 4 の領域に分割する。分割した領域のうち、短辺が一番大きいものを取り出して次に大きいチョコのピースを切り出す。これを繰り返す。

┌─────────────────────┬─────────────────┐
│                     │                 │
│                     │                 │
│                     │                 │
│                     │                 │
│                     │                 │
│          1          │         2       │
│                     │                 │
│                     │                 │
│                     │                 │
│                     │                 │
├─────────────────────┼─────────────────┤
│                     │                 │
│                     │                 │
│          3          │         4       │
│                     │                 │
└─────────────────────┴─────────────────┘

2, 3 の境界と、3, 4 の境界は切ってもいい理由

全てのピースの大きさが2の冪なので大きいピース切り出していくと、境界をまたぐようなピースの置き方はできないので切っても問題ない。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W, N;
    cin >> H >> W >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    sort(rall(A));

    rep(i, N) {
        A[i] = 1 << A[i];
    }

    using P = tuple<ll, ll, ll>;
    priority_queue<P> pq;
    pq.push({min(H, W), H, W});

    int ok = 1;
    rep(i, N) {
        if (pq.size() == 0) {
            ok = 0;
            break;
        }
        auto [_, h, w] = pq.top();
        pq.pop();

        if (A[i] <= min(h, w)) {
            ll dw = w - A[i], dh = h - A[i];
            if (dw > 0) {
                pq.push({min(A[i], dw), A[i], dw});
            }
            if (dh > 0) {
                pq.push({min(dh, A[i]), dh, A[i]});
            }
            if (dw > 0 && dh > 0) {
                pq.push({min(dh, dw), dh, dw});
            }
        } else {
            ok = 0;
        }
    }

    yesno(ok);
}