🔖

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

2021/05/01に公開約4,600字

所感

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}以下であればおkとなっているので,解の探索範囲は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が成立するかを判定すればおk.

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を表現するには,下図の様にすればおk.
つまり,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

ログインするとコメントできます