ABC176
4問解いてもレーティングは伸びません
https://gyazo.com/096ba8d1cc428b4f813302c5e7f71ae5
問題C - Step
https://gyazo.com/0858ad5cbc91a901a8b1fe7e39702cc8
k-1番目まで条件を満たしている時、k-1番目の人は一番高い
ので、k番目の人の踏み台の高さを決める際にk-1番目とだけ比較すればOK
答えは10^14の桁になりうるけどPythonなので大丈夫
code:python
def solve(N, AS):
ret = 0
prevStep = 0
for i in range(1, N):
if prevStep + ASi - 1 > ASi:
prevStep = prevStep + ASi - 1 - ASi
ret += prevStep
else:
prevStep = 0
return ret
D - Wizard in Maze
https://gyazo.com/ed9c4a29cba57fc94914dde342c95e95
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
無駄な探索候補が増えてもこの差は逆転しない
code: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 visitedp:
continue
visitedp = 1
nextJumpOrigin.append(p)
for d in -1, +1, -WIDTH, +WIDTH:
if walkablep + d and not visitedp + 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 walkablep:
continue
if visitedp:
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):
datay + (j + SENTINEL) = 1 if Sj == 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
https://gyazo.com/f6b8c7e382d64944aae25946a26e4ec5
縦横最大3*10^5なので、縦横を掛け算すると10^10を超えてきてダメ
各爆弾ごとに縦線、横線をカウントアップすればたくさん並んでる縦線、横線がわかる
これはO(M)
それぞれの最大値の和…ではない
交点に爆弾がある場合-1なので
最大値の線の交点に爆弾があるかをチェック…
最大値はたくさんあり得る。10^5の桁
交点はやっぱり10^10を超えてしまう
ここまで考えて諦めた
解説を読む
爆弾の個数が高々M
ということは最大値ラインの交点がMより多い場合、確実に「爆弾のない交点」が1つ以上存在するので答えは最大値の和でよい
探索いらなかった！
M以下の場合だけ探索
code: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())
hcounth += 1
wcountw += 1
bombs.add((h, w))
maxh = max(hcount.values())
maxw = max(wcount.values())
hs = [k for k in hcount if hcountk == maxh]
ws = [k for k in wcount if wcountk == 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