−目次

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

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

AtCoder Regular Contest 153

B - Grid Rotations

問題

$H \times W$ のグリッドにそれぞれ文字 $C_{i,j}$ が書かれている
$Q$ 回、以下の操作を行う
- $a_i,b_i$ が与えられる
- グリッドを、 $a_i$ 行目と $a_i+1$ 行目の間の線、 $b_i$ 列目と $b_i+1$ 列目の間の線で十字に分割する
- 分割された4つの長方形領域をそれぞれ180度回転する
最終的なグリッドに書かれた文字を出力せよ
$HW \le 5 \times 10^5$
$1 \le Q \le 2 \times 10^5$

解法

タテヨコは独立に考えていい。
最初の $i$ 行目が最終的に $r_i$ 行目、 $j$ 列目が $c_j$ 列目に移るなら、答えの $(r_i,c_j)$ のマスにあるのは $C_{i,j}$ である。

なので、1次元のクエリ操作を2回考えればよい。
縦方向（ $H$ 行）の操作を考えるとする。

愚直に考えると区間反転をいっぱいしなきゃいけなくて、そんなこと短時間でできるの？となる。
だが、今回は「2つに区切った区間をそれぞれまるっと反転」と決まっているので、実験してみると良い性質がすぐ見えてくる。

最初   1 2 3 4 5 6 7
      |-------|-----|    a=4
1回目  4 3 2 1 7 6 5
      |---|---------|    a=2
2回目  3 4 5 6 7 1 2
      |-----------|-|    a=6
3回目  1 7 6 5 4 3 2
      |-------|-----|    a=4
4回目  5 6 7 1 2 3 4

結局、1回の操作では $1,2,...,N$ の並びが逆順+転回を起こす。

特に2回の操作をまとめると、 $a_1→a_2$ の順で操作が発生すると $(a_1-a_2)\mod{H}$ だけ転回する。

よって、2個ずつ、いくつ転回したかを追っていって、 $Q$ が奇数なら最後の操作だけ愚直にやればよい。

Python3

C - ± Increasing Sequence

問題

$-1$ または $1$ からなる数列 $A=(A_1,...,A_N)$ が与えられる
以下の条件を全て満たす数列 $x=(x_1,...,x_N)$ を構築できるか判定し、可能なら一例を挙げよ
- $|x_i| \le 10^{12}$
- 狭義単調増加、つまり $x_i \lt x_{i+1}$
- $A_i \times x_i$ の $i=1～N$ にわたる総和が $0$
$1 \le N \le 2 \times 10^5$

解法

符号が $A_i$ によって反転されうるため、 $A_ix_i$ の正負が入り交じる。

総和を特定の1つとかある範囲で調整する、ということを考える際、狭義単調増加は置ける値の範囲が $i$ ごとに変わるため扱いにくくて、できれば広義単調増加で考えたい。

最初に $x'=(1,2,3,...,N)$ と仮決めして、そこからの差分 $y$ を考えると、 $y$ は広義単調増加であれば良くなる。

よって、 $x'$ をそのようにした際の $A_ix'_i$ の総和を $S$ とする。

A    -1  1 -1 -1  1 -1
x'    1  2  3  4  5  6
----------------------
     -1  2 -3 -4  5 -6  →  S = -7

ここで、たとえば $S$ が負で、 $A_1=-1$ だったとき、 $y_1$ は好きなだけ減らせるので、逆に総和は $S$ から好きなだけ増やせることになる。（ $10^{12}$ という制約はあるが、一端無視して）

A    -1  1 -1 -1  1 -1
----------------------
x'    1  2  3  4  5  6
y    -7  0  0  0  0  0

x    -6  2  3  4  5  6
----------------------
      6  2 -3 -4  5 -6  →  S = 0

また、同様に $S$ が負で、 $A_N=1$ だったとき、 $y_N$ は好きなだけ増やせるので、同様に $S$ から好きに増やせる。

$S$ が正の時は逆に、 $A_1=1$ または $A_N=-1$ なら総和を好きに減らせる。

じゃあ、そうでない時は？
$y$ には、先頭からある範囲までに一定値を減じる、または末尾からある範囲に一定値を加えてもよい。

たとえば $S$ が負（ $-k$ ）なら、 $y_1～y_j$ に一斉に一定値を減じたとき総和が $k$ 増加してくれればよいので、 $A_1～A_j$ の総和が負（特に微調整を考えると $-1$ ）ならよいことになる。

よって、 $A_i$ の先頭or末尾からの累積和を取っていって、

$S$ が負なら
- ①先頭からの累積和で、総和が $-1$ になるところ
- ②末尾からの累積和で、総和が $+1$ になるところ
- いずれかを見つけ、その範囲の $y$ に①なら $S$ を加算、②なら $S$ を減算
$S$ が正なら
- ③先頭からの累積和で、総和が $+1$ になるところ
- ④末尾からの累積和で、総和が $-1$ になるところ
- いずれかを見つけ、その範囲の $y$ に①なら $S$ を減算、②なら $S$ を加算

すれば、調整が可能となる。
（最初に述べた、先頭・末尾の1項だけで調整する操作も、この処理にまとめられる）

$S \neq 0$ で、そのような箇所が全く登場しないとき（-1と+1が、良い括弧列となっているとき）は、調整ができず不可能。

で、最後にこれが $10^{12}$ を超えないかだが、

$S$ は、最大 $\dfrac{N(N+1)}{2} \le 約 2 \times 10^{10}$ で、 $\pm S$ が $y_i$ の範囲
$x'$ の最大値は $2 \times 10^5$
よって $x=x'+y$ の絶対値は $10^{11}$ を超えない

ので大丈夫と分かる。

Python3

        
          
          
              
              import time
from itertools import accumulate
 
 
def solve(n, aaa):
    fwd_acc = list(accumulate(aaa))
    bwd_acc = list(accumulate(reversed(aaa)))
    bwd_acc.reverse()
    s = fwd_acc[-1]
 
    norm = 0
    for i, a in enumerate(aaa):
        norm += i * a
 
    if norm == 0:
        return list(range(n))
 
    if s != 0:
        whole_offset, norm = divmod(norm, s)
        ans = list(range(-whole_offset, n - whole_offset))
        if norm == 0:
            return ans
    else:
        ans = list(range(n))
 
    if norm > 0:
        fa = 0
        i = 0
        for i in range(n):
            fa += aaa[i]
            if fa > 0:
                break
        else:
            i = -1
        if i >= 0:
            for j in range(i + 1):
                ans[j] -= norm
            return ans
        fa = 0
        i = 0
        for i in range(n - 1, -1, -1):
            fa += aaa[i]
            if fa < 0:
                break
        else:
            i = -1
        if i >= 0:
            for j in range(i, n):
                ans[j] += norm
            return ans
        return False
    else:
        fa = 0
        i = 0
        for i in range(n):
            fa += aaa[i]
            if fa < 0:
                break
        else:
            i = -1
        if i >= 0:
            for j in range(i + 1):
                ans[j] += norm
            return ans
        fa = 0
        i = 0
        for i in range(n - 1, -1, -1):
            fa += aaa[i]
            if fa > 0:
                break
        else:
            i = -1
        if i >= 0:
            for j in range(i, n):
                ans[j] -= norm
            return ans
        return False
 
 
def check(n, aaa, ans):
    s = 0
    for a, b in zip(aaa, ans):
        s += a * b
    if s != 0:
        raise
 
    for i in range(n - 1):
        if ans[i] >= ans[i + 1]:
            time.sleep(3)
 
 
n = int(input())
aaa = list(map(int, input().split()))
 
ans = solve(n, aaa)
 
if ans:
    print('Yes')
    print(*ans)
else:
    print('No')

            

        
      

D - Sum of Sum of Digits

問題

$N$ 個の整数 $A_1,...,A_N$ がある
$f(x)$ を、正整数 $x$ の10進表記での各桁の和とする（ $f(153)=1+5+3=9$ ）
非負整数 $x$ を決めたとき、 $\displaystyle \sum_{i=1}^{N} (f(A_i+x))$ としてあり得る最小値を求めよ

例

A = ( 4 13  8  6)

x=7 とすると、

f( 4+7) = f(11) = 2
f(13+7) = f(20) = 2
f( 8+7) = f(15) = 6
f( 6+7) = f(13) = 4
                 ~~~ 総和は 14

解法

考察は下の桁から考えた方がわかりやすいように思うが、実装は上の桁から行う。ややこしい。

数列 $X$ に対し、問題で求められる値（適切な $x$ を加算したときの $\displaystyle \sum_{i=1}^{N} (f(X_i+x))$ の最小値）を、 $F(X)$ とする。

すると、下の桁から再帰的に求めるようなアルゴリズムができる。（実際はこのままではTLEだが）

A = (141, 926, 358, 793) とする。
下1桁を考えると、(1,6,8,3) である。

x=0 → 1 + 6 + 8 + 3 + F((14,92,35,79))

x=2 → 3 + 8 + 0 + 5 + F((14,92,36,79))  358 が 360 に繰り上がっている
               ~                ~~
x=4 → 5 + 0 + 2 + 7 + F((14,93,36,79))
           ~                 ~~
x=7 → 8 + 3 + 5 + 0 + F((14,93,36,80))
                   ~               ~~
x=9 → 0 + 5 + 7 + 2 + F((15,93,36,80))
       ~                  ~~

答えは、この5つの場合の中の最小値

$x$ の加算による繰り上がりを反映した上で、各 $A_i$ を10で切り捨て除算したような $A'$ に対する $F(A')$ を求める問題に再帰的に縮小できる。

制約的に9回再帰すれば十分であり、その頃には $A$ の値は0か1になっている。
そしたらもう $x$ を足して繰り上げる意味は無いので、 $F(A)=sum(A)$ となる。

$F()$ の引数となりうる状態数は、各桁につき「 $N$ 個のうちどこかまでが繰り上がった状態」なので、 $N+1$ 通り。
$A_i$ の桁数の最大値を $K(\le 9)$ とすると、全部で $O(KN)$ となる。
実行制限時間に間に合わせるには、各 $F()$ を求めるのに $O(1)～O(K)$ 程度までなら大丈夫。

しかし、下の桁からの再帰を素直に実装すると、1つの状態の計算に $O(N)$ かかってしまう。これはダメ。

上の例において、例えば $F((14,92,35,79))$ の結果から $F((14,92,36,79)),F((14,93,36,79)),...$ が順次差分計算できることを利用すれば、ならして $O(1)$ で求められる。

そのような実装は、下の桁からの再帰ではやりにくいので、上の桁から埋めていく。

自分のDPの定義は、あまり説明しやすい実装では無い（もっとわかりやすいDP定義による実装がありそう）が、、、

$\rm{DP}[i,j]=$ 以下のように作られた $B_i$ に対し、 $B_i[j]$ の下1桁がちょうど繰り上がる場合の $F(B_i)$
- $A$ を $A_k \% 10^i$ を基準に降順ソートする
- $B_i[k] = A_k / 10^{i-1}$ （切り捨て除算）とする
$j=0$ の場合は、1つも繰り上がりが発生しない場合の $F(B_i)$

例
A = (141, 926, 358, 793)

DP[2,3]:
  100で割ったあまりの 41,26,58,93 を基準に降順ソート → (793, 358, 141, 926)
  その後、10で割る → B2 = (79, 35, 14, 92)
  
  このB2に対し、B2[3]=14 がちょうど繰り上がる（足す数 $x$ の下1桁が6である）前提での F(B2)

同様に $B_3=(9,7,3,1)$ である。
$DP[3,:]$ から $DP[2,:]$ を求めるにあたり、 $B_2$ と $B_3$ の間で元となった $A_i$ の位置関係 $P_2$ を求めておく。

 i     1       2       3       4
B3   9(926)  7(793)  3(358)  1(141)     ... B3としての値(元のAiの値)

B2  79(793) 35(358) 14(141) 92(926)     ... B2としての値(元のAiの値)
P2     2       3       4       1        ... B2における、元のAiのB3における位置

$DP[3,:]$ と $P_2[:]$ から $DP[2,:]$ を求める。

B2  j  xの下1桁  x加算後のB2の下1桁の和  上の桁
↓  0      0           20       +      F(7,3,1,9)  = DP[2,0]
79  1      1           14       +      F(8,3,1,9)  = DP[2,1]
35  2      5           20       +      F(8,4,1,9)  = DP[2,2]
14  3      6           14       +      F(8,4,2,9)  = DP[2,3]
92  4      8           12       +      F(8,4,2,10) = DP[2,4]

B3  j  xの下1桁  x加算後のB3の下1桁の和  上の桁
↓  0      0           20       +      F(0,0,0,0)  = 20 = DP[3,0]
 9  1      1           14       +      F(1,0,0,0)  = 15 = DP[3,1]
 7  2      3           12       +      F(1,1,0,0)  = 14 = DP[3,2]
 3  3      7           18       +      F(1,1,1,0)  = 21 = DP[3,3]
 1  4      9           16       +      F(1,1,1,1)  = 20 = DP[3,4]

「 $x$ 加算後の $B_2$ の下1桁の和」は、、、

まず素の状態で $B_2$ の下1桁の総和を取る( $9+5+4+2=20$ )。これが $j=0$ のとき。
$j=1$ のとき、 $x$ の下1桁は1のため、 $N$ 個の数に1が足され、うち $j=1$ 個が繰り上がる（桁和が10減る）
- → $j=0$ の時の差分から、 $20 + 1*N - 1*10 = 14$
$j=2$ のとき、 $x$ の下1桁は5のため、 $N$ 個の数に5が足され、うち $j=2$ 個が繰り上がる
- → $j=0$ の時の差分から、 $20 + 5*N - 2*10 = 20$
$j=3$ のとき、 $x$ の下1桁は6のため、 $N$ 個の数に6が足され、うち $j=3$ 個が繰り上がる
- → $j=0$ の時の差分から、 $20 + 6*N - 3*10 = 14$

、、、としていくと、 $O(N)$ で全体を求められる。

$DP[3,:]$ と $P_2[:]$ から $DP[2,:]$ を求める際も、似たような差分計算ができる。

まず、 $DP[2,0]$ を求める際に必要となる $F(7,3,1,9) = \min(DP[3,:]) = 14$ である。
$DP[2,1]$ を求める際に必要となる F(8,3,1,9) は、、、
- $B_3$ における $P_2[1]=2$ 番目の項が1増える (9,7,3,1) → (9,8,3,1)
- 差分を考えると、
  - 1つの項が1増えたため、 $DP[3,:]$ から各項が 1 ずつ増える
  - $B_3$ の値が1増えた $DP[3,2]$ だけは、 $N$ 減る
    - ※ $x$ 加算後の下1桁の和の更新方法を考えれば、こうなることがわかる
  - これによって、初期状態より $DP[3,2]$ が小さくなったら、最適な $\min(DP[3,:])$ が更新される
$DP[2,2]$ を求める際に必要となる F(8,4,1,9) は、、、
- $B_3$ における $P_2[2]=3$ 番目の項が1増える (9,8,3,1) → (9,8,4,1)
- 差分を考えると、
  - 初期から2つの項が1増えたため、 $DP[3,:]$ にとっては各項が 1 ずつ増える
  - $B_3$ の値が1増えた $DP[3,3]$ だけは、 $N$ 減る
  - これによって、 $b+2$ より $DP[3,3]$ が小さくなったら、最適な $\min(DP[3,:])$ が更新される

…としていくと、こちらもならして $O(N)$ で $DP[2,:]$ を埋められる。

例:
DP[2,0]で必要な F(7,3,1,9):

  DP[3,:] =  (20, 15, 14, 21, 20)   →   F(7,3,1,9) = min(DP[3,:]) = 14

DP[2,1]で必要な F(8,3,1,9):

  ・DP[3,:] の各項に1足す
  ・繰り上がった 7 (元のAi=793)がB3で位置するindex = 2 なので、DP[3,2] からN引く
  
  DP'[3,:]=  (21, 16, 11, 22, 21)   →   F(8,3,1,9) = min(DP'[3,:]) = 11

DP[2,2]で必要な F(8,4,1,9):

  ・DP[3,:] の各項にさらに1足す
  ・繰り上がった 3 (元のAi=358)がB3で位置するindex = 3 なので、DP[3,3] からN引く
  
  DP''[3,:]= (22, 17, 12, 19, 22)   →   F(8,4,1,9) = min(DP''[3,:]) = 12

Python3

E - Deque Minimization

問題

'1'～'9'からなる文字列 $X$ に対し、以下を考える
- $X$ に以下の操作を行い、文字列 $S$ を得る
  - $S$ を空文字列で初期化する
  - $X_1,X_2,...,X_N$ の順に、 $S$ の先頭または末尾に挿入する（ $X_i$ は $X$ の $i$ 文字目）
- この操作により得ることができる $S$ のうち、整数としてみたときに最小のものを $f(X)$ とする
'1'～'9'からなる文字列 $Y$ が与えられるので、 $f(X)=Y$ となるような $X$ の個数を $\mod{998244353}$ で求めよ
$1 \le |Y| \le 200000$

解法

$f(X)$ を構成するための操作

$X_1$ はまぁそのまま挿入するとして、最小にするなら下記のようにすればよい。

$X_i$ （ $i \ge 2$ ）を $S$ に挿入するとき、その時点の $S$ の先頭を $S_1$ として、
- $S_1 \ge X_i$ なら、 $X_i$ を先頭に挿入
- $S_1 \lt X_i$ なら、 $X_i$ を末尾に挿入

$S_1=X_i$ の場合も本当に先頭でいいのか？と思うが、上記の方針をとる以上、

暫定の $S$ が全て同じ文字なら、先頭と末尾どちらに挿入しても変わらない
- 重複を除くため、先頭に挿入することで統一する
$S$ が全て同じでないなら、どこかではじめて $S_1$ と異なる文字 $c$ が出てくる
- この $c$ は、必ず $S_1$ より大きい
  - $c$ が $S_1$ より小さくて、 $S_1$ より後に挿入されたなら、先頭に来ているはず
  - $c$ が $S_1$ より小さくて、 $S_1$ より前に挿入されたなら、 $S_1$ の方が後に来ているはず
- よって $X_i$ は先頭に挿入し、 $S_1$ が続く長さを長くした方が良い

また、 $S=11233$ を作れるけど、途中段階では敢えて $S=32131$ みたいにすることで、最終的には $11233$ としたときより $S$ を小さくできる、みたいなことは起こらない。

$11233$ にしようと $32131$ にしようと、これ以降、何をどのような順で前・後ろに挿入可能かは全く同条件であり、

(同じ並び)11233(同じ並び)
(同じ並び)32131(同じ並び)

なら確実に前者の方が小さい。その時々で最小となるように前・後ろのどちらに挿入するかを決めていってよい。

よって、 $X$ が決まっているなら、そこから $f(X)$ を作る操作は意外と単純である。

先頭を固定した場合の数

先頭要素 $X_1$ が $Y$ の何文字目にあたるか（ $Y$ がどこから生成されていったか）を固定する。

$Y_i$ から生成されたと決め打つと、そこから後は左右に広がっていったことになるので、

$Y_{i-1}→Y_{i-2}→...→Y_2→Y_1$
$Y_{i+1}→Y_{i+2}→...→Y_N$

$X_2$ 以降の要素の並び順は、上記のような2つの列をマージしたものに限定される。
（マージ：ここでは、列の中での順序は保たれるように、2つを1つにまとめる操作を指す）

その上で、いくつかの制約がある。

先頭から昇順が続く範囲しか $X_1$ にできない

以下のような時に、3を最初に置くことはできない。

Y:  1  2  4  5  [3]  4  6  ...

3を最初に置いた後に5を挿入したとすると、その5をわざわざ前に持ってこないとこの $Y$ は作れないが、 $f(X)$ を作る操作に違反する。

上記の例なら、先頭の4つ 1,2,4,5 が、 $X_1$ となり得る範囲となる。

置く順序の制約

もし、長さ $n$ と $m$ の2列を単純にマージするなら、場合の数は ${}_{n+m}C_{n}$ で求められるが、そう単純でもない。

前に置かれるべき数が、誤って後に置かれることは基本的にないが、
後に置かれるべき数は、それ以前に自身より小さい値が前に置かれていないと、前に置かれてしまう。
そうなるとより小さい $f(X)$ が作れるような、数え上げの対象ではない $X$ となってしまう。

以下の2通りの場合に注意する。（①は、ちゃんと考えれば②にまとめられるかもしれないが、分けて考えた方がわかりやすい）

①同じ要素が連続している箇所を先頭とする場合
②後に置かれるべき数の列の中で、これまでより小さい値が出てくる場合

今、 $i=6,X_1=5$ を先頭に持ってくるとき、どうなるか考える。

i:  1  2  3  4  5  6  7  8  9 10 11
Y:  1  2  2  3  5 [5] 5  3  4  4  2

$X_2$ 以降は、このような2列のマージとなる。

前に置かれる 5→3→2→2→1
後に置かれる 5→3→4→4→2

次に来るのはいずれでも $5$ だが、 $5$ が来ると、 $f(X)$ の構築方法から考えるとこれは前に置かれることになる。
よって、 $X_2$ には、前に置かれる方の5しか来てはいけないことになる。

次も同様で、（最終的に $i=5,6$ に収まるべき）'55' がある状態に（最終的に $i=7$ に来るべき）'5'が来たら、これは前の方に置かれてしまうのでダメ。ここも前に置かれる方の3しか来れない。

暫定S:   3  5  5

残り列
前に置かれる  2→2→1
後に置かれる  5→3→4→4→2

$S$ の先頭が3になってはじめて、これ以降の5は後に置くべきとなったので、 $X_4$ には前に置かれる'2'も後に置かれるべき'5'も採用できる。

①の制約は、「同じ要素が連続している箇所を先頭とする場合は、その中の末尾以外は、自身より前の、より小さい値が1個置かれるまでは、前にしか置けない」という制約となる。

これにより、たとえば 1233[355555]566… という並びでは、「ある数字の連続箇所の末尾 (3)」と「次の数字の連続箇所の末尾以外 (55555)」において、それを先頭とした場合に実質的に考慮すべき「前に置かれるべき数の列」が同一となる。（3→3→2→1）

また特に、 $Y$ の先頭要素が連続していた場合は、その中の末尾のみ、先頭とすることができる。

Y:  1111112233...
    ~~~~~          先頭にはできない

例に戻って、続けて 5 が置かれた場合の続きを考える。

暫定S:   3  5  5  5

残り列
前に置かれる  2→2→1
後に置かれる  3→4→4→2

ここでもまた、次に後に置かれるべき'3'が来てしまうと前に置かれてしまうので、'2'が先に置かれる必要がある。

同様に、（しばらく進めて）後に置かれるべき列の最後の'2'も、前に置かれるべき'1'の後に置かれる必要がある。

これが②の制約で、「後に置かれるべき値が置かれるときには、先に、より小さい値が前に置かれていないといけない」となる。
ただし、いくつかの要所さえクリアすれば、要所以外は必然的に条件を満たすことが多い。

たとえば後に置かれるべき2つの'4'は、その前に既に'3'が置かれているので、先頭は2以下となっていることがわかっているため、勝手に条件はクリアしている。

要所となり得るのは、「後に置かれるべき列」の中でも「これまでに出てきたどの値より小さい値がはじめて出てきた時（狭義単調減少）」なので、特に値の範囲が1～9である本問題においては、たかだか7個である。

制約の列挙方法としては、例えば、以下のようにすればよい。
$Y$ の中で昇順が保たれる範囲を $Y_{Asc}$ 、それ以降を $Y_{NotAsc}$ とする。

$Y_{NotAsc}$ の先頭から累積minを取りながら、累積minを更新する要素 $Y_j$ を探す。 $Y_j$ に対し、 $Y_j-1$ 以下の要素が $Y_{Asc}$ 中で最後に出てくるのが $Y_i$ だったとすると、「 $Y_j$ が置かれる前に $Y_i$ が置かれなくてはいけない」という制約が見つけられる。
ただし、それより前に見つかった制約と $Y_i$ が同じであれば、無視してよい。

また、 $Y_{NotAsc}$ の中に $Y_1$ より小さい値が出てきたら、そいつを前に置かれることが阻止できないので、そのような $Y$ が $f(X)$ となるような $X$ は0個となる。
（これは最初に確認して例外処理してしまうのが、混乱しなくてよい）

先ほどからの例において、前後に置かれるべき列に②の制約を追加すると以下のようになる。

前に置かれる  2→2→1
             ↓      ↘
後に置かれる  3→4→4→2

具体的な数え上げ方法

先頭を固定して、マージするべき前後の列と制約も定まった。これをマージする方法の数を数え上げたい。

やりたいことはトポロジカルソートの数え上げではあるが、そんなの多項式時間では無理なので、「ベースは2列のマージ」であることを利用することになる。

経路数え上げに言い換えるのがわかりやすい。

前\後  -   3   4   4   2
 -     1 |           |
 2                   |
 2                   |
 1

左上から右か下に進み、右下までの経路数が答えだが、「前の'2'に進む前に後の'3'に立ち入ってはいけない」「前の'1'に進む前に後の'2'に立ち入ってはいけない」という制約は、上記のような壁で表現できる。

愚直には1マスずつ埋めていくとできるが、 $N \le 2 \times 10^5$ なので、 $O(N^2)$ は無理。
しかもこれ、あくまで先頭を固定した場合なので、先頭毎にこれだけかかる。

複数の“ある要素を先頭とした場合の数”を、ある程度まとめて計算できれば嬉しい。

そこで、「どこを先頭にしたって、列の末尾の部分や、そこにかかる制約は同じになる」ことに着目して、逆から考える。

i:  1  2  3  4  5  6  7  8  9 10 11
Y:  1  2  2  3  5  5  5  3  4  4  2

i=6 を先頭とした場合にマージしたい列
  前:  2→2→1
      ↓      `---↓
  後:  5→3→4→4→2

i=3 を先頭とした場合にマージしたい列
  前:  2→1
           `----------------↓
  後:  3→5→5→5→3→4→4→2

それぞれ長さは違うが、末尾から見たときの並びと、制約の張られる位置は同じ

→逆からDPすれば、複数の場合を一度に考えられる

末尾からとした場合、各 $Y_i$ を先頭とした場合の答えがDP配列のどこに現れるかが異なってくる。
答えとなり得る箇所を全て合計すると、全体の答えとなる。

逆にした場合のDPと、各要素を先頭としたときにどこを拾うべきかを示したのが、以下となる。
制約の壁は横になる。

      i     11  10   9   8   7   6   5   4   3   2   1
i 前\後  -   2   4   4   3   5   5   5   3   2   2   1
0  -     1                                  (2)  (1)
1  1    ~~~
2  2                                    (2)
3  2    ~~~~~~~~~~~~~~~~    (5) (5) (3)
4  3                            
5  5
6  5                    (5)

ここまでの考察から、拾うべき位置は以下のようになることがわかる。

基本的には、 $i$ を先頭とするなら、前の列は $i-1$ 、後の列は $i+1$ から始まるので、その斜めのラインに乗っかる
ただし同じ要素が連続している場合、その中での末尾要素以外は、1つ前の値の高さに揃えられる

拾うべき位置の高さがある程度揃う、というのが重要で、 $Y_{Asc}$ の中で同じ要素が連続している箇所の個数はたかだか9個なので、 9種類の高さの、連続する横範囲の値の合計がわかれば良いということになる。

また都合のいいことに、制約の壁が出現する位置も、性質上、同じ高さに来ることになる。

したがって、同じ要素が連続している箇所はイレギュラーのない綺麗な形となり、畳み込みでまとめて計算できる。

より具体的な方法を示すにあたり、後の列においてindexが逆順になっているのがやりにくいので、 $j=N+1-i$ として昇順に振り直す。
（このように、逆順のindexに変換する関数を $f(i)$ とする）

     (i     11  10   9   8   7   6   5   4   3   2   1)
      j  0   1   2   3   4   5   6   7   8   9  10  11
i 前\後  -   2   4   4   3   5   5   5   3   2   2   1
0  -     1                                  (2)  (1)
1  1    ~~~
2  2                                    (2)
3  2    ~~~~~~~~~~~~~~~~    (5) (5) (3)
4  3                            
5  5
6  5                    (5)

初期化
- $DP=[1,0,0,0,...]$
- $l=0$ : 左からDPが切り詰められる（壁によって防がれる）長さ
$Y_{Asc}$ で、出てくる種類数を $K$ 、 $i$ 種類目の要素が最後に出てくるindexを $a_i$ とする
- 便宜的に $a_0=0,a_{K+1}=|Y_{Asc}|+1$ を追加する
- 例) $Y_{Asc}=1223555$ なら、 $a=[0,1,3,4,7,8]$
$i=1,...,K$ の順に、
- $d=a_i-a_{i-1}-1$ …（次に求めるべき行と、DPが現在示す行の差分-1）
- $Q=[{}_{d}C_{d},{}_{d+1}C_{d},{}_{d+2}C_{d},...]$
  - $Q_k$ : 下段に $d$ 、右段に $k$ だけ移動する経路数
- $DP[l:]$ と $Q$ を畳み込み、新たな $DP[l:]$ とする
- $DP$ の必要な箇所を合計する
  - $e=a_{i+1}-a_i$ の時、 $f(i)-e～f(i)-1$ の範囲を合計
- $DP$ を切り詰める
  - 以降、もう答えとして計上した箇所は不要。 $DP=DP[:f(i)-e]$
  - 「 $Y_{ai}$ を置くまで $Y_j$ を置いてはいけない」制約が設定されていれば、 $l=f(j)$ とする

畳み込み、答えの範囲を合計する処理は、1回あたり $O(N \log{N})$ 、それがたかだか9回なので、十分高速となる。

Python3

        
          
          
              
              import numpy as np
 
 
def convolve(f, g):
    fft_len = 1
    true_len = len(f) + len(g) - 1
    while fft_len < true_len:
        fft_len <<= 1
 
    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
    Fh = Ff * Fg
 
    h = np.fft.irfft(Fh, fft_len)
    h = np.rint(h).astype(np.int64)
 
    return h[:true_len]
 
 
def convolve_mod(f, g, p):
    f1, f2 = np.divmod(f, 1 << 15)
    g1, g2 = np.divmod(g, 1 << 15)
 
    a = convolve(f1, g1) % p
    c = convolve(f2, g2) % p
    b = (convolve(f1 + f2, g1 + g2) - (a + c)) % p
 
    h = (a << 30) + (b << 15) + c
    return h % p
 
 
def check(y):
    n = len(y)
    y_arr = list(map(int, y))
 
    # asc_idx: 前から昇順が続く範囲で、i が初めて出てくるindex（1-indexed）
    # 出てこないのは0
    # 便宜的に、昇順が終わった次のindexを asc_idx[10] に保存
    asc_idx = [0] * 11
    asc_idx[y_arr[0]] = 1
    # 前からの昇順が破られているかどうか
    break_asc = False
 
    for i in range(1, n):
        if not break_asc:
            if y_arr[i - 1] > y_arr[i]:
                asc_idx[10] = i + 1
                break_asc = True
            elif y_arr[i - 1] < y_arr[i]:
                asc_idx[y_arr[i]] = i + 1
        if break_asc and y_arr[i] <= y_arr[0]:
            return None
    if asc_idx[10] == 0:
        asc_idx[10] = n + 1
 
    # less_idx: 前からの昇順範囲において、i 未満の値が最後に出てくるindex(1-indexed)
    less_idx = asc_idx.copy()
    for i in range(9, 0, -1):
        if less_idx[i] == 0:
            less_idx[i] = less_idx[i + 1]
    for i in range(1, 10):
        less_idx[i] -= 1
    less_idx = less_idx[:10]
 
    # constraints: 最初に置かれる要素を決めて、そこから両端に加えていくことを考えたとき、
    # 大小関係から、左に属するAは右に属するBより、元の数字で先に来ないといけない、という関係(A,B)
    constraints = {}
    dsc_min = 10
    con_min = n
    for i in range(asc_idx[10] - 1, n):
        if y_arr[i] < dsc_min and less_idx[y_arr[i]] < con_min:
            constraints[less_idx[y_arr[i]]] = i + 1
            dsc_min = y_arr[i]
            con_min = less_idx[y_arr[i]]
 
    return asc_idx, less_idx, constraints
 
 
def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs
 
 
def solve(y):
    MOD = 998244353
    n = len(y)
 
    results = check(y)
    if results is None:
        return 0
    asc_idx, less_idx, constraints = results
 
    # 昇順範囲でiが最後に出てくるindex, 出てこないのは0
    last_idx = []
    for i in range(1, 10):
        if asc_idx[i] == 0:
            continue
        for j in range(i + 1, 11):
            if asc_idx[j] != 0:
                last_idx.append(asc_idx[j] - 1)
                break
    last_idx.append(asc_idx[10])
 
    # constraints を、右端からのindexに変更
    constraints = {l: n + 1 - r for l, r in constraints.items()}
 
    facts, finvs = precompute_factorials(n, MOD)
    invs = [0] * (n + 1)
    for i in range(1, n + 1):
        invs[i] = finvs[i] * facts[i - 1] % MOD
 
    ans = 0
    dp = np.zeros(n, np.int64)
    dp[0] = 1
    l_col = 0
    pre_row = -1
    for i, li1 in enumerate(last_idx[:-1]):
        li2 = last_idx[i + 1]
        row = li1 - 1
        r_col = n - li1
        h = row - pre_row - 1
        w = r_col - l_col
        use = li2 - li1
 
        coef = [1]
        for i in range(w):
            coef.append(coef[-1] * (h + i + 1) % MOD * invs[i + 1] % MOD)
        coef = np.array(coef, dtype=np.int64)
 
        cnv = convolve_mod(dp, coef, MOD)
 
        ans += cnv[w - use + 1:w + 1].sum()
        ans %= MOD
 
        dp = cnv[:w - use + 1]
 
        if li1 in constraints:
            c = constraints[li1]
            dp = dp[c - l_col:]
            l_col = c
 
        pre_row = row
 
    return ans
 
 
y = input()
ans = solve(y)
print(ans)

            

        
      

−目次

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

B - Grid Rotations

問題

解法

C - ± Increasing Sequence

問題

解法

D - Sum of Sum of Digits

問題

例

解法

E - Deque Minimization

問題

解法

f(X)f(X) を構成するための操作

先頭を固定した場合の数

先頭から昇順が続く範囲しか X_1X_1 にできない

置く順序の制約

具体的な数え上げ方法

$f(X)$ を構成するための操作

先頭から昇順が続く範囲しか $X_1$ にできない