ABC176

4問解いてもレーティングは伸びません

k-1番目まで条件を満たしている時、k-1番目の人は一番高い
ので、k番目の人の踏み台の高さを決める際にk-1番目とだけ比較すればOK
答えは10^14の桁になりうるけどPythonなので大丈夫 python

def solve(N, AS):
    ret = 0
    prevStep = 0
    for i in range(1, N):
        if prevStep + AS[i - 1] > AS[i]:
            prevStep = prevStep + AS[i - 1] - AS[i]
            ret += prevStep
        else:
            prevStep = 0
    return ret

D - Wizard in Maze

5回TLEした。最初の2回でTLEが減ったので「これはギリギリに違いない」と判断して頑張って高速化して通した
- 最初にサブミットしてからACまで23分も試行錯誤した…
まず距離Nで行けるマスを全部辿って歩きで行けるところがなくなってから、「今までに辿ったマスからジャンプで行けるところ」を探索候補に追加する
- 距離Nの探索中にゴールにたどり着けば、returnしてよい。
  - N-1でたどり着けないことが確認済みだから、Nが最短だと確定するので。
「ジャンプ」の計算を不用意にやると時間かかる
- 全てのマス(W*H)について「ここにジャンプで来れるか？」をチェックしたらダメ
  - 「道が細切れ」な時に何度も「全マスチェック」が走りまくる
  - ジャンプの回数は大雑把にW*H/6ぐらいになるからW^2 * H^2 / 6
- ひとます歩くたびに周囲25マスを「次にジャンプした時に飛んで良いところ」集合に入れた
  - 歩く回数は「全てのマス」以下なので、そのたびに25回計算しても25 * W * H
その「次にジャンプした時に飛んで良いところ」をどういう形で保持したか
- 最初、地図と同じ形の配列に印をつけてたのだけどTLE
  - ジャンプのたびに地図のサイズを舐めてはダメ
- ワープNで行けるところを全部辿ってからジャンプを試すなら「ワープ回数」を保持する必要がない
  - 「次のジャンプで到達しうる点」だけを保持すればよい
  - 集合setで持った
    - 追加O(1)、全列挙O(N)
- 「大量にジャンプが繰り返される」というTLE狙いの入力の場合も、ジャンプのたびに「次のジャンプ先」集合がリセットされるから大きくならない
僕はこれでACした(654ms)
- 解説のためにソースコードを整理してたらもっと速くなった(387 ms)
- 「次のジャンプで到達しうる点」ではなく「次のジャンプの起点になりうる点」を保持する
  - ジャンプすることが決まるまではジャンプ先を計算する必要がないため
細かい話題
- 上下左右　for d in [-1, +1, -WIDTH, +WIDTH]:
- マップ読み込み時点で壁をつけることで「x==0なら左に進んじゃダメ」みたいな条件分岐をなくす。番兵
  - 地図読み込み時に番兵をつける
- ジャンプ先を集合を使ってユニークにする必要はない
  - そのままtoVisitに重複ありでつっこんでよい
    - 重複の2件目以降はvisitedが真なので速やかにスキップされるから。
  - 今回のケースでは集合を使わない方が20msecほど速い
    - 速くするつもりで修正したらかえって遅くなった
    - どっちもO(1)だが、集合の方がハッシュ値の計算が入るため70nsほど遅い　see Python list v.s. set
    - 無駄な探索候補が増えてもこの差は逆転しない

python

def solve(H, W, Ch, Cw, Dh, Dw, walkable):
    N = HEIGHT * WIDTH
    visited = [0] * N

    start = (Ch + 1) * WIDTH + (Cw + 1)
    goal = (Dh + 1) * WIDTH + (Dw + 1)
    toVisit = []
    toVisit.append(start)

    currentDistance = 0
    while True:
        nextJumpOrigin = []
        while toVisit:
            p = toVisit.pop()
            if p == goal:
                return currentDistance
            if visited[p]:
                continue

            visited[p] = 1
            nextJumpOrigin.append(p)
            for d in [-1, +1, -WIDTH, +WIDTH]:
                if walkable[p + d] and not visited[p + d]:
                    toVisit.append(p + d)

        # no continuous cell
        for origin in nextJumpOrigin:
            for dx in [-2, -1, 0, +1, +2]:
                for dy in [-WIDTH * 2, -WIDTH, 0, WIDTH, WIDTH * 2]:
                    p = origin + dx + dy
                    if not walkable[p]:
                        continue
                    if visited[p]:
                        continue
                    toVisit.append(p)

        currentDistance += 1
        if not toVisit:
            return -1


def readMap(H, W):
    global SENTINEL, HEIGHT, WIDTH
    SENTINEL = 2
    HEIGHT = H + SENTINEL * 2
    WIDTH = W + SENTINEL * 2
    data = [0] * (HEIGHT * WIDTH)
    ok = ord(".")
    for i in range(H):
        S = input().strip()
        y = (i + SENTINEL) * WIDTH
        for j in range(W):
            data[y + (j + SENTINEL)] = 1 if S[j] == ok else 0
    return data


def main():
    # parse input
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    D = readMap(H, W)
    print(solve(H, W, Ch, Cw, Dh, Dw, D))

E - Bomber

縦横最大3*10^5なので、縦横を掛け算すると10^10を超えてきてダメ
各爆弾ごとに縦線、横線をカウントアップすればたくさん並んでる縦線、横線がわかる
- これはO(M)
それぞれの最大値の和…ではない
- 交点に爆弾がある場合-1なので
最大値の線の交点に爆弾があるかをチェック…
- 最大値はたくさんあり得る。10^5の桁
- 交点はやっぱり10^10を超えてしまう
ここまで考えて諦めた
解説を読む
- 爆弾の個数が高々M
- ということは最大値ラインの交点がMより多い場合、確実に「爆弾のない交点」が1つ以上存在するので答えは最大値の和でよい
  - 探索いらなかった！
- M以下の場合だけ探索 python

def solve():
    from collections import defaultdict
    H, W, M = map(int, input().split())
    hcount = defaultdict(int)
    wcount = defaultdict(int)
    bombs = set()
    for _i in range(M):
        h, w = map(int, input().split())
        hcount[h] += 1
        wcount[w] += 1
        bombs.add((h, w))

    maxh = max(hcount.values())
    maxw = max(wcount.values())
    hs = [k for k in hcount if hcount[k] == maxh]
    ws = [k for k in wcount if wcount[k] == maxw]
    if len(hs) * len(ws) > M:
        return maxh + maxw
    for h in hs:
        for w in ws:
            if (h, w) not in bombs:
                return maxh + maxw
    return maxh + maxw - 1

🪴 Quartz 4.0

ABC176

Graph View

Backlinks