Zenn
🍣

[python] ABC184 個人的メモ [AtCoder]

2020/11/22に公開
Python
競技プログラミング
AtCoder
tech

ABC184

所感

abc3完
思ったよりも冷えなかった

A - Determinant 

#!/usr/bin/env python3
a, b = map(int, input().split())
c, d = map(int, input().split())

print(a * d - b * c)

B - Quizzes

不正解時に点数がマイナスにならない様にシミュレーションしてけばおｋ

#!/usr/bin/env python3
N, X = map(int, input().split())
S = input()

ans = X
for s in S:
    if s == "o":
        ans += 1
    else:
        ans = max(0, ans - 1)

print(ans)

C - Super Ryuma

落ち着いて場合分けを考えればおｋ
紙に書いて考えたら分かり易かった
80分かかったけど

コマの移動範囲は上下左右で対称
なので状況を簡単にするために始点を原点，移動方向を第1象限の方向に限定する

まず，斜め方向の移動のみ考える
図に斜め移動のみで到達できるマスを示した
例として(2,8)への移動例を示した
これより以下が分かる

  • c=dのマス(赤)は，斜め移動1回で到達できる
  • c-dが偶数のマス(青)は斜め移動2回で到達できる
  • c-dが奇数のマス(白)は斜め移動のみでは到達できない

しかし，コマはマンハッタン距離3以下の付近のマスにも移動できる
よって，コマは全てのマスに3手以内で到達できると分かる
なので，0,1,2,3手の4種類で終点の位置に応じて場合分けすればおｋ

  • 0手

    • 始点と終点が一致する

  • 1手

    • 赤マス
    • マンハッタン距離3以下

  • 2手

    • 青マス
    • 赤マスからマンハッタン距離3以下
    • マンハッタン距離6以下(白マスでも2手で行ける)

  • 3手

    • 上記以外

コンテスト中の提出はマンハッタン距離6以下の場合を考慮していない嘘解法だったのでafter_contestのテストケースでwa
なので直した

#!/usr/bin/env python3
a, b = map(int, input().split())
c, d = map(int, input().split())

# 原点スタートとする
c = abs(c - a)
d = abs(d - b)
res = abs(c - d)

if c == 0 and d == 0:
    ans = 0

elif c + d <= 3 or res == 0:
    ans = 1

elif res % 2 == 0 or res <= 3 or c + d <= 6:
    ans = 2

else:
    ans = 3

print(ans)

D - increment of coins

確率DP
正直良く分からん

f(i, j, k)=(金貨i枚，銀貨j枚，銅貨k枚の状態から答えへ至るのに必要な操作回数の期待値)とする
そうすると，以下の漸化式が得られる

f(i,j,k)=\frac{i\times (f(i + 1, j, k) + 1) + j\times (f(i, j + 1, k) + 1) + k \times (f(i, j, k + 1) + 1)}{i + j + k}

これを再帰関数で実装する
メモ化しないとTLEする
計算量はO(100 ^ 3)

lru_cacheは関数をメモ化してくれるデコレータ
ただし，辞書でメモ化するのでリストでメモ化するよりも実行速度が遅くなる

#!/usr/bin/env python3
from functools import lru_cache


@lru_cache(maxsize=None)
def func(a, b, c):
    res = 0
    if max(a, b, c) == limit:
        return res
    if a != 0:
        res += a * (func(a + 1, b, c) + 1)
    if b != 0:
        res += b * (func(a, b + 1, c) + 1)
    if c != 0:
        res += c * (func(a, b, c + 1) + 1)
    res /= a + b + c
    return res


A, B, C = map(int, input().split())
limit = 100

print(func(A, B, C))

E - Third Avenue

問題文通りにBFSを実装する
このままだとTLEする

同じ文字のテレポーターを複数回使うのは明らかに無駄
なので，1度使ったテレポーターは使わないようにする
これでおｋ

#!/usr/bin/env python3
from collections import deque, defaultdict

H, W = map(int, input().split())
margin = [["#"] * (W + 2)]
grid = margin + ["#" + input() + "#" for _ in range(H)] + margin

warp = defaultdict(list)
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if grid[i][j] == "." or grid[i][j] == "#":
            continue
        warp[grid[i][j]].append((i, j))

move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
seen = [[-1] * (W + 2) for _ in range(H + 2)]
queue = deque([(warp["S"][0][0], warp["S"][0][1], 0)])
while queue:
    i, j, time = queue.popleft()
    if seen[i][j] != -1:
        continue
    seen[i][j] = time
    if [(i, j)] == warp["G"]:
        break

    # 隣接マスへの移動
    for di, dj in move:
        ni = i + di
        nj = j + dj
        if grid[ni][nj] == "#":
            continue
        queue.append((ni, nj, time + 1))

    # テレポーター
    if grid[i][j] != ".":
        for k in warp[grid[i][j]]:
            ni, nj = k
            queue.append((k[0], k[1], time + 1))
        # テレポーターの複数回使用を除く
        del warp[grid[i][j]]

print(seen[warp["G"][0][0]][warp["G"][0][1]])

参考

Discussion