LoginSignup
13
4

More than 1 year has passed since last update.

@u2dayo

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

Last updated at Posted at 2021-08-09

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

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

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

ご質問・ご指摘はコメントかツイッター、その他のご意見・ご要望などはマシュマロまでお気軽にどうぞ！

Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト : プレゼントしていただけると、やる気が出ます！

よかったらLGTMや拡散していただけると喜びます！

目次

ABC213 まとめ
A問題『Bitwise Exclusive Or』
B問題『Booby Prize』
C問題『Reorder Cards』
D問題『Takahashi Tour』
E問題『Stronger Takahashi』

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

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

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

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

ABC213 まとめ

全提出人数: 8091人

パフォーマンス

パフォ AC 点数 時間 順位(Rated内)
200 AB------ 300 24分 6029(5800)位
400 AB------ 300 8分 4976(4747)位
600 ABC----- 600 73分 4117(3890)位
800 AB-D---- 700 24分 3233(3008)位
1000 ABCD---- 1000 66分 2413(2190)位
1200 ABCD---- 1000 37分 1738(1518)位
1400 ABCD---- 1000 8分 1213(1005)位
1600 ABCDE--- 1500 72分 824(629)位
1800 ABCDE--- 1500 52分 551(367)位
2000 ABCDE--- 1500 37分 345(197)位
2200 ABCDE--- 1500 18分 200(98)位
2400 ABCDEF-- 2000 81分 123(46)位

色別の正解率

色 人数 A B C D E F G H
灰 3459 90.4 % 92.8 % 22.4 % 12.3 % 0.5 % 0.0 % 0.0 % 0.0 %
茶 1413 98.4 % 98.8 % 71.9 % 45.8 % 3.0 % 0.3 % 0.1 % 0.1 %
緑 1128 99.7 % 99.7 % 91.6 % 81.2 % 15.9 % 0.6 % 0.1 % 0.2 %
水 694 99.7 % 99.7 % 99.0 % 96.0 % 56.8 % 3.8 % 0.6 % 0.1 %
青 391 99.7 % 99.7 % 99.2 % 98.5 % 84.4 % 14.8 % 2.3 % 1.0 %
黄 176 96.6 % 96.0 % 94.9 % 95.5 % 84.1 % 31.2 % 5.7 % 2.3 %
橙 37 97.3 % 97.3 % 94.6 % 94.6 % 89.2 % 54.0 % 24.3 % 8.1 %
赤 21 95.2 % 95.2 % 95.2 % 95.2 % 90.5 % 90.5 % 66.7 % 33.3 %

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

A問題『Bitwise Exclusive Or』

問題ページ：A - Bitwise Exclusive Or
灰コーダー正解率：90.4 %
茶コーダー正解率：98.4 %
緑コーダー正解率：99.7 %

やることはXORを足し算や引き算に置き換えた問題と同じですが、初心者の方はXORを知らない人のほうが多いと思います。正解率もB問題より低いです。

考察

XORは演算子^を使うと計算できます。たとえば $A\mbox{ xor }C$​ を計算したいときは、A ^ Cと書けばいいです。これだけ知っていれば、XORが何か知らなくても解けます。

実装1: for文で全探索

問題文に「 $C$​​​ はただ $1$​​​ つ存在し、$0$​​​ 以上 $255$​​​ 以下であることが証明される」とあるので、$A \mbox{ xor }C=B$​​​​ となる $C$​​​ を、$0$​​​ ～ $255$​​​ までforループで全探索すればいいです。この方法はXORについて何も知らなくても解けます。

コード1: for文で全探索

A, B = map(int, input().split())
for C in range(256):
    if A ^ C == B:
        print(C)

実装2: XORの性質を利用して式変形

XORの性質を利用して式を変形すると、全探索せずに答えを求められます。その性質とは $2$​ つあって

  1. $X\mbox{ xor }X =0$
  2. $0\mbox{ xor }X = X$​​

です。$A\mbox{ xor } C = B$​ の両辺を $\mbox{xor } A$​ することで

$A\mbox{ xor }A \mbox{ xor } C = A \mbox{ xor }B$
$0\mbox{ xor }C = A\mbox{ xor }B$
$C = A\mbox{ xor }B$

となります。したがって、A ^ Bを出力すれば正解になります。

コード2: XORの性質を利用して式変形

A, B = map(int, input().split())
print(A ^ B)

B問題『Booby Prize』

問題ページ：B - Booby Prize
灰コーダー正解率：92.8 %
茶コーダー正解率：98.8 %
緑コーダー正解率：99.7 %

考察

  1. $2$​ 番目に大きいスコアを求める
  2. $2$​​​​ 番目に大きいスコアが元のリストの何番目か求めて、+1番の人（リストのインデックスは0スタートのため）

実装

  1. ソートして後ろから $2$​ 番目の要素が $2$​ 番目に大きいスコア
  2. A.index(b) + 1

コード

N = int(input())
A = list(map(int, input().split()))
A_sorted = sorted(A)
b = A_sorted[-2]  # 2番目に大きいスコア
print(A.index(b) + 1)  # 1始まりにするために+1する

C問題『Reorder Cards』

問題ページ：C - Reorder Cards
灰コーダー正解率：22.4 %
茶コーダー正解率：71.9 %
緑コーダー正解率：91.6 %

考察

例えば、この図の場合を考えてみましょう。( $H=9,W=6,N=6$ ​) 左図の赤い数字の書いてあるマスに数字の書いてあるカードがあります。

abc213c.png

カードの置いていない行・列を削除すると、マス目は右図の状態になります。カードの位置を $(行, 列)$​ とあらわすと、操作後のカードの位置はカード $1$​ から順に$(1,2),(2,2),(2,3),(3,1),(4,4),(5,3)$​​​になります。（右の赤い数字が書いてあるマスの位置）

左図のカードの置いてある行・列に、小さい順に割り振った青い数字と、右図の青い数字が対応しています。

この図の場合、

  • カードの置いてある行番号 $(2,3,5,6,9)$​ を $(1,2,3,4,5)$​
  • カードの置いてある列番号 $(1,2,3,4)$​ を $(1,2,3,4)$​

に変換できればいいです。

解き方

行と列の操作はお互いに関係がないので、行と列で $2$ 回同じことをすれば解けます。

  1. カードの行番号のリストRを受け取る
  2. Rから重複を省いて、小さい順にソートしたリストRsを用意する
  3. Rsをつかって、元の行番号が上から何番目に対応するかの辞書Rdを作る

なお、これは『座標圧縮』と呼ばれるテクニックです。

実装

Rから重複を省いてソートしたリストRsは、Rs = sorted(set(R))と書けば作れます。set型に変換して重複を省き、それをsortedでソートされたリストに変換します。

Rdは、Rs[i]: i + 1のdictです。rangeかenumerateを使って作ります。

コード

H, W, N = map(int, input().split())
R = []
C = []

for _ in range(N):
    r, c = map(int, input().split())
    R.append(r)
    C.append(c)

Rs = sorted(set(R))  # `set`で重複を省いてソートしたリスト`Rs`
Cs = sorted(set(C))

# Rd = {Rs[i]: i+1 for i in range(len(Rs))} と同じです
Rd = {x: i for i, x in enumerate(Rs, 1)}
Cd = {x: i for i, x in enumerate(Cs, 1)}

for r, c in zip(R, C):
    print(Rd[r], Cd[c])

D問題『Takahashi Tour』

問題ページ：D - Takahashi Tour
灰コーダー正解率：12.3 %
茶コーダー正解率：45.8 %
緑コーダー正解率：81.2 %

考察

『いまいる都市と道路で直接つながっている都市のうち、まだ訪れたことがない都市が存在するとき、そのような都市のうち番号が最も小さい都市へ移動する』とあるので、忘れずに辺をソートしておきます。

DFS（深さ優先探索）をして、答えのリストに頂点を追加していけば解けますが、以下の $2$ つの場合にリストに頂点を追加する必要があります。

  • その頂点にはじめて訪問したとき
  • その頂点から他の頂点に行って帰ってくるたび

なお、この問題で答える頂点番号の列のことを、オイラーツアーと呼びます。

実装

PyPyは再帰に弱いので、Pythonで提出してください。

sys.setrecursionlimitで再帰の深さの上限を増やさないとRE（実行時エラー）になります。この問題では最大で20万程度になるので、適当にそれ以上の数字を設定します。（20万の都市が一直線につながっている場合、深さが20万程度になる）

解説はしませんが、PyPyでも通せる非再帰版の実装も用意しました。

コード

再帰DFS

def main():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 最大で再帰の深さが2 * 10 ** 5程度になるので、それ以上に設定します

    # 木上のDFSなので、どの頂点から来たかを引数pで渡せば、訪問済みの頂点を覚えなくても済みます
    def dfs(u, p):
        ans.append(u)  # はじめて訪問したとき
        for v in edge[u]:
            if v != p:
                dfs(v, u)
                ans.append(u)  # 他の頂点に行って帰ってくるたび

    N = int(input())
    edge = [[] for _ in range(N + 1)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        edge[a].append(b)
        edge[b].append(a)

    # 小さい順にsortを忘れるとWAです
    for i in range(N + 1):
        edge[i].sort()

    ans = []
    dfs(1, -1)
    print(*ans)


if __name__ == '__main__':
    main()

非再帰版

がんばって非再帰で実装すると、PyPyでも通せます。

def main():
    def dfs():
        for i in range(N + 1):
            edge[i].sort(reverse=True)
        stack = [1]
        seen = [0] * (N + 1)
        seen[1] = 1
        while stack:
            u = stack.pop()
            if u > 0:
                ans.append(u)  # はじめて訪問したとき
                for v in edge[u]:
                    if not seen[v]:
                        seen[v] = 1
                        stack.append(-u)
                        stack.append(v)
            if u < 0:
                ans.append(-u)  # 他の頂点に行って帰ってくるたび

    N = int(input())
    edge = [[] for _ in range(N + 1)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        edge[a].append(b)
        edge[b].append(a)

    ans = []
    dfs()
    print(*ans)


if __name__ == '__main__':
    main()

E問題『Stronger Takahashi』

問題ページ：E - Stronger Takahashi
灰コーダー正解率：0.5 %
茶コーダー正解率：3.0 %
緑コーダー正解率：15.9 %

考察

グリッドの問題ではなくグラフの問題と考えて、頂点間に以下の $2$ 種類の辺があるとみなします。

  • 上下左右の . のマスにコスト $0$​ で移動できる辺
  • マンハッタン距離が $3$​ 以下のマスにコスト $1$​ で移動できる辺（マスの状態は . # どちらでも構わない）

マンハッタン距離が $3$​ 以下のマスとは、下図の@に対するoのマスのことです。つまり、上下左右に $3$ 回移動して到達できるマスのことです。周りがすべて壁であっても o のマスには $1$ 回の壁破壊で移動できます。逆に、それ以外のマスには $1$ 回の壁破壊では移動できません。

xooox
ooooo
oo@oo
ooooo
xooox

もしかすると o のなかに壁を壊さずコスト $0$ で移動できるマスもあるかもしれませんが、そのような場合もコスト $1$ でも移動できることにして構いません。（後述の01BFS、ダイクストラ法では、最短経路にはならない辺が含まれていても問題なく答えを求められます）

01BFS（またはダイクストラ法）で解ける

グラフの辺の貼り方がわかったので、ダイクストラ法か01BFSを使えばこの問題を解くことができます。今回は01BFSで解くことにします。

01BFSは、グラフにコストが $0$​ か $1$​ の辺​だけあるときに使える、ダイクストラ法の亜種です。

優先度付きキューの代わりに、BFSで使う両端キュー（deque）を使います。キューに要素を追加するときに、コスト $0$​​​ の辺を使う場合は先頭に、コスト $1$​​​ の辺を使う場合は末尾に要素を追加します。すると、優先度付きキューと同じことを両端キューで実現できます。

優先度付きキューのコードを貼る手間がなくなり、計算量が $O(HW\ logHW)$ ​​​​から $O(HW)$​​​​ に改善されます。​

コード

def main():
    # 上下左右1マス移動と、上下左右3マス以内移動の方法をあらかじめ作っておく
    from itertools import product  # mov3の内包表記で二重ループを書きたくなかったので
    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]
    mov1 = tuple((r, c) for r, c in zip(dr, dc))
    mov3 = tuple((r, c) for r, c in product(range(-2, 3), repeat=2) if 1 <= abs(r) + abs(c) <= 3)

    def solve():
        from collections import deque

        dist = [[10 ** 7] * W for _ in range(H)]
        dist[0][0] = 0
        deq = deque()
        deq.appendleft((0, 0, 0))

        while deq:
            cost, r, c = deq.popleft()

            for ar, ac in mov1:
                nr, nc = r + ar, c + ac
                if 0 <= nr < H and 0 <= nc < W:
                    if grid[nr][nc] == "." and cost < dist[nr][nc]:
                        dist[nr][nc] = cost
                        deq.appendleft((cost, nr, nc))

            for ar, ac in mov3:
                nr, nc = r + ar, c + ac
                if 0 <= nr < H and 0 <= nc < W:
                    if cost + 1 < dist[nr][nc]:
                        dist[nr][nc] = cost + 1
                        deq.append((cost + 1, nr, nc))
        return dist[-1][-1]

    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        _r = input()
        grid.append(_r)

    print(solve())


if __name__ == '__main__':
    main()
13
4
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
13
4