AtCoder Beginner Contest 174のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
目次
ABC174 まとめ
A問題『Air Conditioner』
B問題『Distance 』
C問題『Repsept』
ABC174 まとめ
全提出人数: 9809人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 13分 | 7284(7079)位 |
| 400 | AB---- | 300 | 6分 | 6317(6113)位 |
| 600 | AB-D-- | 700 | 82分 | 5204(5006)位 |
| 800 | AB-D-- | 700 | 37分 | 4029(3831)位 |
| 1000 | ABCD-- | 1000 | 65分 | 2931(2736)位 |
| 1200 | AB-DE- | 1200 | 26分 | 2036(1845)位 |
| 1400 | ABCDE- | 1500 | 46分 | 1366(1184)位 |
| 1600 | ABCDEF | 2100 | 135分 | 881(720)位 |
| 1800 | ABCDEF | 2100 | 77分 | 543(410)位 |
| 2000 | ABCDEF | 2100 | 56分 | 319(216)位 |
| 2200 | ABCDEF | 2100 | 43分 | 174(107)位 |
| 2400 | ABCDEF | 2100 | 34分 | 96(50)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 4081 | 99.0% | 88.6% | 10.7% | 29.2% | 1.9% | 2.4% |
| 茶 | 1827 | 99.9% | 99.6% | 33.4% | 73.5% | 8.1% | 8.2% |
| 緑 | 1404 | 99.8% | 99.6% | 63.5% | 91.3% | 35.7% | 16.6% |
| 水 | 790 | 99.9% | 99.8% | 90.8% | 97.3% | 84.8% | 38.7% |
| 青 | 365 | 100.0% | 100.0% | 97.0% | 98.6% | 95.1% | 62.5% |
※表示レート、灰に初参加者は含めず
簡易解説
- A問題 (9720人AC)『Air Conditioner』
- if文を使います。
- B問題 (9103人AC)『Distance』
- 小数のまま判定すると誤差で正しく判定できないので、二乗して整数のまま判定します。
- C問題 (3349人AC)『Repsept』
- 適当に1000万項くらいまで判定して、なければ-1を出力すればいいです。
- D問題 (5486人AC)『Alter Altar』[この記事では解説しません]
- 公式のPDFに書いてある方法は、すべての最終状態について何回操作が必要か数える方法です。これ以外にも、左右から尺取法的に操作をシミュレートしても解けます。
- E問題 (2013人AC)『Logs』[この記事では解説しません]
- 通称『決め打ち二分探索』というテクニックを使う、超典型問題です。蟻本（プログラミングコンテストチャレンジブック）の129ページとだいたい同じです。知らないとまず解けませんが、知っていれば茶色の人でも解けるかもしれない問題です。
- F問題 (1257人AC)『Range Set Query』[この記事では解説しません]
- クエリをlかrのどちらかでソートして、Binary Index Tree（解説PDFではフェニック木と呼ばれています）というデータ構造を利用すると解けます。ただし、入力が50万と大きいために、PythonやPyPyでは実行時間制限が厳しいです。
A問題『Air Conditioner』
問題ページ：A - Air Conditioner
実装
条件が単純なので、『三項演算子』を使ったほうが見た目がきれいで、楽かもしれません。
コード
三項演算子を使うコードです。
x = int(input())
print("Yes") if x >= 30 else print("No")
@c-yanさんがコメントしてくださった、下のコードのほうが自然で短いです。ありがとうございます！
x = int(input())
print("Yes" if x >= 30 else "No")
普通のコードです。
x = int(input())
if x >= 30:
print("Yes")
else:
print("No")
B問題『Distance』
問題ページ：B - Distance
問題の意味
原点$(0, 0)$からの距離が$D$以下の点の数を求めてください。
考察：
2次元平面上の二点間の距離は、三平方の定理で求められます。これは問題文に書いてあるので、覚えていなくても問題ありません。
素直にこの式のまま、次のような実装をしたくなります。
if (x**2 + y**2) ** 0.5 <= D:
ans += 1
しかし、これではWAになります。（ この問題ではACになります。@mui_nyanさんにご指摘いただきました。ありがとうございます！ ）
コンピュータの世界で通常使われている方法では、小数を正確に表すことができず、誤差が出るためです。
そこで、元の式の両辺を二乗します。すると、$x^2 + y^2 \le D^2$となり、整数だけで判定をすることができます。
今回の問題では、両辺ともに二乗する前の式がマイナスでないことが確定しているので、気にする必要はありませんが、不等式にマイナスの数をかけると不等号が逆転することに注意してください。
この問題では素直に書いても通りますが、使わずに済むなら、浮動小数点数（Pythonではfloat型）を使わずに整数（int型）だけで済ませたほうが良いです。最近出た浮動小数点数を使うとWAになる問題に、例えばABC169C - Multiplication 3があります。
コード
n, d = map(int, input().split())
ans = 0
for _ in range(n):
x, y = map(int, input().split())
if x ** 2 + y ** 2 <= d ** 2:
ans += 1
print(ans)
C問題『Repsept』
問題ページ：C - Repsept
問題の意味：
$7, 77, 777, 7777,...$という数列があります。この数列ではじめに$K$の倍数が現れるのが第何項目か求めてください。存在しない場合は、かわりに$-1$を出力してください。
なお、ある整数$N$が$K$の倍数となる必要十分条件は、$N$を$K$で割った余りが$0$となることです。
考察：
この数列は、前の数字を$10$倍したあと、$7$を足す数列です。数学っぽく書くと、$a_{n+1} = 10a_{n} + 7$ です。
具体例を第$4$項まで書くと、次のようになっています。
$7$
$7\times10 + 7 = 70 + 7 = 77$
$77\times10 + 7 = 770 + 7 = 777$
$777\times10 + 7 = 7770 + 7 = 7777$
さて、これはABCのC問題なので、難しい数学的考察は通常求められないと思っていいです。そこで、適当に第1000万項くらいまで判定して、見つからなければないとして良い気がします。（やや厳密な話もあとでします）
ただし、数列の値をそのまま使って余りを求めると、数百万桁の数字の余りを数百万回求めることになるので、TLEになります。（私たちが紙で筆算するときと同じように、コンピュータでも桁数が多いほど計算に時間がかかります）
そこで、余りの 「足し算・引き算・掛け算をするたびに余りを取っても、結果が変わらない」 性質を利用します。
つまり、「前の余りを$10$倍して$7$を足したあと、$K$で割った余りを求める」ことを繰り返せばいいです。
整数を$K$で割った余りは最大でも$K-1$なので、この問題の制約では$10^6$未満であることが保証されます。これなら、$1000$万項計算しても間に合います。
やや厳密に言うと：
現在が第何項かにかかわらず、次の項は今の項を10倍して7足したものになっています。つまり、もし同じ余りが2回以上出たら、次の項以降、以前出た余りと同じ結果がループすることになります。
整数を$K$で割った余りは、$0$～$K-1$の、高々$K$通りしかありません。ということは、$K$回以内に余りが$0$にならなければ、$K$の倍数にならないとしていいです。
なぜ適当なことを言ったか
WAのペナルティは$5$分なので、なんとなく合ってそうな解法を思いついて、コードもすぐ書けそうなものの、真面目に証明しようとすると$5$分以上かかりそうなら、とりあえずコードを出してしまったほうがいいからです。
ACならそれで終わりです。WAになったら改めて考えればいいです。
コード
Python3では1070 ms、PyPy3では201msで通りました。
def calc(k):
cur = 0
for i in range(1, 10 ** 7):
cur *= 10
cur += 7
cur %= k
if cur == 0:
return i
return -1
k = int(input())
print(calc(k))
$K$回だけ繰り返すバージョンです。こちらでも通ります。
def calc(k):
cur = 7 % k
for i in range(1, k + 1):
if cur == 0:
return i
else:
cur *= 10
cur += 7
cur %= k
return -1
k = int(input())
print(calc(k))