AtCoder Grand Contest 075 A,B問題メモ

AtCoder Grand Contest 075

A - Divide Grid

• $N \times N$ のグリッドがあります。
• 各マスに $0,1$ のいずれかを書き込む方法に対して、以下のように $f(X)$ を定めます。
• $X$ が書かれているマスから、$1$ 回以上「右に隣接するマスに移動するか、下に隣接するマスに移動する」という操作を繰り返して $X$ が書かれている別のマスへ移動する方法の個数

• $f(0) = f(1)$ を満たす書き込み方を $1$ 個構築してください。この問題の制約下において解が存在することが保証されます。

• $1 \le N \le 500$

盤面を180度回転させても $f(0),f(1)$ は変化しない。

$N$ 偶数の場合は簡単で、$0$ の配置を180度回転させれば $1$ の配置に重なるようにすればよい。 たとえば上半分を $0$、下半分を $1$ にすればよい。

$N$ 奇数が難しい。点対称に配置することはできない。

答えが見つかるかはともかく、考えやすそうなケースとしては以下のものが思いつく。

0000?
000?1
00?11
0?111
?1111

• 既に盤面にある $0$ 同士、$1$ 同士の経路数は、点対称なので同じ
• ? 同士は互いに始終点ペアとなることが無いので、各 ? について個別に考えられる
• 各 ? について「$0$ にした時に $f(0)$ に寄与する経路数」と「$1$ にした時に $f(1)$ に寄与する経路数」は同じ

よって、各 ? について「そこを $0$ にした時に $f(0)$ に寄与する経路数」を計算し、 その部分和がちょうど全体の半分とできるような方法があればよい。

上から $h$ 行目（0-indexed）の ? を $0$ にした場合の経路数は、始点の $0$ の位置を決めて足し合わせれば、

• $\displaystyle (\sum_{i=0}^{h-1}\sum_{j=0}^{N-h-1} \binom{i+j}{i})-1$
  • ※最後の $-1$ は、自分自身を始点とした経路を引いたもの。

で計算できる。

一般に、二項係数 $\binom{n}{r}$ は、$r$ が奇数の項の総和と偶数の項の総和が等しくなる性質がある。
そこから連想して、この場合も偶奇別に足せば等しくならないかを確かめると、ちゃんと等しくなる。

 h    0   1   2   3   4   5   6      偶数の和  奇数の和
N=3   2   4   2                          4         4
N=5   4  13  18  13   4                 26        26
N=7   6  26  54  68  54  26   6        120       120

よって、上記の ? に $0,1$ を交互に埋めていくと、答えとなる。

ちゃんと証明するなら

Python3

def solve(n):
    if n % 2 == 0:
        ans = [[0] * n for _ in range(n // 2)]
        ans += [[1] * n for _ in range(n // 2)]
        return ans

    ans = [[0] * n for _ in range(n)]
    for i in range(n):
        s = n - i - (i % 2)
        for j in range(s, n):
            ans[i][j] = 1
    return ans


n = int(input())
ans = solve(n)
for row in ans:
    print(''.join(map(str, row)))

B - Traffic Light

• ある信号があります。この信号は常に赤になっていますが、PCT 君が $P$ 円払ってボタンを押すと $X$ 秒間緑になります。ただし、PCT 君は以下のルールを守る必要があります。
  • ボタンを押すことが出来るのは整数 $t$ に対して時刻 $t$ と表すことが出来るタイミングのみ。($t$ として負の整数を選ぶことも出来ます。)
  • 時刻 $t$ にボタンを押した場合、時刻 $t+Y$ になるまでボタンを押すことはできない。(時刻 $t+Y$ にボタンを押すことは可能です。)

• この信号を $N$ 人の人が渡ろうとしています。
• $i$ 人目の人は時刻 $A_i + 0.5$ にこの信号を渡ろうとしていて、時刻 $A_i + 0.5$ に信号が緑だと PCT 君に $C_i$ 円を払います。赤だと何もしません。
• (PCT 君の貰ったお金 $-$ ボタンを押すためにかかった費用) としてあり得る最大値を求めてください。

• $T$ 個のテストケースが与えられるので、それぞれについて解いてください。

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $1 \le P \le 10^9$
• $1 \le X \le Y \le 10^9$
• $1 \le A_i \le 10^{18}$
• $1 \le C_i \le 10^9$
• 全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
• 入力される値は全て整数

本番中に考えたが行き詰まった方針。

ボタンを押すべきタイミングとしては、以下のいずれかとなる。

• $A_i$ に押す（通行人 $i$ が渡る直前で青に変わる）
• $A_i-X+1$ に押す（通行人 $i$ が渡った直後に赤になる）
• 前回押してから時間 $Y$ たった直後に押す

「最後にボタンを押した時刻が $t$ の場合の最大収支」などのDPをするにしても、 1つめと2つめだけなら $t$ の候補は $O(N)$ だが、3つめが $O(N\max(A))$ あり、そのままではDPのキーにできない。

一応、収支が $0$ 以下になるなら押す意味は無いので、 そこでボタンを $Y$ 秒毎に押す連鎖が途切れ、 状態数が減ったりしてくれないかな、とか考えたが、 $Y$ 秒程度おきに1人ずつ来るようにすれば $O(N^2)$ であり、まだまだ多すぎる。

DPの基本的な考え方は上記でよいが、2段階くらいの言い換えを挟んで、高速化していく。

$W_t$ を、「時刻 $t$ にボタンを押したときの、その1回分の青時間の収支」とする。
$t$ を1ずつ進めていく過程で、$W_t$ は誰かの $A_i$ が青の時間区間から入るときと出るときしか変化しないので、 変化点、つまり「$W_{t-1} \neq W_{t}$ となるような $t$」の個数は $O(N)$ である。

（※細かな点だが、後の都合上、誰かの出入りがあった $t$ は必ず変化点と扱うことにする。 つまり、$C_i=C_j$ である2人がいて、$t-1→t$ にかけて $i$ が青の区間から出ると同時に $j$ が入った場合、 $W_t$ は変化していないが変化点として扱う）

以下のDPを考える。（※$t$ の範囲は $-X～\max(A)$ となるためこのまま実装はできない）

• $\mathrm{DP}[t]:=$ 時刻 $t$ までのボタンを押すタイミングを決めたときの、最大収支
  • 時刻 $t$ にボタンを押したかは問わない
  • 時刻 $t$ の時点で青が継続している場合、その青が終了するまでの時間を含む

変化点を $T=(t_0,t_1,...,t_m)$ とすると、$W_t$ が同じ時間区間 $[t_{i},t_{i+1})$ はまとめてDPを更新できそう？
この更新を考えてみる。

$i$ 番目の時間区間中にボタンを押したときの収支は一律 $W_{t_i}$ だが、遷移元が異なる。
時刻 $j$ にボタンを押せるのは、最後にボタンを押したのが $j-Y$ 以前の時に限られる。よって、以下のようになる。

• ボタンを押す場合の遷移
  • $\mathrm{DP}[j] = \mathrm{DP}[j-Y] + W_{t_i}$（$t_{i} \le j \lt t_{i+1}$）

また、$i$ 番目の時間区間中ではボタンを押さない方がいい場合もある。
その場合は、$\mathrm{DP}[t_i-1]$ の値をそのまま遷移させる。

• ボタンを押さない場合の遷移
  • $\mathrm{DP}[j] = \mathrm{DP}[t_i-1]$（$t_{i} \le j \lt t_{i+1}$）

この大きい方が採用される。

上の遷移から、加算処理は必ず $Y$ だけ前のindexに対して行われることがわかる。
DPの添字を $\mod{Y}$ で考え、遅延セグ木などに載せることによって、inplace な更新ができるようになる。

• $b = \mathrm{DP}[t_i-1]$ を取得
• $[t_i, t_{i+1})$ に「$W_{t_i}$ を加算後、$b$ で chmax」という演算を作用
  • ※添字はそれぞれ $\mod{Y}$ で考える。1周の区切りをまたぐ場合は2回に分けて更新する。

これでもまだ添字範囲は $O(Y)$ で多すぎるが、座標圧縮することで $O(N)$ に抑えられる。
あくまで「各変化点に付き、$\mod{Y}$ を取った後の値」で座標圧縮する点に注意。

計算量は $O(N \log{N})$ となる。

以下、実装についての細かな点

• 「$a$ を加算してから $b$ でchmaxする」という作用を $(a,b)$ とする。
  • 作用の合成、つまり $(a_1,b_1)→(a_2,b_2)$ の順に作用させた場合の合成後の作用は、$(a_1+a_2,\max(b_1+a_2,b_2))$ で表せる。

• この問題の設定では、$W_{t_i}$ が正の場合、時間区間の長さ $t_{i+1}-t_i \le X \le Y$ である。このおかげで、少し実装が簡略化される。
  • 時間区間長が $Y$ を超えることがあれば、mod Y の周回ごとに $W_{t_i}$ が複数回加算される（$k$ 周する場合、区間全体に$k \times W_{t_i}$ を加算して、改めて端数の分を加算する処理が必要になる）が、今回はそういうのは要らない。
  • これが、冒頭で「誰かの出入りがあったら変化点として扱う」とした理由

• 誰も来ない時間が続く場合は、$t_{i+1}-t_i \gt Y$ であることもありうる。
  • この場合、収支は必ず $-P$ で負なので加算処理は不要。セグ木全体に対して $chmax$ すればよい。

Python3

from collections import defaultdict
from atcoder.lazysegtree import LazySegTree


def solve(n, p, x, y, aaa, ccc):
    # 「時刻 t に緑にした時の収支」が変化する t と収支を列挙
    events = defaultdict(int)
    for i in range(n):
        a = aaa[i]
        c = ccc[i]
        events[a - x + 1] += c
        events[a + 1] -= c
    gain = 0
    flex = []
    events = sorted(events.items())
    t0 = events[0][0]
    mod_y_ts = {0}
    for t, c in events:
        gain += c
        t -= t0
        flex.append((t, gain - p))
        mod_y_ts.add(t % y)
    mod_y_ts = sorted(mod_y_ts)
    m = len(mod_y_ts)
    mod_y_mapping = {t: i for i, t in enumerate(mod_y_ts)}

    # print(f'{flex=}')
    # print(f'{mod_y_ts=}')

    def mapping(a, b):
        return max(b + a[0], a[1])

    def composition(a, b):
        return (a[0] + b[0], max(b[1] + a[0], a[1]))

    sgt = LazySegTree(max, 0, mapping, composition, (0, 0), m)

    for i in range(len(flex) - 1):
        t0, g = flex[i]
        t1, _ = flex[i + 1]

        if t1 - t0 > y:
            assert g == -p
            k = sgt.all_prod()
            sgt.apply(0, m, (0, k))
            # print(f'Interval {t0=} {t1=} {g=} {k=}')
            continue

        l = mod_y_mapping[t0 % y]
        r = mod_y_mapping[t1 % y]
        k = sgt.all_prod()
        g = max(g, 0)
        # print(f'Add {t0=} {t1=} {l=} {r=} {g=} {k=}')
        if l < r:
            sgt.apply(l, r, (g, k))
        else:
            sgt.apply(l, m, (g, k))
            sgt.apply(0, r, (g, k))

    ans = sgt.all_prod()
    return ans


t = int(input())
for _ in range(t):
    n, p, x, y = list(map(int, input().split()))
    aaa = list(map(int, input().split()))
    ccc = list(map(int, input().split()))
    ans = solve(n, p, x, y, aaa, ccc)
    print(ans)