2022-02-06

ABC238 参加記録

ABC XOR ビット演算

コンテスト中AC: A〜D

A - Exponential or Quadratic
D - AND and SUM
- 公式解説メモ
- 連立方程式の解き方

A - Exponential or Quadratic

$n\leq 10^9$ から、 $2^n$ が64bit整数型に収まらなければ、直ちにYesです。
よって、64bit型を超えるまでは、実際に2を掛けていきます。そして、超えた時点でYesとします。
超えなかった場合は、実際に比較してみれば良いです。

2を掛ける最大回数は、おそらく64くらいだと思います。
オーバーフローの判定はC++(GCC?)なら、__builtin_sumlll_overflowでできます。
提出コード

D - AND and SUM

$a_i$ という風に表記したとき、2進数の下からiビット目とします。

$a_i=1$ の時、 $(x_i,y_i)=(1,1)$ とするしかありません。
$a_i=0$ の時、 $(x_i,y_i)=(0,1),(1,0),(0,0)$ の3パターンがあり得ます。少なくとも一方は0にする必要があり、それはどちらでも良いので、 $x_i = 0$ と仮定しておきます。この時、 $x = a$ となります。

$a_i,s_i$ 及び桁上がり $u$ によって、以下のように下の桁から順に、 $y_i$ を決定、もしくは、達成可能か決定できます。

$a_i=1$ の場合
このケースでは $(x_i,y_i)=(1,1)$ で、桁上がりが必ず発生します。
- $u=1$ の場合
  $(1,1)$ と桁上がり1を計算すると、1+1+1 = 11になります。
  - $s_i = 0$ の場合、計算結果と一致しないのでNoです。
  - $s_i = 1$ の場合、矛盾しないので問題ないです。
- $u=0$ の場合
  $(1,1)$ と桁上がり0を計算すると、1+1+0 = 10になります。
  - $s_i = 0$ の場合、矛盾しないので問題ないです。
  - $s_i = 1$ の場合、計算結果と一致しないのでNoです。
$a_i=0$
このケースでは $(x_i,y_i)=(0,?)$ です。
- $u=1$ の場合
  - $s_i = 0$ の場合、 $y_i = 1$ とします。0+1+1=10で、桁上がりが発生します。
  - $s_i = 1$ の場合、 $y_i = 0$ とします。0+0+1=01です。
- $u=0$ の場合
  - $s_i = 0$ の場合、 $y_i = 0$ とします。0+0+0=00です。
  - $s_i = 1$ の場合、 $y_i = 1$ とします。0+1+0=01です。

なお、十分に大きい桁(今回なら制約上60桁目)まで、上記処理を行った後、桁上がりが残っていた場合もNoになります。

提出コード

公式解説メモ

$x + y = x\ XOR\ y + 2(x\ XOR\ y)$

より、

$s = x\ XOR\ y + 2a$

$x\ XOR\ y = s - 2a$

$x\ XOR\ y \geq 0$ より、 $s-2a \geq 0$ を満たしていなければNo

$b = s-2a$ とおく。

$\begin{equation} x\ AND\ y = a \\ x\ XOR\ y = b \\ \end{equation}$

という連立方程式を解く問題となる。桁上がりは不要で、各bitのみを見れば良い。
$a_i = 1 \wedge b_i = 1$ となるbitがあると、達成できずNoとなる。
よって、 $a\ AND\ b = 0$ となるかどうかで判定ができる。

連立方程式の解き方

$x=a$ を仮定すると、 $a\ XOR\ y = b$ より、両辺のa XORを取ると、

$y = a\ XOR\ b$

となるので、 $a\ AND\ y=a$ より、

$a\ AND\ (a\ XOR\ b) = a$

を満たせば良いです。

公式解説は、 $a_i,b_i$ の組が4通りの考慮が必要で、更にそこからa AND b = 0という条件を導き出さないといけないので、それよりは多少楽かなと思いました。

提出コード

2022-02-05

ABC237E Skiing

ABC ダイクストラ負辺

コンテスト中にACしたものの、after_contestでTLEで、嘘解法でした。この記事は公式解説を自分用にまとめたもので、新たな情報などは無いです。

ここでは、標高が低いところから高いところに行く坂を下り坂、逆を上り坂と言うことにします。

2個目の条件を、
X→Yが登り坂なら楽しさが $2(H_X - H_Y)$ 増加する
と読み替えておきます。

例として、広場1から5へ移動した時の楽しさ $W$ を考えます。下り坂なら $\rightarrow$ 上り坂なら、 $\Rightarrow$ とします。

$1\rightarrow 2\rightarrow 4 \rightarrow 5$ $W=H_1 \color{red}{- H_2 + H_2} \color{blue}{- H_4 + H_4} - H_5=H_1 - H_5$
$1\rightarrow 2\Rightarrow 3 \rightarrow 5$ $W=H_1 \color{red}{- H_2 + H_2} \color{blue}{- H_3 + H_3} - H_5 + H_2 - H_3 =H_1 - H_5 - (H_3 - H_2)$
$1\Rightarrow 3\rightarrow 4\Rightarrow 2 \rightarrow 5$ $W=H_1 \color{red}{- H_3 + H_3}\color{blue}{- H_4 + H_4} \color{green}{- H_2 + H_2} - H_5 + H_1 - H_3 + H_4 - H_2 =H_1 - H_5 - \{(H_3 - H_1) + (H_2 - H_4)\}$

ここから、広場1から5への楽しさはすべて、

$W = H_1 - H_5 - C$ という形式をとり、 $H_1 - H_5$ は経路によらず一定
$X \Rightarrow Y$ という上り坂を取るたびに、 $C$ に $H_Y - H_X$ が足される

ことがわかります。

よって、 $W$ を最大化したい時、 $C$ を最小化すればよいことになります。

そのため、

下り坂なら、 $C$ に $0$ が足される
上り坂なら、広場XからYに移動する場合、 $C$ に $H_Y - H_X$ が足される

というようなグラフを考え、広場1から5までの最短経路を求めればよいことになります。
この時の最小コストを $C_{min}$ とすれば、 $W$ の最大値 $W_{max}$ は、
$W_{max} = H_1 - H_5 - C_{min}$
として求められます。

上記議論は広場5のみならず、一般の広場でも適用できることが予想できます。そのため、先程の言い換えたグラフにおいて、広場1から、各広場 $v$ への最短経路 $c_v$ を求めると、その広場での楽しさの最大値 $w_v$ は、
$w_v = H_1 - H_v - c_v$
という風に求められ、答えとなる全体での最大値はこれらのmaxを取れば良いと言うことになります。

なお、このグラフのコストは全て非負なのでダイクストラ法が適用でき、 $O(MlogN)$ で最短経路を求められます。

提出コード

ポテンシャル

テキストの公式解説ではポテンシャルで説明されていました。各頂点にポテンシャル $h_v$ を定め、uからvへの有向辺のコスト $w_i$ を $w'_i=w_i+h_u - h_v$ に変換します。例えば、 $s$ から $t$ への変換後における経路が、
$s \xrightarrow{w'_{1}} 1 \xrightarrow{w'_2} 2 \xrightarrow{w'_3} t$
であった時、 $s$ から $t$ へのコストの和 $d'_t$ は、
$d'_t = w'_1 + w'_2 + w'_3$
です。変換前のコストの和 $d_t$ は、
$d_t = w_1 + w_2 + w_3$ なので、 $d_t = w_1 + w_2 + w_3 = w'_1 + w'_2 + w'_3 + h_s - h_1 + h_1 - h_2 + h_2 - h_t = d'_t + h_s - h_t$

つまり、
$d_t = d'_t + h_s - h_t$

$h_s - h_t$ は経路によらず一定なので、 $d'_t$ を最小化すれば $d_t$ も最小化されます。よって、変換後の最短経路問題を解けば良いということになります。

これの何が良いかと言えば、負辺を含むグラフについて、ポテンシャルを適切に定めることで、負辺を消してダイクストラ法を適用可能にできるということです。
蟻本によれば、フロー問題で複数回最短経路を求めたいときに最初1回だけベルマンフォード法で最短路を求め、最短路をポテンシャルに設定すると、負辺が消え、以降はダイクストラ法を適用できるようになって計算量が落とせるということでした。

AtCoderの問題でポテンシャルを使用することは無いような気もしますが、今回のように

各頂点に何らかの値が設定されている
負辺がある

場合にこのような考え方ができないか検討してみるのも良いかと思いました。

2022-02-01

ABC237 参加記録

ABC 双方向連結リスト

コンテスト中AC:A〜E
Eは嘘解法(Cも若干そうでしたが)だったので、ここでは省略します。

C - kasaka
D - LR insertion

C - kasaka

先頭から連続しているaの個数をhead、末尾から連続しているaの個数をtailとします。
先頭に付け加えるのに必要な個数は、tail - headです。この分だけ付け加えて回文かどうかを判定することで答えを得られます。

参加記録を書くにあたって、実装を見直したところ、何故か末尾の方が少なかった場合に、末尾にもaを追加する実装になっていました(嘘解法でした)。ただ、付け加える個数をtail - headのままにしていたのでACとなっていました。

提出コードは、正しい解法で書き直したものです。
提出コード

D - LR insertion

双方向連結リストにより、挿入操作を $O(1)$ でできます。
$FD[i]$ ：数列 $A$ において、 $i$ の後にある整数
$BK[i]$ ：数列 $A$ において、 $i$ の前にある整数
但し、前または後に何もなければ-1とします。

各挿入操作は以下のようになります。

$S_i = L$ の場合
- iの前はi-1なので、 $FD[i] \leftarrow i-1$
- i-1の後ろはiとなるので、 $BK[i-1] \leftarrow i$
- i-1の後ろにあったものがiの後ろとなるので、 $BK[i] \leftarrow BK[i-1]$
- i-1の後ろに整数xがある場合( $BK[i-1] \neq -1$ )、xの前はiとなるので、 $FD[x] \leftarrow i$
$S_i = R$ の場合
- i-1の前はiとなるので、 $FD[i-1] \leftarrow i$
- iの後ろはi-1となるので、 $BK[i] \leftarrow i-1$
- i-1の前にあったものがiの前となるので、 $FD[i] \leftarrow FD[i-1]$
- i-1の前に整数xがある場合( $FD[i-1] \neq -1$ )、xの後ろはiとなるので、 $BK[x] \leftarrow i$

答えの列は、 $BK$ を辿って先頭まで行き、 $FD$ を辿って末尾まで行くことで、得ることができます。
提出コード

2022-01-30

ARC134 参加記録

ARC 重複組合せ RMQ Segment Tree フェルマーの小定理

コンテスト中AC:A,B
Cはコンテスト後自力AC

A - Bridge and Sheets
B - Reserve or Reverse
C - The Majority

A - Bridge and Sheets

便宜上、 $\ a_{N+1} = L$ を追加しておきます。
最初からかけられているシートのうち、最も右端を $s$ とします。最初 $s=0$ としておきます。
$a_i$ にかけられたシートを考えるとき、前のシートの右端 $s$ から $a_i$ までがシートがかけられていない区間です。

これより、シートが $b_i = max(0,a_i-s)$ の長さ分必要になるので、 $\lceil \frac{b_i}{W} \rceil$ がこの区間で必要なシートの枚数です。なお、シートが重なっていた場合に長さが負になってしまうので、0とmaxをとっています。

$a_i$ のシートの右端は、 $a_i + W$ なので、 $S \leftarrow a_i + W$ と更新します。
この操作をi = 1からN+1まで繰り返し、シートの枚数を足し合わせていけば、それが答えです。
提出コード

B - Reserve or Reverse

交換の優先度はインデックスが小さい方が高いので、交換するかどうかをi = 1から順に考えます。 $s_i$ と交換する対象 $s_j$ は以下の条件を満たすようなものを貪欲に決定できます。

辞書順で $s_i$ より小さい
辞書順で最も小さい
$i' \lt j'$ である $s_{i'},s_{j'}$ を既に交換していた場合、 $i' \lt i \lt j \lt j'$ である
最も後ろに出現する

1は自明だと思います。
2ですが、1を満たす中では、辞書順でできるだけ小さい文字を持ってきた方が全体の辞書順を小さくできます。
3ですが、これまで交換対象としたものより、内側である必要があります。(2と8既にを交換していたら、3〜7の中から選ぶ必要がある)
4ですが、3の条件からわかるように次以降に選ぶ交換対象は今選んだものの内側になってしまいます。そこで、1,2の条件を同時に満たす文字が複数個あった場合、次以降の候補をできるだけ増やす為に、できるだけ出現位置が後ろのものを選ぶのが良いです。

条件を満たすものを得る方法ですが、Segment Treeが使えます。
例えば、AtCoder Libraryのsegtreeであれば、 $(s_i,i)$ の組を記録し、二項演算op、単位元eを以下のように定めておきます。

$op( (s_i,\ i),\ (s_j,\ j) )$ ： $s_i \neq s_j$ なら、小さい方を返す。そうでなければ、 $i,j$ の大きい方を返す。

単位元は $e = (inf,\ -1)$ などとしておけば良いです。

提出コード
こちらの実装では、交換対象を左端と右端から考えていくイメージで、 $tail$ を右側で交換した中で最も小さいものとして記録しています。

C - The Majority

条件を満たす箱の入れ方の一つを例にしてみます。
箱1：1 1 1 1 2 2 2
箱2：1 1 1 3 3
箱3：1 1 4
箱4：1

ここから、

1以外の数字があれば、必ずそれに対応する1が存在する
各箱につきペアとなった1を除いた1が少なくとも1つ存在する

ことが言えます。
1の個数を $sum_1$ とし、1以外の個数を $sum_{\gt 1$ と名づけます。

1つ目の考察から、 $sum_1 \geq sum_{\gt 1}$ が成り立つ必要があるので、これが成り立たない時、0通りです。成り立つ場合、ペアを作るので、その分の1の個数を減らして、
$sum_1 \leftarrow sum_1 - sum_{\gt 1}$
としておきます。

2つ目の考察から、ペア以外の1を各箱に少なくとも1つ入れないといけないので、予め各箱に1つずつ分配しておきます。従って、 $sum_1 \geq K$ である必要があります。これが成り立たないとき、0通りです。
成り立つ場合、1の個数を減らして、
$sum_1 \leftarrow sum_1 - K$
とします。

後は、1の残り及び、1とペアになった各数字を箱にいれていきます。1やペアは区別がないので、これを区別のある箱に入れる組み合わせは、重複組み合わせです。1または1とペアの各数字の個数を $m$ 個とすると、
$_{m+K-1} C _{K-1}$
です。

これを各数字について求めていくわけですが、
$_{m+K-1} C _{K-1}=\frac{(m+K-1)(m+K-2)\cdots (m+K-(K-1))}{(K-1)!}$

なので、 $O(K)$ で分子分母が求まります。
分母は、 $mod\ p$ の乗法逆元を求める必要がありますが、フェルマーの小定理に基づいて $O(p)$ で求めることができます。

ある数字の入れ方それぞれについて他の数字の入れ方が存在するので、上で求めたものの総積を求めると答えになります。

計算量は、各数字について重複組み合わせを計算する必要があるので、 $O(NK)$ です(多分)。
提出コード

2022-01-29

ARC133 参加記録

ARC エラトステネスの篩反転数

コンテスト中AC:A,B

A - Erase by Value
B - Dividing Subsequence

A - Erase by Value

同じ数は消えるので、一旦連続して重複した数について、重複を削除して考えます。
$A_1$ から始めて、単調増加している間は、消すと辞書順では大きくなってしまうので、消さない方がよいです。
そこで、減少に転じた時に、その直前の数(すなわち、 $A_1$ を開始点とした、単調増加な部分の最大値)を消してみます。この時消す数を $A_k$ とし、生成される数列を $B$ とします。

すると、 $A_k$ より後の数を消すと、必ず $A_1,\cdots A_k$ という部分が残るので、この時生成される数列が $B$ より辞書順で小さくなることはあり得ません。よって、 $B$ が辞書順最小となります。

なお、減少に転じない場合もあるので、その場合は末尾の数を削除対象にします。
[提出コード] (https://atcoder.jp/contests/arc133/submissions/28684574)

B - Dividing Subsequence

$P_i,Q_j$ を、それぞれ $a_k,b_k$ とすることを $P_i$ と $Q_j$ を対応させると呼ぶことにします。
また、問題文の制約に沿って生成される $a,b$ を適合列と呼ぶことにします。適合列の要素数と言った時には $a$ (または $b$ )の要素数を指すことにします。

$P_i$ と $Q_j$ を対応させた時に得られる適合列の要素数の最大値は、

$\{P_1,P_2,\cdots ,P_{i-1}\}と\{Q_1,Q_2,\cdots ,Q_{j-1}\}$ から作られる適合列の内、要素数が最大であるもの + 1

です。

添字に着目すると、 $i' \lt i$ かつ $j'\lt j$ を満たすすべての $i',j'$ の適合列の要素数の最大値が計算されていれば、 $i,j$ のときの最大値を計算できます。そこで、添字の問題に帰着させます。　　

$P_i$ と $Q_j$ が対応可能である場合に $A_k=i,B_k=j$ となる配列 $A,B$ を作ることを考えます。

$P$ と $Q$ のあり得るすべての組を $A,B$ に記録します。
例) $P=\{3,1,4,2\}$ , $Q=\{4,2,1,3\}$
$P_1$ は $Q_4$ と対応可能
$P_2$ は $Q_1,Q_2,Q_3,Q_4$ と対応可能
$P_3$ は $Q_1$ と対応可能
$P_4$ は $Q_1,Q_2$ と対応可能
$A=\{1,2,2,2,2,3,4,4\}$
$B=\{4,1,2,3,4,1,1,2\}$

$A,B$ の構築方法は後述します。一見全組を得るのに $O(N^2)$ になりそうですが、エラトステネスの篩と同じ様に $O(NlogN)$ で構成できます。

$B_i$ をキーとして昇順ソートします。すると、 $j \lt i$ なら $B_j \leq B_i$ になります。
一旦、 $B_j=B_i$ の場合を無視すると、

$j \lt i$ を満たす $j$ (つまり、 $i$ より前に出現したもの)のうち、 $A_j \lt A_i$ となる $A_j$ から最大値を得る

問題となります。これはBynary Indexed Treeによって反転数を求める問題の考え方を応用できます。
今回は最大値を得たいので、maxの二項演算が規定されたSegment Treeを使います。Segment Treeの値を保持する配列を $dp$ とします。最初、全て0です。

$dp[A_i]$ を計算したいとき、 $max(dp[0],dp[1],\cdots ,dp[A_i - 1])$ という計算によって、 $A_j \lt A_i$ となる $A_j$ から最大値を得ることができます。
そして、
$dp[A_i]\leftarrow max(dp[0],dp[1],\cdots ,dp[A_i - 1])+1$
と更新すれば良いです。 $B_j = B_i$ の場合ですが、今回はこれを満たす $A_j$ は無視したいです。そこで、 $B_i$ が等しいものについて最大値を全て計算し終わった時点で、一括して上記の更新を行うようにすれば良いです。

上に示した方法によって、 $i$ の小さい方から順に最大値を計算して行くことができます。

さて、後回しにしていた数列 $A,B$ の構築方法です。
配列 $E$ を用意し、 $Q_i$ が出現したインデックス $i$ を記録します( $E[Q_i] = i$ )。
例)
$Q = \{4,1,5,7,2,3,6\}$ の時、 $E = \{2,5,6,1,3,7,4\}$

$P_i$ と対応可能な $Q_j$ は $P_i$ の倍数です。よって、この時の $j$ を得たい場合、配列 $E$ を利用すると、
$j = E[P_i],E[2P_i],E[3P_i],\cdots$
というように得ることができます。

これはエラトステネスの篩と似たような処理であり、 $O(NlogN)$ です。よって、 $A,B$ それぞれの配列サイズも $NlogN$ で収まると言えます。

全体の計算量は、 $E$ の構築に $O(NlogN)$ で、最大値の計算と更新にも $O(NlogN)$ となるので、 $O(NlogN)$ だと思います。
提出コード

ちなみに、上記コードはインデックスの組を二次元配列として持たせています。
iと組が作れるjは、 $B[i] = j_1,j_2,...$

2022-01-27

ABC236 参加記録

状態探索 ABC

コンテスト中AC:A〜C

D - Dance
状態遷移を伴うDFS

D - Dance

解けなかったので、反省点含めて記録します。
まず、Nが小さいことから全探索が可能と予想して、全状態数を見積ってみました。

例えば、N = 3のとき、{1,1,2,2,3,3}を並べ替え、人{1,2,3,4,5,6}に対応させ、同じ数字を2人組にするという方法を考えました。
{1,2,2,3,1,3}なら、{1,5},{2,3},{4,6}という具合です。

これは同じ物を含む並び替えなので、
$\frac{(2N)!}{(2!)^N}$
が並び替えの総数です。N=8の時を計算すると、81,729,648,000通りとなり全探索は無理そうだという結論になりました。しかし、これは誤りです。

例えば、N=2のとき、以下のように全探索できて、楽しさが異なるような組の作り方は3通りになります。

人1と同じ組になる人を全探索する。
{1,2},{1,3},{1,4}のいずれかとなる。
残りの組を決める
- {1,2}のとき、{3,4}を組にして $A_{1,2}\oplus A_{3,4}$ を計算する
- {1,3}のとき、{2,4}を組にして $A_{1,3}\oplus A_{2,4}$ を計算する
- {1,4}のとき、{2,3}を組にする $A_{1,4}\oplus A_{2,3}$ を計算する

最初の見積りだと、6通りになっています。何がまずかったかというと、組の作る順序を考慮してしまっています。言い換えると、組に番号をつけて区別してしまっています。
最初の見積りだと、{1,2,2,3,1,3}と{3,1,1,2,3,2}は区別されます。しかし、排他的論理和は順序によらず同じになるので、これらを同一視できます。

ボールと箱の問題に言い換えてみると、最初の見積もり方法は、

区別のある箱に区別のあるボールを2個ずついれる方法の総数

正しい見積もりは、

区別のない箱に区別のあるボールを2個ずついれる方法の総数

です。

従って、正しい見積もりは、各組の選び方に対して組に番号をふる方法が $N!$ 通りあるので、これを除いた
$\frac{(2N)!}{(2!)^N N!}$
です(多分)。
N=8のとき、2,027,025通りとなり、これで全探索可能ということがわかりました。

実装に移ります。
全探索ですが、同じ組の組み合わせを作らないようにする必要があります。これは典型とも言えるかも知れませんが、小さい順に決定していくと上手くいきます。具体的には、
1. 組を作っていない人の中で番号が最も小さい人 $i$ を選ぶ
2. 人 $i$ と組を作れる人全員について、それぞれの人と組を作り、それぞれの場合について1に戻る

となります。この様に状態が複雑に変化してfor文で処理しきれない場合はDFSが有効です。
一応、実装を載せておきますが、無駄に長く、ややこしい実装になってしまったので、他の人を参考にした方が良いです。
提出コード

ここからは直接問題とは関係の無い内容となります。

状態遷移を伴うDFS

状態遷移を伴うDFSは苦手だったので、今後のために実装方針をまとめておきます。
個人の見解なので、間違いなどあるかもしれません。

考慮すべき事項

状態の管理に必要な情報
情報の受け渡し方法
終了条件

状態の管理に必要な情報

今回の問題場合、以下の2つの情報が必要です。

人iが既に選ばれたかどうか
組に基づくXOR和

人iが選ばれたどうかは、例えば、配列などに記録するか、冪集合で管理します。

情報の受け渡し方法

2パターンに分けてみました。

値渡し
グローバル変数で共有

値渡し

おそらく実装が楽になるので、可能な限りこちらを考慮すべきかなと思います。しかし、情報が配列や二次元配列などを含むと何度もコピーが作られることになるので、この場合は避けた方が無難だと思います。

グローバル変数等で共有

状態に配列が含まれる場合に、必要な変更のみを加えることで計算量を抑えられます。但し、探索が終了した場合に状態を復元する必要があります。

今回の問題では、他の方の実装を見ると、XOR和は値渡しして、人iが使われたかどうかはグローバル変数等で共有しているものが多い様に思います。また、冪集合で管理して値渡しをしているものもありました。

終了条件

探索方法にも絡みますが、終了条件を設定する必要があります。呼び出し先で終了判定するのが良さそうです。
自分の実装では、番号最小の人を選ぶのを呼び出し元で決定してしまっています。組を１つ作って、更に番号最小の人まで選んでしまっているので、終了条件を判定する位置もおかしな場所になり、状態の復元も相まってよくわからない感じになっています。

あとは、図示してみると整理されるのかなと思いますので、時間があれば図示の例を載せたいです。

2022-01-22

ABC235F Variety of Digits

ABC 桁DP

自力AC(一度TLEになったので、解法を見て、合っているか確認した)

条件を満たす桁に関する問題
$N$ 以下の整数全てに関する問題

という条件から、桁DPが有力候補となります。
桁DPに関する情報はネット上に多くあるため、ここでは割愛しますが、大雑把に説明します。

桁DPでは上位桁より考慮していきます。
$N$ の上から $i$ 桁目を $d_i$ とし、 $K$ を $N$ 以下にしたいとします。

$K$ の上から $i-1$ 桁目までが、 $N$ と同じだったとします。すると、 $K$ の $i$ 桁目を $d_i$ より大きくすると、 $K$ は $N$ を超えます。よって、 $K$ の $i$ 桁目は $d_i$ 以下にする必要があります。

次に、 $i-1$ 桁目までで、既に $N$ の桁より小さい桁が存在する(すなわち、 $K$ は $N$ 未満となっていることが確定している)とします。
この場合、 $K$ の $i$ 桁目は0〜9までなんでも良いです。

以上から、 $K$ の $i$ 桁目を決定するときに、 $i-1$ 桁目までが $N$ と同じなのか、もしくは既に $N$ 未満なのか、という情報が必要になることがわかります。
桁DPでは、これを未満フラグとして管理し、

未満フラグが0なら、ここまでの桁が $N$ と同一
未満フラグが1なら、既に $N$ 未満であることが確定している

とします。
桁DPについては以上です。

最悪となる全状態数と遷移にかかる時間を見積ります。
$N$ の各桁に対応して、以下の2つを管理する必要があります。

0〜9のどの整数が出現したか
未満フラグ

1については、冪集合 $k$ で管理するので、 $2^{10}$ 通りあります。
$3072 \rightarrow S=\{0,0,1,0,0,0,1,1,0,1\}$

従って、状態数の最悪は
$10^4\times 2^{10}\times 2\simeq 2\times 10^7$
となります。

最悪計算量については、 $i-1$ 桁目の全状態に対して、 $i$ 桁目に0〜9を付加することを考えると、状態数の10倍の時間がかかるので、 $2\times 10^8$ くらいとなって、なんとか大丈夫です。

実際のDPを考えます。
$dp[i][j][k]:=$ 上から $i$ 番目の桁までを考えたきに、未満フラグが $j$ であって、整数の出現状態が $k$ であるものの総和
以下の例で遷移を考えてみます。

例えば、N = 99999として、{1,2}が出現していて、上から3桁目を7にするとします(未満フラグを1で確定している状況)。
$12??? \rightarrow 127??$
$21??? \rightarrow 217??$
この場合、7の付け方は上記の2通りが存在します。

DP遷移で考えてみます。
$dp[3][1][\{0,1,0,0,0,0,0,1,1,0\}] \leftarrow (12700 + 21700)$
$= dp[3][1][\{0,1,0,0,0,0,0,1,1,0\}] \leftarrow (12000 + 21000) + 700 + 700$
$= dp[3][1][\{0,1,0,0,0,0,0,1,1,0\}] \leftarrow (12000 + 21000) + 2\times 7\times 10^{2}$
$= dp[3][1][\{0,1,0,0,0,0,0,1,1,0\}] \leftarrow dp[2][1][\{0,0,0,0,0,0,0,1,1,0\}] + 2\times 7\times 10^{2}$

ここで問題となるのが、和を計算する時に、700が2個発生しています。なぜ2個発生したかというと、2桁目までで{1,2}が出現したもの(すなわち、 $dp[2][1][\{0,0,0,0,0,0,0,1,1,0\}\$ という状態であるもの)が2個存在していたからです。
このことから、和を計算するときには、同時に状態の個数が必要となります。よって、以下の2つのDPを考えます。

$dp_0 [i][j][k]:=$ 上から $i$ 番目の桁までを考えたきに、未満フラグが $j$ であって、整数の出現状態が $k$ であるものの個数
$dp_1 [i][j][k]:=$ 上から $i$ 番目の桁までを考えたきに、未満フラグが $j$ であって、整数の出現状態が $k$ であるものの総和

遷移式は、 $N$ の桁数を $n$ 、 $i+1$ 桁目を $d_i$ とし、 $i+1$ 桁目を $l$ にしたとすると、 $dp_0 [i+1][j \vee l \lt d_i ][k\ or\ (1\lt \lt l ) ] \leftarrow dp_0 [i][j][k]$
$dp_1 [i+1][j \vee l \lt d_i ][k\ or\ (1\lt \lt l ) ] \leftarrow dp_1 [i][j][k] + dp_0 [i][j][k]\times 10^{n-i}$
となります。但し、 $or$ はビット毎のOR演算で、 $\lt \lt$ は左ビットシフト演算です。
初期値は、 $dp_0 [0][0][1] \leftarrow 1$ で、あとは全て0です。

左辺の詳細はネット上にもありますが、 $j \vee l \lt d_i$ というのは、遷移後に未満フラグが1となるのは、すでに未満フラグが1の時か、または、考慮する桁の数 $l$ が $N$ の $i$ 桁目未満だった時であるため、このような表現になります(trueを1、falseを0としています)。

なお、このまま実装するとダメな部分があります。

leading 0を省く処理

実装上、0のみ出現している状態({0,0,0,0,0,0,0,0,0,0,1})が常に1つあることにしておいた方が楽です。しかし、そのままだと0が既に出現していると誤判定してしまいます。そこで、0しか出現していない状態から遷移するときには0が出現していないことにする処理を加えて対処しました。
例
$000?? \rightarrow 0002?$ にする。
出現状態は普通にすると
$\{0,0,0,0,0,0,0,0,0,1\} \rightarrow \{0,0,0,0,0,0,0,0,1,0,1\}$
という遷移になってしまうので、0bit目を0にする。 $\{0,0,0,0,0,0,0,0,0,\color{red}1\} \rightarrow \{0,0,0,0,0,0,0,0,1,0,\color{red}0\}$

10の冪乗部分の処理

$10^{n-i}$ を毎回繰り返し二乗法で計算していたら、TLEしました。
そのため、前計算しておき、配列などに保持しておく必要がありました。

答えは、 $\{C_1,C_2, \cdots C_M\}$ のビットが全て1である集合を部分集合にもつ集合 $S$ について、 $dp[n][0][S]+dp[n][1][S]$ の総和です(詳細は実装をご覧ください)。

提出コード

geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC238 参加記録

A - Exponential or Quadratic

D - AND and SUM

公式解説メモ

連立方程式の解き方

ABC237E Skiing

ポテンシャル

ABC237 参加記録

C - kasaka

D - LR insertion

ARC134 参加記録

A - Bridge and Sheets

B - Reserve or Reverse

C - The Majority

ARC133 参加記録

A - Erase by Value

B - Dividing Subsequence

ABC236 参加記録

D - Dance

状態遷移を伴うDFS

考慮すべき事項

状態の管理に必要な情報

情報の受け渡し方法

値渡し

グローバル変数等で共有

終了条件

ABC235F Variety of Digits