【ABC349】緑コーダーの競プロ参加記録 #13
今回はAtCoder Beginner Contest 349。使用言語はPythonです。
A問題 - Zero Sum Game
コンテスト中の提出
https://atcoder.jp/contests/abc349/submissions/52295409
$${N}$$人が 1 vs 1 のゲームを何度か行った。(勝ち: +1 点、負け: -1点)
人$${i}$$は$${A_i}$$点を持っている。$${(1 \leq i \leq N - 1)}$$
$${N}$$人目の得点を出力してね。
勝ちで +1、負けで -1 だと、ゲームの前後で 2 人の得点合計は変わりません。
はじめ全員が 0 点からスタートすることを考えると、$${N}$$人全体の合計得点は常に 0 点になります。
よって、$${N}$$人目の得点は、$${N-1}$$人の合計得点の符号を逆転したものです。
""" AC コード """
N = int(input())
A = list(map(int, input().split()))
ans = -sum(A)
print(ans)
「操作の前後で変わらないものを探す」って割と難しい考察を要求されている気がします。
B問題 - Commencement
コンテスト中の提出
https://atcoder.jp/contests/abc349/submissions/52300160
文字列$${S}$$が与えられる。
すべての正整数$${i}$$について、$${S}$$の中に$${i}$$回現れる文字の種類数が$${0}$$または$${2}$$かどうか判定してね。
$${i}$$の上限が決められていませんが、$${S}$$の長さが最大$${100}$$なので$${1 \leq i \leq 100}$$の範囲で$${i}$$を全探索します。
文字の種類ごとに出現数をカウントするのは dict の出番ですが、特に、標準ライブラリの collections モジュールから Counter を使うと楽です。
「$${i}$$回現れる文字が 0 種類でも 2 種類でもない」ケースが 1 回でもあればその時点で答えは 'No' です。
""" AC コード """
from collections import Counter
S = input()
D = Counter(S)
for i in range(1, 101):
cnt = 0
for k, v in D.items():
if v == i:
cnt += 1
if not(cnt == 0 or cnt == 2):
print('No')
exit()
print('Yes')C問題 - Airport Code
コンテスト中の提出
https://atcoder.jp/contests/abc349/submissions/52308239
文字列$${S}$$と、長さ$${3}$$の文字列$${T}$$が与えられる。
$${T}$$がどっちかの条件を満たすか判定してね。
条件 A: 「長さ$${3}$$の$${S}$$の部分列」が$${T}$$である。
条件 B: 「長さ$${2}$$の$${S}$$の部分列 + 'X' 」が$${T}$$である。
部分列とは、文字列$${S}$$からいくつか文字を選んで、順番はそのままで並べた文字列のことを指します。
$${S}$$の左から順に、$${T}$$に含まれる文字を順に最速でピックアップしていって、3 文字ピックアップできるなら答えは 'Yes' です。
先頭 2 文字しかピックアップできなくても、$${T}$$の 3 文字目が 'X' であれば答えは 'Yes' です。
$${S}$$は小文字、$${T}$$は大文字から構成されることに注意します。
""" 入力の文字種を揃える """
S = input()
T = input().lower()
N = len(S)
""" T の k 文字目まで作れるか調べる """
k = 0
for i in range(N):
if k >= 3:
break
if S[i] == T[k]:
k += 1
""" 判定 """
if k < 2:
print('No')
elif k == 2 and T[2] != 'x':
print('No')
else:
print('Yes')D問題 - Divide Interval
コンテスト中の提出
https://atcoder.jp/contests/abc349/submissions/52319519
$${l}$$以上$${r}$$未満の整数を順に並べた数列を$${S(l, r)}$$とする。
$${S(2^ij, 2^i(j+1))}$$は良い数列。
区間$${[L, R)}$$を、最適な良い数列の集合にして出力してね。
貪欲に解いてOK !
$${L}$$に着目して貪欲に解きます。
$${L}$$の素因数$${2}$$の個数を$${i}$$として、$${j = \Large{\frac{L}{2^i}}}$$とします。
$${L = 0}$$の場合は$${i = \infin}$$となってしまうので、$${2^i \geq 2^{60}}$$を満たすよう適当に$${i = 100}$$とでもしておきます。
このとき、$${2^i(j + 1) \leq R}$$でなければ、$${i}$$を減らしていきます。
$${i}$$を減らした分、$${j}$$を2倍ずつ増やすことに注意してください。
これで求まる$${(i, j)}$$が最適な$${S(2^ij, 2^i(j+1))}$$になります。
$${L}$$を$${2^i(j+1)}$$で更新し、$${L}$$と$${R}$$が一致するまで処理を繰り返します。
""" AC コード (貪欲法) """
L, R = map(int, input().split())
ans = []
while L < R:
i, j = 0, L
if j == 0:
i = 100
else:
""" 割り切れる限り 2 で割る """
while j % 2 == 0:
i += 1
j //= 2
while (2 ** i) * (j + 1) > R:
""" 割りすぎた分を戻す """
i -= 1
j *= 2
ans.append(((2 ** i) * j, (2 ** i) * (j + 1)))
L = (2 ** i) * (j + 1)
print(len(ans))
for res in ans:
print(*res)これをもっとスマートに実装したのが公式解説です。
実はセグ木
セグ木でなにかを求めるときに、演算処理をするノード (が表す区間) を列挙する問題です。
非再帰セグ木のコードをほぼそのまま実装して解きました。
""" AC コード (セグ木) """
L, R = map(int, input().split())
ans = []
p = 1
""" セグ木の一部 """
while L < R:
if L & 1 == 1:
ans.append((p * L, p * (L + 1)))
L += 1
if R & 1 == 1:
ans.append((p * (R - 1), p * R))
L >>= 1
R >>= 1
p *= 2
print(len(ans))
for res in sorted(ans):
print(*res)通常のセグ木ではツリーのサイズの半分である$${n}$$を加算しますが、今回は区間の復元時に結局$${n}$$を引くことになるので、しなくても問題ありません。（もちろん、してもよいです。）
""" 実際のセグ木だとこんな感じ """
L, R = map(int, input().split())
n = 1 << (R - 1).bit_length()
L += n
R += n非再帰セグ木のwhileループの補足
セグ木のクエリ処理において、区間の左端が右側ノードの場合、
左端は区間内なので演算する。
親は区間外領域 (左側ノード) の値を含み信頼できないので右にバトンを渡す。
また、区間の右端が右側ノードの場合、
自身は区間外なので左にバトンを渡す。
左隣は区間内なのでその値を演算する。
という挙動をしながら、親ノードへと登っていきます。
「右側ノードである」ことと「ノード番号の 1 ビット目が 1 である」ことは同値です。(1-index実装の場合)
セグ木として捉えると、貪欲解は「右側ノードになるまで上に登って、区間をはみ出していたら下に戻る」、「答えに追加したら右にバトンをわたす」ような動きをしています。
「右側ノードになるまで上に登る」というのは「$${L}$$が左端である区間のうち最大長のものを探す」ことと同じです。
E問題 - Weighted Tic-Tac-Toe
upsolve
https://atcoder.jp/contests/abc349/submissions/52379788
$${3 \times 3}$$のマス目で三目並べをする。
マス$${(i, j)}$$に整数$${A_{i, j}}$$が書かれている。
三目並べに勝つか、総得点の大きい方が勝ち。
2人のプレイヤーが最適に行動したとき、どちらが勝つか出力してね。
ゲーム理論の問題です。
この手の問題では、次の1手は先の展開も見据えて考えます。
あるターンの選択が最適かどうかを知るためにはその次のターンの盤面を知る必要があり、さらにその次のターンの…と続くことから再帰的に解くことができます。
現在の戦況が良いか悪いかを表すものとして評価値を使います。
ゲームの評価値$${Q}$$を「現在の盤面から最終的に得られる、自分の得点と相手の得点の差の最適値」とすると、手番が変わるごとに$${Q}$$の正負を反転することでお互いの評価値を表現できます。
（1P が +100 点で勝っているとき、2P 視点では -100 点です。）
三目並べに勝ったとき、すなわちビンゴになったときに $${+\infin}$$点 を得ることにすると、数値のまま勝ち負けも表現できます。
再帰関数を使って終盤から勝ち負けを決めておくと、ある手番のとき次の1手のうち最適である行動を選ぶことができます。
ここで、「最適である」とは「評価値が最大である」ということです。
初手の評価値が正の値であれば1P プレイヤーの勝ち、そうでなければ 2P プレイヤーの勝ちです。
"""
0 1 2
3 4 5
6 7 8
"""
BINGO = [
int('000000111', 2),int('000111000', 2),int('111000000', 2),
int('001001001', 2),int('010010010', 2),int('100100100', 2),
int('100010001', 2),int('001010100', 2)
]
INF = 1 << 60
def game_clear(t, a):
""" ビンゴができているか判定 """
for line in BINGO:
if (t & line == line) or (a & line == line):
return True
return False
def dfs(t, a, turn, point):
""" ネガマックス法 [point = (自分の点) - (相手の点)] """
if turn == 9:
return point
res = -INF
for i in range(9):
if (t >> i) & 1 == 0 and (a >> i) & 1 == 0:
p = point + A[i]
nt, na = t, a
if turn % 2 == 0:
nt |= (1 << i)
else:
na |= (1 << i)
if game_clear(nt, na):
return INF
res = max(res, -dfs(nt, na, turn + 1, -p))
return res
A = sum([list(map(int, input().split())) for _ in range(3)], [])
ans = dfs(0, 0, 0, 0)
if ans > 0:
print('Takahashi')
else:
print('Aoki')上のコードでは 1P プレイヤー、2P プレイヤーそれぞれの選択したマスをビットマスクで管理しましたが、ビンゴ判定ができればどのようにしてもよいです。
（たとえば、リストの$${i}$$番目の要素が 0 なら未選択、 1 なら 1P、2 なら 2P が選択…など。）
今回使った考え方はネガマックス法と言い、似たものにミニマックス法というものもあります。
以前ちょっとした記事も書いているのでよかったら読んでみてください。
あとがき
今回はABCD 4完 24分で 1480位、1392 perf でした。
E 問題は 1 か月前に勉強したアルゴリズムなのに解けなかったのはよくないですね。
ゲーム系の問題は再帰関数を使うと楽になるイメージなので、TLE に震えないよう Rust でも書けるようにしておこうかな。
ではまた～。
【更新履歴】
2024/04/14 (1時頃): 記事投稿。
2024/04/14 (21時頃): E 問題を追記。
2024/04/17 (19時頃): 図を追加。