AtCoder Regular Contest 204 (Div. 1) A,B,C 問題メモ

AtCoder Regular Contest 204 (Div. 1)

A - Use Udon Coupon

• 正整数 $N, L, R$ と長さ $N$ の正整数列 $A = (A_{1}, A_{2}, \dots, A_{N}), B = (B_{1}, B_{2}, \dots, B_{N})$ が与えられます。
• 整数 $C$ を $0$ で初期化します。その後、以下の行動 $1, 2$ のうちいずれかを選んで行う、ということを $2N$ 回繰り返します。
  • 行動 $1$ :
    • $i$ 回目の行動 $1$ では、$C$ を $\max(0, C - A_{i})$ に置き換える。
    • 行動 $1$ は、計 $N$ 回おこなう。
  • 行動 $2$ :
    • $i$ 回目の行動 $2$ では、$C$ に $B_i$ を加算する。
    • $i$ 回目の行動 $2$ は、それまでの行動 $1$ の回数が $i$ 回以上の時のみおこなえる。
    • 行動 $2$ は、計 $N$ 回おこなう。

• $2N$ 回の操作の方法であって、最終的な $C$ が $L$ 以上 $R$ 以下であるようなものの場合の数を $998244353$ で割ったあまりを求めてください。

• $1\leq N\leq 5000$
• $1\leq L \leq R \leq \sum B$
• $1\leq A_{i}\leq 5000$
• $1\leq B_{i}\leq 5000$
• 入力は全て整数

仮に行動 $1$ で、最小値を0で切らずにそのまま $C←C-A_i$ としていた場合の $C$ を $C'$ と表す。
$2N$ 回後の最終的な $C'$ の値は $T = \mathrm{sum}(B)-\mathrm{sum}(A)$ で一定である。

実際の $C$ は、ここから「途中で経由した $C'$ の最小値」だけ底上げされる、と考えられる。

                       T___
C' 0                  /   ^
    ＼         /\   ／    |実際のC
      ＼/＼   /  ＼/      |
           \／____________v

つまり、問題の条件は「途中で経由する $C'$ の最小値が $T-R$ 以上 $T-L$ 以下」となるような操作列の数、と言い換えられる。

操作順を経路数になぞらえる。
操作の制約が「行動2の回数が行動1の回数を超えてはいけない」ということで、通れるマスに制約がある以下のような図となる。

Ｓ×××××    ↓: 行動1
□□××××    →: 行動2
□□□×××
□□□□××
□□□□□×
□□□□□Ｇ

このマス目の1つ1つにつき、そこへ到達時点の $C'$ の値「$K_{i,j} =$（$j$ までの $B$ の和）-（$i$までの $A$ の和）」は、操作順に依らず固定である。

つまり、条件に当てはまる操作列は、「以下のような図で、“１”のマスを1回以上通り、“２”のマスは通らないで、ＳからＧまで行く経路数」と言い換えられる。

Ｓ×××××    ↓: 行動1
００××××    →: 行動2
１００×××
１０００××    ０:                        T-L <  K_ij
２１１００×    １:         T-R <= K_ij <= T-L
２２１００Ｇ    ２: K_ij <  T-R

“１”を1回以上通ってない/通った、の2通りを持つ経路数DPで $O(N^2)$ で求められる。

Python3

from itertools import accumulate


def solve(n, l, r, aaa, bbb):
    acc_a = [0] + list(accumulate(aaa))
    acc_b = [0] + list(accumulate(bbb))
    total = acc_b[-1] - acc_a[-1]
    min_l = total - r
    min_r = total - l
    is_ok = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        for j in range(i + 1):
            if min_r < acc_b[j] - acc_a[i]:
                is_ok[i][j] = 0
            elif min_l <= acc_b[j] - acc_a[i] <= min_r:
                is_ok[i][j] = 1
            else:
                is_ok[i][j] = 2
    # print(is_ok)
    dp0 = [[0] * (n + 1) for _ in range(n + 1)]
    dp1 = [[0] * (n + 1) for _ in range(n + 1)]
    if min_r < 0:
        dp0[0][0] = 1
    elif min_l <= 0 <= min_r:
        dp1[0][0] = 1
    else:
        return 0

    MOD = 998244353
    for i in range(1, n + 1):
        for j in range(i + 1):
            if is_ok[i][j] == 0:
                if i > 0:
                    dp0[i][j] += dp0[i - 1][j]
                    dp1[i][j] += dp1[i - 1][j]
                if j > 0:
                    dp0[i][j] += dp0[i][j - 1]
                    dp1[i][j] += dp1[i][j - 1]
                dp0[i][j] %= MOD
                dp1[i][j] %= MOD
            elif is_ok[i][j] == 1:
                if i > 0:
                    dp1[i][j] += dp0[i - 1][j]
                    dp1[i][j] += dp1[i - 1][j]
                if j > 0:
                    dp1[i][j] += dp0[i][j - 1]
                    dp1[i][j] += dp1[i][j - 1]
                dp1[i][j] %= MOD
    return dp1[n][n]


n, l, r = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ans = solve(n, l, r, aaa, bbb)
print(ans)

B - Sort Permutation

• 正整数 $N, K$ と、$(1, 2, \dots, NK)$ の順列 $P = (P_{1}, P_{2}, \dots, P_{NK})$ が与えられます。
• Alice は以下の操作を繰り返し、$P$ を昇順ソートします。
  • $1$ 以上 $NK$ 以下の整数 $i, j(i\neq j)$ を選び、$P_{i}$ と $P_{j}$ を入れ替える。
  • このとき、$|i - j|$ が $N$ の倍数なら、Alice は $1$ ポイントもらえる。

• Alice は最小の操作回数で $P$ を昇順ソートし、その上でもらえるポイントの和を最大化する行動をします。
• Alice が得るポイントの和を出力してください。

• $1\leq N\leq 500$
• $1\leq K\leq 10$
• $(P_{1}, P_{2}, \dots , P_{NK})$ は $(1, 2, \dots, NK)$ の順列
• 入力は全て整数

まず、順列の任意位置swapによる操作回数最小化は、置換グラフの連結成分数で求められる。

• $i→P_i$ に辺を張ったグラフ（置換グラフ）を考えると、連結成分はいくつかのサイクルに分かれる。
• サイクル毎に独立に、サイズ $L$ のサイクルは $L-1$ 回で構成要素を正しい位置に並び替えられ、それが最小となる。

この時、「同じ連結成分内にある2要素をswapする」ことさえ守れば、操作順は特に関係ない。

差が $N$ の倍数である $(i,j)$ が、最初から別の連結成分（サイクル）にあったら、$(i,j)$ に対する操作はできない。

では、同じサイクルにあったら必ず操作できるのか？というと、否。
もともとが同じサイクルにある $(i,j)$ でも、同サイクル内の他のペアを先に操作したことでサイクルが再構成され、 $(i,j)$ に操作をするときには別のサイクルに分かれてしまっている、という場合は、やはり操作できない。
（じゃあってんで $(i,j)$ を先に操作すると、今度はまた別のペアができなくなる）

サイクル毎に独立に考える。サイクル順に頂点番号を並べて、$\mod{N}$ に置き換える。

0→9→8→21→15→22→19→16→17→11
^--------------------------------'
↓mod N (N=4の場合)

0→1→0→1→3→2→3→0→1→3
^--------------------------'

「$\mod{N}$ が同じ値同士（から向かう辺の先）をswap」したら1ポイント得られる。
ある2つを swap すると、サイクルは以下のように再構成される。

0→1→0→[1]→3→2→3→0→[1]→3
^------------------------------'
↓
           ,-------------------v
0→1→0→[1]  3→2→3→0→[1]  3
^             ^------------'   |
`------------------------------'

つまり、「ペアに挟まれた頂点」が全て、右側の頂点と合わせて別のサイクルになる。

この操作で別のサイクルになったペアは操作できなくなる。
逆に同じサイクルになったペアはまだ操作できるので、 結局、操作可能な条件は「swapするペアが交差してはいけない」というように言い換えられる。

      x  y  z     z  x  y        xとyをどちらも操作することはできない。
0→1→0→1→3→2→3→0→1→3     xとzなど、包含の関係はOK

また、以下のように同じ数字が3回以上出てくる場合、同じ箇所を重複して使うのはOKである。
この場合、$(0,7),(2,7)$ のように一方が一方を内包する形でペアを作ってもいいのだが、 今回は $(0,2),(2,7)$ のように使用する中で互いに近いもの同士をペアにする形に限定して考える（後のDPで考えやすくなるため）。 こうしても、作れるペア数や他の区間との交差には影響しない。

[0]→1→[0]→1→3→2→3→[0]→1→3    真ん中の[0]を2回使って2ペア取ってよい
 `------' `---------------'

以上の条件で、各サイクルで「交差しないで取れる最大ペア数」を求めたい。

サイクルはループしているが、適当な頂点で切り開いて考えてよい。
交差するペアはどこで切り開いても交差しているし、交わらない or 包含関係のペアはどこで切り開いても交差しないので。

適当な頂点で切り開いた、$\mod{N}$ されたサイクル順の列を、$B=(B_1,...,B_L)$ とする。$L$ をサイクル長とする。

区間DPをおこなう。

• $\mathrm{DP}[l,r]:=B[l,r)$ の範囲で、交差しないで取れる最大ペア数

だが、素直な区間DPでは、状態数 $O(L^2)$、遷移 $O(L)$ の、全体 $O(L^3)$ の計算量となる。 $L = NK = 5000$ になり得るので、普通にやるとTLEとなってしまう。

ここで、$K \le 10$ という制約が効いてくる。
「$P$ において、$\mod{N}$ が同じ数字は高々 $K$ 回しか登場しない」ので、 つまり、$B_l$ と同じ値になる $B_j$（$j \neq l$）は $9$ 個以下しか無い。

$\mathrm{DP}[l,r]$ を求める場合を考える。

• ① $l$ を含むペアを使わない
• ② $l$ を含むペアを使う
  • ②a) $l$ の相方は、$r-1$
  • ②b) $l$ の相方は、$l \lt j \lt r-1$ の範囲にある $j$

①の場合、$\mathrm{DP}[l+1,r]$ と等しくなる。

②a) の場合は、$B_l=B_{r-1}$ であることが条件となる。$\mathrm{DP}[l+1,r-1]+1$ となる。

②b) の場合、$l$ とのペア候補は高々 $K-1$ 個である。
$l$ の相方を $j$ とする場合、$j$ 自体は両方の区間に被って使えるため、$\mathrm{DP}[l,j+1]+\mathrm{DP}[j,r]$ となる。

... l           j             r-1 ...
    0     0     0   0     0    ?
   [             ]
               [                ]

必ずしも $l$ のすぐ右の同じ値を相方とした方がよい、とは限らない点に注意。

... l       j       k
    0 1 2 3 0 3 2 1 0 ...    lは、j と相方としようとすると3つのペアが犠牲になる。
      | | `---' | |          j でポイントを得ることは諦めて、k とペアにした方がよい。
      | `-------' |
      `-----------'

これらを試した中での最大値が $\mathrm{DP}[l,r]$ となる。これは全体 $O((NK)^2K)$ で求められる。

なぜか途中まで、勘違いして $|i-j|$ が $N$ の倍数でなく $K$ の倍数になるものを求めようとしてた。
注意してても自然と思い込んじゃってるんだよな。おそろしや。

Python3

def get_cycle(n, ppp):
    used = [False] * n
    for i in range(n):
        if used[i]:
            continue
        s = i
        i = ppp[i]
        tmp = [s]
        used[s] = True
        while i != s:
            tmp.append(i)
            used[i] = True
            i = ppp[i]
        yield tmp


def solve(n, k, ppp):
    ppp = [p - 1 for p in ppp]
    ans = 0
    for grp in get_cycle(n * k, ppp):
        m = len(grp)
        grp = [p % n for p in grp]
        last_i = {}
        next_same = [n * k] * m
        for i in range(m):
            p = grp[i]
            if p in last_i:
                next_same[last_i[p]] = i
            last_i[p] = i
        dp = [[0] * (m + 1) for _ in range(m)]
        for w in range(2, m + 1):
            for l in range(m - w + 1):
                r = l + w
                tmp = dp[l + 1][r]
                if grp[l] == grp[r - 1]:
                    tmp = max(tmp, dp[l + 1][r - 1] + 1)
                mid = next_same[l]
                while mid < r - 1:
                    tmp = max(tmp, dp[l][mid + 1] + dp[mid][r])
                    mid = next_same[mid]
                dp[l][r] = tmp
        ans += dp[0][m]
    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
ans = solve(n, k, ppp)
print(ans)

C - Maximize Sum of Mex

• 正整数 $N$ と $(1, 2, \dots , N)$ の順列 $P = (P_{1}, P_{2}, \dots, P_{N})$が与えられます。
• $Q$ 個のクエリを処理してください。各クエリでは非負整数 $A_{0}, A_{1}, A_{2}$ が与えられるので以下の問題の答えを出力してください。なお、$A_{0} + A_{1} + A_{2} = N$ であることが保証されます。
  • 長さ $N$ の数列 $B$ であって、以下の条件をすべて満たす数列を good な数列とします。
    • $B_{i} = 0$ が成り立つ $1$ 以上 $N$ 以下の整数 $i$ はちょうど $A_{0}$ 個
    • $B_{i} = 1$ が成り立つ $1$ 以上 $N$ 以下の整数 $i$ はちょうど $A_{1}$ 個
    • $B_{i} = 2$ が成り立つ $1$ 以上 $N$ 以下の整数 $i$ はちょうど $A_{2}$ 個
  • 長さ $N$ の数列 $B$ に対して、スコアを以下のように定義します。
    • $\displaystyle\sum_{i = 1}^{N}\mathrm{MEX}(B_{i}, B_{P_{i}})$
    • ただし、$\mathrm{MEX}(x, y)$ は $x$ でも $y$ でもない最小の非負整数であると定義します。
  • good な数列全てに対するスコアの最大値を求めてください。

• $1\leq N\leq 3\times 10^{5}$
• $(P_{1}, P_{2}, \dots , P_{N})$ は $(1, 2, \dots , N)$ の順列
• $1\leq Q\leq 3\times 10^{5}$
• $0\leq A_{i}$
• それぞれのクエリに対して $A_{0} + A_{1} + A_{2} = N$
• 入力は全て整数

Bに続きサイクルの問題。

極論、場合分けを泥臭くおこなっていけば難しいアルゴリズムは不要なのだが、 それなりに上手く場合分けを減らす方法を見つけないと実装・バグ取り地獄に陥る（陥った）。

$P$ を置換グラフに変換し、辺で結ばれた2頂点の $B_i$ の関係性により、得点が得られる。
$\{0,1\}$ の組で $2$ 点得られ、$\{0,0\},\{0,2\}$ の組で $1$ 点、他は $0$ 点となる。

..--⓪--①--⓪--⓪--②--①--..
      2   2   1   1   0

この得点は、0に由来するものと1に由来するものに分けて考えられる。

• $0$ は、基本的に1つにつき両側で $2$ 点得られるが、$0$ 同士を隣接させると効果がダブってしまい損する。
• $1$ は、両側が $0$ の場所に置いたら $2$ 点、片側が $0$ の場所に置いたら $1$ 点得られる。
  • ※ $0$ で既に得ている得点から追加で得られる点

もし以下のことが言えれば、「まず $0$ を配置し、次に $1$ を配置する」という順での考察ができ、 場合分けにおいて「$0$ と $1$ の残数を同時に考慮する」という煩雑さがなくなって嬉しい。

• 仮説: 最大得点を達成する $0$ の配置は $A_1$ の値によらず、$A_0$ の値によってのみ決まる

これは正しく、貪欲法に近い $0$ の配置手順が存在する。

ひとまず「$0$ → $1$ の順に配置して得点を最大化する」という手順を踏もうとすると、以下のような手順が考えられる。

• $0$ を置いていく。
  • なるべく隣接させないように置いていく。
    • 特に、$1$ での得点を最大化するため、なるべく1つおきになるように配置する。
  • 最初から $2A_0$ 点をもらっておき、隣接させて置いたらそのような箇所1箇所につき、$1$ 点失う。
    • 単独頂点に置くのは1隣接と見なす。
  • 配置後、以下のように変数を定義する。
    • $p_2$: 両側に $0$ がある、$0$ を置いていない箇所数
    • $p_1$: 片側のみ $0$ がある、$0$ を置いていない箇所数
    • $y$: $0$ の隣接箇所数
• $1$ を置いていく。
  • $p_2→p_1$ の優先順位で置いていく。
  • $p_2,p_1$ を埋めて余った分は得点に寄与することはない。

得点を増やすためには、

• $0$ の配置において、$y$ は-1で寄与するためなるべく減らしたい
• $1$ の配置において、$p_2$ は多い方がよい。
  • $2A_0=2p_2+p_1+2y$ という関係式が成り立つ
  • $y$ が同じ中では $2p_2+p_1$ は一定値
    • $p_2$ が1増えて $p_1$ が2減ると、$1$ の配置時に得られる得点は、最大1上がる
  • $y$ が1増えると、$p_2$ が少なくとも $1$ 増えていないと、絶対に得にならない

ある2つの $0$ の配置方法 $f,g$ にて、以下がともに言えれば、$A_1$ の値に依らず $f$ の最終得点は常に $g$ 以上になるといえる。

• $y_f \le y_g$
• $p_{2,f} - y_f \ge p_{2,g} - y_g$

ここで、以下のような優先順位で $0$ を埋めていくことを考える。
やや天下り的ではあるが、効率よく $y$ を減らし $p_2$ を増やす配置を考えると割と自然に辿り着けるはず。

1. (A) 偶数長サイクルをちょうど敷き詰める
2. (B) それ以外でサイクルに隣接しないように置く
3. (C) (B)で余った一方に置く
4. (D) 単独頂点に置く
5. (E) その他

まず、(A) 偶数長サイクル（長さ $2m$）にちょうど $m$ 個の $0$ を1個置きに配置するのが強い。
$y$ を増やさず、$p_2$ を $m$ 個増やせ、最大効率である。

⓪--○--⓪  ○--○--○
｜      ｜  ｜    ／
○--⓪--○  ○--○      ○  ○

次は、(B) 偶数長（長さ $2m$）または奇数長サイクル（$2m-1$）に、$m-1$ 個以下の $0$ を配置できる。
$x$ 個置いたとすると、$y$ を増やさず、$p_2$ を $x-1$ 個、$p_1$ を $2$ 個増やせる。$p_2$ を作る効率が(A)よりわずかに劣る。

⓪--○--⓪  ○--⓪--○
｜      ｜  ｜    ／
○--⓪--○  ⓪--○      ○  ○

これ以上の $0$ を配置しようとすると、どうしても隣接が発生する。

(C) 長さ3以上の奇数長サイクルで (B) を最大までおこなうと、未配置が2個連続している箇所が残る。
この一方を $0$ にすることで、$y$ を1増やし、$p_2$ を1個増やし、$p_1$ は2減る。

⓪--○--⓪  ○--⓪--⓪ ←ここ
｜      ｜  ｜    ／
○--⓪--○  ⓪--○      ○  ○

(D) 単独頂点は、$y$ を1増やすのみ。

⓪--○--⓪  ○--⓪--⓪
｜      ｜  ｜    ／
○--⓪--○  ⓪--○      ⓪  ⓪

(E) ここまで来ると、もう「1つおき」の隙間を潰すしかない。1つにつき $y$ が2増え、$p_2$ が1減る。

以上の優先順位において、 $y$ は (A)(B)→(C)(D)→(E) の順に $0$ 1個あたりの発生数が多くなり、最小化されている。

また、どの優先順位においても、$0$ 1個あたりの $p_2-y$ の効率は 上位 ≧ 下位 であり、逆転することはない。

言い換えると、もし(B)や(C)に配置できるスペースが余っているのに(D)や(E)に配置されている⓪が存在するなら、移し替えて損しない。
（(A)への配置はまとまった個数が必要となるが、同じように、必要数の(B)以下の⓪があったら移し替えて損しない）

よって、上記の優先順位で配置することで、最大得点を達成する $0$ の配置の1つが得られる。

$1$ の配置で得られる得点は $p_2,p_1$ の個数のみから求められるため、 ほぼ「$0$ の配置をどうするか」だけ考えればよいことがわかった。

優先順位に従って $A_0$ 個の $0$ を配置するアルゴリズムを考える。

まず、(A) だけで完結できるなら、その方がよい。
つまり、偶数長サイクルの長さの多重集合 $(2m_1,2m_2,...,)$ の部分和で $2A_0$ を作れたら嬉しい。

部分和はナップサック問題のように考えられ、以下のDPで前計算できる。

• $\mathrm{DP}[i,j]:=i$ 番目のサイクルまで考慮して、サイクル長の和が $j$ である組合せを作れるか（bool）

これは愚直にやると $O(N^2)$ かかってしまうが、 同じ長さのサイクルは遷移をまとめることである程度高速化でき、 「スライド最小値」や「2冪にまとめる」などの方法で、$O(N \sqrt{N})$ または $O(N \sqrt{N} \log{N})$ で求められる。 （全アイテムのサイクル長の総和は $N$ 以下なので、異なる長さのサイクルは $O(\sqrt{N})$ 種類に限られる）

ちょうど $2A_0$ になる部分和を作れなかった場合でも、 とりあえず (A) の方法で配置できる最大数までは (A) で配置する。
その後、(B)の配置を考えるにあたり、以下に分岐する。

• 偶数長サイクルが残っている場合
• 偶数長サイクルが残っていない場合

偶数長サイクルが残っている場合、残っているサイクルは必ず未配置の $0$ を全て配置できるだけの長さを持つ（サイクル長＞未配置の0の2倍）。 でないと「(A) の方法で配置できる最大数までは (A) で配置」という前提に矛盾する。
よってその1サイクルに(B)の方法で配置して必ず $0$ を使い切り、(C)以降に配置することはない。

残っていない場合は奇数長サイクルに配置していく。 この場合は必ずしも1サイクルで完結するとは限らないが、なるべく長さの大きいサイクルから使用するのが良い。
同じ個数の $0$ を「でかい少数のサイクルに配置」「細かい多数のサイクルに配置」では、前者の方が $p_2$ を大きくできる。

サイクル長を大きい順にソートし、各サイクルに隣接無しで置ける $0$ の最大数の累積和をとっておくことで、 各クエリにおいて、未配置の $0$ を (B) の方法で配置するのに必要なサイクル数が特定できる。 そこから作れる $p_2$ と $p_1$ の個数が計算できる。

それでも $0$ が残る場合は (C)(D)(E) に配置していくが、これらは複雑ではないため割愛。

これで得られた $(p_2, p_1, y)$ から、総スコアを計算できる。
(A)での偶数長サイクルにちょうど配置できる0の個数と、(B)での奇数長サイクルの累積和の前計算さえあれば、各クエリは条件分岐のみの $O(1)$ で答えられる。

Python3

from bisect import bisect
from collections import defaultdict
from itertools import accumulate


def get_cycle(n, ppp):
    used = [False] * n
    for i in range(n):
        if used[i]:
            continue
        s = i
        i = ppp[i]
        tmp = [s]
        used[s] = True
        while i != s:
            tmp.append(i)
            used[i] = True
            i = ppp[i]
        yield tmp


def solve(n, ppp, q, queries):
    ppp = [p - 1 for p in ppp]
    size_count = defaultdict(int)
    for cycle in get_cycle(n, ppp):
        size_count[len(cycle)] += 1

    odd_cycles = []
    even_partial_sums = {0}
    iso_total_v = 0
    odd_total_c = 0
    odd_total_v = 0
    even_total_c = 0
    even_total_v = 0
    for s, c in size_count.items():
        if s % 2 == 0:
            even_total_c += c
            even_total_v += s * c
            b = (c + 1).bit_length() - 1
            for i in range(b):
                weight = (1 << i) * (s // 2)
                even_partial_sums.update({c + weight for c in even_partial_sums})
            r = c - (1 << b) + 1
            if r > 0:
                weight = r * (s // 2)
                even_partial_sums.update({c + weight for c in even_partial_sums})
        else:
            if s == 1:
                iso_total_v += c
            else:
                odd_total_c += c
                odd_total_v += s * c
                odd_cycles.extend([s // 2] * c)

    even_cycles = [0] * (n + 1)
    for c in even_partial_sums:
        even_cycles[c] = c
    for i in range(n):
        even_cycles[i + 1] = max(even_cycles[i + 1], even_cycles[i])

    odd_cycles.sort(reverse=True)
    odd_cycle_no_adjacent_max = sum(odd_cycles)
    odd_cycle_count = [0] * (n + 1)
    acc = 0
    for c in odd_cycles:
        odd_cycle_count[acc + 1] += 1
        acc += c
    for i in range(n):
        odd_cycle_count[i + 1] += odd_cycle_count[i]

    def put_zero(x):
        tmp = x * 2
        if even_cycles[x] == x:
            return tmp, x, 0
        if even_cycles[x] < even_cycles[-1]:
            return tmp, x - 1, 2
        p2 = even_cycles[x]
        x -= even_cycles[x]
        if x <= odd_cycle_no_adjacent_max:
            occ = odd_cycle_count[x]
            return tmp, p2 + x - occ, occ * 2
        p2 += odd_cycle_no_adjacent_max - odd_cycle_count[-1]
        p1 = odd_cycle_count[-1] * 2
        x -= odd_cycle_no_adjacent_max
        if x <= odd_cycle_count[-1]:
            return tmp - x, p2 + x, p1 - x * 2
        tmp -= odd_cycle_count[-1]
        p2 += odd_cycle_count[-1]
        p1 -= odd_cycle_count[-1] * 2
        x -= odd_cycle_count[-1]
        if x <= iso_total_v:
            return tmp - x, p2, p1
        tmp -= iso_total_v
        x -= iso_total_v
        return tmp - x * 2, p2 - x, p1

    ans = []
    for x, y, z in queries:
        score, p2, p1 = put_zero(x)
        score += min(p2, y) * 2
        y -= min(y, p2)
        score += min(p1, y)
        ans.append(score)

    return ans


n = int(input())
ppp = list(map(int, input().split()))
q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, ppp, q, queries)
print('\n'.join(map(str, ans)))