今回のコンテストはいかがでしたでしょうか。平均的な ARC と比べ、相当チャレンジングな問題セットだったと思いますが、楽しんでいただけたのであれば嬉しいです。それでは解説を始めていきたいと思います。

初心者の方へ

• プログラミングを始めたばかりで何から手を付ければよいか分からない方は、まずは practice contest の問題 A「Welcome to AtCoder」をお試しください。
• また、プログラミングのコンテストに慣れていない方は AtCoder Beginners Selection の問題をいくつか試すことをおすすめします。

初級者 (AtCoder Rating 400 未満) の方へ

• 今回は特に難しい問題でしたが、一般的に AtCoder Regular Contest (ARC) の問題は AtCoder Beginner Contest (ABC) より大幅に難易度が高いです。
• ARC が難しいと感じた方は、ABC に参加したり、ABC の過去問を解いたりすることもおすすめです。
• 過去問演習は AtCoder Problems などのウェブサイトが便利ですので、ぜひご活用ください。

---

ステップ 1

まずは持っている板チョコの大きさが \(7 \times 11\) の場合について、以下の \(3\) つの具体例を考えてみましょう。

• \(1 \times 1\) を \(28\) 個、\(2 \times 2\) を \(5\) 個、\(4\times 4\) を \(2\) 個渡す
• \(1 \times 1\) を \(10\) 個、\(2 \times 2\) を \(8\) 個、\(4\times 4\) を \(2\) 個渡す
• \(1 \times 1\) を \(10\) 個、\(2 \times 2\) を \(1\) 個、\(4\times 4\) を \(3\) 個渡す

具体例 1 の答え

この例では、全員に板チョコを渡すことができません。なぜなら、渡すべき板チョコの合計面積が \(80\) であり、持っている板チョコの面積 \(7 \times 11 = 77\) を超えてしまうからです。

具体例 2 の答え

この例でも、全員に板チョコを渡すことができません。なぜなら、渡すべき \(2 \times 2\) 以上の板チョコの合計面積が \(64\) となり、\(60\) を超えてしまうからです。ここで、面積が \(60\) を超えるとダメな理由を説明します。

• まず、\(2 \times 2\) の板チョコは下図のように最大 \(15\) 枚しか渡すことができません。
• したがって、\(2 \times 2\) の板チョコを面積 \(60\) を超えて渡すことはできません。
• また、\(2 \times 2\) 以上の板チョコを合計面積 \(x\) 渡すことは、\(2 \times 2\) の板チョコを面積 \(x\) 渡すことより難しいです。
• したがって、\(2 \times 2\) 以上の板チョコを合計面積 \(60\) を超えて渡すことはできません。

なお、\(2 \times 2\) の板チョコを \(15\) 枚しか渡せない理由の証明は、解説の最後に記されています。今の段階では、直感的に正しいと思っておいてください。

具体例 3 の答え

この例でも、全員に板チョコを渡すことができません。なぜなら、\(4 \times 4\) の板チョコは下図のように \(2\) 個しか渡すことができないからです。

ステップ 2

さて、ここまでの具体例で、答えが No となる条件として以下の \(3\) つが挙げられました。(\(3\) つ目の条件は、後々処理しやすいように面積の形に直しています)

• \(1 \times 1\) 以上の板チョコの合計面積が \(77\) を超える
• \(2 \times 2\) 以上の板チョコの合計面積が \(60\) を超える
• \(4 \times 4\) 以上の板チョコの合計面積が \(32\) を超える

それでは、これらの \(3\) 条件をすべて満たさない場合、絶対に答えが Yes になるのでしょうか。実は正しいです。この理由は次のように説明できます。

解説を見る

以下の手順で板チョコを渡していくと、必ずすべての板チョコを渡すことができます。

• 左上の \(4 \times 8\) の範囲に収まるように、左上から順に必要分の \(4 \times 4\) の板チョコを取り出す
• 左上の \(6 \times 10\) の範囲に収まるように、左上から順に必要分の \(2 \times 2\) の板チョコを取り出す
• 左上の \(7 \times 11\) の範囲に収まるように、左上から順に必要分の \(1 \times 1\) の板チョコを取り出す

たとえば \(1 \times 1\) を \(20\) 個、\(2 \times 2\) を \(10\) 個、\(4 \times 4\) を \(1\) 個渡さなければならない場合、手順は下図のようになります。

ステップ 3

最後に、ここまでの考察を板チョコの大きさが \(7 \times 11\) 以外の場合にも一般化してみましょう。まず、以下の条件を満たす場合、絶対に答えは No です。(\(\lfloor x \rfloor\) は \(x\) の小数点以下切り捨てを意味します)

• \(1 \times 1\) 以上の板チョコの合計面積が \(H \times W\) を超える
• \(2 \times 2\) 以上の板チョコの合計面積が \(\lfloor H/2 \rfloor \times \lfloor W/2 \rfloor \times 2^2\) を超える
• \(4 \times 4\) 以上の板チョコの合計面積が \(\lfloor H/4 \rfloor \times \lfloor W/4 \rfloor \times 4^2\) を超える
• \(8 \times 8\) 以上の板チョコの合計面積が \(\lfloor H/8 \rfloor \times \lfloor W/8 \rfloor \times 8^2\) を超える
• \(16 \times 16\)、\(32 \times 32\)…、についても同様

また、ステップ 2 と同様、上記の条件をすべて満たさない場合は絶対に答えが Yes になります。したがって、以下の実装例のように合計面積を計算するプログラムを実装すると、AC となります。

なお、本問題の制約下では合計面積が \(10^{18}\) 程度になることもあるため、int 型などの \(32\) ビット整数を使うとオーバーフローを起こしてしまいます。long long 型などの \(64\) ビット整数を使わなければ正解とならないのでご注意ください。

---

実装例 (C++)

#include <iostream>
using namespace std;

long long H;
long long W;
long long N;
long long A[1009];

// 大きさ (2 の r 乗) * (2 の r 乗) 以上の渡すべきチョコの合計面積を返す関数
long long TotalArea(long long r) {
	long long Area = 0;
	for (int i = 1; i <= N; i++) {
		if (A[i] >= r) {
			// 2 の A[i] 乗は (1LL << A[i]) で計算できることに注意
			Area += (1LL << A[i]) * (1LL << A[i]);
		}
	}
	return Area;
}

// メイン関数
int main() {
	// Step 1. 入力
	cin >> H >> W >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}

	// Step 2. 大きさ 1, 2, 4, ..., (2 の 25 乗) について、条件を満たしているかをチェック
	// 2 の r 乗は (1LL << r) で計算できることに注意
	for (int r = 0; r <= 25; r++) {
		long long LimitH = (H / (1LL << r)); // (H / (2 の r 乗)) の切り捨て
		long long LimitW = (W / (1LL << r)); // (W / (2 の r 乗)) の切り捨て
		long long LimitArea = LimitH * LimitW * (1LL << r) * (1LL << r); // 面積の上限

		// 渡すべき合計面積と比較する
		long long ActualArea = TotalArea(r);

		// もし上限を超えていたら、答えは即 No
		if (ActualArea > LimitArea) {
			cout << "No" << endl;
			return 0;
		}
	}

	// Step 3. もし全条件を満たせば Yes を出力
	cout << "Yes" << endl;
	return 0;
}

実装例 (Python)

import sys

# 大きさ (2 の r 乗) * (2 の r 乗) 以上の渡すべきチョコの合計面積を返す関数
def TotalArea(H, W, N, A, r):
    Area = 0
    for i in A:
        if i >= r:
            Area += (2 ** i) * (2 ** i)
    return Area

# Step 1. 入力
H, W, N = map(int, input().split())
A = list(map(int, input().split()))

# Step 2. 大きさ 1, 2, 4, ..., (2 の 25 乗) について、条件を満たしているかをチェック
for r in range(0, 26):
    LimitH = H // (2 ** r) # H / (2 の r 乗) の切り捨て
    LimitW = W // (2 ** r) # W / (2 の r 乗) の切り捨て
    LimitArea = LimitH * LimitW * (2 ** r) * (2 ** r) # 面積の上限

    # 渡すべき合計面積と比較する
    ActualArea = TotalArea(H, W, N, A, r)

    # もし上限を超えていたら、答えは即 No
    if ActualArea > LimitArea:
        print("No")
        sys.exit(0)

# Step 3. もし全条件を満たせば Yes を出力
print("Yes")

---

補足：ステップ 1 の証明

ステップ 1 の解説では、\(7 \times 11\) の板チョコを持っているとき \(2 \times 2\) の板チョコを \(15\) 枚しか取り出せないことを「直感的に正しい」と説明していました。しかし、一体どうやって証明できるのでしょうか。

• まず、下図のように上から \(2\) の倍数行目・左から \(2\) の倍数列目を赤く塗ることを考えます。
• このとき、赤いマスは全部で \(3 \times 5 = 15\) 個あります。
• しかし \(2 \times 2\) の板チョコは赤いマスを絶対に \(1\) つ含むため、最大でも \(15\) 枚しか取り出せません。

なお、同様に考えると、\(H \times W\) の板チョコから \(L \times L\) の板チョコを最大 \(\lfloor H/L \rfloor \times \lfloor W/L \rfloor\) 枚しか取り出せないことも証明できます。