ABC349をPythonで（A～E）

AtCoder Beginner Contest 349の解答等のまとめ

A問題

Aの総和の正負を反転させたものが正解

A

input()
print(-sum(map(int, input().split())))

B問題

1. 各文字の使用個数を計算
2. 使用個数の個数を計算
3. 条件に適合するか調べる

B

d = dict()
for s_i in input():
    if s_i not in d:
        d[s_i] = 0
    d[s_i] += 1

count = [0] * 110
for val in d.values():
    count[val] += 1

print("Yes" if all(c_i in {0, 2} for c_i in count) else "No")

C問題

Tと同じ文字がSにあるか最初から確かめる
3文字使用されているか２文字使用かつ最後が$x$ならYes

C

s = input()
t = input().lower()

flag = 0
i = 0
for s_i in s:
    if s_i == t[i]:
        i += 1
    if i >= 3:
        break

print("Yes" if i >= 3 or i == 2 and t[-1] == "x" else "No")

D問題

$l$のビットを小さいほうから見て、立っているかつそれを切り上げても$r$以下なら切り上げる。超えたら打ち切り
その後、$r$を超えないように上から値を追加して$r$に収束させる

D

l, r = map(int, input().split())

ans = []
now = l
for _ in range(200):
    for i in range(61):
        if now >> i & 1:
            nxt = now + 2 ** i
            if nxt <= r:
                ans.append([now, nxt])
                now = nxt
            else:
                break

for i in range(60, -1, -1):
    if r >> i & 1 and not (now >> i & 1):
        ans.append([now, now + 2 ** i])
        now += 2 ** i

print(len(ans))
for a_i in ans:
    print(*a_i)

E問題

マルバツゲームを解く
全マス埋まったらその盤面のスコアを計算して判定する

たぶんどこかにあるマルバツゲームのコードをコピペしたら早かったと思う

E

from functools import lru_cache

a = [list(map(int, input().split())) for _ in range(3)]
lst = [[(1, 2), (3, 6), (4, 8)],
       [(0, 2), (4, 7)],
       [(0, 1), (5, 8), (4, 6)],
       [(4, 5), (1, 7)],
       [(3, 5), (1, 7), (0, 8), (2, 6)],
       [(3, 4), (2, 8)],
       [(7, 8), (0, 3), (2, 4)],
       [(6, 8), (1, 4)],
       [(6, 7), (2, 5), (0, 4)]]


@lru_cache(maxsize=None)
def three(P):
    p = []
    for _ in range(9):
        p.append(P % 3)
        P //= 3

    for i, j, k in [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]:
        if p[i] == p[j] == p[k] != 0:
            return p[i], p
    return 0, p


@lru_cache(maxsize=None)
def dfs(is_first=True, P=0):
    # その盤面をもらった人が勝つか
    turn = 1 if is_first else 2
    x, p = three(P)
    # print(is_first, x, p, P)
    if x != 0:  # 並んでいるところがあったら、もらった人は負け
        return False

    if 0 not in p:  # 最終盤面
        f, s = 0, 0
        for i in range(3):
            for j in range(3):
                if p[i * 3 + j] == 1:
                    f += a[i][j]
                elif p[i * 3 + j] == 2:
                    s += a[i][j]
        # print(f, s)
        return s > f

    else:
        lst_2 = []
        for i in range(9):
            if p[i] > 0:
                continue
            for l_i in lst[i]:
                if p[l_i[0]] == p[l_i[1]] and ((is_first and p[l_i[0]] == 1) or (not is_first and p[l_i[0]] == 2)):
                    return True

            lst_2.append(i)

        for i in lst_2:
            f = dfs(is_first ^ True, P + (3 ** i * turn))
            if not f:
                return True

    return False


flag = dfs()

print("Takahashi" if flag else "Aoki")