ABC307をPythonで解いてみたよ。(A～E問題)

AtCoder Beginners Contest 307 (ABC307) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。

A - Weekly Records

問題ページ

考察

左から$7$個ずつ数を取ります。
$A[l:r]$と書くと、$A[l]$～$A[r+1]$の数列を表すことができるのと、sum関数でリスト内の数の和を出せるのをつかって書きました。
他にもいろんな書き方があって、どの書き方でもokです。

コード

N = int(input())
A = list(map(int, input().split()))
ans = []
for i in range(N):
    ans.append(sum(A[7 * i:7 * (i + 1)]))
print(*ans)

B - racecar

問題ページ

考察

文字列の数$N$は最大でも$100$なので、相異なる$(i, j)$の組は全部で$100 \times 99 = 9900$通りしかありません。この程度の量なら、全パターンで回文かどうかを試してしまいます。
$S_i$と$S_j$をくっつけて回文になるのがあればYes、そうでなければNoです。
文字列の反転は$T[::-1]$と書けます、回文判定ではこれを使うことにしました。

コード

N = int(input())
S = [input() for _ in range(N)]

for i in range(N):
    for j in range(N):
        # 相異なるi, jだけを見る。
        if i == j:
            continue
        T = S[i] + S[j]
        if T == T[::-1]:
            print("Yes")
            exit()

print("No")

C - Ideal Sheet

問題ページ

ひとこと

実装がめちゃくちゃしんどいです。解けなくても気にしないでね。

問題の要約

透明なシートに黒ペンで模様を描いたのがシート$A$とシート$B$。
その2つを重ね合わせて、シート$X$に描かれてる模様とおなじのをつくれますか？
(上に出てきた3種類のシートはどれも回転させたり裏返したりするのはダメで、重ね合わせた後に黒い部分を一部切り取って別の模様にするのもダメ）

考察

制約を見ると、どのシートも辺の長さは最大で$10$です。高難度問題みたいなテクニカルなことをしなくても、ありえるものを全通り試してみる「全探索」がつかえそう。
全部が透明なシート$Y$を用意します。先にシート$A$を持ってきて、重ね合わせます。'#'の部分はシート$Y$でも'#'にしてあげます。シート$A$を離して今度はシート$B$をシート$Y$と重ね合わせます。先ほどとおなじようにシート$B$で'#'のところは'#'にしてあげます。シート$A$とシート$B$どっちについても、シート$Y$と重ね合わせるときの位置関係を全探索することにします。

まず、シート$A$とシート$Y$だけを考えます。
シート$Y$と被っている部分で'#'の部分があったら、シート$Y$のその部分を'#'に変えてあげます。
シート$A$を$(0, 0)$～$(Ha-1, Wa-1)$の領域に置きます。そしてシート$Y$を$(Ha, Wa)～(Ha+Hx-1, Wa+Wx-1)$の領域に置きます。(このあたりからどこかに図をメモしてみてね)
シート$A$を移動させていきます。$(0, 0)$の点にある部分が$(Ha+Hx-1,Wa+Wx-1)$に来るまで全探索します。それぞれについてシート$Y$を用意してあげて、シート$A$で'#'の部分はシート$Y$でも'#'にします。シート$Y$の一部分を切り取って別の模様をつくるのはダメなので、黒で塗った回数も数えておいて、塗った回数とシート$A$の黒マスの個数がちがったらダメということにします。
シート$B$についても同じように動かして、シート$Y$も'#'に変える部分は変えてあげます。

1つでも完成したシート$Y$がシート$X$と一緒ならYesを出力して、1つもなかったらNoを出力すればokです。

下のコードでもコメントをつけてるので、参考にしてみてください。

コード

# 2次元配列内の'#'の数を返す関数
def black_cnt(lis):
    cnt = 0
    for row in lis:
        cnt += row.count('#')
    return cnt


Ha, Wa = map(int, input().split())
A = [input() for _ in range(Ha)]
black_A = black_cnt(A)
Hb, Wb = map(int, input().split())
B = [input() for _ in range(Hb)]
black_B = black_cnt(B)
Hx, Wx = map(int, input().split())
X = [input() for _ in range(Hx)]


def is_ok(ia, ja, ib, jb):
    """
    ・シートAとシートYについて
    シートYが(Ha,Wa)～(Ha+Hx-1,Wa+Wx-1)の位置で、
    シートAが(ia,ja)～(ia+Ha-1,ja+Wa-1)の位置のとき

    ・シートBとシートYについて
    シートYが(Hb,Wb)～(Hb+Hx-1,Wb+Wx-1)の位置で、
    シートBが(ib,jb)～(ib+Hb-1,jb+Wb-1)の位置のとき
    """
    Y = [['.'] * Wx for _ in range(Hx)]
    cnt_a, cnt_b = 0, 0

    # シートYの各点が塗れるかどうかを調べる。
    for i in range(Hx):
        for j in range(Wx):
            di, dj = Ha + i - ia, Wa + j - ja
            if 0 <= di < Ha and 0 <= dj < Wa:
                if A[di][dj] == '#':
                    Y[i][j] = '#'
                    cnt_a += 1
            di, dj = Hb + i - ib, Wb + j - jb
            if 0 <= di < Hb and 0 <= dj < Wb:
                if B[di][dj] == '#':
                    Y[i][j] = '#'
                    cnt_b += 1
    
    # シートAについて、シートAにある'#'がすべて使われていなかったらアウト
    # シートBについてもおなじ
    if cnt_a != black_A or cnt_b != black_B:
        return False
    
    # シートXとシートYの一致判定
    for i in range(Hx):
        for j in range(Wx):
            if X[i][j] != Y[i][j]:
                return False
    return True


# シートAで、最初(0,0)だった点が(ia,ja)の点に移動している状態
for ia in range(Ha + Hx):
    for ja in range(Wa + Wx):
        # シートBで、最初(0,0)だった点が(ib,jb)の点に移動している状態
        for ib in range(Hb + Hx):
            for jb in range(Wb + Wx):
                if is_ok(ia, ja, ib, jb):
                    print("Yes")
                    exit()
print("No")

D - Mismatched Parentheses

問題ページ

考察

文字列Sの左端から順番に文字をスタックに入れていきます。
もし'('を入れるときは、変数$cnt$を$1$だけ増やします。
もし')'を入れるときは、スタックの中に'('がなかったらそのままスタックに入れて、'('があったらスタックの右側から'('が出てくるまで文字を取り出し続けます。
文字を見る回数は、1文字あたり多くても$2$回(スタックに入れるときと取り出すとき)なので、O(N)で十分間に合います。

コード

N = int(input())
S = input()
lst = []
cnt = 0  # lstの中にある'('の数
for s in S:
    if s == ')':
        if cnt > 0:
            cnt -= 1
            while True:
                el = lst.pop()
                if el == '(':
                    break
        else:
            lst.append(s)
    elif s == '(':
        cnt += 1
        lst.append(s)
    else:
        lst.append(s)
print(*lst, sep='')

E - Distinct Adjacent

問題ページ

考察

円環じゃなかったらどうするか考えてみます。
人$1$は$M$通り、人$2$は人$1$の数以外の数を渡せばよくて$M-1$通り、人$3$以降もみんな$M-1$通り。
全体で$M \times (M-1)^{N-1}$通りです。

ただし今回は円環です。上の数え方だと、人$1$と人$N$が同じ色になってるパターンも余分に数えちゃってます。なのでその余分に数えた分を引きます。
人$1$と人$N$が同じ色のパターンが何通りあるかを考えます。同じ色にするなら、人$1$と人$N$を1人の人だと考えてもパターンの数は変わらないので、そうすることにします。するとこれは$N-1$人の人に$M$通りの数を渡していくパターンの数になっています。
人が$N$人のときの答えを$f(N)$とすると、$f(N)=M*(M-1)^{N-1}-f(N-1)$になっているわけです。
この式をちゃんと詰めれば累乗の計算だけでO(logN)まで落とせるけど、今回はO(N)でも間に合うので、上の漸化式を計算していくことにします。

コード

MOD = 998244353

N, M = map(int, input().split())
f = [0] * (N + 1)
f[2] = M * (M - 1) % MOD
val = f[2]
for i in range(3, N + 1):
    val = val * (M - 1) % MOD
    f[i] = val - f[i - 1]
    if f[i] < 0:
        f[i] += MOD
print(f[N])