[ABC295 Python]AtCoder Beginner Contest 295A～D問題Python解説

A問題

A - Probably English

# 入力
N = int(input())
W = list(input().split())
# 全ての文字列を順番に見ていく
for i in W:
    # もし、いずれかと一致するなら
    if i in ["and", "not", "that", "the", "you"]:
        # その時点でYesと出力してプログラムを終了する
        print("Yes")
        exit()
# 一度も一致しない場合はNoと出力する
print("No")

Wのリストの中に、"and", "not", "that", "the", "you"
が入っているかどうかを確認します。

Wを先頭から見ていって、
"and", "not", "that", "the", "you"が入っていた時点でYesが確定します。
条件に見合わない場合Noと出力します。

B問題

B - Bombs

# インポート
from collections import defaultdict
# 入力
R, C = map(int, input().split())
B = [list(input()) for _ in range(R)]
# 爆弾の保存する辞書
bombs = defaultdict(list)
# 全てのマスの中で、爆弾になるマスの座標を威力ごとに保存する
for r in range(R):
    for c in range(C):
        if B[r][c] != "." and B[r][c] != "#":
            bombs[int(B[r][c])].append([r, c])

# 全てのマスについて爆発の班にないかどうかを確認する
for r1 in range(R):
    for c1 in range(C):
        for power in bombs:
            for bomb in bombs[power]:
                r2 = bomb[0]
                c2 = bomb[1]
                if abs(r1-r2)+abs(c1-c2) <= power:
                    B[r1][c1] = "."
# マス目を1行ずつ出力する
for b in B:
    print("".join(b))
        

B問題にしては難易度が高い問題でした。

まずは爆弾がどこにあるかを爆弾の大きさごとに座標を保存しておきます。
数字を見つけるのは大変なので、空きマスと壁どちらでもないマスを爆弾のマスとして、判断します。

次にすべてのマスを見ていき、
問題文のとおりマンハッタン距離より爆弾の威力が大きいかどうかを確認します。

今いる座標と爆弾とのマンハッタン距離が爆弾の威力より小さければ、今いる座標は空きマスに変化します。

C問題

C - Socks

# インポート
from collections import defaultdict
# 入力
N = int(input())
A = list(map(int, input().split()))
# 辞書型dを作成しておく
d = defaultdict(int)
# 靴下の色ごとに靴下の枚数をカウント
for i in range(N):
    d[A[i]] += 1

ans = 0
# 靴下の色ごとにペアができたら答えに加算
for i in d:
    ans += d[i]//2
# 答えを出力
print(ans)

まずは、靴下を色ごとにカウントします。
靴下は2枚でペアになるので、
2で割った商をペア数として加算しましょう。

D問題

D - Three Days Ago

# インポート
from collections import defaultdict
# 入力
S = input()
# 辞書型を定義
count01 = defaultdict(int)
# 最初は全部0
S_count = [0 for i in range(10)]
# でた数字をカウントしていく
# 例えば1が出たとすると、S_count[1] += 1 となる
count01["0000000000"] += 1
# 文字列Sを先頭から見ていき、
for i in range(len(S)):
    # 入力された文字S[i]に対応するS_countを2で割った余りを
    # 新たなS_count[S[i]]とする
    S_count[int(S[i])] = (S_count[int(S[i])]+1)%2
    # S_countを文字列化して
    S_count_list = "".join(list(map(str, S_count)))
    # 辞書型count01に文字列ごとに個数を数える
    count01[S_count_list] += 1
# 提出する答え
ans = 0
# 同じグループごとに、組合せを考える
for i in count01:
    ans += count01[i]*(count01[i]-1)//2
# 出力
print(ans)

2023/03/27追記しました。

問題文のとおり、ｌとｒをlen(S)*len(S)で求めてしまうとTLEになりますので工夫が必要です。

まず最初に嬉しい列となる条件について考えてみましょう。
20230322を見ていただいてもわかるように、
「全ての文字の個数が2の倍数」
であることがうれしい列となる条件のようです。

ではこの条件を満たすのはどのようなときか、
具体的には、
「文字列Sを先頭から見ていき、これまで出てきた文字の個数が
奇数→奇数、もしくは偶数→偶数である」
この時にS[l:r]は嬉しい列となります。

奇数偶数が変わらなかったときには、
その間に確実に偶数個(0も含む)の該当する文字が含まれていることになります。
確実に奇数個含まれていることはないと言い切れる訳ですね。

嬉しい文字列になる箇所が見つかれば、
その組み合わせ分嬉しい列が作成されるので、
(スクリプト通りにいけば、
例えば、"000000000"の箇所が3か所あれば、その組み合わせで、
3通りの嬉しい列が生まれる)
その個数の合計値が今回の答えとなります。