2022-04-06

ABC246 参加記録

ABC 包除原理二次元マスdijkstra 移動中の状態をもつ二分探索

コンテスト中AC:A〜C,E
D,Fも自力ACできたので、書きます。

コンテスト全体の感想
D - 2-variable Function
E - Bishop 2
F - typewriter

コンテスト全体の感想

Dが思いつかなかったので、Eを先に解きました。Eは解法自体はわかったのですが、実装に時間がかかってしまいました。

Fで残り時間10分くらいで、包除原理はわかったのですが、実装は間に合いませんでした。コンテスト後に解きましたが、最初 $S_i$ から作られる文字列の数の計算方法が間違っていました。

Dのように変数か複数ある場合、どれかを固定するという考え方が大事ですね。(一方は全探索できて、片方が決まれば、他は高速に計算できる場合がある)

D - 2-variable Function

$a$ の上限は $10^6$ で、全探索可能です。 $a$ を固定すると、 $b=0,1,\cdots$ に対して $X$ は狭義単調増加です。よって、 $X\leq N$ となるような $b$ を二分探索できます。

提出コード

E - Bishop 2

マスを4倍に拡張し、左上、右上、左下、右下への移動中を表す状態を追加します。具体的には、

$dp[i][j][k]:=$ マス $(i,j)$ にいて状態が $k$ の時の最短距離

とします。
但し、 $k=\{0,1,2,3\}$ とし、
$k=0$ の時、左上に移動中
$k=1$ の時、右上に移動中
$k=2$ の時、左下に移動中
$k=3$ の時、右下に移動中
とします。

まず、同じマス内ではコスト1で方向転換ができます。(同じ向きになるのは無駄ですが、実装が楽です。) 従って、 $k'=0,1,2,3$ について、

$dp[i][j][k']\leftarrow dp[i][j][k]+1$

次に、 $k$ に応じて、以下の通りに進行方向の次のマスにコスト0で動けます。

$k=0$ の時、左上に進める。
$dp[i-1][j-1][k] \leftarrow dp[i][j][k]$
$k=1$ の時、右上に進める。
$dp[i-1][j+1][k] \leftarrow dp[i][j][k]$
$k=2$ の時、左下に進める。
$dp[i+1][j-1][k] \leftarrow dp[i][j][k]$
$k=3$ の時、右下に進める。
$dp[i+1][j+1][k] \leftarrow dp[i][j][k]$

初期値は、既に1回目の移動が始まっていることにする必要があるので、 $k=0,1,2,3$ について、

$dp[A_x][A_y][k] \leftarrow 1$

です。

これをダイクストラ法で解けば良いです。

答えは、 $k=0,1,2,3$ について、 $dp[B_x][B_y][k]$ の中の最小値です。
なお、到達可能かの判定が必要なことに気をつける必要があります。

実装ですが、AtCoderの過去問にも同様の問題があったので、その時の公式解説の実装方法に倣っています。
マス $(i,j)$ の状態 $k$ の頂点番号を

id = 4(i+j*N)+k

とします。
idからi,j,kを得たい時は、C++なら、

i = id/4%N
j = id/4/N
k = id%4

とすれば良いです。
このようにするメリットは、通常のダイクストラ同様に、(距離, 頂点番号)という組だけで管理できる点です。i,j,kを全て管理するなら、構造体などが必要です。
提出コード

F - typewriter

包除原理で解けます。
包除原理についてはネットで調べると出てくるので、詳細は割愛します。
ここでは、小さい例で示します。

$f(S)$ を使用する文字の集合 $S$ のみから得られる長さ $L$ の文字列の数とします。
$g(S)$ を使用する文字の集合 $S$ から得られる全ての長さ $L$ の文字列の数とします。

入力例1でいえば、
$f(S_1)=\{ab,ba,bb\}$
$f(S_2)=\{ac,ca,cc\}$
$f(S_1 \cap S_2)=\{aa\}$

$g(S_1)=\{aa,ab,ba,bb\}$
$g(S_2)=\{aa,ac,ca,cc\}$
$g(S_1 \cap S_2)=\{aa\}$

$g(S)$ は、実は簡単に求められます。 $S$ に含まれる文字は何回使っても良いので、 $i$ 番目の文字は $|S|$ 通りから選ぶことになり、選ぶ文字によって得られる文字列は異なるので、

$g(S)={|S|}^L$ となります。これは繰り返し二乗法により、 $O(logL)$ で計算できます。

(とはいえ、 $g(S)$ の求め方がコンテスト中悩んでしまいました。重複組み合わせと重複並び替えを組み合わせようとしてしまっていました。)

では、 $N=3$ のケースで、包除原理の一例を示します。
今求めたいものは、

$ans = f(S_1)+f(S_2)+f(S_3)+f(S_1 \cap S_2)+f(S_1 \cap S_3)+f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$

です。ベン図で他の集合と重なっていない部分の和と考えればわかりやすいです。

初め、 $X=0$ とします。

まず、 $f(S_1),f(S_2),f(S_3)$ を足したいです。

$g(S_1)=f(S_1)+f(S_1 \cap S_2)+f(S_1 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$
$g(S_2)=f(S_2)+f(S_1 \cap S_2)+f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$
$g(S_3)=f(S_3)+f(S_1 \cap S_3)+f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$

より、 $X$ に $g(S_1),g(S_2),g(S_3)$ を足します。すると、

$X=f(S_1)+f(S_2)+f(S_3)+2f(S_1 \cap S_2)+2f(S_1 \cap S_3)+2f(S_2 \cap S_3)+3f(S_1 \cap S_2 \cap S_3)$

次に、 $f(S_1 \cap S_2),f(S_1 \cap S_3),f(S_2 \cap S_3)$ は一個ずつ多いので減らしたいです。

$g(S_1 \cap S_2)=f(S_1 \cap S_2)+f(S_1 \cap S_2 \cap S_3)$
$g(S_1 \cap S_3)=f(S_1 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$
$g(S_2 \cap S_3)=f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$

より、 $X$ から $g(S_1 \cap S_2),g(S_1 \cap S_3),g(S_2 \cap S_3)$ を引きます。

$X=f(S_1)+f(S_2)+f(S_3)+f(S_1 \cap S_2)+f(S_1 \cap S_3)+f(S_2 \cap S_3)$

最後に、 $f(S_1 \cap S_2 \cap S_3)$ が足りなくなったので、足したいです。

$g(S_1 \cap S_2 \cap S_3)=f(S_1 \cap S_2 \cap S_3)$

より、 $X$ に $g(S_1 \cap S_2 \cap S_3)$ を足します。

$X = f(S_1)+f(S_2)+f(S_3)+f(S_1 \cap S_2)+f(S_1 \cap S_3)+f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$

この時点で、 $X=ans$ となります。

結局、
$ans$
$= f(S_1)+f(S_2)+f(S_3)+f(S_1 \cap S_2)+f(S_1 \cap S_3)+f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$
$= g(S_1)+g(S_2)+g(S_3)-g(S_1 \cap S_2)-g(S_1 \cap S_3)-g(S_2 \cap S_3)+g(S_1 \cap S_2 \cap S_3)$

となります。

これを一般化すると、 $g(S)$ の積集合 $S$ に含まれる $S_1,S_2, \cdots ,S_N$ の個数が奇数なら足す、偶数なら引くということになります。

解法に移ります。

$S=\{S_1,S_2,\cdots S_N\}$ とします。

$ans=0$ とする

$S$ の空集合を除く全部分集合 $T$ について、3,4を行う

$T$ に含まれる $S_i$ の積集合を、 $U$ とする

$T$ の要素数が奇数なら $ans$ に $g(U)$ を足す。偶数なら引く

$S_i$ における使用可能なアルファベットの集合はビットによる冪集合で管理すればよいです。
$S$ の全部分集合もビット全探索すればよいです。

$T$ に含まれる $S_i$ の数や、 $U$ に含まれるアルファベットの数はpopcountで得られます。

計算量は、部分集合の全探索に $2^N$ 、全探索中のそれぞれについて積集合を求めるのに $O(N)$ 、積集合から得られる文字列の数を求めるのに $O(logL)$ なので、全体で多分 $(N+logL)2^N$ です。
提出コード

2022-04-01

ABC245 参加記録

ABC 貪欲法強連結成分分解多項式

コンテスト中AC:A〜C
コンテスト後解説なしでE,FをAC。
Dは解説見たが、方針は間違っていなかったが、考慮できていない部分があった。

D - Polynomial division
E - Wrapping Chocolate
F - Endless Walk

D - Polynomial division

$C_i = A_0 B_i + A_1 B_{i-1}+\cdots +A_i B_0$

であるので、

$i=0$ の時、 $B_0 = \frac{C_0}{A_0}$

$i\geq 1$ の時、 $B_i = \frac{C_i - (A_1 B_{i-1}+\cdots +A_i B_0)}{A_0}$

として、 $B_0, B_1,\cdots ,B_M$ の順で求められると考えました。
(なお、 $i\gt N$ の時は $A_i=0$ としておけば良い)

しかしながら、これはREになっていました。
なぜかというと、 $A_0 = 0$ の場合があるからでした。

そこで、以下のように考えました。
$A_i \neq 0$ となる最小の $i$ を $pos$ とします。

$C_{pos} = A_{pos} B_{0}$

$C_{pos+1} = A_{pos+1} B_{0} + A_{pos} B_{1}$

$C_{pos+2} = A_{pos+2} B_{0} + A_{pos+1} B_{1} + A_{pos} B_{0}$

$\cdots$

となるので、以下の方針としました。

$i=pos$ の時、 $B_0 = \frac{C_0}{A_{pos}}$
$i\geq pos+1$ の時、 $B_{pos-i} = \frac{C_{i} - (A_{i} B_{i-1}+\cdots +A_{pos} B_0)}{A_{pos}}$

とします。しかし、この解法でもREとなり、時間内にACできませんでした。

コンテスト後に考えた結果、実装時に色々と考慮できていなかった部分があったことが原因であり、解法自体は正しいことがわかりました。

以下がACしたコードです。

提出コード

上の実装に、 $n = max(N,M)$ として、 $A,B,C$ について、それぞれ $2n-1$ 個分の領域を確保する処理がありますが、ここは不要です。

全て $N+M$ 個分確保しておけば良いです。逆にこれより少なくとだめです。
なぜなら、 $A_N\neq 0$ のみが保証されているため、 $i$ は最大で $N+M$ になるからです。

また、今回、 $A$ のインデックスをベースに実装しましたが、 $B$ をベースにした方がわかりやすいと思います。
提出コード

E - Wrapping Chocolate

小さいチョコレートから優先して箱に入れる場合、大きい箱に入れると、後々入れられないチョコレートが出てくる可能性があります。そこで、チョコレートを大きいものから順に入れることを考えます。

ここでチョコレートの大小関係を定義しておきます。チョコレートを縦を第一キー、横を第二キーとして降順ソートしたときの基準を適用します。すなわち、 $i$ 番目の $j$ 番目のチョコレートについて、

$A_j \lt A_i$ の場合は $i$ 番目が大きく、 $A_j = A_i$ の場合は $B_j \lt B_i$ なら $i$ 番目が大きい

となります。

まだ箱に入れられていないチョコレートの中で最大のものを $i$ 番目とします。

まず、縦を考えます。
$A_i \leq C_j$ を満たす箱 $j$ に入れることが可能です。ここで、これを満たす箱であれば、どれに入れても、縦の制限によって箱に入れられないチョコレートが発生することはありません。なぜなら、残ったチョコレートの縦は $A_i$ 以下だからです。

次に横を考えます。
横については、 $B_i \leq D_j$ を満たす箱 $j$ ならどれでもよいというわけにはいきません。なぜなら、残ったチョコレートの横は $B_i$ 以下であるとは限らないからです。
ということから、横は $B_i \leq D_j$ を満たす中で最小のものにしておく必要があります。

以上をまとめると、以下のような貪欲法になります。

1.箱に入っていないチョコレートの中で最大をものを1つ選びチョコレート $i$ とする
2.チョコレートが入っておらず、かつ、チョコレート $i$ が入れられる箱の中で、横が最小の箱 $j$ を選ぶ
3.チョコレート $i$ を箱 $j$ に入れる

具体的はアルゴリズムに移ります。

順序付き多重集合 $S$ にチョコレート $i$ を入れる候補となる箱を記録することにします。 $S$ の順序は $D$ の昇順とします。

$S$ には、チョコレート $i$ を入れたい時、 $A_i \leq C_j$ を満たす箱 $j$ を全て記録します。その中から、 $B_i \leq D_k$ を満たす中で最小の箱 $k$ を二分探索によって探し、 $S$ から削除します。

なお、 $S$ に入っている箱は全て $A_i \leq C_j$ を満たすので、 $C_j$ は記録する必要がなく、 $D_j$ だけ記録しておけばよいです。

これを素直に実装すると、各チョコレートについて、候補となる箱を探すため、集合への追加を除いても $O(NM)$ となり、間に合いません。

そこで以下の方法とします。

まず、チョコレートと箱はそれぞれ縦( $A_i,C_i$ )を第一キーに、横( $B_i,D_i$ )を第二キーとして降順ソートします。

$i\lt i'$ の時、 $A_{i'} \leq A_{i}$ なので、 $A_i \leq C_j$ である時、 $A_{i'} \leq C_j$ となります。

そのため、チョコレート $i$ で $S$ に追加した箱は、チョコレート $i'$ でも追加したままにしておけます。

従って、 $i=1,2,\cdots ,N$ の順に調べる時、チョコレート $i$ で $S$ に追加された箱は、チョコレート $i+1$ でも追加したままにでき、チョコレート $i+1$ で新たに必要になった箱だけを $S$ に追加すればよくなります。

これにより、箱は $S$ に高々1回しか追加されず、全体で $O(N)$ となります。

多重集合としてC++のmultisetを使えば、追加、検索、削除はlog時間でできるので、高速に実現できます。

提出コード

F - Endless Walk

頂点 $v$ を出発して、頂点 $v$ に帰って来れるような閉路が存在すれば、 $v$ に到達後に無限に移動できることが確定します。

ある強連結成分 $C_i = \{v_{i_1},v_{i_2},\cdots v_{i_m}\}$ に属する全ての頂点は、この条件を満たします。

よって、強連結成分の集合族を $C=\{C_1,C_2,...,C_m\}$ としたとき、これら強連結成分に属するいずれかの頂点に到達できれば、無限に移動できます。

強連結成分は、強連結成分分解で $O(N+M)$ で得られます。AtCoder Libraryのscc_graphを強連結成分が二次元配列で得られるので、列のサイズが2以上であれば閉路を含み、 $C_i$ とみなせます。

(補足:グラフが単純でなければ、自己ループを考慮する必要があるので、サイズが1でも閉路となります。)

あとは、強連結成分の頂点に到達可能な頂点を調べれば良いですが、以下のように言い換えました。

$G$ の有向辺を全て逆向きにしたグラフ $G'$ において、強連結成分のいずれかの頂点から到達可能な頂点を調べる

これは強連結成分に属する全ての頂点をキューに入れてBFSを開始すれば良いです。

提出コード

2022-03-23

ABC244 参加記録

ABC グラフ上のDP インタラクティブ

コンテスト中AC:A〜E

C - Yamanote Line Game
D - Swap Hats
E - King Bombee

C - Yamanote Line Game

インタラクティブな問題を初めて解いたのでメモ
提出コード

D - Swap Hats

自信ないまま通してしまいました。

操作を偶数回行った後に生成される状態には $10^{18}$ 回行った後もその状態にできます。

10回操作すると状態数は $2^{10}$ になるものの、RGBの順番の入れ替えの通り数は6通りしかありません。
そのため、 $S$ を10回操作して $T$ にできれば達成できると考えました。

実際に実装してデバッグしてみると、状態数は偶数回、奇数回共に早々に3個に限定され、解を得られそうだとわかりました。
そして、提出した結果ACできました。

公式解説によれば、6種類の状態の関係性をグラフにすると、二部グラフになり、 $S,T$ が同一のグループになれば達成できるということでした。

提出コード

E - King Bombee

パスに関する以下のDPを考えます。

$dp[u][k]:=$ $k$ 回移動した後に頂点 $u$ にいるようなパスの総数
初期値は $dp[S][0] = 1$

これは、 $A=\{A_0,A_1,\cdots ,A_k\}$ のうち、 $A_k =u$ であるものの総数に一致します。

このDPテーブルの更新は、以下のような3重ループになります。

for k = 1からKまで
    for u in 全ての頂点
        for v in uと接続する全ての頂点
            dp[v][k] = dp[u][k-1] //uからvに移動する

for v in uと接続する全ての頂点の部分は、 $k$ のループの1回につき、合計で $2M$ 回しか実行されないので、 $O((N+M)K)$ になります。
また、 $K$ 回目で $T$ にいるパスの総数は $dp[T][K]$ となります。

ここまでは、同様の考え方が過去に出題されました。

あとは $X$ に訪れた回数( $A$ に含まれる $X$ の個数)の偶奇の情報が欲しいので、DPテーブルに加えます。

$dp[u][k][x]:=$ $k$ 回移動した後に頂点 $u$ にいて、かつ $X$ に訪れた回数の偶奇が $x$ であるようなパスの総数
但し、 $x=\{0,1\}$ であり、 $x=0$ の時は $X$ に訪れた回数が偶数、 $x=1$ の時は奇数

DPテーブルの更新は、以下のように $v=X$ の時だけ、偶奇を入れ替えればよいです。

for k = 1からKまで
    for u in 全ての頂点
        for v in uと接続する全ての頂点
            if vがX
                dp[v][k][0] = dp[u][k-1][1]
                dp[v][k][1] = dp[u][k-1][0]
            else
                dp[v][k][0] = dp[u][k-1][0]
                dp[v][k][1] = dp[u][k-1][1]

答えは $dp[K][T][0]$ です。
提出コード

2022-03-21

ARC137 参加記録

ARC iとj独立に計算連続する部分列素数の間隔素数

コンテスト中AC:なし
A,B解説AC

A - Coprime Pair
B - Count 1's

A - Coprime Pair

公式解説

素数の間隔(prime gap)が重要とのことです。

素数の間隔 - Wikipedia

公式解説及び上記のwikiによれば、問題の制約における素数間の極大の間隔(maximum gap)は1500らしいです。

よって、 $L\leq x \leq L+1500$ 及び $R-1500 \leq y \leq R$ を満たす組 $(x,y)$ のうち少なくとも1つは $x,y$ がいずれも素数である組が存在するということでした。

$d=y-x$ とすると、 $R-L-3000\leq d \leq R-L$ の範囲だけ $gcd(x,y)=1$ となる組を調べれば良くなり、全探索可能になるということでした。

提出コード

B - Count 1's

コンテスト中にたどり着いた部分

連続した部分列の0の個数を $S^0$ 、1の個数を $S^1$ 、初期状態における1の個数を $X$ とすると、操作後の1の数を $X+S^0 - S^1$ にできます。

また、 $S=S^0 - S^1$ の最大値を $S_{max}$ とし、その時の連続した部分列の区間を閉区間 $[l,r]$ とします。

区間が空の状態から、+1ずつ伸長して $[l,r]$ にした時、 $S$ も+1ずつしかされないので、 $S=0,1,\cdots ,S_{max}$ にできます。

最小値 $S_{min}$ についても同様です。
従って、 $S$ は、 $S_{min}\leq S \leq S_{max}$ を満たす全ての整数にすることができます。

以上から、 $S_{min}\leq S \leq S_{max}$ に0を含むなら $S_{max} - S_{min} +1$ が答えとなります。
0を含まないなら、空の部分列を選ぶと0にもできるので、 $S_{max} - S_{min} +2$ となります。

コンテスト中わからなかった部分

$S_{min},\ S_{max}$ の求め方がわかりませんでした。
公式解説によれば簡単に求められるとなっていました。

閉区間 $[1,i]$ の部分列に含まれる0の個数を $S^0_i$ 、1の個数を $S^1_i$ とします。

$[i,j]$ に含まれる0の個数は $S^0_i - S^0_{j-1}$ 、1の個数は $S^1_i - S^1_{j-1}$ です。
よって、 $[i,j]$ の $S^0 - S^1$ は以下のように計算できます。
$S^0_i - S^0_{j-1} - (S^1_i - S^1_{j-1}) = S^0_i - S^1_i - (S^0_{j-1} - S^1_{j-1})$

従って、 $i$ を末尾とする連続した部分列の $S^0 - S^1$ が最大となるのは、 $0\leq j \lt i$ を満たす $j$ のうち、 $S^0_j - S^1_{j}$ が最小となるもの選んだ場合です(便宜上、 $S^0_0 - S^1_0= 0$ )。
同様に、 $S^0 - S^1$ が最小となるのは、 $S^0_j - S^1_{j}$ が最大となるもの選んだ場合です。