AtCoder Beginner Contest 176のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
目次
ABC176 まとめ
A問題『Takoyaki』
B問題『Multiple of 9』
C問題『Step』
ABC176 まとめ
全提出人数: 9496人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | ABC--- | 600 | 46分 | 7062(6912)位 |
| 400 | ABC--- | 600 | 28分 | 6110(5962)位 |
| 600 | ABC--- | 600 | 18分 | 5010(4862)位 |
| 800 | ABC--- | 600 | 12分 | 3848(3700)位 |
| 1000 | ABC--- | 600 | 7分 | 2774(2626)位 |
| 1200 | ABC-E- | 1100 | 115分 | 1904(1760)位 |
| 1400 | ABCDE- | 1500 | 128分 | 1265(1125)位 |
| 1600 | ABCDE- | 1500 | 77分 | 815(682)位 |
| 1800 | ABCDE- | 1500 | 58分 | 504(387)位 |
| 2000 | ABCDE- | 1500 | 45分 | 305(203)位 |
| 2200 | ABCDE- | 1500 | 36分 | 178(100)位 |
| 2400 | ABCDE- | 1500 | 30分 | 110(47)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 4052 | 96.7 % | 86.9 % | 81.7 % | 2.1 % | 4.6 % | 0.0 % |
| 茶 | 1772 | 99.4 % | 98.9 % | 98.9 % | 8.6 % | 13.5 % | 0.0 % |
| 緑 | 1340 | 99.7 % | 99.7 % | 99.5 % | 36.0 % | 30.8 % | 0.0 % |
| 水 | 726 | 99.9 % | 99.9 % | 99.7 % | 74.7 % | 75.3 % | 0.1 % |
| 青 | 365 | 99.7 % | 99.7 % | 99.7 % | 92.6 % | 95.3 % | 1.6 % |
| 黄 | 125 | 94.4 % | 93.6 % | 92.8 % | 90.4 % | 96.0 % | 1.6 % |
| 橙 | 26 | 96.2 % | 96.2 % | 100.0 % | 100.0 % | 100.0 % | 30.8 % |
| 赤 | 6 | 66.7 % | 66.7 % | 66.7 % | 66.7 % | 66.7 % | 16.7 % |
※表示レート、灰に初参加者は含めず
簡易解説
- A問題 (9228人AC)『Takoyaki』
- 何回焼く必要があるか、$N$ を $X$ で割って切り上げると求められます
- B問題 (8679人AC)『Multiple of 9』
- 書かれているとおり、1文字ずつ見て足した合計が $9$ で割り切れるか判定してもいいですが、実はPythonでは、元の数字が $9$ で割り切れるか、そのまま判定してもできます。
- C問題 (8381人AC)『Step』
- 今までの最大の高さを持って、前から順番に見ていけばいいです。
- D問題 (1804人AC)『Wizard in Maze』[この記事では解説しません]
- BFSです。縦横の最大は $1000$ なので、最大で $100$ 万マスあります。各マスから移動できる座標は $24$ 通りあります。PyPyを使うと、 $24\times{100} 万$ = $2400$ 万通り確認して間に合います。
- E問題 (1958人AC)『Bomber』[この記事では解説しません]
- 基本的には行と列を独立に考えればいいですが、ダブルカウントしてしまう場合があります。ダブルカウントしないかどうか、各障害物の座標について確認すればいいです。Dより簡単です。
- F問題 (18人AC)『Brave CHAIN』[この記事では解説しません]
- 超面倒っぽい動的計画法です。
- $(N+X-1)$ を $X$ で整数除算する方法（
(n + x - 1) // x） -
mathモジュールのceil関数を使って、$N$ を $X$ で割った値を切り上げる方法
私の結果（参考）
A問題『Takoyaki』
問題ページ：A - Takoyaki
考察：
焼くのにかかる時間は作る個数によりません。したがって、何回焼く必要があるかわかれば、それに $T$ 分掛けて求められます。
これは、焼く必要のあるたこ焼きの個数 $N$ を、一度に焼ける個数 $X$ で割った答えを、小数点切り上げすれば求められます。
実装
切り上げの方法は2つあります。
この問題はどちらを使ってもACできますが、できるだけ前者を使って整数だけで済ませたほうがいいです。
コンピュータが通常使っている小数点数の表し方では、完全に正確に表すことができず、誤差が生じる恐れがあるからです。
コード
n, x, t = map(int, input().split())
k = (n + x - 1) // x
ans = k * t
print(ans)
ceil()を使うコードです。おすすめはしませんが、A, B問題でceil()を使ってWAになる問題はあまり出題されないと思います。
from math import ceil
n, x, t = map(int, input().split())
k = ceil(n / x)
print(k * t)
B問題『Multiple of 9』
問題ページ：B - Multiple of 9
実装
書かれているとおりに、各桁の和が $9$ で割り切れるか判定すればいいです。
これをやるには、まず入力を文字列で受け取ります。そして、forループで1文字ずつ取り出し、int()関数で整数に変換するといいです。
コード
n = input()
cur = 0
for x in n:
cur += int(x)
if cur % 9 == 0:
print("Yes")
else:
print("No")
Pythonは整数を表すために、多倍長整数という、大きさの上限がない仕組みを使っています。（C++などのように、オーバーフローしません）
ですので、整数で受け取ってそのまま $9$ で割り切れるか判定してもACできてしまいます。
ただし、巨大な数（最大 $200000$桁）を扱うので、ただの割り算（余りの計算） $1$ 回だけでもそこそこ実行時間がかかります。
n = int(input())
if n % 9 == 0:
print("Yes")
else:
print("No")
Python3の実行時間は、正攻法のコードが $72$ ms、そのまま求めるコードが $216$ msでした。
C問題『Step』
問題ページ：C - Step
考察：
自分より前に背の高い人が存在しないように、踏み台の高さを決めます。
踏み台の高さの合計を最小にしたいので、できるだけ踏み台は小さいものを使ったほうがいいです。
「自分より前にいる人のうち一番背の高い人」と、「自分の身長」を比較します。もし自分のほうが低ければ、身長の差と同じ高さの踏み台を使って、その人と同じ身長になればいいです。
実装
一番背の高い人を求めるためにmax()関数を使うと、計算量が $O(N^2)$ になってしまいます。max()関数は、入力の全要素を $1$ 個ずつ確認して最大値を求めるからです。
そこで、今まで出てきた一番背の高い人の身長を持っておいて、1人見るたびに更新していけばいいです。こうすれば、計算量が $O(N)$ になります。
コード
n = int(input())
a = list(map(int, input().split()))
ans = 0
cur_max = 0
for x in a:
if cur_max > x:
ans += cur_max - x
cur_max = max(cur_max, x)
print(ans)