AtCoder Beginner Contest 240 F,G問題メモ

コンテストに参加してたら、数字が綺麗に並ぶ 2022/02/20 22:02:20 をうっかり見逃したので、ABC許さない（とばっちり）

F - Sum Sum Max

問題

整数列 $C$ は、$x_1～x_N,y_1～y_N$ を使って以下のように表される
- $x_1$ を $y_1$ 個、$x_2$ を $y_2$ 個、…… $x_N$ を $y_N$ 個、この順に繋げた数列
整数列 $B$ は、$C$ の先頭からの累積和である
整数列 $A$ は、$B$ の先頭からの累積和である
$A$ の最大値を求めよ
$T$ 個のテストケースが与えられるので、それぞれについて求めよ
1つのテストケースにおける整数列の長さ $\le 10^9$
1つの入力に含まれる全テストケースの $N$ の総和 $\le 2 \times 10^5$

解法

i   0   1   2   3   4   5   6   7
C  -2  -2   4   4   4  -3  -3  -3
B  -2  -4   0   4   8   5   2  -1
A  -2  -6  -6  -2   6  11  13  12
                          ~~~~   ←最大値

$A$ の最大値を求める上では、$B_i$ と比べて $B_{i+1}$ が正なら次も足した方がいいし、負ならそこでひとまず止めた方がいい。

よって、数列の長さは非常に長くなりうるが、最大値をチェックするのは $B$ が正から負に切り替わるタイミング（と、最初と最後）だけでよい。

それがいつ切り替わるかを直接求めるのは難しいが、$B$ における $N$ 個の $x_i,y_i$ の切り替わり点を追っていけばわかる。

       j1          j2          j3
i   0   1   2   3   4   5   6   7
C  -2  -2   4   4   4  -3  -3  -3
B      -4           8          -1

切り替わり点の $i$ を $j_1,j_2,...$ と表す。
$B_{j_k}$ は、単に $x_k \times y_k$ を累積的に足していけば求められる。
$B_{j_k}$ と $B_{j_{k+1}}$ を比べると、その中に $A$ の最大値があり得るかどうかわかる。

正→正: 末尾が最大
負→正: 末尾か先頭が最大
負→負: 先頭が最大
正→負: 「途中に、正から負に切り替わる＝最大値を取りうる箇所が存在する」

正→負の区間だけチェックすればよいとわかった。

この中で切り替わる具体的な箇所 $i$ を特定し、そこから最大値候補である $A_i$ を求めたい。

切り替わり点から $i$ が1つ進む毎に $x_k$ だけ減っていくので、$\dfrac{B_{j_{k-1}}}{-x_k}$（切り捨て）だけ進んだ箇所が正、その次が負となる。

       j1          j2          j3
i   0   1   2   3   4   5   6   7
C  -2  -2   4   4   4  -3  -3  -3
B      -4           8→ 5→ 2→-1

              B[j2]/-x3 = 8/3 = 2 より、
              i=4 から 2 進んだ i=6 がこの区間の中で最大を取る箇所

前の区間の終わり $i=4$ から $d=2$ 進んだ箇所が最大値をとるとわかったので、$A_6$ を求める。

先頭から累積的に計算することで、$A_{j_1},A_{j_2},...$ は計算できる。

       j1          j2          j3
i   0   1   2   3   4   5   6   7
C  -2  -2   4   4   4  -3  -3  -3
B      -4           8          -1
A      -6           6      []  12

1つ前の区間の終わりが $A_r$ で、その次に $C$ において $n$ 個の $x_i$ が並んでいると、

$A_{r+n} = A_r + B_r \times n + \dfrac{n(n+1)}{2} \times x_i$

と表現できる。

これを使うと、$A_6 = A_4 + B_4 \times d + \dfrac{d(d+1)}{2} \times x_3 = 13$ となり、正しく求められている。

正→負となる区間毎に調べていって、$O(N)$ で全て求められる。

Python3

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    ccc = [tuple(map(int, input().split())) for _ in range(n)]
    bbb = [0]
    for x, y in ccc:
        bbb.append(bbb[-1] + x * y)

    aaa = [0]
    ans = ccc[0][0]
    for i in range(n):
        x, y = ccc[i]
        aaa.append(aaa[-1] + bbb[i] * y + y * (y + 1) // 2 * x)

        l = bbb[i]
        r = bbb[i + 1]
        if r >= 0:
            ans = max(ans, aaa[-1])
        elif l <= 0:
            ans = max(ans, aaa[-1])
        else:
            d = l // -x
            tmp = aaa[-2] + bbb[i] * d + d * (d + 1) // 2 * x
            ans = max(ans, tmp)
    print(ans)

G - Teleporting Takahashi

問題

3次元グリッド上で、隣接する6つの立方体のいずれかに移動することを繰り返す
原点 $(0,0,0)$ からちょうど $N$ 回の移動後に $(X,Y,Z)$ に存在する移動方法の個数を $\mod{998244353}$ で求めよ
$1 \le N \le 10^7$

解法

2次元なら、過去に類題があった（けどすっかり忘れてた）。

2次元の場合

$N$ 回ちょうどで $(0,0)$ から $(X,Y)$ に移動する。

操作回数が最低限の $|X|+|Y|$ に足りなかったり、偶奇が合わない場合は最初に除く。

最低限から余る移動回数については、無駄な移動（同じ軸の正方向と負方向の移動のセット）を $k=\dfrac{N-(|X|+|Y|)}{2}$ 回、しなくちゃいけない。

素直に考えると、$x$ 軸方向で何回、$y$ 軸方向で何回行うか決めれば計算できる。片方の無駄を $0～k$ に固定して場合分けすればよい。しかし、これだと $O(k)$ かかる。

$x$ 軸方向に $m$ 回の無駄を挟むなら、計 $X+2m$ 回の移動の中で目標と反対に移動する $m$ 回の位置を決めればよい
- ${}_{X+2m}C_{m}$

テクニックとして、45度回転させ、$(+1,+1),(+1,-1),(-1,+1),(-1,-1)$ の4つの移動で $(X+Y,X-Y)$ に到達する、と問題を言い換えると、 2つの軸を独立に考えることができ、2つの二項係数の積で $O(1)$ で計算できてしまう。

3次元の場合

今回の制約では、単純に1次元の無駄回数を $0～k$ で固定して、2次元に帰着させるのを全通り試せばよい。

最初の階乗計算を除けば、全体 $O(N)$ で求められる。