Zenn
🔖

AtCoder ZONeエナジー プログラミングコンテスト “HELLO SPACE” ZONE2021 個人的メモ

2021/05/02に公開
Python
#
競技プログラミング
AtCoder
tech

所感

abd3完
zone2021_score

A - UFO Invasion

countメソッドを使った．
https://docs.python.org/ja/3/library/stdtypes.html#str.count

S = input()

ans = S.count("ZONe")
print(ans)

B - Sign of Friendship

解は0.000から1000.000の範囲内で，解が正しいかの判定はO(N)で済みそう．
なので解を二分探索で求めれば全体の計算量はO(NlogN)で良さそう．
解の相対誤差が10^{-3}以下であればおｋとなっているので，解の探索範囲は10^7．

xy座標上で，UFOの座標を(H,D)，解の候補の座標を(0,n)とすると，その2点を結ぶ直線はy=\frac{H-n}{D}x+nで表される．
この式に各遮蔽物の(d,h)をyとxに代入してh\leq \frac{H-n}{D}d+nが成立するかを判定すればおｋ．

def is_ok(n: int):
    a = H - n  # y=ax+bのa
    a /= D
    if all(h <= a * d + n for d, h in obstacles):
        return True
    else:
        return False


N, D, H = map(int, input().split())
obstacles = [list(map(int, input().split())) for _ in range(N)]

low = 0
top = 1000
border = 10 ** (-4)
while abs(low - top) > border:
    mid = low + top
    mid /= 2
    if is_ok(mid):
        top = mid
    else:
        low = mid

print(low)

D - Message from Aliens

(SからTをつくる)→(重複を削除)とやったらTLEした．
なので，2つを同時に行う．

Rが来るたびにTを反転させていると，ABC199CのようにTLEしそう．
(Tを反転させてから末尾に文字を加える)=(Tの先頭に文字を加える)なので，そうすれば計算量が少なく済む．

from collections import deque

S = input()

ans = deque([])
is_reversed = False
for s in S:
    if s == "R":
        is_reversed ^= 1  # is_reversedフラグのTrueとFalseを反転(xor)
        continue
    if not ans:
        ans.append(s)
        continue

    if is_reversed:
        if ans[0] == s:
            ans.popleft()
        else:
            ans.appendleft(s)
    else:
        if ans[-1] == s:
            ans.pop()
        else:
            ans.append(s)

ans = "".join(ans)
if is_reversed:
    ans = ans[::-1]

print(ans)

E - Sneaking

ダイクストラ法

ダイクストラ法で解けそうだが，4種類の移動の内の4つ目がネックになる．
この移動は(R,C)=(4,1)としたとき下図の様な辺で表せる．
zone2021e_smallcase
この辺の数は，C\sum _{i=1} ^R (i-1)で表せるので，(500,500)のとき62,375,000本になる．
優先度付きキューを用いたダイクストラ法の計算量は頂点の数をV，辺の数をEとした時O((V + E)logV)で表される．
よって，問題文通りに実装するとpythonでは厳しい．
なので，高速化する．
想定解通りに4つ目の移動の辺を減らす方法を考える．
コストが1+iでは無く，iだとすると下図の様に辺を減らせる．
zone2021e_smallcase_translation
残りのコスト+1を表現するには，下図の様にすればおｋ．
つまり，4つ目の移動にのみ用いる頂点(裏とする)を用意し，元々あった頂点(表とする)から裏へ入るのにコスト+1がかかり，出るのにコスト+0が掛かる．
裏は(r-1,c)の頂点へコスト+1で移動できる辺が張られている．
これで，裏への出入りにコスト+1かかり，(r-i,c)への移動にコスト+iがかかるので，4つ目の移動を当初よりも少ない辺(大体2Rぐらい)で表現できた．
zone2021e_translation

from heapq import heappush, heappop


def solve():
    """関数に入れないとTLEする"""
    shortest = [[[INF] * C for _ in range(R)] for _ in range(2)]
    visited = [[[False] * C for _ in range(R)] for _ in range(2)]
    # queueには(現在のコスト，r座標，c座標，今裏にいるか？(真偽値))の情報を保持
    queue = [(0, 0, 0, 0)]
    while queue:
        dist, r, c, is_back = heappop(queue)
        if visited[is_back][r][c]:
            continue
        visited[is_back][r][c] = True
        if visited[0][-1][-1]:
            break

        move = []
        if is_back:
            move.append((0, 0, 0, 0))  # 裏から表へ
            if 0 < r:
                move.append((1, -1, 0, 1))  # 裏でr-1へ移動
        else:
            if c < C - 1:
                move.append((A[r][c], 0, 1, 0))       # 1つ目の移動
            if 0 < c:
                move.append((A[r][c - 1], 0, -1, 0))  # 2つ目の移動
            if r < R - 1:
                move.append((B[r][c], 1, 0, 0))       # 3つ目の移動
            if 0 < r:
                move.append((1, 0, 0, 1))  # 4つ目の移動のために裏へ移動

        for cost, dr, dc, go_back in move:
            tmp_dist = dist + cost
            nr = r + dr
            nc = c + dc
            if shortest[go_back][nr][nc] <= tmp_dist:
                continue
            shortest[go_back][nr][nc] = tmp_dist
            heappush(queue, (tmp_dist, nr, nc, go_back))

    return shortest[0][-1][-1]


R, C = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(R)]
B = [list(map(int, input().split())) for _ in range(R - 1)]
INF = 10 ** 18

print(solve())

参考

https://atcoder.jp/contests/zone2021/editorial/1202
https://qiita.com/ansain/items/8a2762446cdf2eb47759
https://ja.wikipedia.org/wiki/ダイクストラ法

Discussion