AtCoder Regular Contest 178 B,C,D,E問題メモ

AtCoder Regular Contest 178

Bみたいな問題、ひたすら時間かかってしまうな。おかげで後ろの問題が間に合わない……。

B - 1 + 6 = 7

• 正整数 $A,B,C$ が与えられる
• 以下を全て満たすような正整数の組 $(X,Y,Z)$ の個数を $\mod{998244353}$ で求めよ
  • $X$ は $A$ 桁（10進表記で）
  • $Y$ は $B$ 桁
  • $Z$ は $C$ 桁
  • $X+Y=Z$
• 1つの入力に $T$ ケース与えられる
• $1 \le T \le 10^5$
• $1 \le A,B,C \le 10^9$

$A \le B$ として一般性を失わないので、そうする。

足し算で繰り上がるのはせいぜい1桁なので、$B=C$ または $B+1=C$ である必要がある。そうでない場合は0通り。

この場合の問題は、以下のように言い換えられる。

例) d=A=B=C とし、d=7 とする。

9999999 個のボールがある。これを X,Y に分配する。
~~d桁~~
あらかじめ桁数保証のため Xに1000000個、Yに1000000個 配っておく。
                            ~~d桁~~       ~~d桁~~
残りを (X,Y,どちらでもない) の3グループに分けるような組合せが、答えとなる。
XとYが決まればZも自動的に決まり、Zも必ずd桁となる。

これは、(9999999-1000000-1000000+2) 個から2つの仕切りを選ぶ、と考えられるので

8000001_C_2 = 8000001 * 8000000 / 2 で求められる。

この考え方は $A=B=C$ とは限らない場合にも出てくるので、後続の説明のためにも一般化して式を立てると、以下のようになる。

• $f(A,B,C)={}_{10^{C}-10^{A-1}-10^{B-1}+1}C_{2}$

$f$ の意味合いは「$X$ が $A$ 桁以上、$Y$ が $B$ 桁以上、$Z$ が $C$ 桁以下で、$X+Y=Z$ を満たすような組の個数」となる。
$A=B=C$ の場合はいずれもちょうど $A,B,C$ 桁になることが保証されるので、この方法で求められる。

答えはmodで求まればよいので、10の累乗はmodをとりながら行う。

$A=B=C$ の場合とほぼ同じだが、$X$ が $A$ 桁を超えて $A+1$ 桁となってしまうような数え方も含まれるので除く必要がある。

$f(A,B,C)-f(A+1,B,C)$ が答えとなる。

$d=A=B$ とし、$d$ 桁の $X$ と $Y$ をそれぞれ独立に決める方法は、$(10^d-10^{d-1})^2$ 通り。

$X,Y$ を決めると $Z=X+Y$ は自動的に決まり、$C-1$ 桁か $C$ 桁のいずれかになる。
よって、$X,Y$ の決め方から、足して繰り上がりが発生しないものを引けばよい。

繰り上がりが発生しないものは、$f(A,B,C-1)$ 個となる。

$Y$ も $Z$ も、$A$ 桁目より上位の部分は自由度がなく、以下のように決まってしまう。

A=3  B=7  C=8

X       ???
Y   9999???    ※ Xの??? + Yの??? は4桁目へ繰り上がる必要がある
Z  10000???

よって、ほとんど $A=B=C-1$ の時と変わらなくなるのだが、 「$Y$ の “???” の部分は、$A$ 桁でなくても（最上位桁が0でも）よい」という違いがある。

$X$ と $Y$ の “???” を独立に決める方法は、$(10^A-10^{A-1})10^A$ 通りとなる。

また、除外対象（繰り上がりが発生しないもの）の計算においても、$Y$ には予めボールを配る必要は無く、${}_{10^{A}-10^{A-1}+1}C_{2}$ となる。

以上の4通りが全てである。

Python3

C - Sum of Abs 2

• 正整数 $N,L$ と長さ $N$ の正整数列 $A = (A_{1}, A_{2}, \dots , A_{N})$ が与えられます。
• $i = 1, 2, \dots , N$ について、以下の問いに答えてください。
  • $\displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = A_{i}$ を満たす、長さ $L$ の非負整数列 $B = (B_{1}, B_{2}, \dots B_{L})$ が存在するか判定し、存在するならそのような $B$ に対する $\max(B)$ の最小値を求めてください。

• $1\leq N \leq 2 \times 10 ^ {5}$
• $2\leq L \leq 2 \times 10 ^ {5}$
• $1\leq A_{i} \leq 2 \times 10 ^ {5}$
• 入力は全て整数

1個1個の要素から、隣接要素との差分に着目点を移せるかがポイント。

まず、$\displaystyle f(B) = \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}|$ の 計算に順番は関係なく、$B$ はソートされているものとしてよい。

すると、「$B_1=0$、長さ $L$ のソートされた非負整数列 $B$」と 「その隣接要素の差分を記録した長さ $L-1$ 個の非負整数列 $C$」は、1対1対応する。

B   0  3  3  4  6  6  6  8
            ↓↑
C     3  0  1  2  0  0  2

この時、$\sum {C} = B_L = \max(B)$ となる。

ところで、たとえば $B$ において左に5個、右に3個の境界にある位置の $C_i$ を1増やすと、$f(B)$ は $5 \times 3$ 増加する。

C     0  0  0  0  1  0  0
                 ↓
B   0  0  0  0  0  1  1  1

Bの左の5要素のそれぞれに対して、右の3要素との差分が1ずつ増える
→ 全体で 5x3 増える

この性質は、既にいくつか足された $C$ に対して追加で1増やしても変わらない。

よって、$i=1,...,L-1$ について、$C_i$ を1増やすと、それぞれ $i(L-i)$ だけ $f(B)$ が増えることになる。

• $\mathrm{DP}[k]=1(L-1),2(L-2),3(L-3),...$ を使って和を $k$ にするために必要な最小個数
  • 同じものを複数個使ってもよい

をすると、$\mathrm{DP}[A_i]$ が、各 $A_i$ に対する答えとなる。

ただ、$k$ は $O(\max(A)) \simeq 2 \times 10^5$ の範囲を動き、それぞれ遷移先が $O(L)$ 個あるので計算量は大丈夫？と思うが、

• $L$ が大きい時、各 $i(L-i)$ はさらに大きくなり、更新時、すぐに $k$ の範囲をオーバーしてしまう

そのため、実際に必要な更新箇所はあまり多くならない。$O(\max(A) ^ {3/2})$ で抑えられる。

Python3

D - Delete Range Mex

• $0～N-1$ の順列 $P$ に対し、以下のような操作を繰り返しおこなえるとする
  • $P$ の任意の連続区間 $[l,r]$ を決める
  • $P_{l},P_{l+1},...,P_{r}$ のMEXを $B$ とする。$B$ が $P$ に含まれていれば、取り除く
• 長さ $M$ の数列 $A=(A_1,...,A_M)$ が与えられる
  • $A$ の各要素は $0 \le A_i \le N-1$ で、互いに異なる
• 「操作を適切におこなうと $A$ にすることができる」ような $0～N-1$ の順列 $P$ の個数を、$\mod{998244353}$ で求めよ
• $1 \le M \le N \le 500$

ある $P$ から $A$ を作ろうとすると、$A$ に存在しない数を全て消す必要があるが、大きい方から消していくことになる。
たとえば6を消したら、以降、MEXを6以上にすることはできなくなるので。

また、「6」を消すためには最初の $P$ の中で、0～5 が全て6の 左 or 右 の同じ側に位置していないといけない。

.. 6 .. 1 5 .. 2 .. 4 3 0 ..   ○0～5を含む区間を指定することで、6を消せる
        ~~~~~~~~~~~~~~~~~      

.. 2 .. 1 5 .. 6 .. 4 3 0 ..   ×0～5を全て含めないと6は消せないが、
   ~~~~~~~~~~~~~~~~~~~~~~        そうすると6も含まれてしまい、MEXは7以上になって消せない

よって、以下の手順で $A$ から復元できるような $P$ の個数が、答えとなる。

• $A$ に存在しない数を、大きい方から $A$ に挿入していく
• $x$ を挿入する際は、$0～x-1$ の数が同じ側に位置するようにしなければならない

N = 12

A  9 3 4 0 1 5 7     存在しない数: 11 10 8 6 2
  ^ ^ ^ ^ ^ ^ ^ ^     o: その数字の挿入可能位置
  
  o             o    11: 両端のどちらか
  o             o    10: これも両端のどちらか。
                         11と同じ位置に挿入する場合は、11の内側で一意に決まる
  o o           o     8: 両端と、あと9の内側には入ってよい
                         11や10を挿入した位置に挿入する場合は、それらの内側
  o o         o o     6: 7の内側にも入ってよい。
                         ただし、8を挿入した位置の外側はダメ
  o o o o   o o o     2: 置ける位置がぐっと増える。
                         ただし、8や6を挿入した位置の外側はダメ

置ける位置は左右からだんだん広がっていくが、前の数字を置いた位置より外側に置くのはダメ、ということになる。

左右の挿入位置を持つ以下のDPで状態を管理できそう。

• $\mathrm{DP}[i,l,r]=$ 大きい方から $i$ 番目の挿入すべき値まで挿入して、左側で最も右に挿入した位置が $l$、右側で最も左に挿入した位置が $r$ の時の状態数

挿入位置のindexは、最初のAにおける隙間を基準とする。上例の通り、複数の数字を同じ位置へ挿入することになっても、後から挿入する方が内側になるように並べ方は一意に決まるので、「Aのどこに挿入したか」さえわかればよい。

            A    9 3 4 0 1 5 7
                ^ ^ ^ ^ ^ ^ ^ ^
挿入位置index   0 1 2 3 4 5 6 7

ただ、この方法では、$A$ に0から連続したいくつかの値（$0,1,2,3,...$ など）が含まれない場合、 そいつらを挿入する段階になると $l=r$ となってしまう可能性があり、そうなると「前の数字の内側」がどこなのか、曖昧になって状態管理が難しくなる。

よって、このDPで管理するのは、$\min(A)$ より上の値の挿入までとする。それなら、$l \lt r$ が保証され、「内側」が明確になり考えやすい。
$\min(A)$ 未満の値の挿入方法は、別途考える。

初期状態は、$DP[0,0,M]=1$

$i$ 番目の挿入すべき値を $X_i$ とする。

左に挿入する場合、$l$ を増やしていって、$A_l \lt X_i$ となる手前までのそれぞれに遷移できる。

右に挿入する場合、$r$ を減らしていって、$A_{r-1} \lt X_i$ となる手前までのそれぞれに遷移できる。

          A    9 3 4 0 1 5 7
   挿入位置   0 1 2 3 4 5 6 7
2が遷移可能   o o o o   o o o

↓l\r  0  1  2  3  4  5  6  7   i=5 として、X5 = 2 を挿入する場合、
  0                             挿入位置は l<=3 までと r>=5 までに遷移できる。
  1                   <  <  *
  2                         v   DP[i-1, 1, 7] からの遷移イメージ。
  3                         v    * の位置はダブルで加算
  :

DPの状態数が $O(N^3)$ あるため、遷移を愚直に1マスずつ加算していったらさらに $O(N)$ かかり、 全体で $O(N^4)$ となるためアウト。

2次元配列の中で連続していることを利用して累積和で更新すれば、全体 $O(N^3)$ のままで済む。
各 $X_i$ が、左、右それぞれどこまで内側に置けるかは、前もって $O(N)$ で事前計算できる。

$\min(A)$ より大きい挿入すべき値の個数を $K$ とし、$\mathrm{DP}[K,*,*]$ まで求められたとする。

$\min(A)=0$ の場合は、そのまま $\sum_l\sum_r\mathrm{DP}[K,l,r]$ が答え。以下、$\min(A) \ge 1$ とする。

たとえば $\min(A)=4$ として、$0,1,2,3$ の4つの値を挿入する方法の個数を考える。

この4数の並べ方は、まず0を置いて、1,2,3を順に先頭か末尾のいずれかにくっつけるような置き方でないといけない。
（元の $P$ の中で連続している必要は無いが、部分列として取り出したらその順でないといけない）

○ (3 0 1 2)
× (2 3 0 1)  ←3を消せない

よって $2^{\min(A)-1}$ 通りの並べ方がある。

$A[l:r]$ の間に「長さ $\min(A)$ の数列」を順番を保ったまま挿入する方法の個数は、${}_{\min(A)+r-l}C_{r-l}$ となる。

したがって、$\mathrm{DP}[K,l,r]$ ごとに、$2^{\min(A)-1} \times {}_{\min(A)+r-l}C_{r-l}$ だけ乗算し、その合計が答えとなる。

Python3

E - Serval Survival

• 長さ $L$ の橋の上にサーバルキャットが $N$ 匹いる
• $i$ 匹目のサーバルは橋の左から $A_i$ の位置にいる（$0 < A_1 < A_2 < \cdots < A_N < L$）
• $i = 1, 2, \ldots, N$ について、以下の問いに答えよ
  • サーバルたちは以下の 3 つの行動を順番に行う
    • 行動1: $i$ 匹目のサーバルを除く $N - 1$ 匹のサーバルが左右のいずれかの方を向く
    • 行動2: $i$ 匹目のサーバルが左右いずれかの方を向く
    • 行動3: 全てのサーバルが、Ants の行動ルールで一斉に動き出す
  • $i$ 匹目のサーバルは、行動2で方向を選ぶとき、他の $N - 1$ 匹の向いている方を見て行動3の際により長く橋の上にいられる方を選ぶ
  • 行動1で $N - 1$ 匹のサーバルが向く方向の組み合わせは $2^{N-1}$ 通りあるが、その全てにおける、$i$ 匹目のサーバルが橋の上にいられる時間の総和を $998244353$ で割ったあまりを求めよ
• $1 \leq N \leq 10^5$
• $0 < A_1 < A_2 < \cdots < A_N < L \leq 10^9$

横軸に橋上の位置、縦軸に時間を取ったグラフで各サーバルの位置を表す。
サーバルを区別しないとすると「衝突したら互いに引き返す」は「そのまますれ違う」として見た目上は変わらない。
サーバル $i$ が橋からいなくなる時間は、「どれかのサーバルが、左か右にまっすぐ進み続けて橋からいなくなる時間」と一致する（それ以外の時間で橋から出るサーバルは存在しないので）。

たとえば以下の例で、$i$ が右に進んだときの実際の軌跡を追っていくと、$i$ が橋から出るのは「$j$ からまっすぐ右に進んだとき」と一致することが分かる。また左に進んだときは、「$k$ からまっすぐ左に進んだとき」と一致する。

時|        ＼
間|          ＼／          ／
  |＼        ／＼        ／
  |  ＼    ／    ＼    ／
  |    ＼／   ?    ＼／     ／
  |    ／＼ ↖ ↗  ／＼   ／
--+---j-------i--------k------ 位置

行動1で $N-1$ 匹中 $L$ 匹が左を向いたとする。（$R=N-L-1$ 匹は右）

サーバル同士の相対的な位置は変わらないので、 最終的に左から出るのは初期位置で左から $L$ 匹にいたサーバルたち、 右から出るのは右から $R$ 匹にいたサーバルたちに確定する。
確定した中に $i$ が含まれていれば、$i$ は最初にどちらを向こうが、決まった方から出ざるを得ないことになる。

サーバルのindexを0-indexedとする。以下の3パターンとなる。

• ①$i \lt L$ のとき、サーバル $i$ は確定で左から出る
• ②$i = L$ のとき、自身が選んだ方から出る
• ③$i \gt L$ のとき、サーバル $i$ は確定で右から出る

この時、サーバル $i$ が橋の上にいる時間は以下のようになる。

• ①や②で、左から出る場合
  • 「$i$ 自身を含めて左を向いた中で左から $i$ 番目のサーバル（$j$ とする）が↖にまっすぐ移動した時間」と一致し、$A_j$
• ②や③で、右から出る場合
  • 「$i$ 自身を含めて右を向いた中で右から $N-i-1$ 番目のサーバル（$j$ とする）が↗にまっすぐ移動した時間」と一致し、$L-A_j$

つまり、①の場合、$i$ 自身は、長く橋に残るためには最初に右を向くのがよい。③の場合は左。
②の場合は自身が最初に向いた方から出ることになる。

ここで、主客転倒して「$j$ から右に進んだときの距離 $L-A_j$ は、様々な $i$ の答えに、何回寄与するのか？」を考える。
「パターン②で右に進む場合」「パターン③」を数え上げれば、左右逆転させて同じことをすれば、①と②で左に進んだ場合も求まる。

          ↗      ↖
--o--o---j--o---o---i---o---o--o------ 位置

|-自由-|   |--- ここからN-i-1個 ---|

サーバル $j$ の右には、$j,i$ 以外で $N-j-2$ 匹のサーバルがいる。
このうち $N-i-1$ 匹が右を向いたような初期配置の場合に、$L-A_j$ が $i$ の答えに寄与することになる。

サーバル $j$ の左にいる $j$ 匹の向きは自由。よって、$i$ への寄与は、様々な $j$ をまとめると、以下のようになる。

• $\displaystyle \sum_{j \lt i} (L-A_j) 2^j {}_{N-j-2}C_{N-i-1} = \sum_{j \lt i} (L-A_j)2^j(N-j-2)! \times \dfrac{1}{(N-i-1)!} \times \dfrac{1}{(i-j-1)!}$

これは素直には $O(N^2)$ かかるが、$i,j,i-j$ に依存する項の積に分解できるので、 $j,i-j$ を畳み込めば各 $i$ に対する結果が $O(N \log{N})$ で求められる。

一番左で↗に向いたサーバルを $j$、一番右で↖に向いたサーバル $k$ として、 橋を出るまでの時間について、$i$ は $L-A_j$ と $A_k$ を選べる。

↖↖...↖    ↗                ↖     ↗↗...↗
------------j--o--o--o--i--o--o--k-------------
              ~~~~~~~~~   ~~~~~~
              ここの↗ と ここの↖ の個数が一緒ならパターン②

i は、↗を向けば L-Aj 
      ↖を向けば Ak   の距離を実現できる。大きい方を選ぶ。

ここで、$L-A_j \gt A_k$ となる最も右の $k$ を $K_j$ とする。

 j    0   1   2   3   4   L=20
Aj    2   8   9  15  19
L-Aj 18  12  11   5   1

j=0              K0       j=0のとき、Ak が L-A0=18 より小さい最大の k は 3
j=1          K1           j=1のとき、Ak が L-A1=12 より小さい最大の k は 2
j=2          K2           j=2のとき、Ak が L-A2=11 より小さい最大の k は 2

$j$ の相手となる $k$ が $K_j$ 以下なら、$L-A_j$ の方が $i$ に寄与することになる。
逆に $K_j$ より右が $k$ だったら、サーバル $k$ の距離（$A_k$）の方が選ばれてしまうため、考えなくてよい。

（実際には、上例の $j=2$ のように $j=K_j$ となってしまうケースは、後の計算でまとめて処理しにくくなってしまう。この場合は明らかに $i$ のみに $L-A_j$ だけ寄与するため個別で処理し、$j \lt K_j$ であるもののみ、以下では扱う）

$j$ を固定し、$i,k$ を小さなケースで実験すると、$L-A_j$ は $j \le i \lt K_j$ までの $i$ に、 二項係数分だけ寄与するっぽいことが分かる。

|------j--o--o--o--o--o--Kj-------------

       1  5 10 10  5  1   ←各位置を i とした場合に、L-Aj が寄与する係数

|--------j2--o--o--o--Kj2-------------

          1  3  3  1      ←j を変えると Kj も変わりうる。二項係数も長さに即した値になる

これらを $i$ を軸にまとめ上げるには、以下の感じの、左端が1ずつ増加、右端が広義単調減少の 逆ピラミッド状に配置された二項係数を縦に合計したい。

    i  0  1  2  3  4  5  6  7  8  ...
-------o--o--o--o--o--o--o--o--o--
j
 0     1  8 28 56 70 56 28  8  1   × L-A0
 1        1  5 10 10  5  1         × L-A1
 2           1  4  6  4  1         × L-A2
 3              1  2  1            × L-A3
 4             ：  1               × L-A4
               ↓
    パターン②の i=3 への寄与は、(L-A0)*56 + (L-A1)*10 + (L-A2)*4 + (L-A3)*1

一筋縄ではいかないのだが、分割統治を用いる方法がある。
二項係数は、形式的冪級数では $(1+x)$ をその個数分だけ累乗したものと言い換えられるので、

    i    0     1     2     3     4     5     6     7     8
 0    (L-A0)*(1+x)*(1+x)*(1+x)*(1+x)*(1+x)*(1+x)*(1+x)*(1+x)
 1          (L-A1)*(1+x)*(1+x)*(1+x)*(1+x)*(1+x)
 2                (L-A2)*(1+x)*(1+x)*(1+x)*(1+x)
 3                      (L-A3)*(1+x)*(1+x)
 4                            (L-A4)

これを各行、かけ算し、位置を揃えて足し合わせた多項式 $F(x)$ の各 $x^i$ の係数が、求めたいものと考えることができる。

単純にするため各位置を□で表すと、 もし、仮に以下の■の部分を掛け合わせた多項式（位置を揃えて足し合わせ済み）が部分的に求められているとすれば

 j  i 0 1 2 3 4 5 6 7 8
 0   ■■■■■□□□□
 1     ■■□□□□
 2       ■□□□□
 3         □□□
 4           □

 j  i 0 1 2 3 4 5 6 7 8
 0   ■■■■■→→→→    そこに (1+x)^4 を乗じるのは、
 1     ■■→→→→        一度にまとめておこなえる、というのが根幹の発想。
 2       ■→→→→
 3         □□□
 4           □

右端の位置を揃えて合成していく。

 j  i 0 1 2 3 4 5 6 7 8    j=0 と 1 の部分的なマージ
 0   ■→→→□□□□□    
 1     ■□□□□□        右端が2ずれているので、
 2       □□□□□        2ずれる位置まで j=0 の畳み込みを進め、
 3         □□□          その結果に j=1 を足す
 4           □

 j  i 0 1 2 3 4 5 6 7 8    j=2 と 3 の部分的なマージ
 0   ◇◇◇◇□□□□□
 1     ◇□□□□□        同様に、j=2 について
 2       ■→→□□        右端のズレ分を考慮して畳み込みを進め、
 3         ■□□          j=3 を足す
 4           □

 j  i 0 1 2 3 4 5 6 7 8    [0,2) と [2,4) のマージ
 0   ■■■■→→→□□
 1     ■→→→□□        [0,2) の右端が揃う位置まで畳み込みを進め、
 2       ■■■□□        [2,4) を位置を合わせて足す
 3         ■□□
 4           □

これを繰り返すと、大きな配列を畳み込む回数を減らせる。
$\log{N}$ 回おこなわれる分割で、それぞれ長さ合計 $N$ までの畳み込みが行われるので、$O(N \log^2{N})$ となる。

以上を逆からも行えば答え。

注意点として、パターン②において「$j$ から↗」と「$k$ から↖」の距離が一致してしまうことがある。
「順方向に行う場合のみ、採用する」など、重複を除く必要がある。

Python3