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

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

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

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

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

目次

ABC180 まとめ
A問題『box』
B問題『Various distances』
C問題『Cream puff』

ABC180 まとめ

全提出人数: 5748人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	A-C---	400	30分	4393(4250)位
400	ABC---	600	51分	3638(3499)位
600	ABC---	600	23分	3008(2869)位
800	ABCD--	1000	115分	2357(2219)位
1000	ABCD--	1000	62分	1749(1614)位
1200	ABCD--	1000	23分	1241(1110)位
1400	ABCDE-	1500	85分	850(724)位
1600	ABCDE-	1500	60分	565(441)位
1800	ABCDE-	1500	44分	364(251)位
2000	ABCDE-	1500	33分	227(131)位
2200	ABCDE-	1500	26分	136(63)位
2400	ABCDE-	1500	17分	83(29)位

色別の正解率

色	人数	A	B	C	D	E	F
灰	2412	99.0 %	68.4 %	64.4 %	12.4 %	1.2 %	0.0 %
茶	1093	99.5 %	92.5 %	93.7 %	45.6 %	7.0 %	0.2 %
緑	889	99.9 %	97.6 %	99.0 %	79.0 %	31.6 %	0.1 %
水	544	100.0 %	99.8 %	99.8 %	95.8 %	73.2 %	0.7 %
青	268	100.0 %	99.6 %	99.6 %	97.8 %	94.0 %	6.3 %
黄	109	98.2 %	97.2 %	99.1 %	98.2 %	91.7 %	26.6 %
橙	26	100.0 %	100.0 %	100.0 %	96.2 %	96.2 %	69.2 %
赤	8	62.5 %	62.5 %	62.5 %	62.5 %	75.0 %	100.0 %

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

簡易解説

A問題 (5699人AC)『box』

足し算と引き算のコードが書ければOKです。

B問題 (4683人AC)『Various distances』

forループを使って、書かれているとおりに求めればいいです。

C問題 (4585人AC)『Cream puff』

約数を昇順に出力する問題です。約数列挙は $O(N)$ でできます。

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

$A$ 倍にしたほうがいい間は、実際に $A$ 倍してシミュレートします。$B$ 足したほうがよくなったら、計算して残り回数を求めます。
$2^{60}>10^{18}$ より、$A$ 倍する回数は多くても $60$ 回程度になります。

E問題 (1189人AC)『Traveling Salesman among Aerial Cities』[この記事では解説しません]

都市間のコストは多くても $17^2=375$ 通りしかなく、簡単に求められるので、先に求めます。
すると、ただの巡回セールスマン問題になります。
巡回セールスマン問題は全てのルートを試すと $O(N!)$ ですが、いわゆるbitDPという動的計画法を使うと $O(N^{2}2^{N})$で解けます。

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

動的計画法らしいです。問題名のとおり、グラフは枝分かれしません。

私（うにだよ）の結果（参考）

応用情報の勉強をしていたので、バーチャル参加です。

A問題『box』

問題ページ：A - box

考察

$A$ 個取り出そうとしても足りない場合を考える必要はありません。問題文に書いておらず、また制約が $A\le{100}\le{N}$ だからです。

したがって、$N-A+B$ が答えです。

コード

N, A, B = map(int, input().split())
print(N - A + B)

B問題『Various distances』

問題ページ：B - Various distances

考察

距離を求める式は問題文に書いてあります。距離の意味がわからなくても書かれたとおりに計算すればいいです。（ついでに、$4$ 次元以上の距離を具体的に考えるのは無理です）

それぞれの式の意味は以下のとおりです。

1. マンハッタン距離

『 $x_i$ の絶対値 $|x_i|$ 』 の総和（合計）です。

2. ユークリッド距離

『 $x_i$ の 二乗 ${x_i}^{2}$ 』 の総和の平方根です。マイナスの値を二乗するとプラスになるので、絶対値を外しても構いません。

一見難しそうですが、$2$ 次元平面では $\sqrt{x^2+y^2}$ 、$3$ 次元空間では $\sqrt{x^2+y^2+z^2}$ になります。これは、中学か高校の数学で習う普通の距離です。

3. チェビシェフ距離

『$x_i$ の絶対値 $|x_i|$』の最大値です。

実装

初期値 $0$ の変数 first, second_temp, thirdを作ります。それぞれ出力する順番どおりの『マンハッタン距離』『ユークリッド距離の平方根の中身』『チェビシェフ距離』に対応します。

点の座標のリスト X の要素をforループで $1$ つずつ見ていって、この $3$ つを計算します。

forループ内の処理

forループ内で行う処理です。

$1$ 番目の『マンハッタン距離』は絶対値を足せばいいので、first += abs(x) です。

$2$ 番目の『ユークリッド距離の平方根の中身』は二乗を足せばいいので、second_temp += x**2 です。

$3$ 番目の『チェビシェフ距離』は、絶対値の最大値を更新すればいいので、third = max(third, abs(x))です。

forループ後の処理

『ユークリッド距離』を求めるために、second のルートを取ります。つまり、second = second_temp ** 0.5 です。

全て求められたので、first, second, third の順番に出力して終わりです。

コード

Pythonでは気にしなくていいですが、second_tempは $10^{15}$ 程度の大きさになる場合があります。C++などではオーバーフローに注意する必要があります。

N = int(input())
X = list(map(int, input().split()))

first, second_temp, third = 0, 0, 0

for x in X:
    first += abs(x)
    second_temp += x ** 2
    third = max(third, abs(x))

second = second_temp ** 0.5

print(first)
print(second)
print(third)

おまけ

やる必要はありませんが、高階関数（関数を引数とする関数）のmapやreduceを使うと、それぞれ $1$ 行で求めることもできます。

# たぶんもっといい書き方はある
N = int(input())
X = list(map(int, input().split()))

print(sum(map(abs, X)))
print((sum(map(lambda x: x ** 2, X))) ** 0.5)
print(max(map(abs, X)))

C問題『Cream puff』

問題ページ：C - Cream puff

問題の意味

$N$ の約数を昇順に出力してください。

考察

シュークリームは最大 $10^{12}$ 個ほどになるので、$1$ から $10^{12}$ まで、割り切れるかすべて試す方法では間に合いません。

ところで、『シュークリームを分割することなく平等に分けることができるような人数』とはつまり、『$N$ を割り切れる数』のことです。

『整数 $N$ を割り切れる数』のことを、『$N$ の約数』といいます。

約数の列挙は $O(\sqrt{N})$ でできます。$\sqrt{10^{12}}=10^6$ なので、間に合います。（$10^6$ は $100$ 万です）

効率的な約数列挙の方法

約数には『$\sqrt{N}$ 以下の約数がすべてわかれば、それらで $N$ を 割ると $\sqrt{N}$ 以上の約数もすべてわかる』 という性質があります。

この性質を利用して、『$N$ を $\sqrt{N}$ までで実際に割ってみて、割り切れたら $x$ と$N/x$ を約数リストに加える』と、$O(\sqrt{N})$ で約数を列挙できます。

詳しい理由

$N$ に約数 $x$ があるとします。このとき、 $\frac{N}{x}$ は 必ず $N$ の約数になります。

$N\div{\frac{N}{x}} = N\times{\frac{x}{N}} = x$ だからです。例えば、$36 = 3\times{12}$ は、$3$ と $12$ のどちらも $36$ の約数です。

このような $x$ と $\frac{N}{x}$ を 『約数のペア』 と呼ぶことにします。『約数のペア』は、必ずどちらかが $\sqrt{N}$ 以下で、もう片方が $\sqrt{N}$ 以上になります。

$\sqrt{N}$ 以上の約数があれば、必ずペアは $\sqrt{N}$ 以下です。よって、すべての $\sqrt{N}$ 以下の約数で $N$ を割れば約数が列挙できます。

証明

『約数のペア』は、必ずどちらかが $\sqrt{N}$ 以下で、もう片方が $\sqrt{N}$ 以上になることを背理法で証明します。

どちらも $\sqrt{N}$ より小さい、つまり $x\lt{\sqrt{N}}$　かつ $\frac{N}{x}\lt{\sqrt{N}}$ と仮定します。

不等式をかけ合わせると

x\times{\frac{N}{x}} < \sqrt{N}\times{\sqrt{N}}\\
N < N

になります。$N = N$ のなので、これはおかしいです。つまり、仮定が間違っていてありえません。

同様に、不等式の向きを反対にした「どちらも $\sqrt{N}$ より大きい」もありえません。

以上より、『約数のペア』は、必ずどちらかが $\sqrt{N}$ 以下で、もう片方が $\sqrt{N}$ 以上になります。

実装

基本的には、下のようなコードを書けばいいです。

divs = []

x = 1
while x ** 2 <= N:
    if N % x == 0:
        divs.append(x)
        divs.append(N // x)
    x += 1

ただし、このコードには問題が $2$ つあります。

• $\sqrt{N}$ が約数になるとき、$\sqrt{N}$ を $2$ つリストに追加してしまう
• 結果が昇順にならない

$1$ つ目の問題は $\sqrt{N}$ が約数になる場合を分けても解決できますが、面倒です。

重複を省くためにset型を使うことにします。set型は『順序なし集合』を扱う型で、同じ要素は $1$ つだけしか含まれないようになっています。既に存在する要素を加えても何も起きません。

$2$ 番目の問題は、ソートすれば解決できます。ただし、set型には順序の概念がないのでソートできません。リストに変換してからソートします。

コード

N = int(input())
divs = set()  # 重複を省くために、setを使います

# 数式的にはx <= N ** 0.5 と同じですが、誤差の出ない整数で比較したほうが安全です
x = 1
while x ** 2 <= N:
    if N % x == 0:
        divs.add(x)  # setへの追加はappendではなくaddです
        divs.add(N // x)
    x += 1

ans = list(divs)  # 昇順にしたいので、リストにしてソートします
ans.sort()

for x in ans:
    print(x)