ABC204 Bでは、各木について10個を超えた分だけを計算し、その合計を求めます。 木ごとの値はほかの木の処理や後の選択を変えないため、各 Ai に max(Ai - 10, 0) を適用すれば解けます。問題の条件と公式の処理は、AtCoder公式の問題文と公式解説で確認できます。
この問題は、局所的な計算が独立している例です。依存する選択を含む問題一般で、貪欲法が正しいことを証明する例ではありません。どこまでなら同じ考え方を使えるかを、制約、追跡例、コード、境界の順に確認します。
ABC204 Bの条件は「各木の超過分を足す」
N 本の木があり、i 番目の木には Ai 個の木の実があります。1本の木から収穫できるのは、木の実が10個以下なら0個、10個より多ければ10個を残した Ai - 10 個です。したがって、木1本の寄与は max(Ai - 10, 0) と表せます。
| 項目 | 条件 |
|---|---|
木の本数 N | 1 ≤ N ≤ 1000 |
各木の実 Ai | 0 ≤ Ai ≤ 1000 |
| 入力 | 1行目に N、2行目に A1 ... AN |
| 出力 | 収穫できる木の実の合計 |
各木の寄与を決めるとき、別の木の値や処理順を参照しません。最初の木で何個収穫したかによって、次の木で収穫できる個数が変わる規則もありません。この独立性があるので、木を1本ずつ見て合計できます。
公式サンプルで0、7、18を足す
公式問題文のサンプル1は、次の入力です。
3
6 17 286 は10以下なので寄与が0、17 は10個を残して 17 - 10 = 7、28 は 28 - 10 = 18 です。合計は 0 + 7 + 18 = 25 になります。
25このサンプルでも、最大の木から処理する、順番を工夫する、といった選択は必要ありません。各値から決まる寄与を、そのまま足しています。
記事作成者による追跡例：[9, 10, 11, 14] は5
次の例は公式サンプルではありません。問題の規則から作った記事作成者による追跡例です。 各値へ max(Ai - 10, 0) を適用すると、記事作成者による追跡結果は [9, 10, 11, 14] → 5 になります。
| 順番 | Ai | その木の寄与 | 累積値 |
|---|---|---|---|
| 1 | 9 | 0 | 0 |
| 2 | 10 | 0 | 0 |
| 3 | 11 | 1 | 1 |
| 4 | 14 | 4 | 5 |
10 までは残す10個を超えないため0で、11 から初めて1個が収穫できます。最後の 14 からは4個を足し、累積値が5になります。どの行の計算も、ほかの行の結果を見て変える必要はありません。
Pythonコードを問題文の各条件へ対応させる
次のコードは、公式解説のPython例にある全木走査と条件分岐を使った、入力から出力までの完全な参考コードです。
N = int(input())
A = map(int, input().split())
ans = 0
for a in A:
if a > 10:
ans += a - 10
print(ans)行ごとの役割は次のとおりです。
N = int(input())で1行目の木の本数を読みます。問題文が2行目にN個の値を与えるため、ループの回数は入力に含まれる値の並びで決まります。A = map(int, input().split())で2行目の値を整数へ変換しながら反復できる形にします。値を別の計算結果へ置き換えるのではなく、各木の値を順に読みます。ans = 0で収穫合計の初期値を作ります。for a in Aは各木の値を1回ずつ取り出します。6、17、28のように、入力された順番で処理します。if a > 10のときだけ、a - 10をansに加えます。10以下の値では何も加えないため、寄与0の処理が条件分岐に対応します。print(ans)で全ての木の寄与を足した合計を出力します。
正しさ、O(N)時間、入力を含めたメモリの見方
各木について、a ≤ 10 なら問題文どおり収穫量は0なので加算しません。a > 10 なら残す10個を除いた a - 10 個を加算します。木ごとの収穫量が互いに独立しているため、全ての木でこの処理を行った ans が合計になります。
N 本の値を1回ずつ処理するので、時間計算量は O(N) です。A は map の反復子で、計算中に値を別の配列へ蓄積していません。そのため、入力を保持するバッファを除いたアルゴリズム上の追加メモリはO(1) と表現できます。
正確なコード A = map(int, input().split()) でも、input() が受け取る入力行自体は、N 個の値を含むため O(N) の長さです。さらに input().split() は O(N) 個のトークン文字列を作って保持します。したがって、入力行とトークン列を含めたピークの入力保持、および示した制約での実行時の総メモリは O(N) です。map は変換後の整数リストを追加で作らず、ループ状態と ans の作業領域は入力の保持を除けば O(1) ですが、トークン列をなくすわけではありません。A = list(map(...)) と書く場合も入力を整数リストとして保持するため、同じく O(N) です。
0、9、10、11とN=1を境界で確認する
| 値 | 寄与 | 理由 |
|---|---|---|
0 | 0 | 10以下 |
9 | 0 | 10以下 |
10 | 0 | 残す10個を超えない |
11 | 1 | 10個を残して1個 |
N = 1 なら、1本の寄与だけを計算して出力します。たとえば値が 11 なら結果は1です。公式制約に負の Ai はないため、負数を公式入力の境界ケースとして扱う必要はありません。
同じ値が複数あっても、それぞれに同じ計算を適用します。この問題では候補から1つを選ぶ場面がないため、同点の木をどちらから処理しても寄与は変わりません。
一般の貪欲法へ広げる前に確認する4点
ABC204 Bの公式問題文と解説が支えるのは、各木を確認し、条件に応じて超過分を足す処理です。そこから、依存する選択を含む問題一般の貪欲法まで正しいと結論づけることはできません。別の問題で「その場で最善そうな候補を選ぶ」方針を考えるときは、少なくとも次を確認します。
- 独立性と実行可能性：1つの局所的な選択が、別の要素の選択や、その後も選べる条件を変えないかを確認します。選択自体が問題の条件を満たしているかも分けて確かめます。ABC204 Bでは、木ごとの収穫量が他の木の処理に影響せず、各寄与を計算できます。
- 順番が将来の選択肢を変えないか：処理順を変えたとき、後から選べる候補や実行可能性が変わらないかを見ます。変わらないことを説明できるなら、順番に依存しない計算として整理できます。
- 同点と境界：同じ評価の候補があるとき、どれを選んでも結果が変わらないのかを確認します。条件が切り替わる値も、
10以下と10より大きい場合のように、等号を含めて手計算します。 - 局所規則の証明を止める境界：局所的な選択が後の選択肢や実行可能性を変え、全体の結果へつながる理由を説明できないなら、それを貪欲法と呼ぶのを止めます。DPや探索など別の手法を検討する段階です。この資料はABC204 B以外の解法比較を扱っていないため、特定の別問題の正解法までは断定しません。
ABC204 Bで書ける説明は、「各木の寄与が独立し、値の順序を変えても合計が変わらないので、全てを1回ずつ計算する」という範囲です。公式サンプルと記事作成者による追跡例、0・9・10・11の境界を自分のコードで確かめたうえで、同じ説明が別の問題にも成り立つかを、独立性・将来の選択肢・同点・境界から判断してください。
