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

AtCoder Beginners Contest 165のA,B,(C),D問題をPython3で解く方法を、なるべく丁寧に解説していきます。

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

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

5/17 C問題が非常に難しく、記事が長くなったので、別記事に分離しました。

【AtCoder解説】ABC165のC問題をPythonで制する！

ABC165

開催日: 2020-05-02(土) 21:10 ~ 2020-05-02(土) 22:50 (100分)
A問題提出人数: 11626人

パフォ	AC	点数	時間	順位	目安
400	AB--	300	14分	7325位	茶パフォ
600	A--D	500	98分	5940位	8回で茶色レート
800	AB-D	700	75分	4505位	緑パフォ
1200	ABCD	1000	93分	2194位	水パフォ

(参考)私：パフォ1426 ABCD-- 41:05 1379位 Dを先に解いてCに戻りました

A問題（11225人AC）

やや難しかったと思います。

B問題（9994人AC）

切り捨てを忘れないようにしましょう。サンプルで確認する癖をつけていれば、WAを出さずに済みます。

C問題（2514人AC）

とても難しかったです。総当りするだけといえばそうなのですが……。

D問題（5554人AC）

C問題と難易度が逆です。試していればわかる問題です。

C問題が、難しいD問題レベルの難易度です。「総当りして答えをすべて確認する」というだけならC問題でもよく出てきます。

しかし、この問題はありえる数列を総当りできることに気づくのが難しいです。そのうえで、ありえる数列をすべて作る方法を知らないと解けません。

一方で、D問題がいつものC問題レベルの難易度でした。こういう問題セットのときは、一旦落ち着いてD問題を確認したあと、C問題を捨ててD問題をやる勇気が必要です。

ABC165A 『We Love Golf』

問題ページ：A - We Love Golf
むずかしさ：★★☆☆☆
ポイント：数学、whileの扱い

b以下のkの倍数をすべて作る方法がわかっていれば解けます。

解き方

　1.　どうするか考える

ステップ1: 問題文を読む

簡単に思いつく方法は、b以下のkの倍数を全て列挙して、a以上になるものが1つでもあれば"OK"とする方法です。これでコードを書き始めていいと思います。

ですが、公式の解説PDFに書いてある「b以下で最大のkの倍数を求め、それがa以上ならば"OK"」という方法のほうが楽なので、思いついたならこっちで書いたほうがいいです。私は思いつきませんでした。

コード

2つの方法を書いておきます。

k = int(input())
a, b = list(map(int, input().split()))

x = 0

# もう少しきれいに書ける気はしますが、とりあえず無限ループ+breakで
while True:
    x += k
    if a <= x <= b:
        print("OK")
        break

    if x > b:
        print("NG")
        break

k = int(input())
a, b = list(map(int, input().split()))

# 「b以下の最大のkの倍数」を求めます
largest = (b // k) * k

if a <= largest:
    print("OK")
else:
    print("NG")

ABC165B『1%』

問題ページ：B - 1%
むずかしさ：★★☆☆☆
ポイント：whileの扱い、問題文を正確に読むこと

書いてあるとおりにやるだけですが、**「毎年小数点以下のお金は切り捨てる」**という、大事なことがカッコ内に書いてあります。

なお、C++などの場合オーバーフローに注意する必要がありますが、Pythonでは気にする必要はありません。さすがPythonですね。

解き方

1. どうするか考える

ステップ1: どうするか考える

最初に100円持っていて、年1%ずつ複利で増えます。この通りにやれば解けます。

問題文をよく読むと、カッコ内に(複利、小数点以下切り捨て)とすごく大事なことが書いてあります。

ですので、小数点以下は切り捨てましょう。

コード

問題文をちゃんと読めたら、あとは書くだけです。

もし小数点以下切り捨てを見逃したとしても、サンプルで確認すると答えがズレるので、何かがおかしいことに気づけます。私は気づきました。

具体的には、サンプル2の答えが3760に対し出力が3703、サンプル3が1706に対し1649になります。

サンプル2が制約で最大の$10^{18}$なので、これが通れば誤差の心配はないだろうと自信を持てます。

x = int(input())

year = 0 # 答え
money = 100 # 初期値の100円

# x円以上になるまでループを回す
while money < x:
    money *= 1.01
    money = int(money)
    year += 1

print(year)

ABC165C『Many Requirements』

問題ページ：C - Many Requirements
むずかしさ：★★★★★★★★★★（難しいD問題レベル！）
タイプ：総当りの発想、深さ優先探索（他の方法もあり）、過去問演習

まず問題文を読んで意味を理解するのが大変です。意味がわかっても、すべての数列を作って確かめるという発想が必要です。そして、総当りすることがわかっても、どうやって数列を作るか知らないと解けません。

正直言って、難しいD問題の難易度です。

やること

1. （やばそうなので、D問題が簡単ではないか確認する）
2. 問題文を解読する
3. 解法を考える
4. 実装を考える

ステップ1 （やばそうなので、D問題が簡単ではないか確認する）

は？と思われそうですが、これは大事なことです。AtCoderでは、問題の難易度が逆転していることは結構よくあります。後ろの問題のほうが解けそうであれば、そっちをやったほうが配点的にも良いです。

今回はCのAC者が2500人に対し、DのAC者が5000人と、なんと2倍以上の差がありました。これほど難易度に差があることは珍しいですが、少しの難易度の差ならよくあります。

問題に集中してしまうと後ろの問題を解くという発想は出てこないので、一度冷静になって問題から離れてみる気持ちも大事です。

私はコンテスト終了後に「こっちの問題なら解けたのに！」と悔しい思いをすることがよくあったので、少し考えてわからなかったら後ろの問題を確認するようにしています。

私は今回、Cを5分考えてやばそうだと感じたので、Dを10分で解いたあと、Cに戻って15分かけて解きました。

ステップ2～ 別記事

長くなったので、別記事に分割しました。3種類の方法で解説します。

• itertools.combinations_with_replacementを使う（一番楽）
• キュー再帰で作る（汎用性が高い方法）
• 深さ優先探索（解説PDFの方法）

【AtCoder解説】PythonでABC165のC問題『Many Requirements』を制する！

##類題
類題をいくつか紹介します。後ろの2つはやや難しいD問題レベルの難易度ですが、それでもこの問題よりは簡単です。

茶レベル： ABC029 C - Brute-force Attack
緑レベル： ABC161 D - Lunlun Number
緑レベル： パナソニックプログラミングコンテスト2020 D - String Equivalence

↓↓↓↓↓↓↓ あなたの記事の内容

ABC165D『Floor Function』

───────

コード

（とりあえず記事を完成させたいので、後でもう少し読みやすくします）

提出してACになることは確認しましたが、私の実力ではこれ以上わかりやすく書けませんでした。まずは最初のdfs関数は読み飛ばして、コードの本体を読んでください。本体はコメントを抜くと4行です。

dfs関数の引数は、dfs(今の数列, 今の数列の長さ, 次の数字の下限)です。次の数字の下限は、さっき新しく付け加えた数字と同じです。初期値については最後に説明します。

例えば、数列1,1に3を付け加えて、1,1,3になったとします。次に付け加える数字は3以上でなければいけないので、(次の数字の下限)は今付け加えた3です。

今の数列の長さがn未満の場合は、(数字の下限)~(数字の上限m)を付け加えた新しい数列をそれぞれすべて、再びdfs(今つくった数列、今つくった数列の長さ、次の数字の最小値)をします。

今の数列が1,1,3で、上限$M = 4$ならば、
1,1,3,3
1,1,3,4
をdfsに渡すということです。

長さがnになって完成したら、得点を計算します。得点が出たら、ans = max(ans, score)として最大値を更新します。これは普通の問題と同じです。

最終的にすべてが終わったら、ansを返して本体のコードに戻ります。これをprintして終わりです。

def dfs(nums, length, min_lim):
# 返り値は、すべての数列の得点の最大値 ans です。
# numsは数列の本体、lengthは数字の何個目まで決めたか、min_limは次の数字の最小値
    ans = 0
    if length == n:
    # 数列が完成したので、得点を計算します
        score_ret = 0
        for a, b, c, d in req:
            # nums[0]を捨てたので、nums[b-1]...としなくて済みます
            if nums[b] - nums[a] == c:  
                score_ret += d
        return score_ret  # この数列の得点を返します
    else:
        # まだ数列が完成していません
        for nu in range(min_lim, m + 1):
        # 次の数字の下限はmin_limで、上限はmです
            new_nums = nums + [nu]  # 長さ1のリスト[nu]を連結します
            # lengthは1増えて、次の下限は今付け加えた数字nuです
            score = dfs(new_nums, length + 1, nu)
            ans = max(ans, score) # 最大の得点を更新します

    # すべてが終わったので、答えを返します
    return ans


n, m, q = list(map(int, input().split()))

# 問題文のa,b,c,dの「リストのリスト」reqです。[[a1,b1,c1,d1],[a2,b2,c2,d2],[a3,b3,c3,d3]]のようになります。
req = [list(map(int, input().split())) for _ in range(q)]

# 最終的に答えが返ってくるようにします。処理はすべてdfsメソッドでやってもらいます。
# 数列の番号と添字を一致させたいので、適当な長さ1のリストを最初の状態にしておきます。
# 例えばサンプル1の1,3,4は[-1, 1, 3, 4]になります。
ans = dfs([-1], 0, 1)
print(ans)

ABC165D『Floor Function』

↑↑↑↑↑↑↑ 編集リクエストの内容
問題ページ：D - Floor Function
むずかしさ：★★★☆☆
タイプ：数学

数学が得意な人なら直感的に答えがわかりそうな問題です。数学が得意でない私たちの場合、いろいろ試してみるとわかります。

やること

1. とりあえず試して考えてみる

ステップ1: とりあえず試して考えてみる

こういう問題は、とりあえず数字を代入して試してみるといいです。

$floor(Ax/B)$ は大きいほうが嬉しくて、$A\times{floor(x/B)}$は小さい方が嬉しいです。

後者は $x$ が $B$ の倍数ちょうどのときに大きくなることがわかります。そこで、色々試すと、$f(x+B)=f(x)$ であることがわかります。

したがって、 $x$ は $0～(B-1)$ の範囲だけ考えればいいです。このとき、引くほうの $A\times{floor(x/B)} = 0$なので、存在を忘れて構いません。

さて、 $floor(Ax/B)$ は $x$ が大きいほど大きくなるので、 $x$ は $B-1$ にすればいいです。ただし、$x$ は $N$ 以下という条件があるので、 $N$ と $B-1$ で小さいほうが答えになります。

コード

わかれば書くだけタイプの問題です。

    a, b, n = list(map(int, input().split()))
    x = min(b - 1, n) # b-1がいいけど、上限nが許してくれないこともあります。
    ans = int(a * x / b) # 計算します。後ろの項は0なので書かなくていいです。
    print(ans)