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

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

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

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

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

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

目次

ABC197 まとめ
A問題『Rotate』
B問題『Visibility』
C問題『ORXOR』

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

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

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

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

ABC197 まとめ

全提出人数: 7885人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	AB----	300	72分	5842(5638)位
400	AB----	300	32分	4789(4585)位
600	AB----	300	16分	3923(3719)位
800	ABC---	600	47分	3036(2834)位
1000	AB-D--	700	58分	2227(2027)位
1200	ABCD--	1000	73分	1576(1378)位
1400	ABC-E-	1100	84分	1093(898)位
1600	ABCDE-	1500	83分	744(556)位
1800	ABCDE-	1500	57分	502(321)位
2000	ABCDEF	2100	110分	331(170)位
2200	ABCDEF	2100	83分	224(82)位
2400	ABCDEF	2100	69分	148(37)位

色別の正解率

色	人数	A	B	C	D	E	F
灰	3455	98.1 %	64.7 %	6.0 %	10.5 %	0.4 %	0.1 %
茶	1334	99.7 %	96.8 %	35.4 %	36.7 %	2.0 %	0.1 %
緑	1079	99.3 %	99.1 %	75.3 %	64.1 %	14.7 %	0.9 %
水	607	99.5 %	99.2 %	93.6 %	77.4 %	63.3 %	7.1 %
青	369	99.7 %	99.7 %	98.1 %	93.2 %	94.8 %	39.6 %
黄	161	97.5 %	96.3 %	97.5 %	94.4 %	95.7 %	78.9 %
橙	36	100.0 %	97.2 %	97.2 %	91.7 %	94.4 %	91.7 %
赤	9	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %

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

私（うにだよ）の結果

D問題の幾何ができなくて悲しかったです。Eを通してから、中点が外接円の中心ということに気づきましたが、惜しいところでできませんでした。

A問題『Rotate』

問題ページ：A - Rotate
灰コーダー正解率：98.1 %
茶コーダー正解率：99.7 %
緑コーダー正解率：99.3 %

実装

S[1] + S[2] + S[0]を出力すれば良いです。スライスを使ってS[1:] + S[0] と書くと楽です。

コード

S = input()
print(S[1:] + S[0])

B問題『Visibility』

問題ページ：B - Visibility
灰コーダー正解率：64.7 %
茶コーダー正解率：96.8 %
緑コーダー正解率：99.1 %

考察

上下左右の四方向、 $(X,\ Y)$ の隣からスタートして、'#' にぶつかるまで '.' の数を数えます。

なお、この問題で与えられる $(X,\ Y)$ は、 $X$ が上下方向で、$Y$ が左右方向の座標です。学校で普通習うグラフと逆になっているので注意してください。

実装

マス目は二次元リストでもつことにします。入力の $X, Y$ は $1$ スタートですが、リストの $0$ スタートと合わせたいのではじめに $-1$ しておきます。

forループを上下左右方向の四つ書いて、rangeの範囲をうまく指定します。上方向と左方向はそれぞれreversed(range(X))、reversed(range(Y))と書くと楽です。（下のコードを見てください）

コード

H, W, X, Y = map(int, input().split())
X -= 1  # 0スタートにしたいので、-1します
Y -= 1  # Xは縦方向で、Yは横方向です。
grid = []

for _ in range(H):
    s = input()
    grid.append(s)

ans = 1  # (X, Y)自身も含むので、初期値は1にします
         # なお、四方向ごとに(X, Y)自身も含める実装の場合、1-4=-3が初期値になります

# 上　X-1 ～ 0
for row in reversed(range(X)):
    if grid[row][Y] == "#":
        # この先は見えないのでbreakします
        break
    else:
        ans += 1

# 下 X+1 ～ H-1
for row in range(X + 1, H):
    if grid[row][Y] == "#":
        break
    else:
        ans += 1

# 左 Y-1 ～ 0
for col in reversed(range(Y)):
    if grid[X][col] == "#":
        break
    else:
        ans += 1

# 右 Y+1 ～ W-1
for col in range(Y + 1, W):
    if grid[X][col] == "#":
        break
    else:
        ans += 1

print(ans)

C問題『ORXOR』

問題ページ：C - ORXOR
灰コーダー正解率：6.0 %
茶コーダー正解率：35.4 %
緑コーダー正解率：75.3 %

考察

はじめに大事なことを言います。この問題はORやXORの性質について何一つわからなくても解けます。ORの演算子 | と、XORの演算子を ^ さえ知っていれば、四則演算の+ - * /と同じように使って、問題文に書いてある通りに計算するだけです。

さて、この問題は区切り方をすべて試して、各区切り方ごとに答えを計算し、その中の最小値を出力する全探索問題です。区切り方の全探索には、いわゆる 『bit全探索』 という方法を使います。

区切る場所は $N-1$ 箇所あって、それぞれ区切るか区切らないかの $2$ 通りなので、区切り方は全部で $2^{N-1}$ 通りあります。$N\le{20}$ ですから、区切り方は最大で $2^{20-1}=2^{19}=524,288$ 通りあります。この程度であれば全探索が間に合います。

ある区切り方 $1$ つに対する答えを求めるために range(N) のforループを使うことにすると、計算量は $O(N)$ ですから、全体の計算量は $O(N・2^{N})$ になります。

実装

Pythonでbit全探索をするときは、itertoolsモジュールのproductを使うと楽です。具体的には、次のように書きます。

for bit in product((True, False), repeat=N - 1):
    # ここで今回の区切り方`bit`に対する答えを求めて、答えの最小値を更新する

こうすると、各要素がTrueかFalseのどちらかである長さ $N-1$ のタプルbitを、 $2^{N-1}$ 通り全探索ができます。

具体的には、bitは(True, False, False, True) という感じになっています。bit[i]がTrueであればA[i]とA[i+1]の間に区切り棒があり、Falseであればないことになります。

ある区切り方に対する答えの計算方法

この問題全体で求める答えをansとし、初期値は正の無限大としておきます。

ある一つの区切り方bitに対する答えを求める実装を考えます。

用意する変数

まず、二つの変数を用意します。どちらも初期値は $0$ です。

• 各区間の値のXORを格納する変数 score
• 現区間のORを取ったものを格納する変数cur

scoreは、最終的にこの区切り方に対する答えになります。

forループで計算する

forループで、数列の要素A[i]と区切り棒の有無bit[i]を $0$ から順に見ていきます。

• cur |= A[i]として、今の区間のORの計算をします
• bit[i]がTrueであれば、今の区間は終わりです。score ^= cur としてXORをとり、次の区間のためにcur = 0にします。
• bit[i]がFalseであれば、まだ今の区間が続くので、何もしません。

番兵として勝手に末尾に区切り棒を追加しておく

ところで上の方法では、何の工夫もしないと、最後の区間だけ別にコードを書く必要があります。

数列の要素は $N$ 個ありますが、区切り棒の入る位置は $N-1$ 箇所しかありません。ですので、配列外参照を防ぐために、数列の最後の要素A[N-1]はforループの外側で処理する必要があります。
さらに、区切り棒が来たときにXORを取るようにしていますから、最後の区間のXORもforループの外側で処理する必要があります。

これは面倒なので、勝手に番兵としてbitの末尾にTrueを追加してしまうと良いです。こうしてrange(N)で回せば配列外参照もせず、最後の区間も勝手にXORをとってくれます。

まとめると、次のコードになります。

for _bit in product((True, False), repeat=N - 1):
    bit = list(_bit) + [True]  # A[N-1]の右に常に区切り棒があることにします
    score = 0  # 各区間のXOR
    cur = 0  # 現区間のOR
    for i in range(N):
        cur |= A[i]  # | -> or
        if bit[i]:
            # 区切り棒が来たら、今の区間は終わりです
            score ^= cur  # ^ -> xor
            cur = 0  # 区間のorを0にリセットします

    # N番目の区切り棒を追加しているので、最後の区間を特別に処理せずに済みます

    ans = min(ans, score)  # 最小値を更新します

コード

実行時間制限について

なお、この問題はPythonだと実行時間制限が厳しいので、次のどちらかの工夫をする必要があります。

• メインコードを関数化する（名前空間のスコープが狭くなり、高速化します）
• PyPy3で提出する（Python 3.7以降の機能が使えないことにだけ注意して、何も考えずそのまま提出するだけでいいです）

コード1: 末尾に区切り棒（番兵）を追加する場合

下のコードはPythonだと1300ms程度、PyPyだと300ms程度で通ります。

def solve():
    from itertools import product

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

    ans = float('INF')

    for _bit in product((True, False), repeat=N - 1):
        bit = list(_bit) + [True]  # A[N-1]の右に常に区切り棒があることにします
        score = 0  # 各区間のXOR
        cur = 0  # 現区間のOR
        for i in range(N):
            cur |= A[i]  # | -> or
            if bit[i]:
                # 区切り棒が来たら、今の区間は終わりです
                score ^= cur  # ^ -> xor
                cur = 0  # 区間のorを0にリセットします

        # N番目の区切り棒を追加しているので、最後の区間を特別に処理せずに済みます

        ans = min(ans, score)  # 最小値を更新します

    print(ans)


solve()

コード2: 末尾に区切り棒（番兵）を追加しない場合

もし番兵として一番右の区切り棒を追加しない場合、下のコードになります。大して変わらないといえば変わらないですが、ちょっとミスが起きやすいかもしれません。

def solve():
    from itertools import product

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

    ans = float('INF')

    for bit in product((True, False), repeat=N - 1):
        score = 0  # 各区間のXOR
        cur = 0  # 現区間のOR

        # 区切り棒の入る位置はrange(N-1)、つまり 0～N-2番までしかないです
        for i in range(N-1):
            cur |= A[i]  # | -> or
            if bit[i]:
                # 区切り棒が来たら、今の区間は終わりです
                score ^= cur  # ^ -> xor
                cur = 0  # 区間のorを0にリセットします

        # ここでA[N-1]と最後の区間の処理をします
        cur |= A[N-1]
        score ^= cur

        ans = min(ans, score)  # 最小値を更新します

    print(ans)


solve()