AtCoder Beginner Contest 407（Promotion of AtCoderJobs）E,F,G問題メモ

AtCoder Beginner Contest 407（Promotion of AtCoderJobs）

E - Most Valuable Parentheses

• 長さ $2N$ の非負整数列 $A = (A_1, \dots, A_{2N})$ が与えられます。
• 長さ $2N$ の括弧列 $s$ のスコアを、以下で得られる値として定義します。
  • $s$ の $i$ 文字目が ')' であるようなすべての整数 $i$ について $A_i$ の値を $0$ に変えた場合の、$A$ の要素の総和。
• 長さ $2N$ の正しい括弧列のスコアとしてありうる最大値を求めてください。
• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1 \leq T \leq 500$
• $1 \leq N \leq 2 \times 10^5$
• 各入力ファイルについて、すべてのテストケースの $N$ の総和は $2 \times 10^5$ 以下である。
• $0 \leq A_i \leq 10^9$ ($1 \leq i \leq 2N$)
• 入力はすべて整数である。

絶対、どっかで似た問題見てるはずなんだよな。頭の引き出しさん……

「正しい括弧列」の表し方・確認の仕方はいろいろあるが、この問題では以下が使いやすい。開き括弧と閉じ括弧の個数が等しいのは前提の上で、

• 全ての $i=1,2,...,|S|$ に対して、$S$ の先頭 $i$ 文字にある '(' の個数は $\lceil \frac{i}{2} \rceil$ 以上

つまり、

• 先頭 $1$ 文字のうち、$1$ 文字以上が '('
• 先頭 $3$ 文字のうち、$2$ 文字以上が '('
• 先頭 $5$ 文字のうち、$3$ 文字以上が '('
• :
• 先頭 $2N-1$ 文字のうち、$N$ 文字以上が '('

が満たされていれば良い。

HeapQueue を使って $A_{2i},A_{2i+1}$ を突っ込んで最大のものを1個取り出す、を繰り返せば良い。

Python3

F - Sums of Sliding Window Maximum

• 長さ $N$ の非負整数列 $A = (A_1, \dots, A_N)$ が与えられます。
• $k = 1, \dots, N$ について、次の問題を解いてください。
  • $A$ の連続部分列のうち長さが $k$ のものは $N-k+1$ 個ある。
  • それぞれの連続部分列について最大値を求めたとき、それらの合計を求めよ。

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^7$ ($1 \leq i \leq N$)
• 入力はすべて整数である。

答えとなる配列 $Ans=(x_1,x_2,...,x_N)$ を用意し、はじめは $0$ で初期化する。

$A_i$ の大きい方から（同率は適当に決める）順に、 「自身が、長さ $k=1,...,N$ の連続部分列それぞれで最大値となって寄与する分」を Ans に足し込んでいく。

              
k\A  3  1  4  1  5 [9] 2  6  5
1                  -+-

2               ----+-
                   -+----

3            -------+-
                ----+----
                   -+-------

4         ----------+-
             -------+----
                ----+-------
                   -+----------

5      -------------+-
          ----------+----
             -------+-------
                ----+----------

6   ----------------+-
       -------------+----
          ----------+-------
             -------+----------

7   ----------------+----
       -------------+-------
          ----------+----------

8   ----------------+-------
       -------------+----------

9   ----------------+----------

$9$ は $Ans=(x_1,...,x_9)$ にそれぞれ $1,2,3,4,4,4,3,2,1$ 回寄与する。

より一般的には、「区間の長さ $w$」「左にある要素数 $l$（自身を含む）」「右にある要素数 $r$（自身を含む）」としたとき、 Ansの $x_1,x_2,...,x_w$ にわたって、$u=\min(l,r,\lceil \frac{w}{2} \rceil)$ を上限として、 「$1,2,...,u-1,u,u,...,u,u,u-1,...,2,1$」というように寄与する。

次に大きい数は、既に処理された要素で分割された区間で同様に考えられる。

k\A  3  1  4  1  5  9  2 [6] 5
1                   |    -+-          w=3（9により分割されているため）
                    |                 l=2
2                   | ----+-          r=2
                    |    -+----
                    |                 x1,x2,x3 に 1,2,1 回ずつ寄与する
3                   | ----+----

k\A  3  1  4  1 [5] 9  2  6  5
1               -+- |     |           w=5
                    |     |           l=5
2            ----+- |     |           r=1
           :        |     |
5   -------------+- |     |           x1～x5 に 1,1,1,1,1 回ずつ寄与する

よって、「自身の左右で一番近い、既に処理されたindex」が取得できるとよい。
SortedSet や、二分探索付き FenwickTree などで実装できる。

Ansに足し込む部分はちょっと悩むが、途中で取得クエリが来るわけではなく、 最終的な結果を1回取得できればよいことを考えると、「差分の差分」を管理するというアイデアで実装できる。

■足し込みたい数列
  9 18 27 36 36 36 27 18  9

■差分
  9  9  9  9  0  0 -9 -9 -9 -9

■差分の差分
  9  0  0  0 -9  0 -9  0  0  0  9

このように、差分の差分で更新する箇所は1要素につき高々4箇所で済むので、 そこだけ足し込んでおいて、最後に2回累積和を取ると、答えとなる。

Python3

G - Domino Covering SUM

• $H$ 行 $W$ 列のマス目があります。
  • 上から $i$ 行目 $(1\leq i\leq H)$、左から $j$ 列目 $(1\leq j\leq W)$ のマスをマス $(i,j)$ と呼ぶことにします。
  • マス $(i,j)\ (1\leq i\leq H,1\leq j\leq W)$ には整数 $A _ {i,j}$ が書かれています。
• このマス目にドミノを $0$ 個以上置きます。
• $1$ つのドミノは隣り合う $2$ つのマス、つまり以下のどれかに置くことができます。
  • $1\leq i\leq H,1\leq j\lt W$ に対するマス $(i,j)$ とマス $(i,j+1)$
  • $1\leq i\lt H,1\leq j\leq W$ に対するマス $(i,j)$ とマス $(i+1,j)$
• ただし、同じマスに対して複数のドミノを置くことはできません。

• ドミノの置き方に対して、置き方のスコアをドミノが置かれていないマスに書かれた整数すべての和として定めます。
• ドミノの置き方のスコアとしてありうる最大値を求めてください。

• $1\leq H$
• $1\leq W$
• $HW\leq2000$
• $-10 ^ {12}\leq A _ {i,j}\leq10 ^ {12}\ (1\leq i\leq H,1\leq j\leq W)$
• 入力はすべて整数

「（盤面全体の数字の和）－（ドミノを置いた箇所の $A_{i,j}$ の総和）」が答えで、これを最大化したいので、 「ドミノを置いた箇所の $A_{i,j}$ の総和」が最小化できればよい。

グリッドグラフは二部グラフ、という性質を使った問題は過去にも出題されている。
マスを頂点とみなし、市松模様の白と黒で頂点をグループ分けすれば、 辺（＝隣接マス関係）は必ず2グループ間に張られ、同グループ間に辺が張られることはない。

グリッドににドミノを置く行為は、グラフ上では「辺を選ぶ」行為に相当する。
ドミノを重ねてはいけないという制約は、「選んだ辺が頂点を共有してはいけない」という制約になる。

これは、二部グラフ上のマッチング問題に置き換えられる。
今回は、辺にコストが決められていて、コストの総和を最小化させるように辺を選ぶので、「最小重みマッチング問題」となる。（必ずしも、最大マッチングでなくても良い点に注意）

最小重みマッチング問題は、最小費用流に置き換えて解ける。

以下のような $HW+2$ 頂点のグラフを構築すればよい。
ただし、$i+j$ が偶数の頂点をグループ $A$、奇数の頂点をグループ $B$ に属させるとする。
また、始点を $s$、終点を $t$ とする。

• $s$→グループAの各頂点間に、容量 $1$、コスト $0$ の辺
• グループBの各頂点→$t$ 間に、容量 $1$、コスト $0$ の辺
• 各隣接マス関係につき、その2マスに書かれた $A_{i,j}$ の和を $m$ として、容量 $1$、コスト $m$ の辺
  • ※辺は Aに属する頂点→Bに属する頂点 の方向に張る

ただし、今回は $m$ が負になりえるため、適当に下駄を履かせて非負にしておく。

流す量を1ずつ増やしていくと、しばらくは（下駄を元に戻した）コストが減少し続けるが、どこかで増加に転じるか、最大マッチングとなりそれ以上流せなくなる。
増加に転じたら探索は打ち切ってよい。

AtCoder Library にある mincostflow では、slope という関数があり、 少しずつ流量を増やしていったときのコストの線形区分関数を作成してくれる。

Python3