ABC349 with Python (A～E)

ABC349のA~E問題をpythonで解説していきます。

A - Zero Sum Game

問題

$1$ から $N$ の番号が付けられた $N$ 人の人がおり、この中で一対一の勝敗のつくゲームを何度か行いました。$N$ 人は最初にそれぞれ持ち点として $0$ を持っており、各ゲームでは勝者の持ち点が $1$ 増え、敗者の持ち点が $1$ 減ります（持ち点が負になることもあります）。最終的に人 $i\ (1\leq i\leq N-1)$ の持ち点が $A_i$ になったとき、人 $N$ の持ち点を求めてください。なお、ゲームの進行によらず最終的な人 $N$ の持ち点は一意に定まることが示せます。

考察

各ゲームを終えた後、勝者の持ち点が1増え、敗者の持ち点が1減るため、すべての人の持ち点の合計は必ず0になっています。したがって、$\sum_{i=1}^N A_i = 0$より、$A_N = -\sum_{i=1}^{N-1} A_i$で求まります。

コード

A.py

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

B - Commencement

問題

英小文字からなる文字列 $S$ が良い文字列であるとは、すべての $1$ 以上の整数 $i$ について次の性質が成り立つことであるとします。

• $S$ にちょうど $i$ 回現れる文字はちょうど $0$ 種類またはちょうど $2$ 種類ある

文字列 $S$ が与えられるので、 $S$ が良い文字列か判定してください。

考察

まず辞書を使って、$S$に現れるそれぞれの文字をカウントアップします。その後、それをもとに$i$ 回現れる文字はちょうど $0$ 種類またはちょうど $2$ 種類あるという条件を満たさないものがあったらNoと、そうでなかったらYesと出力すればよいです。

コード

B.py

from collections import defaultdict

S = list(input())
cnt = defaultdict(int)
for s in S:
    cnt[s] += 1

ans = defaultdict(int)
for val in cnt.values():
    ans[val] += 1
for val in ans.values():
    if val != 0 and val != 2:
        print("No")
        exit()
print("Yes")

C - Airport Code

問題

英大文字からなる長さ $3$ の文字列 $T$ が、英小文字からなる文字列 $S$ の 空港コード であるとは、 $T$ が $S$ から次のいずれかの方法により得られることとします。

• $S$ の長さ $3$ の（連続とは限らない）部分列をとり、それを英大文字に変換したものを $T$ とする
• $S$ の長さ $2$ の（連続とは限らない）部分列をとり、それを英大文字に変換したものの末尾に X を追加したものを $T$ とする

文字列 $S$, $T$ が与えられるので、 $T$ が $S$ の空港コードであるか判定してください。

考察

まず、$S$は受け取ってすぐに大文字変換しても問題ないのでそうします。また、$T$の末尾がXだった場合、それはないものとします。その後、$S$の文字を最初から順番に見ていき、$T$の文字と一致したら$T$の文字を一つ右に進めるといった風に尺取り法の要領で進めていき、最終的にすべてのTと一致し終えていたらYes、そうでなければNoとなります。

コード

C.py

S = list(input().upper())
T = list(input())
if T[-1] == "X":
    T = T[:-1]
LT = len(T)
LS = len(S)
i_s = 0
i_t = 0
while i_s < LS and i_t < LT:
    if T[i_t] == S[i_s]:
        i_t += 1
    i_s += 1
if i_t == LT:
    print("Yes")
else:
    print("No")

D - Divide Interval

問題

非負整数 $l,r\ (l<r)$ に対して、$l$ 以上 $r$ 未満の整数を順に並べた数列 $(l,l+1,\ldots,r-2,r-1)$ を $S(l,r)$ で表します。また、非負整数 $i,j$ を用いて $S(2^{i}j, 2^{i}(j+1))$ と表される数列を良い数列と呼ぶことにします。

非負整数 $L,R\ (L\lt R)$ が与えられます。数列 $S(L,R)$ をできるだけ少ない個数の良い数列に分割するとき、その個数と分割の方法を出力してください。より厳密には、以下を満たす非負整数の組の列 $(l_1,r_1),(l_2,r_2),\ldots,(l_M,r_M)$ が存在するような正整数 $M$ の最小値を求め、そのときの $(l_1,r_1),(l_2,r_2),\ldots,(l_M,r_M)$ を出力してください。

• $L=l_1<r_1=l_2<r_2=\cdots=l_M<r_M=R$
• $S(l_1,r_1),S(l_2,r_2),\ldots,S(l_M,r_M)$ は良い数列

なお、$M$ が最小となるような分割方法は一通りのみ存在することが示せます。

考察

一見すると眼をそむけたくなるような激ムズ問題ですが、よくよく読んでみるとただの貪欲法で解けることがわかります。具体的には、$i$の値が大きければ大きいほど１個の良い数列で広い範囲をカバーできるので、$R$を超えないギリギリの大きさの$i$を求め、それを使って$L$を更新します。あとは、$L$と$R$が一致するまでこれを行うだけです。

コード

D.py

L, R = map(int, input().split())
ans = []
while L < R:
    now = 1
    for i in range(61):
        if L % now == 0:
            j = L // now
            if (1 << i) * (j + 1) <= R:
                si = i
                sj = L // now
        now *= 2
    ans.append(((1 << si) * sj, (1 << si) * (sj + 1)))
    L = (1 << si) * (sj + 1)
print(len(ans))
for l, r in ans:
    print(l, r)

E - Weighted Tic-Tac-Toe

問題

$3 \times 3$ のマス目があります。上から $i$ 行目、左から $j$ 列目 $(1 \leq i,j \leq 3)$ のマスをマス $(i,j)$ と表します。マス $(i,j)$ には整数 $A_{i,j}$ が書かれています。ここで、 $\sum_{i=1}^3 \sum_{j=1}^3 A_{i,j}$ は奇数であることが保証されます。また、すべてのマスははじめ白で塗られています。

高橋君と青木君が、このマス目を使ってゲームを行います。ゲームでは、高橋君を先手として、二人が交互に以下の操作を行います。

• 白で塗られているマス $(i,j),(1\leq i,j \leq 3)$ を選ぶ（操作が行われる時点で、そのようなマスは必ず存在することが示せる）。操作をしているプレイヤーが得点 $A_{i,j}$ を得る。次に、操作をしているプレイヤーが高橋君ならば、マス $(i,j)$ を赤で、青木君ならば青で塗る。

各操作のあと、次の判定を行います。

• 赤または青の同じ色で塗られたマスが縦・横・斜めのいずれかの方向に $3$ つ連続する箇所があるか判定する。そのような箇所があれば、その時点でゲームを終了し、赤が $3$ つ連続しているならば高橋君が、青が $3$ つ連続しているならば青木君が勝利する。
• 白で塗られているマスが存在するか判定する。存在しなければ、その時点でゲームを終了し、その時点までに獲得した累計の得点が高い方のプレイヤーが勝利する。

ゲームは必ず有限回の操作で終了し、高橋君または青木君の一方が勝利することが示せます。両者が勝ちを目指して最適に行動するとき、どちらが勝つか判定してください。

考察

まず、自分がプレイヤーになった気持ちで最善の手を考えますが、絶対にTic-Tac-Toeとして負けないようにすること以外は、できるだけ大きな値をとるようにするくらいしか思いつきませんし、必ずしも一番大きな値からとっていくことが最善とは限らないので、貪欲法は厳しそうだと考えます。よって、どの手を打ったら最終的に勝敗がどうなるかを全探索することを考えます。これは、再帰を使えば簡単に実装することができます(関数呼び出しの多くなる再帰では、CPythonで提出したほうが速くなることがあります)。

感覚的になぜこれで勝ち負けが決まるのかわからない人は、一度最終盤面から考えてみることをお勧めします。例えば残りの空きマスが２マスの時、どちらに置いたら勝敗がどうなるかが決まることはわかると思います。ここで、当然自分が勝つことができるマスがあるのならばそこに置くべきで、そこに置いたら確定で勝つことができます。この情報を用いれば、残り空きマスが３マスの場合も勝敗を求めることができ、それをもとに残り４マス、残り５マス・・・と調べていけば、最終的に最初の晩面での勝敗がわかります。

コード

E.py

import sys
import copy

sys.setrecursionlimit(int(1e7))  # 再帰上限解放

A = [list(map(int, input().split())) for _ in range(3)]


def dfs(board, player, score):
    # 終了判定 ----------
    fin = True
    # 横
    for i in range(3):
        if 0 in board[i]:
            fin = False
        if board[i] == [player, player, player]:
            return player
        if board[i] == [-player, -player, -player]:
            return -player
    if fin:
        if score[0] > score[1]:
            return 1
        else:
            return -1
    # 縦
    for j in range(3):
        tmp = []
        for i in range(3):
            tmp.append(board[i][j])
        if tmp == [player, player, player]:
            return player
        if tmp == [-player, -player, -player]:
            return -player
    # 斜め
    if (
        board[0][0] == board[1][1] == board[2][2] == player
        or board[0][2] == board[1][1] == board[2][0] == player
    ):
        return player

    if (
        board[0][0] == board[1][1] == board[2][2] == -player
        or board[0][2] == board[1][1] == board[2][0] == -player
    ):
        return -player

    # ----------

    # 空きマスに駒を置く
    for i in range(3):
        for j in range(3):
            if board[i][j] == 0:
                new_board = copy.deepcopy(board)
                new_board[i][j] = player
                new_score = copy.deepcopy(score)
                if player == 1:
                    new_score[0] += A[i][j]
                else:
                    new_score[1] += A[i][j]
                result = dfs(new_board, -player, new_score)
                if result == player:  # 絶対に勝てる盤面に移行できるなら勝利
                    return player
    return -player


result = dfs([[0] * 3 for _ in range(3)], 1, [0, 0])
if result == 1:
    print("Takahashi")
else:
    print("Aoki")