筆者はレート800前後の茶～緑コーダ
ABC479のD問題を解いていく
実装コード
L と R の累積minを前計算しておき、各クエリは「そのまま進む」か「一度逆向きに進んでから向きを変える」の小さい方を出力する。
-
Lは先頭に0、Rは末尾に0を付けて、どちらも長さNにそろえる -
A[i]はL[i:]の最小値になるように、後ろから累積minを取る -
B[i]はR[:i+1]の最小値になるように、前から累積minを取る - クエリ
s, tを0-indexedで読み、s < tなら右向き、そうでなければ左向きとして扱う - 右向きのときは
R[s]と、L[s]で左へ進んでから左側のRの最小値B[s - 1]を使う場合を比べる - 左向きのときは
L[s]と、R[s]で右へ進んでから右側のLの最小値A[s + 1]を使う場合を比べる - 小さい方を答えとして出力する
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
N, Q = rLI()
L = [0] + rLI()
R = rLI() + [0]
A = L[:]
B = R[:]
for i in range(N - 2, -1, -1):
A[i] = min(A[i], A[i + 1])
for i in range(1, N):
B[i] = min(B[i], B[i - 1])
for _ in range(Q):
s, t = rLI1()
if s < t:
ans = R[s]
if s > 0:
ans = min(ans, L[s] + B[s - 1])
else:
ans = L[s]
if s < N - 1:
ans = min(ans, R[s] + A[s + 1])
print(ans)
if __name__ == '__main__':
main()
感想
一度逆向きに進んでから向きを変える場合も、累積minを前計算しておけば各クエリでO(1)で比べられるのが便利だった。