ABC201 参加記録

• 4完2ペナ 80分でした

A - Tiny Arithmetic Sequence

数列は増加列でも減少列でも良いので、ソートして差分が等しければ作れると判断できます。

B - Do you know the second highest mountain?

python では、列を指定してソートできるので、それを使います。 list.sort(key=lambda x: x[1], reverse=True) で書けます。

N = int(input())
l = []
for _ in range(N):
    S, T = input()[:-1].split()
    T = int(T)
    l.append((S, T))

l.sort(key=lambda x: x[1], reverse=True)
print(l[1][0])

C - Secret Number

全探索のやり方が思い浮かばなかったのは反省です。。 本番では、丸の数が 5 個以上の場合は答え 0 、4個のときは、3個のときは、...とそれぞれで場合の数を求めて加算しました。 使う数字の種類で並び替えの計算が変わるので、それぞれで計算する方針です。これは(工夫次第で短くはなると思いますが)実装の時間が取られますね。。

全探索の方針は、0000〜9999 を順に調べて、全ての o が含まれているかどうかチェックする方針です。 こちらの方が考え方も実装もシンプルです。

D - Game in Momotetsu World

このような勝ち負けのゲームでは後ろから考えていくのがセオリーのようです。それに従って、右下のマスから左上に戻るように探索します。

各マスで、 を考えます。高橋くんは、この値を最大化するように動こうとし、青木くんはこれを最小化するように動こうとします。便宜上、この値をスコアと呼びます。

高橋くんが移動可能なマスと青木くんが移動可能なマスは固定されているので、分けて考えてしまいます。高橋くんは位置 h と w の偶奇が異なるマスに移動可能で、青木くんは偶奇が一致しているマスに移動できます。

高橋くんが移動可能なマスでは、スコアは最小化の更新を行います。青木くんが移動可能なマスでは最大化の更新です。高橋くんは自分が移動できるマスのスコアのうち高い方を選んで移動し、青木くんは自分が移動できるマスのスコアのうち小さい方を選んで移動します。

最終的に、最初の左上のマスから、高橋くんの移動可能なマスのスコアの最大値を見て勝ち負けを判断することができます。

回答コード

import sys

input = sys.stdin.readline
dig = [(-1, 0), (0, -1)]

H, W = map(int, input().split())
field = []
for _ in range(H):
    tmp = list(input()[:-1])
    field.append(tmp)
field[0][0] = '*'

if H == 1 and W == 1:
    print('Draw')
    return

check = [[float('inf')] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if i%2 == j%2: check[i][j] = -float('inf')

if (H-1)%2 == (W-1)%2: check[H-1][W-1] = -1 if field[H-1][W-1] == '+' else 1
else: check[H-1][W-1] = 1 if field[H-1][W-1] == '+' else -1

for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        base = check[h][w]
        for dh, dw in dig:
            i = h + dh
            j = w + dw
            if not (0 <= i < H and 0 <= j < W):
                continue
            tmp = field[i][j]
            if i%2 == j%2: check[i][j] = max(check[i][j], base - (tmp == '+') + (tmp == '-'))
            else: check[i][j] = min(check[i][j], base + (tmp == '+') - (tmp == '-'))

res = check[0][0]
if H > 1: res = max(check[1][0], res)
if W > 1: res = max(check[0][1], res)

if res > 0:
    ans = 'Takahashi'
elif res < 0:
    ans = 'Aoki'
else:
    ans = 'Draw'
print(ans)