ABC295 A-D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、競技プログラミングコンテストのことです。

A-D問題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC295

A – Probably English

問題

A問題

N 個の文字列のうち一つ以上が and, not, that, the, you のいずれかと一致するかどうかを判定する問題です。

解説

素直に文字列を一つずつ見ていきましょう。

文字列がand, not, that, the, you のいずれかと一致すれば、Yesと出力し、exit()で処理終了します。

exit()が行われず for 文が終了すれば、条件を満たす文字列がなかったということですので、Noを出力します。

コード

N = int(input())
W = input().split()

for word in W:
    if word in {"and", "not", "that", "the", "you"}:
        print("Yes")
        exit()
print("No")

B – Bombs

問題

B問題

盤面に爆弾があり、そこから爆発後の盤面を出力する問題です。

解説

爆発前の盤面をはじめに複製しておきます。

片方は爆発前の盤面としてキープしておき、もう片方に爆発の結果を反映させていきます。前者の盤面をA、後者の盤面をBと呼ぶことにします。

盤面Aを1マスずつ調べ、爆弾があるマスの場合、その爆弾の影響があるマスかどうかを盤面Bで1マスずつ調べます。

つまり、盤面Aの縦方向、横方向と、盤面Bの縦方向、横方向で4重ループをさせることになります。縦や横の長さは20以下ですので、4乗しても160000以下であり、十分高速に処理することができます。このようなオーダー感覚は非常に大切です。

ところで盤面を複製する際、deepcopyではなく普通のcopyをしていまい、上手くいかずに時間を消費してしまいました。地味に要注意ですね。

【参考】浅いコピーと深いコピー（外部リンク）

コード

from sys import stdin
import copy
R, C = map(int, input().split())
A = [list(stdin.readline()[:-1]) for _ in range(R)]

B = copy.deepcopy(A)

for i in range(R):
    for j in range(C):
        if A[i][j].isnumeric():
            for k in range(R):
                for l in range(C):
                    if abs(i - k) + abs(j - l) <= int(B[i][j]):
                        B[k][l] = "."

for row in B:
    print(*row, sep="")

C – Socks

問題

C問題

N枚の靴下から何ペア作れるかを求める問題です。

解説

同じ種類ごとの靴下の枚数を求めれば良いです。dictionaryを使いましょう。

下記のようなイメージです。
{種類1の靴下: 2, 種類2の靴下: 3, 種類3の靴下: 1 }

これさえ作れれば、あとは各種類ごとに2で割った商を求めることで、できるペア数を求めることができます。

ではdictionaryを作っていきましょう。

各靴下を調べます。靴下がまだdictionaryに登録されていなければ、値1で登録します。すでに登録済みの靴下であれば、登録済みの値に1加算します。

この処理は、dictionaryのgetメソッドを使うことで簡単に表現できます。getメソッドでは第2引数でdictionaryに登録されていない場合の値を指定できるためです。今回は0を指定することで、まだ登録されていない靴下を値1で登録できるようにしています。

コード

N = int(input())
A = list(map(int, input().split()))

d = dict()
for num in A:
    d[num] = d.get(num, 0) + 1

ans = 0
for val in d.values():
    ans += val // 2

print(ans)

D – Three Days Ago

問題

D問題

解説

文字列が並べ替えによって同じ列を 2 度繰り返した列になるためには、文字列内の全ての文字が偶数回含まれている必要があります。

今回の問題では文字列 S の連続する部分文字列をすべて考える必要があります。そのためには累積和の発想を使うとよいでしょう。

今回、何を累積させるべきかというと、「0〜9の各数字の登場回数」です。更に言うと、重要なのは偶奇性であることから、「0〜9の各数字の登場回数（mod2）」を累積させましょう。

例として、5文字目までの「0〜9の各数字の登場回数（mod2）」と、11文字目までの「0〜9の各数字の登場回数（mod2）」が同じ結果になっていたとすると、6〜11文字目の部分文字列には全ての文字が偶数回含まれていることになります。

累積和のなかで、このように「0〜9の各数字の登場回数（mod2）」が同じ結果になっているものがどれだけあるかを調べればよいでしょう。

各パターンが何回登場したかを数えます。この部分はC問題と共通ですね。

あとは各パターンごとにnC2の計算をすることで、ペア数を求めることができます。

この問題のカギは、

「0〜9の各数字の登場回数（mod2）」を調べればよいことに気づけるか
部分列から累積和の発想に気づけるか

の２点です。良問ですね。

コード

S = input()

l = [[0] * 10 for _ in range(len(S) + 1)]

for i in range(1, len(S) + 1):
    l[i] = l[i - 1].copy()
    l[i][int(S[i - 1])] = (l[i][int(S[i - 1])] + 1) % 2

d = dict()
for row in l:
    s = ''.join(map(str, row))
    d[s] = d.get(s, 0) + 1

ans = 0
for val in d.values():
    ans += (val * (val - 1)) // 2

print(ans)