AtCoder Beginner Contest 182のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo
目次
ABC182 まとめ
A問題『twiblr』
B問題『Almost GCD』
C問題『To 3』
ABC182 まとめ
全提出人数: 7497人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 37分 | 5814(5649)位 |
| 400 | ABC--- | 600 | 96分 | 4832(4668)位 |
| 600 | ABC--- | 600 | 44分 | 3991(3829)位 |
| 800 | ABCD-- | 1000 | 100分 | 3118(2956)位 |
| 1000 | ABCD-- | 1000 | 50分 | 2306(2144)位 |
| 1200 | ABCDE- | 1500 | 96分 | 1631(1475)位 |
| 1400 | ABCDE- | 1500 | 67分 | 1117(965)位 |
| 1600 | ABCDE- | 1500 | 50分 | 744(596)位 |
| 1800 | ABCDE- | 1500 | 37分 | 483(341)位 |
| 2000 | ABCDE- | 1500 | 27分 | 304(181)位 |
| 2200 | ABCDEF | 2100 | 97分 | 185(88)位 |
| 2400 | ABCDEF | 2100 | 80分 | 110(40)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 3040 | 99.1 % | 69.9 % | 42.3 % | 12.5 % | 2.9 % | 0.0 % |
| 茶 | 1461 | 99.5 % | 97.7 % | 87.7 % | 51.8 % | 12.7 % | 0.1 % |
| 緑 | 1122 | 99.5 % | 99.5 % | 97.2 % | 87.5 % | 50.7 % | 0.6 % |
| 水 | 692 | 100.0 % | 100.0 % | 98.8 % | 97.7 % | 86.6 % | 3.6 % |
| 青 | 357 | 100.0 % | 100.0 % | 99.2 % | 98.9 % | 97.2 % | 24.4 % |
| 黄 | 134 | 96.3 % | 96.3 % | 95.5 % | 96.3 % | 91.8 % | 59.7 % |
| 橙 | 27 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 77.8 % |
| 赤 | 7 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % |
※表示レート、灰に初参加者は含めず
簡易解説
- A問題 (7436人AC)『twiblr』
- 算数です。
- B問題 (6249人AC)『Almost GCD』
- $A_i$ は最大 $1000$ です。 $1000$ は $1001$ 以上の数では絶対に割り切れません。
$2$ ～ $1000$ がそれぞれいくつ割り切れるか実際に試して、最大の数字を出力すればいいです。 - C問題 (5077人AC)『To 3』
- $N$ は $10^{18}$ 未満です。つまり、最大 $18$ 桁しかありません。
桁の消し方は、 最大 $18$ 桁 それぞれについて、消すか消さないかの $2$ 通りあります。
$2^{18}$ 通り はだいたい $26$万 通りなので、すべての桁の消し方を試して、3の倍数になるか判定すればいいです。
いわゆる bit全探索 というアルゴリズムです。
全部消して $0$ にすることは許されていないので、その場合は $-1$ を出力することに注意してください。 - D問題 (3419人AC)『Wandering』[この記事では解説しません]
- 累積和を使います。紙に書いて考えるとわかるかもしれません。
- E問題 (1988人AC)『Akari』[この記事では解説しません]
- 最大 $50$ 万個の電球全部について、明かりが届くマスを調べていてはとても間に合いません。
「この先は既に照らされていることがわかりきっている」時点で打ち切れば、計算量が $O(HW+N+M)$ になって間に合います。 - F問題 (233人AC)『Valid payments』[この記事では解説しません]
- 動的計画法らしいです。
私（うにだよ）の結果（参考）
D問題をもうちょっと落ち着いて考えたほうがよかったと思います。
A問題『twiblr』
問題ページ：A - twiblr
灰コーダー正解率：99.1 %
茶コーダー正解率：99.5 %
緑コーダー正解率：99.5 %
考察
単純な算数ですが、勢いでペナルティをもらうともったいないので、少し立ち止まって確認するといいかもしれません。
コード
A, B = map(int, input().split())
print(2 * A + 100 - B)
B問題『Almost GCD』
問題ページ：B - Almost GCD
灰コーダー正解率：69.9 %
茶コーダー正解率：97.7 %
緑コーダー正解率：99.5 %
考察
ある正の整数 $K$ があるとします。$K$ は、$K$ よりも大きい数では絶対に割り切れません。例えば、 $6$ は $7$ 以上の数では絶対に割り切れません。
この問題の数列の最大値は $1000$ に設定されているので、$1001$ 以上の数は 与えられた数字を $1$ つも割り切れないことが確定しています。
答えの候補である$2$ から $1000$ まで、数列をいくつ割り切れるか全部試しても間に合います。
コード
N = int(input())
A = list(map(int, input().split()))
ans = 0
current_max = 0
for x in range(2, 1001):
score = 0 # 割り切れた数（GCD度）です
for a in A:
if a % x == 0:
score += 1
if score > current_max:
ans = x
current_max = score
print(ans)
C問題『To 3』
問題ページ：C - To 3
灰コーダー正解率：42.3 %
茶コーダー正解率：87.7 %
緑コーダー正解率：97.2 %
考察
数学的な考察が必要な問題に見えますが、実は 「ありえる桁の消し方を全探索して判定する」と工夫せずに解けます。
$N$ の制約は、$10^{18}$ 未満です。最大で $18$ 桁しかありません。各桁について、消すか消さないかの $2$ 通りあります。よって、桁の消し方は最大で $2^{18}$ 通りあります。$2^{18} = 262,144$ です。全部試しても間に合います。
（全部の桁を消す $1$ 通りは許されていないので、本当は $2^{18}-1=262,143$ ですが、簡単のため含めています）
実装
『使う・使わない』の2通りは『bit全探索』
この問題のような『使う・使わない』の $2$ 通りを全探索するときは、いわゆる『bit全探索』という方法を使います。
bit全探索の詳細は省きます。（本当は詳しく書きたいのですが、bit全探索が出るたびに詳しく書くのはつらいので、そのうちどこかにまとめるかもしれません）
pythonでは、bit全探索はitertoolsモジュールのproductを使うと楽です。
from itertools import product
product((True, False), repeat=l)
こう書くと、長さ $l$ で、各要素がTrueかFalseどちらでできる組み合わせがもれなく全て生成されます。
3の倍数の判定法
「数字を消したあとくっつけて整数に戻して、$3$ で割り切れるか判定する」のは、明らかに面倒くさそうです。
そこで、「ある整数 $N$ が $3$ の倍数」⇔「$N$ の各桁の数字の合計が $3$ の倍数」であることを利用すると、楽に実装できます。
（例：$18 → 1 + 8 = 9$ 、 $762 → 7 + 6 + 2 = 15$ ）
具体的には、$N$ を $1$ 桁ごとに分解したリストを作ります。例えば、$1234567$ なら、[1,2,3,4,5,6,7]にします。ある桁を消さずに使うなら桁和に足して、消すなら足しません。そして、最終的に桁和が $3$ の倍数かどうか判定すればいいです。
全部消すのはダメです
桁を全部消すと桁和が $0$ になるので、必ず $3$ の倍数になります。しかし、この問題では許されていません。
わざわざ除外するのは面倒なので、答えが初期値のままなら $-1$ を出力すればいいです。
コード
from itertools import product
# とりあえず文字列Sで受け取ったあと、桁ごとの数字のリストAにすると扱いやすいです
# N = 6227384 -> A = [6,2,2,7,3,8,4]
S = input()
A = [int(x) for x in S]
l = len(S) # Sの桁数です（Sは文字列で受け取ったので、len(S)を使えます）
ans = l
for bits in product((True, False), repeat=l):
digit_sum = 0 # 消してない桁の和です
score = 0 # 桁を消した数で、少ないほうがうれしいです
for i, bit in enumerate(bits):
if bit:
# 上からi桁目を消さずに使います
digit_sum += A[i]
else:
# 上からi桁目を消します
score += 1
if digit_sum % 3 == 0:
# 3の倍数になる消し方なら、最小値を更新します
ans = min(ans, score)
if ans == l:
# 3の倍数にならなかったので、-1を出力します
print(-1)
else:
print(ans)