AtCoder Beginner Contest 128 D,E,F問題メモ

AtCoder Beginner Contest 128

回を重ねる毎に解けた問題数が減っていくのは何故だ。

D - equeue

• 水平に置かれた細長い筒に $N$ 個の宝石が一列に詰まっている
• 宝石は左から順に $v_1,v_2,...,v_N$ の価値を持つ。負の価値もありうる。
• 以下の操作を合計 $K$ 回まで、何度でも好きな順に行える
  • 筒の一番左の宝石を1個、手元に取り出す（筒に宝石がある場合）
  • 筒の一番右の宝石を1個、手元に取り出す（筒に宝石がある場合）
  • 手元の宝石を1個、筒の一番左に詰める（手元に宝石がある場合）
  • 手元の宝石を1個、筒の一番右に詰める（手元に宝石がある場合）
• 最終的な手元の宝石の価値を最大化せよ
• $1 \le N \le 50$
• $1 \le K \le 100$

Dequeを筒に見立てているが、特に解法にDequeが必要なわけではない。

なるべく負の価値を持つ宝石は取りたくないが、筒の奥にある価値の高い宝石を得るために一時的に取った方が得になることもある。

-2  -1  -3  100000  -5  -10

その際、取った負の宝石は筒に戻したいが、これは $K$ 回の内ならいつ戻してもよいので、必要なだけ取り出してから、戻せる分を戻す、という操作の順番に固定して考えてよい。

以下のデータを作る。

• $DP_L[k]=$ 操作 $k$ 回までで、取り出す場合は筒の左からのみ取り出して得られる価値の最大値
• $DP_R[k]=$ 操作 $k$ 回までで、取り出す場合は筒の右からのみ取り出して得られる価値の最大値

すると $k=0,1,2,...,K$ の中で、$DP_L[k]+DP_R[K-k]$ の最大値が答えとなる。

ただし、$DP_L$ と $DP_R$ の最大値が、ともに同じ宝石を取ってしまっているケースが考えられる。 操作回数が十分だと、得られる価値の最大値は正の価値を持つ宝石だけの和なので、超えている場合はその上界に上書きする。

データの作り方は、もっと上手い方法はあるとは思うが、制約が小さいので

• 左から $t$ 個取ると決めると、$DP_L[t] \leftarrow sum(v_1～v_t)$
• $t$ 個中、最も低い宝石の価値 $v_w$ が負なら、筒に戻す。$DP_L[t+1] \leftarrow DP_L[t]-v_w$
• 最も低い宝石の価値が非負になるまで繰り返す

というのを $t=0～N$ までシミュレーションして間に合う。ただし $\leftarrow$ は、現在値と比較して大きければ更新という操作を示す。

また、あくまで上で埋められるのは「$K$ 回ちょうど」の最大値であり、答えるのは「最大 $K$ 回」なので、最後に累積MAXを取る。

from itertools import accumulate


def make_dp(vvv, n, k):
    dp = [0] * (k + 1)

    for i in range(min(n, k)):
        i += 1
        vv = vvv[:i]
        vv.sort(reverse=True)
        sm = sum(vv)
        dp[i] = max(dp[i], sm)
        while i < k and vv and vv[-1] < 0:
            sm -= vv.pop()
            i += 1
            dp[i] = max(dp[i], sm)

    return list(accumulate(dp, func=max))


n, k = list(map(int, input().split()))
vvv = list(map(int, input().split()))

acl = make_dp(vvv, n, k)
vvv.reverse()
acr = make_dp(vvv, n, k)
acr.reverse()

ans = max(map(sum, zip(acl, acr)))
ans = min(ans, sum(v for v in vvv if v > 0))
print(ans)

E - Roadwork

• 1次元の数直線で示される道路がある
• 道路工事が $N$ 件予定され、$i$ 件目は時刻 $S_i-0.5$ から $T_i-0.5$ までの間、地点 $X_i$ が通行できなくなる
• $Q$ 人の人が、道路上を正方向に速さ1で移動しようとしている
• $i$ 番目の人は、時刻 $D_i$ に点0を出発する
• $Q$ 人のそれぞれについて、最初に通行止めに直面する地点の座標を求めよ。1件も直面しない場合は-1を出力せよ
• $1 \le N,Q \le 2 \times 10^5$
• $0 \le S_i \lt T_i \le 10^9$
• $1 \le X_i \le 10^9$
• $0 \le D_1 \lt D_2 \lt ... \lt D_Q \le 10^9$

区間Updateセグ木問題、のはずが、PythonだとPyPyでも時間的に厳しくてTLE。 セグ木を諦めて汎用性はなくなるが高速な解法にすると、とりあえずは間に合う。 セグ木でも間に合ってる人もいるっぽいので、実装をちょっと頑張れば通せるはず。（自分の実装が悪い気がする）

問題文で時刻に0.5を引いているのは「開始ちょうど、終了ちょうどに到達した場合がどうなるかのあやふやさを無くすため」だと思う。 「$S_i$ ちょうどに到着したら既に始まってるので引っかかる」 「$T_i$ ちょうどに到着したら既に終わってるので引っかからない」と解釈すればよい。

ここから $X_i$ までの移動にかかる時間を差し引くと「この工事に引っかかる可能性のある人の、地点0を出発した時刻の範囲」がわかり、$[S_i-X_i,T_i-X_i)$ となる。

2つ以上の工事に該当する人は座標が小さい方の工事に最初に引っかかるので、 一度Updateされた区間は上書きされないようなセグ木で、座標が小さい方から順に区間Updateを行えばよい。

その際、$D_i$ の取り得る範囲は $10^9$ と大きいので、以下のいずれかで座標変換を行う。

• $D_i$ のみを0からのindexに振り当てる。工事の開始終了時刻から該当する $i$ を特定するには、$\{D_1,D_2,...,D_Q\}$ の配列上で二分探索を用いる
• $D_i,S_i-X_i,T_i-X_i$ をあわせて0からのindexに振り当てる。要素数は3倍程度に増えるが、indexを $O(1)$ で取得できる

$Q=10^5$ の場合 $\log{Q}=16.6$ なので毎回二分探索にそれだけの計算量がかかることを考えると、下の方がいいのかな。

この問題のように、Updateする優先順位が決まっていて、一度Updateした部分はもう変更されない場合、セグ木よりもっと簡単な実装がある。

• $ans[i]=i$ 番目の人の答え、'-1' で初期化
• $skip[i]=i$ 番目の人が手前の工事で既に引っかかっていた場合、何番目の人まで同じ工事で引っかかったか＝どこまでポインタをスキップできるか

$[s_i,t_i)$ を $x_i$ にする更新クエリが来たら、

i = si
while i < ti:
    if ans[i] == -1:  # まだ手前の工事に引っかかってない
        ans[i] = xi
        skip[i] = ti
        i += 1
    else:             # 手前で引っかかり済み
        i = skip[i]

全体で $ans$ の各要素には1回しか代入されないので、単純ながらも高速になる。

解説PDFの方法。「今出発したら引っかかる工事リスト」を作る。

道路工事開始イベント、道路工事終了イベント、$i$ 番目の人出発イベントを、出発時刻順にソートする。

• 工事終了イベント: $(T_i-X_i, 1, X_i)$
• 工事開始イベント: $(S_i-X_i, 2, X_i)$
• 出発イベント: $(D_i, 3)$

終了、開始、出発イベントの順に取り出されるようにする。

開始イベントでは工事リストに $X_i$ を追加、終了イベントでは削除する。 出発イベントが取り出された時点の工事リストの最小値が、その人が最初に直面する工事の座標となる。

ただし、工事リストのデータ構造がPythonでは難しい。 追加、削除に加え、最小値の取得をそれぞれ $O(\log{N})$ 程度で行いたいが、setでは最小値の取得が $O(N)$ となる（? 少なくともlogではないっぽい）し、heapqでは要素の削除が出来ない。 二分探索木などを実装すれば良いが、ちょっと過剰。

副次的な方法として、setは検索は速いので、heapqとsetを2つ持ち、最小値の取得をheapq、それが有効であるかどうかをsetで確かめるようにすると、そこそこ速くなる。

import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    while ss < tt:
        if skip[ss] == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = skip[ss]
print('\n'.join(map(str, ans)))

F - Frog Jump

• $N$ 枚の蓮の葉が水面に一列に並び、$0,1,2,...,N-1$ と番号が付けられている
• 各葉には得点が決められており、番号 $i$ の葉の得点は $s_i$
• カエルが1匹、0の葉にいて、以下の要領で $N-1$ の葉まで移動する
  1. 最初に正整数 $A,B$ を決める
  2. 現在の葉を $x$ とすると、$x+A$ の葉にジャンプする。$s_{x+A}$ の得点を得る。$x$ の葉は沈んで無くなる
  3. 現在の葉を $x$ とすると、$x-B$ の葉にジャンプする。$s_{x-B}$ の得点を得る。$x$ の葉は沈んで無くなる
  4. 2に戻る
• $N-1$ の葉に到着した時点で移動を終了する
• 移動先が存在しない葉や、既に沈んだ葉なら、得点が $10^{100}$ 減少して移動を終了する
• 移動終了後の得点を最大化せよ
• $3 \le N \le 10^5$
• $-10^9 \le s_i \le 10^9$

N=11
番号  0   1   2   3   4   5   6   7   8   9  10
得点  0  -4   0 -99  31  14 -15 -39  43  18   0

A=3, B=2
移動  0→3→1→4→2→5→(3)
次に3に移動しようとするが、既に沈んでいるため、移動終了

A=6, B=4
移動  0→6→2→8→4→10
無事10の葉にたどり着く。得点は 0+0+31-15+43 = 59

カエルの行動から水前寺清子氏を連想した。

前提として、水に落ちてはいけない。マイナス $10^{100}$ 点とか、制約上どう見ても取り返せない。 落ちずに $N-1$ に到達する移動を考える。

前方向に移動するのを移動A、後方向に移動するのを移動Bとする。

$A,B$ の持つ性質を考えてみる。

移動Bで $N-1$ に着地することはない。 なぜなら、移動の直前には $N-1$ より先の葉にいなければいけないが、そんな葉は無い。 $N-1$ へは移動Aで到達する。

ここで $A$ を固定すると、$N-1$ 直前にいる葉は $N-1-A$ である。

また、各移動Bの後にいる葉の番号は $A-B$ の倍数となる。よって $C=A-B$ として、$C$ は $N-1-A$ の約数である。

$A$ と $C$ を決めれば移動が特定され、得点が計算できる。

さて、しかしここで 「$A$ を決める」→「$N-1-A$ の約数を列挙して $C$ を決める」 →「同じ葉を踏まないか確認する」→「得点を計算する」とするのは、上手くいかない。 $A$ の列挙が $O(N)$、約数列挙が試し割りで $O(\sqrt{N})$、得点の計算が $O(N)$、合計 $O(N^2 \sqrt{N})$ くらいかかってしまう。

ならばと、$C$ を固定して考えてみる。

すると、移動Bを行った回数を $k$ とし、$k$ で場合分けすると、 不可能なパターンを探索しなくて済むと同時に、過去の計算結果を綺麗に活用できる。

N=16  C=2
k=0  0 → 15
k=1  0 → ⑬ → ② → 15
k=2  0 → ⑪ →  2 → 13 → ④ → 15
k=3  0 → ⑨ →  2 → 11 →  4 → 13 → ⑥ → 15
k=4  0 → ⑦ →  2 →  9 →  4 → 11 →  6 → 13 → ⑧ → 15
...

$k$ が1増えると、順番は変わっているものの 直前の $k$ で踏んだ葉はそのまま、ある特定の2枚の葉を新しく踏むことになっている。

その2枚とは、$N-1-kC$ と $kC$ である。なお、$N-1-kC=A$ である。

これなら $C$ と $k$ の列挙に $O(\sum_C{\frac{N}{C}})$ で調和級数となるので、$O(N \log{N})$ くらいに収まる。 切り口次第でがらっと計算量が変わるのが美しい。

ただ、上の例では終了条件をきちんと考えていない。満たすべき条件は以下の通りである。

• $C=A-B$ でどちらも正のため、$A>C$
• 同じ葉を踏んでしまうケース
  • 同じ葉を踏むのは、移動Aと移動Bの組合せである（移動A同士、移動B同士の移動先が被ることはない）
  • 各 $k$ の時点で新しく追加された葉が、既存の葉と被りうる
  • 例えば上記の例で、$k=4$ の時追加された「7」（移動A）が被るとしたら、6または8の位置にある葉である
  • それより小さい葉で被るとしたら、もっと前に被っている
  • よって $N-1-kC$ が、$kC$ または $(k-1)C$ と等しければ、$k$ の列挙を打ち切ってよい

コードはかなりシンプル。便宜上'k'の指す意味が $kC$ となっている。

n = int(input())
sss = list(map(int, input().split()))

ans = 0
for c in range(1, n // 2):
    a = n - 1 - c
    k = c
    tmp = 0
    while a > c and a != k and a + c != k:
        tmp += sss[a] + sss[k]
        ans = max(ans, tmp)
        a -= c
        k += c
print(ans)