第五回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 180）A,B,C,D問題メモ

第五回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 180）

A - ABA and BAB

• A, B からなる長さ $N$ の文字列 $S$ が与えられます．
• あなたは以下の $2$ 種類の操作を好きな順序で $0$ 回以上繰り返すことができます．
  • $S$ の中で ABA となっている (連続した) 部分を選び，それを A で置き換える．
  • $S$ の中で BAB となっている (連続した) 部分を選び，それを B で置き換える．
• 操作後の $S$ としてあり得る文字列の個数を $10^9+7$ で割ったあまりを求めてください．

• $1 \leq N \leq 250000$
• $S$ は A, B からなる長さ $N$ の文字列

ここのところ、○○で割ったあまりというと $998244353$ だったのに、唐突な $10^9+7$。（5分くらい気付かずに、あれ？っていってた）

$S$ の中で “…AA…” のように A が続いてるところは、操作の性質から、A の連続から変わることはない。B の連続も同じ。

よって、同じ文字の連続で区切って、各成分毎に考えたものを、最後にくっつけると考えてよい。

BBABABAABABAAAABA
↓
B BABABA ABABA A A ABA

区切った後の各成分はABが交互に現れるが、 どこに操作しようが'AB'の組が1つ分消えることに変わりはない。（できあがる文字列が変わらない）

残り1または2文字になるまで2文字ずつ消していけるので、長さを $L$ として、 操作しない場合を含めて $\frac{L+1}{2}$ 通りのバリエーションがある。

各成分で掛け合わせたものが答え。

B BABABA ABABA A A ABA
1*   3  *  3  *1*1* 2   = 18

Python3

B - Improve Inversions

• $(1,2,\cdots,N)$ の順列 $P=(P_1,P_2,\cdots,P_N)$ が与えられます．また整数 $K$ も与えられます．
• あなたはこれから以下の操作を $0$ 回以上行います．
  • 整数 $l,r$ ($1 \leq l \lt r \leq N$) を選ぶ．ただしここで $(l,r)$ は以下の条件をすべて満たす必要がある．
    • $K \leq r-l$
    • 操作を行う段階で $P_l \gt P_r$ である．
    • 同じ組 $(l,r)$ を今までに選んだことが一度もない．
  • そして，$P_l$ と $P_r$ の値を入れ替える．
• あなたは操作回数を最大化したいです．その方法を一つ求めてください．

• $2 \leq N \leq 500$
• $1 \leq K \leq N-1$
• $(P_1,P_2,\cdots,P_N)$ は $(1,2,\cdots,N)$ の順列

入力例4に対し、出力例4に従って操作した時の変化を実際に追ってみると、 5と4、6と5など、なるべく数値的に近いペアをスワップしている様子が観察できる。
（ただし、2数の差は1であることが多いものの、必ずしもそうではなく、2や3の時もある）

[7, 6, 5, 9, 8, 2, 0, 4, 1, 3]    i  j
       v              v           3  8
[7, 6, 4, 9, 8, 2, 0, 5, 1, 3]
    v                 v           2  8
[7, 5, 4, 9, 8, 2, 0, 6, 1, 3]
       v                    v     3 10
[7, 5, 3, 9, 8, 2, 0, 6, 1, 4]
             :

なので、距離 $K$ 以上離れている中で、差が小さいペアを優先して貪欲にスワップしてみると、通る（未証明）。

公式Editorialにある。

$P$ に対し、各要素の位置を示す数列（逆置換）を $Q$ とする。
操作を $Q$ に対するものとして考えると、以下を全て満たすとき、$Q_i$ と $Q_j$ でswapできる。

• $i \lt j$
• $Q_i - Q_j \ge K$
• $(Q_i,Q_j)$ はこれまで操作されたことが無い（異なる位置であっても、値のペアとして）

同様に入力例4で $Q$ の変化を追ってみると、

[7, 9, 6, 10, 8, 3, 2, 1, 5, 4]   Qi Qj
               ×                  3  8
[7, 9, 6, 10, 3, 8, 2, 1, 5, 4]
                  ×               2  8
[7, 9, 6, 10, 3, 2, 8, 1, 5, 4]
            ×                     3 10
[7, 9, 6, 3, 10, 2, 8, 1, 5, 4]

このように、なるべく隣り合う要素で、値が $K=5$ 以上離れたものをswapしていることがわかる。
（ただし、必ずしも隣接している要素のみでなく、1個飛ばし、2個飛ばしなどもある）

例えば 3 にとって、「自分より左にある、$3+K=8$ より大きい要素」には、8,9,10が存在する。
3に位置的に近い方からswapしていくと、必ずこの3つの全てとのswapが発生するようにできる。

以下のような「疑似転倒数」（この解説だけの用語）を定義すると、

• $i \lt j$ かつ $Q_i - Q_j \ge K$ を満たす $(i,j)$ の個数

操作によって疑似転倒数は必ず1以上減少するため、初期状態の疑似転倒数が操作回数の上限となる。

■Q上でXとYをswapした場合の、疑似転倒数の変化
(例) K=5 X=19 Y=12

....  19  ....  12  ....
           ↓               XとY自体の疑似転倒数は1減る
....  12  ....  19  ....

|--|                |--|    この範囲にある数は、swapによって転倒状態に影響はない
          |--|              XとYに挟まれた数は変化する可能性がある

X-Y<2K の場合、XとYに挟まれた数は以下の5通りに場合分けできる
                  例
       x <= Y-K:   7  19との転倒はなくなるが、12と新たに転倒、差し引き   0
Y-K <  x <= X-K:  13  19との転倒がなくなり、12はそもそも転倒対象でない。-1
X-K <  x <  Y+K:  15  19とも12とも転倒対象でない。                       0
Y+K <= x <  X+K:  20  12との転倒がなくなり、19はそもそも転倒対象でない。-1
X+K <= x          25  12との転倒はなくなるが、19と新たに転倒、差し引き   0


(例) K=5 X=25 Y=12
....  25  ....  12  ....
           ↓               XとY自体の疑似転倒数は1減る
....  12  ....  25  ....

X-Y>=2K の場合、XとYに挟まれた数は以下の5通りに場合分けできる
                  例
       x <= Y-K:   7  25との転倒はなくなるが、12と新たに転倒、差し引き   0
Y-K <  x <  Y+K:  14  25との転倒がなくなり、12はそもそも転倒対象でない。-1
Y+K <= x <= X-K:  18  25とも12とも転倒がなくなる。                      -2
X-K <  x <  X+K:  23  12との転倒がなくなり、25はそもそも転倒対象でない。-1
X+K <= x          30  12との転倒はなくなるが、25と新たに転倒、差し引き   0

いずれにしろ、操作により疑似転倒数は必ず1以上減ることが確認できる。

そして、なるべく位置的に近い要素からswapすることで必ず「1だけ」減少させるように操作できるので、上限を達成できる。
（上記の場合分けで2以上減るようなパターンは、そもそもXとYに挟まれた中に、 XまたはYとswap可能な他の要素がある場合に限られるので、そっちからswapすればよい）

具体的な実装としては、バブルソートのように $i=1,2,...,N$ の順に、 $Q_i$ より左にあって $Q_i$ と疑似転倒している要素を近い方から順次swapしていき、 $Q_i$ が行ける最も左まで移動させる、ということを繰り返していくと $O(N^2)$ となる。

または、indexの差分 $d=j-i$ を小さい方から $d=1,2,...,N-1$ と決め打って、$Q_i - Q_{i+d} \ge K$ を満たすものが見つかったらswap、 リセットしてまた $d=1$ から探し、見つからなくなったら終了という方法でも、 雑な見積もりでは最悪 $O(N^4)$ となるものの、実際はだいたいすぐに見つかるためか、間に合う（ちゃんとした解析はしてない）。

Python3

C - Subsequence and Prefix Sum

• 長さ $N$ の整数列 $A=(A_1,A_2,\cdots,A_N)$ が与えられます．
• あなたは以下の操作をちょうど $1$ 回行います．
  • $A$ の (連続とは限らない) 非空な部分列を選び，それを累積和で置き換える．
  • より正確に述べれば，
    • まず $1 \leq i_1 \lt i_2 \lt \cdots \lt i_k \leq N$ を満たす好きな長さの添字の列 $(i_1,i_2,\cdots,i_k)$ を決める．
    • その後，各 $j$ ($1 \leq j \leq k$) について，$A_{i_j}$ の値を $\sum_{1 \leq x \leq j} A_{i_x}$ で置き換える．この置き換えはすべて同時に行う．
• 操作後の $A$ としてあり得る数列の個数を $10^9+7$ で割ったあまりを求めてください．

• $1 \leq N \leq 100$
• $-10 \leq A_i \leq 10$
• 入力される値はすべて整数

見たことない操作。

つかみ所が無いので、何となくで、シンプルなDPを試してみる。

• $\mathrm{DP}_{仮}[i,j]=A_i$ まで採用有無を決めて、その時点の累積和が $j$ の時の、$(A_1,...,A_i)$ としてあり得る列の個数

まぁ、当然上手くいかない。何が上手くいかないのかを確認すると、

• 選んだ添字列 $(i_1,i_2,...)$ のうち最初の $A_{i1}$ は（累積和に影響はするが）それ自体は置き換わらない

という操作の性質があるので、異なる添字列でも操作後の $A$ が同じになってしまうものがある。

   A:  1  1  2
採用:  *     *  ┬ この2つは、操作後のAが一緒だが、
          *  *  ┘ DPでは重複して数えられてしまう

また、これは最初だけでなく、途中で累積和が0になった次の要素も同じことが言える

   A:  1  2 -3  1  1  2
採用:  *  *  *  *     *  ┬ この2つも、操作後のAが一緒だが、
       *  *  *     *  *  ┘ DPでは重複して数えられてしまう
             :
             ここで累積和が0になる

また、累積和が0になってから、最後に1要素だけ選んだものは、選ばなかったものと変わらない、という問題もある。

   A:  1  2 -3  1  1  2
採用:  *  *  *  *        ┬ この2つも、操作後のAが一緒だが、
       *  *  *           ┘ DPでは重複して数えられてしまう

これらの問題点を区別できるようにするため、累積和と採用数で、DPを3段階に分けて持つ。

• $\mathrm{DP}_0[i,k]=A_i$ まで決めて、累積和が0（全て未採用も含む）のうち、次に $A_j=k$ である要素を採用したときに他と重複しないものの個数
• $\mathrm{DP}_1[i,k]=A_i$ まで決めて、累積和が0になってから $A_j=k$（≠0）である要素を1個だけ採用した状態の個数
• $\mathrm{DP}_2[i,k]=A_i$ まで決めて、累積和が0になってから2要素以上採用した状態で、累積和が $k$（≠0）のものの個数

$DP_0[i]$ は直前の状態をほぼ引き継ぐので、添字 $i$ は省略して $DP_0[k]$ としてよい。

最初、$DP_0[k] = 1$（$k=-10～10$、実装上はindexをずらして表現）とする。

$A_i$（≠0）について処理する時、累積和が0の状態から最初に出現した $A_i$ に対してのみ、$DP_0$ から $DP_1$ に遷移したい。
$DP_1[i,A_i] += DP_0[A_i]$ とした後に $DP_0[A_i]=0$ として、次以降に $A_j=A_i$ である $j$ が来ても状態を加算しないようにしておく。

その後、$DP_1$ と $DP_2$ について処理する。
通常は、$DP_2[i,s+A_i] += DP_{1 \ or \ 2}[i-1,s]$ のように遷移していけばよい。

しかし、例えば $s=-A_i$ からの遷移では累積和が0になる。
その場合、$DP_2$ には遷移させず、$k=-10～10$ につき $DP_0[k]+=DP_1[i-1,-A_i]$ として、 $DP_0$ に新たに累積和が0になったパターン分を加算する。

「途中で累積和が0になった際のパターン数の総和」+「最終的な $DP_2$ に記録されたパターン数の総和」が答えとなる。

Python3

D - Division into 3

• 長さ $N$ の整数列 $A=(A_1,A_2,\cdots,A_N)$ が与えられます．
• 以下の $Q$ 個のクエリに答えてください．
  • $i$ 番目のクエリ: 整数 $L_i,R_i$ が与えられる．
  • $B=(A_{L_i},A_{L_i+1},\cdots,A_{R_i})$ に対して次の問題を解け．
    • $B$ を $3$ つの非空な連続部分列に分割する．各連続部分列についてその要素の最大値を求める．これらの値の総和としてあり得る最小値を求めよ．

• $3 \leq N \leq 250000$
• $1 \leq Q \leq 250000$
• $1 \leq A_i \leq 10^8$
• $1 \leq L_i \leq R_i \leq N$
• $R_i-L_i \geq 2$
• 入力される値はすべて整数

公式Editorialを参考にしての自分用の整理。

あり得る分割のされ方は、ある程度決まってくる。

• ① (1,?,1): 両端は長さ1で、中央部分の長さが長い
• ② (?,1,?): どこかに長さ1の区間がある

証明は、クエリ区間中の最大値に着目するとできる。

$[L_i,R_i]$ の中の最大値を $M$ として、3つに分割した区間 $(X,Y,Z)$ の どこに $M$ （のうちの1つ）が入るか、を考える。 $M$ が入った区間は、どれだけ伸ばしても最大値が変わらない。

(a) 中央 Y に入る
  Li               Ri
   3 1 4 1 5[9]2 6 5
   X|------- Y ---|Z
  
  クエリの両端 Li,Ri は、それぞれ必ず X,Z に属する。
  → max(X), max(Z) はそれぞれ A_Li, A_Ri 未満になることはない。
  Y をどれだけ伸ばしても max(Y) は不変だが、
  X,Z を伸ばすと max(X),max(Z) は増えてしまうことがある。
  → Y を伸ばせるだけ伸ばし、X,Z は端の1つだけとして損しない。
  → (1,?,1) の形となる

(b) 左 X に入る

  適当に、仮の分け方を決めてみる。
  この時、Y の長さが2以上なら、(a)と同様の理論より、1になるまで切り詰めて損しない。
  
  Li               Ri
   5 6 2[9]5 1 3 1 4
   X------|--Y--|--Z    最大値が X に含まれる中での分け方の一例
           ↓
   5 6 2[9]5 1 3 1 4
   X----------|Y|--Z    Y は右の1個だけ残して切り詰めて、↑から悪化することはない
  
  どの位置を Y とするのが最適かは全通り試す必要があるが、
  いずれにしろ Y は長さ1となり、(?,1,?) の形だけを考えて問題ない。

(c) 右 Z に入る
  (b) の場合を左右反転させれば同様に考えられ、(?,1,?) の形となる。

(a)の場合、区間最大値をSparceTableやSegmentTreeなどで求められるように事前計算しておけば、$L_i,R_i$ から簡単に求まる。

(b)を考える。

ここで、区間の分け方を考察する際には最大値に着目したが、 答えを探索する際には、最大値がちゃんと想定の $X$ の位置に入っているかは（大変なので）特に考慮しないものとする。
(a)(b)(c)パターンを全て試した中で最適なものは、自動的に想定の位置に入っているはずなので。

よって、「$Y+max(Z)$ の最小化」を目指す。
これに $[L_i,R_i]$ の最大値を足したものを(b)の結果とする。

唐突だが、クエリ $[L_i,R_i]$ に答える時点で、$A$ の $1～R_i$ を以下のように、 末尾から見た最大値が更新される箇所で分けた各区間の情報が計算されているとする。

   Ai  30↑    o
       25│  o :        o            ※末尾から見たときに
         │    :    o oo:              最大値が更新される箇所で分割。
       15│    :o o     : o  o         （更新する数は各区間の右端の値となる）
        8│o  o: o   o  :o  o:o
        5│    :   *    :  * ::o o o   各区間の右端の値・位置と、区間内の最小値を記録。
         │ *  :        :    :: * o:
         ┼----]--------]----]]----]--→i
                                   Ri
右端の値    30     25     15  8   5
└のindex    5     14     19 20  25
最小値       3      5      6  -   4

これは、「各区間に含まれる値のいずれかを $Y$ としたければ、$\max(Z)$ はその区間の右端の値となる」ことを意味する。
ただし、長さ1の区間はこのような取り方ができないので、最小値（-）は計算上はINFとして扱う。

たとえば、$[L_i,R_i]=[10,25]$ のクエリに対して、

       Ai↑    o
         │  o :        o
         │    :    o oo:
         │    :o o     : o  o
         │o  o: o   o  :o  o:o
         │    :   *    :  * ::o o o
         │ *  :        :    :: * o:
         ┼----]--------]----]]----]--→i
                                   Ri
右端の値    30     20     15  8   5
└のindex    5     14     19 20  25
最小値       3      5      6  -   4
クエリ              |-C-|----D-----|
                   10             25

答えは、以下のいずれかになる。

• (D): クエリに完全に含まれる各区間の「最小値 + 右端の値」の中で最小の値
• (C) クエリが左にはみ出る区間の「$\min(L_i～右端のindex-1)$ + 右端の値」

上記の例の場合は、一番右の区間が、$4+5=9$ で最小となる。
これにクエリ内最大値 $20$ をあわせた $29$ を、(b)におけるこのクエリの結果とする。

(D)は、区間最小値を求めるSegmentTree、(C) もSegmentTreeやSparceTableなどで取得できる。
1つのクエリ毎に、必要な処理は

• $L_i$ をindex上で二分探索する（Cがどの区間になるかを調べる）
• (D) の答えをセグメント木のクエリで求める
• (C) の答えをSparceTableなどで求める

よって、1クエリ $O(\log{N})$ で求められる。

この方法では、(C) とは逆に「クエリが右にはみ出る部分」があると、上手く求めることができない。
たとえば、$[L_i,R_i]=[2,10]$ だったとして、 「$i=14$ ではなく、$i=10$ までにおける最大値」を右端の値としなければいけないが、 その情報は消えてしまっている。

よって、この「右端の値・位置・最小値」の情報は、$i=1,2,...$ と左から徐々に伸ばしながら構築していき、
右端がちょうど $R_i$ と一致したクエリに対して、そのタイミングで答えを求める、という方法になる。

この情報は、スタックを用いれば全体 $O(N)$、(D) を求めるためのセグメント木の更新を合わせると $O(N \log{N})$ で管理できる。

SparseTableの構築やその他の事前計算もあわせ、問題全体に対し計算量は $O((N+Q)\log{N})$ となる。

Python3