LoginSignup
17
15

More than 1 year has passed since last update.

@u2dayo

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

Last updated at Posted at 2021-05-15

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

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

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

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

よかったらLGTMしていただけると、私のやる気がでます！

目次

ABC201 まとめ
A問題『Tiny Arithmetic Sequence』
B問題『Do you know the second highest mountain?』
C問題『Secret Number』
D問題『Game in Momotetsu World』

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

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

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

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

ABC201 まとめ

全提出人数: 8739人

パフォーマンス

パフォ AC 点数 時間 順位(Rated内)
200 AB---- 300 29分 6533(6276)位
400 AB---- 300 11分 5329(5072)位
600 ABC--- 600 98分 4346(4093)位
800 ABC--- 600 58分 3348(3095)位
1000 ABC--- 600 34分 2445(2193)位
1200 ABC--- 600 17分 1724(1475)位
1400 ABCD-- 1000 76分 1187(944)位
1600 ABCD-- 1000 36分 808(574)位
1800 ABCDE- 1500 107分 522(326)位
2000 ABCDE- 1500 74分 346(170)位
2200 ABCDE- 1500 55分 229(82)位
2400 ABCDE- 1500 43分 168(38)位

色別の正解率

色 人数 A B C D E F
灰 3873 95.4 % 86.5 % 24.5 % 1.1 % 0.4 % 0.0 %
茶 1610 99.4 % 99.3 % 71.5 % 5.0 % 1.7 % 0.0 %
緑 1179 99.8 % 99.7 % 90.9 % 24.5 % 6.4 % 0.2 %
水 674 99.8 % 100.0 % 99.0 % 63.6 % 23.7 % 0.3 %
青 336 99.4 % 99.4 % 98.8 % 85.7 % 60.1 % 3.0 %
黄 189 97.9 % 97.9 % 96.8 % 90.5 % 75.1 % 19.1 %
橙 45 97.8 % 97.8 % 95.6 % 97.8 % 97.8 % 80.0 %
赤 24 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 91.7 %

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

私（うにだよ）の結果

screenshot.61.png

どうしてこうなった

screenshot.63.png

A問題『Tiny Arithmetic Sequence』

問題ページ：A - Tiny Arithmetic Sequence
灰コーダー正解率：95.4 %
茶コーダー正解率：99.4 %
緑コーダー正解率：99.8 %

実装

入力をリストとして受け取って、ソートします。そして、問題文通り $A_3 - A_2 = A_2 - A_1$ かどうか判定します。

コード

def main():
    A = list(map(int, input().split()))
    A.sort()

    if A[1] - A[0] == A[2] - A[1]:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

B問題『Do you know the second highest mountain?』

問題ページ：B - Do you know the second highest mountain?
灰コーダー正解率：86.5 %
茶コーダー正解率：99.3 %
緑コーダー正解率：99.7 %

実装

リストLに、$(T_i,\ S_i)$ のタプルを入れます。これをL.sort(reverse=True)で降順にソートすると、$T_i$ が大きい順にソートされます。$2$ 番目に高い山の名前はL[1][1] です。

コード

def main():
    N = int(input())
    L = []

    for _ in range(N):
        s, t = input().split()
        t = int(t)
        L.append((t, s))
    L.sort(reverse=True)
    print(L[1][1])


if __name__ == '__main__':
    main()

C問題『Secret Number』

問題ページ：C - Secret Number
灰コーダー正解率：24.5 %
茶コーダー正解率：71.5 %
緑コーダー正解率：90.9 %

考察

がんばれば数学的に解くこともできますが、$4$ 桁の暗証番号は $0000$ ～ $9999$ の $1$ 万通りしかないので、全部の暗証番号の候補に対して条件を満たすかチェックして、答えがいくつか数えればいいです。

実装

暗証番号や判定はすべて文字列で行うと楽です。

下のように書くと、文字列で"0000"～"9999"を生成することができます。

for i in range(10000):
    s = str(i).zfill(4)

文字列sに特定の文字charが含まれていること判定するには、if～inを使えばできます。

if char in s:

反対に、文字列sに特定の文字charが含まれていないこと判定するには、if～not inを使えばできます。

if char not in s:

入力 $S$ から、確実に含まれている文字（"0"～"9"）のリストO、含まれていない文字のリストXを作ります。

  • 確実に含まれている数字のリスト（["0", "1", "2"])
  • 確実に含まれていない数字のリスト（["6", 7", "8", "9"]）

そして、以上のif文で $1$ 万通りの暗証番号に対してチェックすればいいです。

コード

def main():
    def judge(s):
        for o in O:
            # oはsに確実に含まれています
            if o not in s:
                return False
        for x in X:
            # xはsに確実に含まれていません
            if x in s:
                return False
        return True

    S = input()
    O = []
    X = []

    for i, char in enumerate(S):
        if char == "o":
            O.append(str(i))
        elif char == "x":
            X.append(str(i))

    ans = 0

    for i in range(10000):
        s = str(i).zfill(4)
        if judge(s):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

D問題『Game in Momotetsu World』

問題ページ：D - Game in Momotetsu World
灰コーダー正解率：1.1 %
茶コーダー正解率：5.0 %
緑コーダー正解率：24.5 %

考察

ルールの言い換え

ゲームの勝敗は$（高橋くんの点数）-（青木くんの点数）$の符号で決まります。プラスなら高橋くんの勝ち、マイナスなら青木くんの勝ち、0なら引き分けです。

そこで、ルールを次のように言い換えます。

『全体の点数が0点からスタートします。高橋君が+のマスを踏んだら+1点、-のマスを踏んだら-1点されます。青木君が+のマスを踏んだら-1点、-のマスを踏んだら+1点されます。最終的な点数がプラスなら高橋君の勝ち、マイナスなら青木君の勝ち、0点なら引き分けです。』

このルールでは、高橋くんは点数の最大化、青木くんは点数の最小化が目的になります。

ゲームDPで解ける

このようにルールを言い換えたことで、いわゆる『ゲームDP』で解くことができます。なぜなら

  • 移動先の点数がどちらも確定しているマスの勝敗も確定する
  • 一番右下のマスの点数が0点に確定している（動けないので）

よって、一番右下から点数が確定しているマスを広げていけば、最終的に一番左上の点数を確定させることができるからです。

実装

高橋くんからゲームをはじめると、スタート地点からの移動回数が偶数回のマスでは高橋くん、奇数回のマスでは青木くんの手番になります。

しかし、手番の処理を入れると面倒でバグるので、すべてのマスについて、高橋くん、青木くんからスタートしたときの勝敗をどちらも求めてしまいます。

定義とDPの遷移

$grid[row][col]：$$(row,\,col)$ が + なら $+1$、- なら$-1$
$dp_{first}[row][col]$：$(row,\,col)$ から高橋くんの手番でゲームを開始して、両者が最適な行動をとった際の最終的な点数
$dp_{second}[row][col]$：$(row,\,col)$ から青木くんの手番で〃

最終的な答え：$dp_{first}[0][0]$（一番左上のマスから高橋くんの手番でゲームを開始して、両者が最適な行動をとった際の最終的な点数） の符号

$(row,\, col)$ からは、マス目の外に出ない限り、$(row+1,\, col)$ （下）か $(row,\, col+1)$ （右）に移動することができます。

高橋くんのDP

  • 点数の最大化が目的
  • 移動すると $+grid[row][col]$ 点得る
  • 移動した先では、青木くんの手番になる

$dp_{first}[row][col] = max(dp_{second}[row+1][col] + grid[row+1][col], dp_{second}[row][col+1] + grid[row][col+1])$

ただし、マス目の外に出る移動は $-\infty$ 点とする

青木くんのDP

  • 点数の最小化が目的
  • 移動すると $-grid[row][col]$ 点得る（符号が反転することに注意）
  • 移動した先では、高橋くんの手番になる

$dp_{second}[row][col] = min(dp_{first}[row+1][col] - grid[row+1][col], dp_{first}[row][col+1] - grid[row][col+1])$

ただし、マス目の外に出る移動は $+\infty$ 点とする

コード

PythonではTLEになるので、PyPyで提出してください。

解説のコード

def main():
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        _s = input()
        r = [1 if char == "+" else -1 for char in _s]
        grid.append(r)

    INF = float("INF")
    dp_first = [[0] * W for _ in range(H)]  # 高橋くんからゲームをはじめたとき
    dp_second = [[0] * W for _ in range(H)]  # 青木くんからゲームをはじめたとき
    for row in reversed(range(H)):
        for col in reversed(range(W)):
            if row == H - 1 and col == W - 1:
                #  右下が-INFやINF点になるのを防ぐため
                continue

            # 先攻
            s1, s2 = -INF, -INF  # 点数の最大化が目的なので、負の無限大で初期化
            if row + 1 < H:
                s1 = dp_second[row + 1][col] + grid[row + 1][col]
            if col + 1 < W:
                s2 = dp_second[row][col + 1] + grid[row][col + 1]
            dp_first[row][col] = max(s1, s2)

            # 後攻
            s1, s2 = INF, INF # 点数の最小化が目的なので、負の無限大で初期化
            if row + 1 < H:
                s1 = dp_first[row + 1][col] - grid[row + 1][col]
            if col + 1 < W:
                s2 = dp_first[row][col + 1] - grid[row][col + 1]
            dp_second[row][col] = min(s1, s2)

    x = dp_first[0][0]
    if x == 0:
        print("Draw")
    elif x > 0:
        print("Takahashi")
    else:
        print("Aoki")


if __name__ == '__main__':
    main()

おまけ：『配るDP』コード

こっちのほうがいいかもしれません。

def main():
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        _s = input()
        r = [1 if char == "+" else -1 for char in _s]
        grid.append(r)

    INF = float("INF")
    dp_first = [[-INF] * W for _ in range(H)]  # 高橋くんからゲームをはじめたとき
    dp_second = [[INF] * W for _ in range(H)]  # 青木くんからゲームをはじめたとき
    dp_first[-1][-1] = 0
    dp_second[-1][-1] = 0

    for row in reversed(range(H)):
        for col in reversed(range(W)):
            if row - 1 >= 0:
                dp_first[row - 1][col] = max(dp_first[row - 1][col], dp_second[row][col] + grid[row][col])
                dp_second[row - 1][col] = min(dp_second[row - 1][col], dp_first[row][col] - grid[row][col])
            if col - 1 >= 0:
                dp_first[row][col - 1] = max(dp_first[row][col - 1], dp_second[row][col] + grid[row][col])
                dp_second[row][col - 1] = min(dp_second[row][col - 1], dp_first[row][col] - grid[row][col])

    x = dp_first[0][0]

    if x == 0:
        print("Draw")
    elif x > 0:
        print("Takahashi")
    else:
        print("Aoki")


if __name__ == '__main__':
    main()
17
15
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
17
15