デンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309）F,G問題メモ

デンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309）

誤読により序盤の問題でWAを連発する回。（不定期に発生）

F - Box in Box

• 直方体が $N$ 個、それぞれ高さ、幅、奥行きが $h_i,w_i,d_i$
• 2つの直方体で、一方がもう一方に完全に内包される（同じ長さは不可）ようなものがあるか判定せよ
  • 必要なら回転させてもいい
• $2 \le N \le 2 \times 10^5$
• $1 \le h_i,w_i,d_i \le 10^9$

基本は 公式Editorial の通り。

上記ではセグメント木を使っているが、この問題は FenwickTree を使ってもよい。

通常、区間minはFenwickTree上で使うには厳しめの制約があるのだが、本問題では

• 求めたいのは常に $[0, i)$ という、先頭からの区間の値
• 各要素 $A_i$ は常にminで更新されるのみであり、現在より大きい値への上書きは発生しない

という条件を満たすので、FenwickTreeを使え、定数倍高速になる。

（まぁ、無理してFenwickTreeを使わないと通らないような時間制約でもないので、セグ木を使えばよいのだが）

Python3

G - Ban Permutation

• $1～N$ の順列 $P=(P_1,...,P_N)$ のうち、以下の条件を満たすものの個数を $\mod{998244353}$ で求めよ
  • 全ての $i$ に対して $|i-P_i| \ge X$
• $1 \le N \le 100$
• $1 \le X \le 5$

空の箱を $N$ 個並べて、番号の付いたボールを1から順にどれかの箱に1個ずつ入れていき、順列を作ることをイメージする。

ボール $i$ は「$i-X$ より前の箱」か「$i+X$ より後の箱」にしか入れられないので、 その範囲の空いている箱の数を $i=1,2,...,N$ で乗じていけば答えとなる。

ただ、$i-1$ 以前のボールをどこに入れたかにより、$i$ を入れられる箱の数が変わってくる。
$i$ が禁止されていない箱に多く入れてたら、その分 $i$ を入れるときに空いている箱は減る。

N=9  X=3  i=5
箱  1  2  3  4  5  6  7  8  9
    o  o  x  x  x  x  x  o  o    : 5の玉を入れられる範囲
    
    4           2  1  3          : 既に入れたボールの状態の一例
                                   このとき、5のボールは2,8,9の3箇所の箱に入れられる
    
    4              2     3  1    : 既に入れたボールの状態の一例2
                                   このとき、5のボールは2の1箇所の箱にしか入れられない

なので、その状態別に分けてDPをおこないたい。

いま仮に、$[1, i-X]$、$(i-X, i+X)$、$[i+X, N]$ で区間を分けて、 それぞれで $i-1$ までのボールを入れた個数が判明していたら、 $i$ のボールを入れられる箱の個数は計算できる。

大まかにこういう感じの情報をDPに持たせればよさそうなのだが、、、

ただ、それを $i+1$ に遷移させると、必要な区間が $[1, i-X+1]$、$(i-X+1, i+X+1)$、$[i+X+1, N]$ となる。
$i-X+1$ と $i+X$ が区間境界をまたいで移るが、 それらに入ってる/入ってないのが何通りかがわからないと遷移ができない。

区間でまとめて個数をカウントしているため、パッと分からなそうに見える。

ところが、2つのうち「$i+X$」の方にボールが入っている/入ってないパターン数は、実は計算できる。

$i$ の小さい方から考えている以上、$[i+X, N]$ にはこれまでどのボールでも自由に入れられた。
また、その入れ方は $i+X-1$ より前とは独立している。

よって、DPに記録されたパターンは対称的であり、確率で按分できる。
例えば $[i+X,N]$ に入れたボールの数が $r$ 個の時にDPの値が $k$ だとすると、

• 「$i+X～N$ の中から $r$ 個をランダムに選ぶとき、$i+X$ が選ばれる確率」を $p$ として
  • $i+X$ に入っているパターン数: $k \times p$
  • $i+X$ が空いているパターン数: $k \times (1-p)$

となる。

$i-X+1$ の方は残念ながら対称的ではないのでこのような按分はできない。
ただ、$X$ が十分小さいので、$(i-X,i+X)$ の状態はbitsetで管理してやればよい。

• $DP[i,j,S]=$ ボール $i$ まで入れる箱を決めて、$i+X$ より小さい箱に入れた個数が $j$ 個、うち $(i-X,i+X)$ の範囲の状態がbitset $S$ で表される状態のパターン数

こうすると、遷移は $O(1)$ であり、全体で $O(N^2 4^X)$ で求められる。

Python3