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

2020/12/16 更新:
C問題の重複組み合わせの解説を少し丁寧に修正
C問題のコンビネーションを求める関数を自分で実装するパターンに、mathモジュールのfactorial関数を使うものを追加
C問題のコンビネーションの記法が誤っていたため、正しく表示されていなかったのを修正

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

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

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

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

LGTMしていただけると、こっそりとても喜びます

目次

ABC185 まとめ
A問題『ABC Preparation』
B問題『Smartphone Addiction』
C問題『Duodecim Ferra』

ABC185 まとめ

全提出人数: 7478人

宣伝：『AtCoderFacts』というアプリを作ったよ

『AtCoderFacts』というアプリを作りました。この記事でいつもやっている、『レートごとの正解率』『パフォーマンス目安』を見ることができます。

今はまだそれだけですが、今後より機能が充実する予定です。ぜひ使ってください。

リンク：https://app.atcoder-facts.com/

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	AB----	300	71分	5827(5641)位
400	AB----	300	17分	4879(4693)位
600	ABC---	600	36分	4046(3862)位
800	ABCD--	1000	85分	3154(2973)位
1000	ABCD--	1000	46分	2321(2141)位
1200	ABCD-F	1600	93分	1639(1461)位
1400	ABCD-F	1600	52分	1129(952)位
1600	ABCDEF	2100	92分	747(587)位
1800	ABCDEF	2100	65分	489(338)位
2000	ABCDEF	2100	52分	312(179)位
2200	ABCDEF	2100	41分	201(87)位
2400	ABCDEF	2100	35分	126(39)位

色別の正解率

色	人数	A	B	C	D	E	F
灰	2861	98.0 %	68.4 %	31.7 %	20.8 %	1.4 %	3.9 %
茶	1420	99.3 %	95.6 %	74.9 %	69.8 %	4.2 %	15.5 %
緑	1062	99.8 %	98.6 %	92.9 %	92.9 %	13.2 %	44.4 %
水	685	99.7 %	99.1 %	98.1 %	98.4 %	43.9 %	90.1 %
青	345	99.7 %	99.7 %	99.7 %	99.7 %	80.0 %	98.0 %
黄	151	97.3 %	96.7 %	96.0 %	95.4 %	90.1 %	98.0 %
橙	27	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %
赤	9	77.8 %	77.8 %	88.9 %	88.9 %	100.0 %	100.0 %

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

簡易解説

A問題 (7332人AC)『ABC Preparation』

min(A)です。

B問題 (5993人AC)『Smartphone Addiction』

ややこしいですが、書かれているとおりにシミュレートすれば計算量 $O(M)$ で解けます。

C問題 (4326人AC)『Duodecim Ferra』

重複組み合わせです。Python 3.8 の場合、mathモジュールのcomb関数を使えばいいです。（PyPy7.3.0では使えません）

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

ハンコの長さは一番短い連続白マス区間の長さと同じにします。
それ以上長くすると、その区間をどうやっても押せなくなってしまいます。
赤マスを二重に押すのは許されているので、ある $1$ つの白マス区間を赤く塗りつぶすには、その区間の長さをハンコの長さで割って、小数点以下を切り上げた回数だけかかります。
これを全白マス区間について求めて足せばいいです。

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

編集距離そのものです。 『問題解決力を鍛える！アルゴリズムとデータ構造』（けんちょん本） の78ページの動的計画法をそのまま書けばいいです。

F問題 (1994人AC)『Range Xor Query』[この記事では解説しません]

『やるだけ』という言葉は好きではありませんが、本当にセグメントツリーを貼るだけです。ACLを使うか、抽象セグ木のライブラリを用意しておくといいです。

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

はじめて全完しました。

A問題『ABC Preparation』

問題ページ：A - ABC Preparation
灰コーダー正解率：98.0 %
茶コーダー正解率：99.3 %
緑コーダー正解率：99.8 %

コード

A = [*map(int, input().split())]
print(min(A))

B問題『Smartphone Addiction』

問題ページ：B - Smartphone Addiction
灰コーダー正解率：68.4 %
茶コーダー正解率：95.6 %
緑コーダー正解率：98.6 %

考察

$2$ つの時間 $t_0, t_1$（$t_0 < t_1$）があるとします。 経過時間は $t_1 - t_0$ で求められます。

問題文には、時刻 $n + 0.5$ になるとバッテリーが増減するとあります。数直線を書いてみるとわかりますが、これは $1$ 秒経つごとに増減するという意味です。

時刻は最大 $10^9$ になりますが、カフェの数は最大 $1000$ です。『カフェを出てから次のカフェまでの経過時間』『カフェの滞在時間』は引き算をすれば $O(1)$ で求められるので、シミュレートすれば計算量 $O(M)$ でこの問題を解けます。

実装

バッテリーは $0$ ちょうどになってもダメです。判定は $0$ 『以下』です。『未満』ではありません。

また、最後のカフェから自宅に帰る間にバッテリーが $0$ になってもダメなことに注意してください。

コード

def solve():
    rem = N  # 残りのバッテリー残量
    prev = 0  # 直前のカフェ（or スタート地点）を出た時間

    for _ in range(M):
        a, b = map(int, input().split())
        rem -= a - prev  # 直前のカフェ（or スタート地点）を出てからの経過時間だけバッテリーが減ります
        if rem <= 0:
            # カフェにつく前にバッテリーが0になる場合、"No"です（0ちょうどもアウト）
            return False
        rem += b - a  # カフェの滞在時間分、バッテリーが回復します
        rem = min(N, rem)  # バッテリー残量は上限Nを超えないことに注意しましょう
        prev = b  # 時刻bにカフェを出ます

    rem -= (T - prev)  # 時刻Tに自宅に帰るまでが遠足です
    if rem <= 0:
        return False
    return True


N, M, T = map(int, input().split())

if solve():
    print("Yes")
else:
    print("No")

C問題『Duodecim Ferra』

問題ページ：C - Duodecim Ferra
灰コーダー正解率：31.7 %
茶コーダー正解率：74.9 %
緑コーダー正解率：92.9 %

やる気があったら図を追加してもうちょっと丁寧に書きます

考察

L = 12 の場合

$L=12$ の場合、長さ $1$ の棒を $12$ 本作るしかないので、明らかに答えは $1$ 通りです。（長さ $0$ の棒はダメです）

L = 13 の場合

$L=13$ の場合、まず $12$ 本の長さ $1$ の棒を作ります。 すると、長さが $1$ 余ります。余った長さを使って、$12$ 本のうち $1$ 本だけ選んで長さ $2$ にできます。したがって、答えは $12$ 通りです。

L = 14 の場合

$L=14$ の場合、長さが $2$ 余るのを、$12$ 本の棒に自由に割り当てることができます。棒の伸ばし方は、次の $2$ パターンあります。

1. 長さ $3$ の棒を $1$本 作る
2. 長さ $2$ の棒を $2$本 作る

パターン $1$ は $12$ 通りです。パターン $2$ は、${}_{12} C _{2}=66$通りです。よって、合計で $78$ 通りになります。

L = 15以上の場合

ここまでは場合分けで計算できましたが、$L$ が大きくなるにつれてパターン数は爆発的に増えるので、場合分けで解くのは不可能です。

そこで、別の方法を使います。

この問題のような『いくつかのグループ（この問題では $12$ 本の棒）に、重複を許してもの（この問題では余った長さ）を割り当てる場合の数』を求めるには、『重複組み合わせ』 というものを使うとうまく計算できます。

参考リンク：重複組合せの公式と例題（玉，整数解の個数） | 高校数学の美しい物語
（このページの『どれも1つ以上選ぶパターン』がこの問題と全く同じです）

重複組み合わせの例

$L=15$ を例にします。余った長さは $15 - 12 = 3$です。

$12-1=11$ 本の 仕切り | と、$3$ 個の丸 ● があります。

| と ● を割り当てるための、$11+3=14$ 個の空きスペース □ を作ります。

□□□□□□□□□□□□□□

$14$ 個の空きスペースから、$11$ 箇所を選んで、| を置きます。例として、次のように配置したことにします。

□||||||||□□|||

そして、余った $3$ 個のスペースに、● を割り当てます。

●||||||||●●|||

これは、

『1番目の仕切りより左にある●の数』だけ『1番目の棒を伸ばす』
『1番目の仕切りと2番めの仕切りの間にある●の数』だけ『2番目の棒を伸ばす』
……
『11番目の仕切りより右にある●の数』だけ『12番目の棒を伸ばす』

ということを表しています。

上の配置では、$1$ 番目の棒に $+1$ して長さ $2$、$9$ 番目の棒に $+2$ して長さ $3$、残りの棒は伸ばさないので長さ $1$ になります。

一般の求め方

●：$L - 12$ 個
|：$11$ 個
空きスペース：$(L - 12) + 11 = L-1$ 個

$L - 1$ 個ある空きスペースのうち、$11$ 箇所を選んで | を設置して、余ったところに ● を割り当てる

ということで、${}_{L-1} C _{11}$ で求めることができます。組み合わせの計算は $O(N)$ でできるので、余裕で間に合います。

実装

C++などの扱える整数値の範囲に制限がある言語の場合、少し工夫しないとオーバーフローで正しい答えが出ません。一方、Pythonは扱える整数値の範囲に制限がありません。ですので、何も考えずに普通に計算すればいいです。最高ですね。

さて、組み合わせの計算の実装の話に移ります。Python 3.8.2 と PyPy 7.3.0 のどちらを使っているかで、少し変わってきます。

Python 3.8.2 の場合

Python 3.8.2の場合、mathモジュールのcomb関数を使えます。これを使えば終わりです。

from math import comb
ans = comb(X + 11, 11)

PyPy 7.3.0 の場合

PyPy 7.3.0は Python 3.6がベースです。ですので、Python 3.8 で追加された関数のcomb関数は使えません。使おうとすると、実行時エラー（RE）でペナルティをくらいます。

ですので、自分で定義どおりにcomb関数を書けばいいです。数学的なことは何も考えずに、調べたら出てくる下の式をそのままコードに落とし込めばいいです。

 {}_n C_k =\frac{n!}{k!(n-k!)}

この式には、階乗が $3$ つ出てきます。forループで階乗の計算をしてもいいですが、mathモジュールのfactorial関数を使うと楽です。

from math import factorial

def comb(n, k):
    return factorial(n) // (factorial(k) * factorial(n - k))

なお、制約の最大値で計算するfactorial(200)は次のような375桁の巨大数になりますが、それでもPythonは問題なく計算をしてくれます。

>>> import math
>>> math.factorial(200)
788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000

>>> len(str(math.factorial(200)))
375

コード

Python 3.8.2のcomb関数の場合

Python 3.8.2でmathモジュールのcomb関数を使う場合のコードです。

from math import comb

L = int(input())
X = L - 12
ans = comb(X + 11, 11)
print(ans)

factoriral関数で書く場合

from math import factorial

def comb(n, k):
    return factorial(n) // (factorial(k) * factorial(n - k))

L = int(input())
X = L - 12
ans = comb(X + 11, 11)
print(ans)

forループ3つで書く場合

最初は解説にこのコードしか載せていませんでしたが、この問題は制約が小さくfactorial関数を使うことができるので、あまりおすすめはしません。

def comb(n, k):
    ret = 1
    for i in range(1, n + 1):
        ret *= i
    for i in range(1, k + 1):
        ret //= i
    for i in range(1, n - k + 1):
        ret //= i
    return ret


L = int(input())
X = L - 12
ans = comb(X + 11, 11)
print(ans)