【AtCoder解説】PythonでABC193のA,B,C問題を制する！

AtCoder Beginner Contest 193のA,B,C問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

• シンプル：余計なことを考えずに済む
• 実装が楽：ミスやバグが減ってうれしい
• 時間がかからない：パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo

目次

ABC193 まとめ
A問題『Discount』
B問題『Play Snuke』
C問題『Unexpressed』

アプリ AtCoderFacts を開発しています

コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。

- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス

今後も機能を追加していく予定です。使ってくれると喜びます。

ABC193 まとめ

全提出人数: 7780人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	AB----	300	22分	5915(5688)位
400	AB----	300	8分	4886(4659)位
600	ABC---	600	64分	4041(3818)位
800	ABC---	600	30分	3180(2958)位
1000	ABCD--	1000	94分	2384(2166)位
1200	ABCD--	1000	68分	1724(1508)位
1400	ABCD--	1000	51分	1211(1000)位
1600	ABCD--	1000	38分	830(626)位
1800	ABCD--	1000	26分	542(363)位
2000	ABCDE-	1500	88分	330(194)位
2200	ABCDE-	1500	62分	211(94)位
2400	ABCDE-	1500	42分	142(43)位

色別の正解率

色	人数	A	B	C	D	E	F
灰	3341	97.5 %	85.8 %	31.8 %	5.4 %	0.1 %	0.0 %
茶	1404	99.4 %	98.6 %	73.7 %	29.2 %	0.5 %	0.0 %
緑	1162	99.5 %	99.0 %	90.7 %	74.3 %	1.5 %	0.1 %
水	726	100.0 %	99.9 %	97.0 %	90.9 %	11.6 %	0.7 %
青	394	99.8 %	99.2 %	98.2 %	96.5 %	41.4 %	4.1 %
黄	165	97.0 %	96.4 %	97.0 %	93.9 %	55.1 %	24.2 %
橙	43	97.7 %	97.7 %	97.7 %	97.7 %	79.1 %	74.4 %
赤	22	95.5 %	95.5 %	95.5 %	95.5 %	95.5 %	68.2 %

※表示レート、灰に初参加者は含めず

簡易解説

A問題 (7641人AC)『Discount』

$100\times{\frac{(A - B)}{A}}\%$ 引きです。

B問題 (7114人AC)『Play Snuke』

$A_i < X_i$ なら、在庫が残っているので $P_i$ 円でスヌケマシンを買えます。
買えるスヌケマシンの中で一番安い価格を出力すればいいです。

C問題 (4602人AC)『Unexpressed』

$N\le{10^{10}}$ なので、$N$ 以下の 正の整数すべてについて $a^b$ と表せないものを判定することはできません。
そこで、反対に $a^b$ と表せるものを数えて全体から引くことを考えます。
$(10^5)^2 = 10^{10}$ なので、$2$ から $10^5$ まで全探索すれば良いです。

D問題 (2771人AC)『Poker』[この記事では解説しません]

確率の問題です。
裏向きのカード2枚の組み合わせは $9\times{9} = 81$通りあります。
全ての場合についてその組み合わせになる確率と点数を計算し、高橋くんが勝つなら答えに足します。
裏向きのカードが2人とも同じ数字になる $9$ 通りの場合は、確率の計算式が変わるので注意しましょう。

E問題 (423人AC)『Oversleeping』[この記事では解説しません]

$Y,P$ が小さいので、全探索できます。
中国剰余定理というのを使うと解けます。

F問題 (110人AC)『Zebraness』[この記事では解説しません]

フローの問題らしいです。（解説しか見てない）

私（うにだよ）の結果

C問題で結構手間取りました。D問題10分は速かったと思います。

E問題の考察はできましたが、中国剰余定理を知らなかったので、$Ax - By = z$ で $x,y$ がどちらも非負になる解を求めようとしてダメでした。

A問題『Discount』

問題ページ：A - Discount
灰コーダー正解率：97.5 %
茶コーダー正解率：99.4 %
緑コーダー正解率：99.5 %

考察

算数です。答えの単位はパーセントなので、${100}\times{\frac{(A-B)}{A}}\%$ と $100$ 倍することに注意しましょう。

コード

A, B = map(int, input().split())
print(100 * (A - B) / A)

B問題『Play Snuke』

問題ページ：B - Play Snuke
灰コーダー正解率：85.8 %
茶コーダー正解率：98.6 %
緑コーダー正解率：99.0 %

考察

${A_i}\lt{X_i}$ の店のスヌケマシン を$P_i$ 円で買えるので、その中で最小の価格を出力すればいいです。

$A_i=X_i$ の場合は在庫切れで買えないことに注意してください。「ちょうど今売り切れてしまいました！ごめんなさい！」です。

コード

N = int(input())

INF = float('INF')  # 正の無限大です
ans = INF

for _ in range(N):
    A, P, X = map(int, input().split())
    if A < X:
        # A < X なら買えます
        ans = min(ans, P)

if ans == INF:
    # 買えない場合、ansはINFのままです
    print(-1)
else:
    print(ans)

C問題『Unexpressed』

問題ページ：C - Unexpressed
灰コーダー正解率：31.8 %
茶コーダー正解率：73.7 %
緑コーダー正解率：90.7 %

考察

制約が $N\le{10^{10}}$ と大きいです。$N$ 以下の整数すべてについて $2$ 以上の整数 $a, b$ を用いて $a ^ b$ と表せるか判定するのは不可能です。

そこで、反対に $a ^ b$ と表せる整数をすべて列挙して、その個数を $N$ から引くことを考えます。

先に正解のコードを載せます。

N = int(input())

S = set()  # a ** b の形で表せる数をsetに入れます（重複を省くため）

# (10 ** 5 + 1)**2 > 10**10 なので、10**5まで調べればいいです
for a in range(2, 10 ** 5 + 1):
    cur = a ** 2  # a ** 2 からはじめます 
    while cur <= N:
        S.add(cur)
        cur *= a

print(N - len(S))

$a ^ 2 > N$ になる $a$ は調べる必要がありません。$a$ が大きくなると $a^2$ も大きくなるので、それ以上の $a$ も調べなくていいです。

$a ^ 2 \le{N}$ となる最大の $a$ は $a \le{\sqrt{N}}$ を満たす最大の整数です。$N$ は最大で $10^{10}$ ですから、$a$ は $\sqrt{10^{10}}=10^5$ まで調べれば十分です。（各ケースについて$\sqrt{N}$ を求めてもいいです）

まとめると、次のコードを書けばこの問題をACできます。

• $2\le a \le{10^5}$ の整数 $a$ をforループで全探索する
• 各 $a$ についてwhileループで $N$ を超えるまで $a$ 倍ずつして、$a^b$ と表せる数を列挙する
• $N$ から 『$a^b$ で表せる数の個数』を引いて答えを求める

重複して数えないように注意

例えば $16$ は、 $2^4, 4^2$ の $2$ 通りの表し方があります。何も考えずに実装すると、このような数を重複して数えてしまいます。

そこで、重複を省くためにset型を使って出てきた数を管理します。set型は同一の要素を $1$ つしか含まないようにしてくれるので、要素数をlen()で求めれば重複せずに数えられます。

ループ回数の見積もり

上記のコードで間に合うか判断するために、制約で最大の $N = 10^{10}$ のときのループ回数を適当に見積もってみます。

$a$ は $2$ から $10^5$ の約 $10^5$ 個をforループで全探索します。$b$ が最も大きくなるのは、$a$ が最小の $a = 2$ のときです。$10^{10}\lt{2^{34}}$ですから、ある $a$ に対してwhileループは最大でも $33$ 回しか回りません。

以上より、全体のループ回数は $33\times{10^{5}}$ 回（$330$ 万回）より少ないことがわかり、間に合いそうだと判断できます。

コード

先ほどのコードと同じものです。

N = int(input())

S = set()  # a ** b の形で表せる数をsetに入れます（重複を省くため）

# (10 ** 5 + 1)**2 > 10**10 なので、10**5まで調べればいいです
for a in range(2, 10 ** 5 + 1):
    cur = a ** 2  # a ** 2 からはじめます 
    while cur <= N:
        S.add(cur)
        cur *= a

print(N - len(S))