AtCoder Beginner Contest 349の解説記事です。
ABC349 A – Zero Sum Game
問題
問題文の要約は以下の通りです。
問題の要約
\(N\) 人で一対一の勝敗のつくゲームを何度か行う。 最初にそれぞれ持ち点として 0 を持っており、各ゲームでは勝者の持ち点が 1 増え、敗者の持ち点が 1 減ります。最終的に人 \(i\) \(( 1 \le i \le N-1 )\)の持ち点が \(A_i\)になったとき、人 \(N\) の持ち点を求めよ。
解説
全員の得点の合計は0になります。
人 \(N\) の持ち点は人 \(N\) 以外の持ち点の合計を-1倍したものです。
解説
まず入力を受け取ります。この \(N\) は使用しません。
# 入力（使用しない）
N=int(input())入力の合計を-1倍して出力します。
# 入力の合計を-1倍して出力
print(-sum(list(map(int,input().split()))))解答
# 入力（使用しない）
N=int(input())
# 入力の合計を-1倍して出力
print(-sum(list(map(int,input().split()))))ABC349 B – Commencement
問題
問題文の要約は以下の通りです。
問題の要約
英小文字からなる文字列 \(S\) が良い文字列であるかどうか判定せよ。良い文字列であるとは \(S\) にちょうど \(i\) 回現れる文字は 0 種類または 2 種類であるときにいう。
解説
collections.Counterを用いて出現回数をカウントする。
解説
collections.Counterをimportします。
from collections import Counter入力を受け取ります。
# 入力
S=input()\(S\) の出現回数をカウント、その出現回数ごとに何種類の文字があるかをカウントします。
各出現回数に対して、その出現回数を持つ文字が0種類または2種類であるかチェックし答えを出力します。
# 文字列の出現回数をカウント
char_count = Counter(S)
# 出現回数ごとに何種類の文字があるかをカウント
frequency_count = Counter(char_count.values())
# 各出現回数に対して、その出現回数を持つ文字が0種類または2種類であるかチェック
for value in frequency_count.values():
if value != 0 and value != 2:
print('No')
exit()
print('Yes')解答
from collections import Counter
# 入力
S=input()
# 文字列の出現回数をカウント
char_count = Counter(S)
# 出現回数ごとに何種類の文字があるかをカウント
frequency_count = Counter(char_count.values())
# 各出現回数に対して、その出現回数を持つ文字が0種類または2種類であるかチェック
for value in frequency_count.values():
if value != 0 and value != 2:
print('No')
exit()
print('Yes')ABC349 C – Airport Code
問題
問題文の要約は以下の通りです。
問題の要約
与えられた英小文字の文字列 \(S\) から、特定の規則に従って生成された英大文字の長さ 3 の文字列 \(T\) が空港コードとして適切かどうかを判定せよ。空港コードであるとは、次のいずれかに該当する場合をいう。
\(S\) の長さ 3 の任意の部分列を取り出し、それを英大文字に変換して得られた文字列が \(T\) と一致する場合。
\(S\) の長さ 2 の任意の部分列を取り出し、それを英大文字に変換し、末尾にXを追加した文字列 \(T\) と一致する場合。
解説
\(T\) の 3 文字目がXであるときは最初の 2 文字、そうでないときは 3 文字が、\(S\) を大文字に変換した文字列の部分列と一致するかを判定する。
解説
入力を受け取ります。
# 入力
S = input()
T = input()\(S\) を大文字に変換します。
# Sを大文字に変換
S = S.upper() \(T\) の 3 文字目がXであるときは最初の 2 文字、そうでないときは 3 文字を確認します。
# Tの3文字目が'X'かどうか
if T[2] == 'X':
# Tの最初の2文字だけを確認する
t = T[:2]
else:
# Tの3文字を確認する
t=T\(S\) を大文字に変換した文字列の部分列と一致するかを判定します。
# tの現在のインデックス
i = 0
for s in S:
if s == t[i]:
i += 1
if i == len(t):
print('Yes')
exit()
print('No')解答
# 入力
S = input()
T = input()
# Sを大文字に変換
S = S.upper()
# Tの3文字目が'X'かどうか
if T[2] == 'X':
# Tの最初の2文字だけを確認する
t = T[:2]
else:
# Tの3文字を確認する
t=T
# tの現在のインデックス
i = 0
for s in S:
if s == t[i]:
i += 1
if i == len(t):
print('Yes')
exit()
print('No')ABC349 E – Weighted Tic-Tac-Toe
問題
問題文の要約は以下の通りです。
問題の要約
3 x 3 のマス目が与えられ、各マスには整数が記されています。全てのマスの数の合計は奇数です。
ゲームでは、二人のプレイヤー（高橋君と青木君）が交互に白いマスを選び、選んだマスに書かれた数値を得点として加算し、そのマスを自分の色（高橋君は赤、青木君は青）で塗ります。選択後、以下の判定が行われます。
任意の行、列、または対角線に同一色のマスが3つ連続していれば、その色のプレイヤーが勝利します。
全てのマスが塗られた場合、得点が高いプレイヤーが勝利します。
最適にプレイする場合の勝者を判定せよ。
解説
交互にマスを選ぶ動作を再帰関数で表現し、勝敗を判定する。
解説
- 状態の表現: 3×3のマス目を配列やリストで表し、各マスがどのプレイヤーによって選択されたか（または未選択か）を記録する。
- 再帰関数の定義: プレイヤーが交互にマスを選ぶ動作を再帰関数で表現します。この関数は次に行動するプレイヤーを引数として受け取ります。
- 勝敗の判定: 現在の盤面で勝敗が決しているかどうかを確認します。行、列、対角線に同色のマスが3つ並んでいるか、または全てのマスが塗られているかをチェックします。
- 最適な手の探索: 現在のプレイヤーが最も良い結果を得られる手を選ぶために、可能なすべての手を試してその結果を評価します。
- 結果の評価: 各選択肢について、その手が選ばれた場合のゲームの最終結果（勝利、敗北）を評価し、最適な手を選びます。
- 結果の出力: 最終的にどちらのプレイヤーが勝つかを出力します。
解答
def find_best_move(turn):
# 縦・横・斜めに3 つ連続する箇所があるか判定
for i in range(3):
# 横一列が同じ色かチェック
if colors[3*i] == colors[3*i+1] == colors[3*i+2] and colors[3*i] != -1:
return colors[3*i]
# 縦一列が同じ色かチェック
if colors[i] == colors[i+3] == colors[i+6] and colors[i] != -1:
return colors[i]
# 2つの対角線が同じ色かチェック
if colors[0] == colors[4] == colors[8] and colors[0] != -1:
return colors[0]
if colors[2] == colors[4] == colors[6] and colors[2] != -1:
return colors[2]
if all(color != -1 for color in colors):
# 全てのマスが塗られていれば、得点を比較して勝者を決める
score_takahashi = sum(A[i][j] for i in range(3) for j in range(3) if colors[i * 3 + j] == 0)
score_aoki = sum(A[i][j] for i in range(3) for j in range(3) if colors[i * 3 + j] == 1)
# 高橋君の方がスコアが高ければ0を、そうでなければ1を返す
if score_takahashi > score_aoki:
return 0
else:
return 1
# 空いているマスに色を塗る
for i in range(9):
if colors[i] == -1:
colors[i] = turn
if find_best_move(1 - turn) == turn:
# 自分の手番で勝てることが確定したら、その手を選ぶ
colors[i] = -1
return turn
# 状態を元に戻す
colors[i] = -1
# 自分の手番で勝てない場合は相手の勝ち
return 1 - turn
# 入力
A = [list(map(int, input().split())) for _ in range(3)]
# マスの状態を表す配列。-1は白、0は高橋君の赤、1は青木君の青を表す
colors = [-1] * 9
# ゲームを始める。高橋君からスタート
winner = find_best_move(0)
# 勝者を出力
print("Takahashi" if winner == 0 else "Aoki")