Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
3
Help us understand the problem. What are the problem?
@u2dayo

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

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

AtCoder Beginner Contest 185A,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を使うか、抽象セグ木のライブラリを用意しておくといいです。

私(うにだよ)の結果(参考)

screenshot.45.jpg

はじめて全完しました。

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)
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
3
Help us understand the problem. What are the problem?