AtCoder Beginner Contest 195のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo
よかったらLGTMしていただけると、私のやる気がでます！
目次
ABC195 まとめ
A問題『Health M Death』
B問題『Many Oranges』
C問題『Comma』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC195 まとめ
全提出人数: 7679人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | A----- | 100 | 2分 | 5734(5509)位 |
| 400 | A-C--- | 400 | 78分 | 4708(4483)位 |
| 600 | ABC--- | 600 | 111分 | 3870(3646)位 |
| 800 | ABC--- | 600 | 57分 | 3023(2801)位 |
| 1000 | A-CD-- | 800 | 68分 | 2252(2033)位 |
| 1200 | ABCD-- | 1000 | 79分 | 1619(1403)位 |
| 1400 | ABCD-- | 1000 | 54分 | 1139(926)位 |
| 1600 | ABC-E- | 1100 | 54分 | 781(577)位 |
| 1800 | ABCDE- | 1500 | 74分 | 527(334)位 |
| 2000 | ABCDE- | 1500 | 47分 | 352(176)位 |
| 2200 | ABCDEF | 2100 | 92分 | 204(85)位 |
| 2400 | ABCDEF | 2100 | 71分 | 120(39)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 3355 | 98.8 % | 28.6 % | 41.7 % | 4.9 % | 0.4 % | 0.1 % |
| 茶 | 1416 | 99.6 % | 61.0 % | 79.8 % | 24.9 % | 1.4 % | 0.5 % |
| 緑 | 1124 | 99.7 % | 81.7 % | 93.4 % | 63.6 % | 6.3 % | 0.7 % |
| 水 | 628 | 99.5 % | 92.0 % | 95.9 % | 82.0 % | 31.4 % | 4.8 % |
| 青 | 392 | 99.7 % | 96.4 % | 98.7 % | 92.6 % | 75.8 % | 24.0 % |
| 黄 | 178 | 98.9 % | 96.6 % | 97.2 % | 91.6 % | 88.2 % | 61.8 % |
| 橙 | 34 | 97.1 % | 94.1 % | 97.1 % | 91.2 % | 91.2 % | 85.3 % |
| 赤 | 16 | 93.8 % | 93.8 % | 93.8 % | 93.8 % | 87.5 % | 93.8 % |
※表示レート、灰に初参加者は含めず
簡易解説
- A問題 (7588人AC)『Health M Death』
- 体力 $H$ が$M$ の倍数とはつまり、$H$ を $M$ で割った余りが $0$ ということです。
- B問題 (4054人AC)『Many Oranges』
-
みかんの重さの合計 $W$ の単位が『キログラム』であることに注意してください。
みかんの個数を全探索します。$NA\le{1000W}\le{NB}$ であれば、みかん $N$ 個で $W$ キログラムを作ることができます。
- C問題 (4989人AC)『Comma』
- $N\le{10^{15}}$ なので、$1$ から $N$ までコンマの数を数えて足す方法ではTLEです。
コンマの位置ごとに考えます。
$1,000$ 以上の数には $3$ 桁目と $4$ 桁目の間のコンマが必ずあります。
$1,000,000$ 以上の数には $6$ 桁目と $7$ 桁目の間のコンマが必ずあります。
……というふうに考えると、計算で求めることができます。 - D問題 (2369人AC)『Shipping Center』[この記事では解説しません]
- クエリごとに独立した問題として解きます。
価値の高いものから、入る中で一番小さいサイズの箱に入れていく貪欲法で解けます。 - E問題 (811人AC)『Lucky 7 Battle』[この記事では解説しません]
- 後ろから見るゲームDPです。
- F問題 (304人AC)『Coprime Present』[この記事では解説しません]
- bitDPです。
私（うにだよ）の結果
おやすみしました。
A問題『Health M Death』
問題ページ：A - Health M Death
灰コーダー正解率：98.8 %
茶コーダー正解率：99.6 %
緑コーダー正解率：99.7 %
考察
体力 $H$ が$M$ の倍数とはつまり、$H$ を $M$ で割った余りが $0$ ということです。これを判定すればいいです。
コード
M, H = map(int, input().split())
if H % M == 0:
print("Yes")
else:
print("No")
B問題『Many Oranges』
問題ページ：B - Many Oranges
灰コーダー正解率：28.6 %
茶コーダー正解率：61.0 %
緑コーダー正解率：81.7 %
考察
まず、みかんの重さの合計 $W$ の単位が『キログラム』であることに注意してください。
みかん $1$ 個 の重さは $A$ グラム以上 $B$ グラム以下の間で、どんな値でも自由に取れます。みかん $N$ 個 の重さは $NA$ グラム以上 $NB$ グラム以下の間で、どんな値でも自由に取れます。
みかんの個数を全探索します。$NA\le{1000W}\le{NB}$ であれば、みかん $N$ 個で $W$ キログラムを作ることができます。
みかんの重さは $1\le{A}$ なので、最低で $1$ グラムです。また、$W\le{1000}$ （キログラム）なので、$W$ は最大で $10^6$ グラム（$100$ 万グラム）です。よって、みかんの数は $10^6$ 個まで試せばいいです。
まとめると、みかん $1$ 個 から $10^6$ 個まで全て試して、$NA\le{1000W}\le{NB}$ を満たす $N$ の最小値と最大値を出力すればいいです。そのような $N$ がひとつも見つからなければ、'UNSATISFIABLE'と出力すればいいです。『最小値と最大値のどちらかしか見つからない』ことはありえません。
コード
A, B, _W = map(int, input().split())
W = 1000 * _W # 先にグラムに変換しておきます
mn = float('INF') # 正の無限大です
mx = -1
for n in range(1, 10 ** 6 + 100):
l = A * n
r = B * n
if l <= W <= r:
mn = min(mn, n)
mx = max(mx, n)
if mx == -1:
print('UNSATISFIABLE')
else:
# 最大値か最小値のどちらかしか見つからないことはありません
print(mn, mx)
C問題『Comma』
問題ページ：C - Comma
灰コーダー正解率：41.7 %
茶コーダー正解率：79.8 %
緑コーダー正解率：93.4 %
問題の意味
考察
コンマの打たれる位置ごとに、個数を数えます。
$3$ 桁目と $4$ 桁目の間にあるコンマは、すべての $1,000$ 以上の数にあります。
$6$ 桁目と $7$ 桁目の間にあるコンマは、すべての $1,000,000$ 以上の数にあります。
$9$ 桁目と $10$ 桁目の間にあるコンマは、すべての $1,000,000,000$ 以上の数にあります。
$12$ 桁目と $13$ 桁目の間にあるコンマは、すべての $1,000,000,000,000$ 以上の数にあります。
$15$ 桁目と $16$ 桁目の間にあるコンマは、すべての $1,000,000,000,000,000$ 以上の数にあります。
$N\le{10^{15}}$ なので、$N$ は最大で $16$ 桁です。ここまで考えれば十分です。（$1,000,000,000,000,000$ ちょうどの場合があるので、$15$ 桁ではありません）
実際にどう数えるか考えます。
$3$ 桁目と $4$ 桁目の間にあるコンマは、$N$ が $1,000$ 以上のとき、$N - 999$ 個あります。
$6$ 桁目と $7$ 桁目の間にあるコンマは、$N$ が $1,000,000$ 以上のとき、$N - 999,999$ 個あります。
（省略）
これを足し合わせていけばいいです。
実装
例えば、$N = 1$ のときに、$3$ 桁目と $4$ 桁目の間にあるコンマは $1-999=-998$ 個あるとしてしまうといけません。これを防ぐために、if N >= 1000と場合分けする必要があります。
また、手書きで $N - 999999999999$ と書くとミスするので、 N - (10 ** 12 - 1) と書くといいです。
さらに、条件文を $5$ 個書くのは面倒なので、forループで range(3, 18, 3) を回して、10 ** i - 1 など書くと楽です。
（詳しくはコードを見てください）
コード
N = int(input())
ans = 0
for i in range(3, 18, 3):
if N >= 10 ** i:
ans += N - (10 ** i - 1)
print(ans)