2023-05-19

AtCoder Beginner Contest 301 メモ

ABC 巡回セールスマン問題

コンテストページ: パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301） - AtCoder
コンテスト中AC: A〜C
コンテスト後にD,Eを自力AC

D - Bitmask
E - Pac-Takahashi

D - Bitmask

以下の説明で、 $N$ の最大値を十分に超えるため、最上位ビットを63としておきます。 $S$ がこれより小さい場合はサイズが63になるように0を追加しておきます。

上位のビットから?のビットを決定していくことを考えます。上位ビットをできるだけ大きくした方が、値として大きくできるため、優先します。

この時、 $N$ より小さい数にするために、?を使うのは高々1箇所であると言えます。なぜなら、一度 $N$ 未満となれば、その後の下位ビットをどのようにしたとしても、 $N$ 以上となることはありえないからです。

仮に $i$ 番目のビットで $S$ が $N$ 未満であることが確定した場合に最適解であったとします。この時、最上位ビットから $i+1$ 番目までのビットは $N$ と $S$ で一致していることが言えます。

もし一致していなければ、 $i$ 番目より上位のビットで $S$ が $N$ 未満であるか、 $N$ より大きいかのいずれかとなってしまいます。

また、 $i-1$ 番目以降の?は全て1にするのが最適です。

$S$ を $N$ 未満にするというのは、 $N$ の $i$ ビット目が1であり、かつ、 $S$ の $i$ ビット目が?である状況で、?を0にすることと言えます。

そこで、 $S$ の?を1つずつ0にした場合について、その時の $S$ の最大値を全探索します。この時、

$L_i:=$ $S$ の最上位ビットから $i$ ビット目までについて、?の箇所を全て $N$ と同一にし、 $i-1$ 以降は0であるような値

$R_i:=$ $S$ の0ビット目から $i$ ビット目までについて、?の箇所を全て1とし、 $i+1$ ビット目以降は0であるような値

となるように配列 $L,R$ を作っておくと、 $i$ ビット目で $N$ 未満となった時の値を $L_{i+1}+R_{i-1}$ で計算できます。但し、便宜上、 $L_{64}=R_{-1}=0$ とします。(ビットを1オリジンで実装すれば-1が0になって実装しやすくなります。)
解の最大値の更新は、この値が $N$ 以下である場合のみ行えばよいです。

テーブルは $O(N)$ で構築でき、全探索も $O(N)$ でできます。

なお、 $N$ 未満となる箇所が0箇所の場合も考慮する必要があります。これは、 $R_{63}$ と同じです。

実装: Submission #41405709 - Panasonic Programming Contest 2023（AtCoder Beginner Contest 301）

E - Pac-Takahashi

同じお菓子を2回食べられないので、既に食べたお菓子の状態を冪集合で管理したいです。状態数分のマスを拡張したBFSはおそらく計算量的に厳しいです。

考慮すべきは、スタート-お菓子、お菓子-お菓子、お菓子-ゴール間の最短距離のみです。また、後は各状態に対する移動距離の最小値が求められればよいです。ここで思いつくのが巡回セールスマン問題です。

お菓子を頂点とみなします。また、計算量は定数倍落ちますが、実装の簡便さからスタートとゴールも頂点とみなします。
これら頂点に対する巡回セールスマン問題を考えると、状態 $S$ で頂点 $u$ にいる場合の最短距離を、頂点数を $N$ として $O(N^2 2^N)$ で求めることができます。

最短距離を求めた後は、ゴールの頂点にいるdp値について、 $T$ 以下か調べます。 $T$ 以下であれば、冪集合の1の数をカウントし、更にそこからスタートとゴールの頂点数2を引いた値で、答えの最大値を更新すればよいです。

全点対間最短経路は各頂点からBFSすることで、 $O(HW)$ で求められます。

実装: Submission #41471658 - Panasonic Programming Contest 2023（AtCoder Beginner Contest 301）

なお、詳細は割愛しますが、スタートとゴールは巡回セールスマン問題を解く時の頂点から除いて考えることができ、定数倍軽くなります。但し、例外処理などに気をつける必要があります。

実装: Submission #41471658 - Panasonic Programming Contest 2023（AtCoder Beginner Contest 301）

2023-04-24

AtCoder Beginner Contest 299 メモ

ABC

コンテストページ: Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 299) - AtCoder
コンテスト中AC: A〜E

D - Find by Query
E - Nearest Black Vertex

D - Find by Query

20回以下の指定なので、log時間の方法を疑います。すなわち、二分探索です。

最初、 $l = 1, r = N$ とします。最初、 $[l,r]$ は、0......1です。

$m=\lfloor \frac{r+l}{2}\rfloor$ とします。 $S_m = 0$ の場合、0...0...1という感じです。 $l\leftarrow m$ とすると、 $[l,r]$ は、0......1となります。

$S_m = 1$ の場合、0...1...1という感じです。 $r\leftarrow m$ とすると、 $[l,r]$ は、0......1となります。

このように二分探索を繰り返すと、常に $[l,r]$ は、0......1という状態が保たれます。 $r=l+1$ となるまでこれを繰り返し、 $l$ を $p$ とすれば、答えの条件を満たします。

実装: Submission #40850245 - Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 299)

E - Nearest Black Vertex

問題文中の条件である、

全ての $p_i$ について、 $p_i$ との距離がちょうど $d_i$ であるような頂点の内のいずれかを黒に塗る

について、どの頂点を黒にすればよいか決めることは困難です。しかし、白に塗る頂点は以下のように確定します。

全ての $p_i$ について、 $p_i$ との距離が $d_i$ 未満であるような頂点は全て白で塗る

これにより、全ての $p_i$ について、黒に塗った頂点との距離が最小のものが $d_i$ 未満とならないことが保証されます。

白で塗った頂点以外は、何色で塗ってもよいです。そのため、条件を満たすために黒で塗るのが最適です。

これで白黒の塗り方が決まりました。後は、問題文の条件を満たすか確かめれば良いです。

塗り方の決定及び条件を満たすかの確認は全点対間最短経路が分かっていればよく、Warshall-Floyd法では間に合わないので、全頂点を始点としてBFSを行えばよいです。計算量は $O(N(N+M)+NK)$ だと思います。

実装: Submission #40877876 - Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 299)

2023-04-22

AtCoder Beginner Contest 298 メモ

ABC 期待値DP Segment Tree

コンテストページ: TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298) - AtCoder
コンテスト中AC: A〜F

E - Unfair Sugoroku
F - Rook Score

E - Unfair Sugoroku

期待値や確率の問題はメモ化再帰で解ける場合が多いです。

状態遷移を考えた時、

遷移する確率×遷移先で得られた確率

の総和により答えを計算できます。具体的には、

$f(a,b,t):=$ 高橋くんがマス $a$ 、青木くんがマス $b$ で、手番の状態が $t$ の時に高橋くんが勝つ確率
但し、 $t\in \{0,1\}$ であり、 $t=1$ のときは高橋くんの手番、 $t=0$ のときは青木くんの手番とします。

$f(a,b,t)$ からは以下のように遷移します。

$t=1$ の時
$f(a+1,\ b,\ 0),\ f(a+2,\ b,\ 0),\ \cdots ,\ f(a+P,\ b,\ 0)$
$t=0$ の時
$f(a,\ b+1,\ 1),\ f(a,\ b+2,\ 1),\ \cdots ,\ f(a,\ b+Q,\ 1)$

今回遷移する確率は等確率なので、

$t=1$ の時
$f(a,\ b,\ t)=\frac{1}{P}f(a+1,\ b,\ 0)+\frac{1}{P}f(a+2,\ b,\ 0)+\cdots +\frac{1}{P}f(a+P,\ b,\ 0)$
$t=0$ の時
$f(a,b,t)=\frac{1}{Q}f(a,\ b+1,\ 1)+\frac{1}{Q}f(a,\ b+2,\ 1)+\cdots +\frac{1}{Q}f(a,\ b+Q,\ 1)$

です。
再帰の終了条件は、 $a\geq N$ なら高橋くんの勝ちなので $f(a,b,t)=1$ 、 $b\geq N$ なら青木くんの勝ちなので $f(a,b,t)=0$ です。

後は、メモ化再帰して、 $f(A,\ B,\ 1)$ を解けばよいです。

計算量は、ワーストケースで状態数が $200^2$ で、各状態につき遷移に $10$ かかるので、 $4\times 10^5$ であり問題ありません。

実装: Submission #40661914 - TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298)

F - Rook Score

行のスコアの最大値+列のスコアの最大値を答えとできれば単純ですが、このようにはいきません。なぜなら、行 $r$ と列 $c$ を選んだ時、マス $(r,c)$ の整数が2回足されるため、この整数を引かなければいけないためです。

計算量的に選ぶ行を全探索することは可能です。後は、行を固定したときの列のスコアの最大値が高速にわかれば解くことができます。

やや大雑把ですが、例とともに解法を説明します。行 $r$ を選んだとします。
列 $i$ の整数の和が $s_i$ であるような数列を $s$ とします。また、 $r$ 行には列 $1,3,10$ に整数 $x_1,x_2,x_3$ が書かれていたとします。
今求めたいのは、元の $s$ から同じ行の整数を引いた

$max(s_1 - x_1,\ s_2,\ s_3-x_2,\ \cdots ,\ s_{10}-x_3,\ \cdots ,\ s_{10^9})$

です。
列の座標圧縮をします。仮に、

$\{1,2,3,...,10,...,10^9\}\rightarrow \{1,2,3,...,6,...,m\}$

と変換されたとします。求めたいものは、

$max(s_1 - x_1,\ s_2,\ s_3-x_2,\ \cdots ,\ s_{6}-x_3,\ \cdots ,\ s_{m})$

となります。
座標圧縮後の $m$ は $N$ 以下なので、配列として保持できるサイズとなります。そのため、Segment Treeにより、区間最大のクエリに答えることで最大値を得ることが可能です。

後は、同じ行に存在する整数を引く部分ですが、これは各行毎に以下のように処理します。

同じ行の整数を $s$ から引く
最大値を得る
同じ行の整数を $s$ に足し、元に戻す

各整数につき、引く・足すが1回ずつしか行われないので、Segment Treeの値更新を考えても $O(NlogN)$ で処理できます。

実装: Submission #40675301 - TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298)

2023-04-16

AtCoder Beginner Contest 297 メモ

ABC 整数論 DP 個数制限のない部分和問題包除原理ユークリッドの互除法

コンテストページ: AtCoder Beginner Contest 297 - AtCoder
コンテスト中AC: A〜D
コンテスト後にE,Fを自力AC

D - Count Subtractions
E - Kth Takoyaki Set
F - Minimum Bounding Box 2

D - Count Subtractions

基本的な動きはユークリッドの互除法と同じなので、その通りにすれば概ね問題ないですが、一点注意が必要です。
$A,B$ の大きい方を $a$ 、小さい方を $b$ とします。 $b$ が $a$ の倍数となった時、ユークリッドの互除法では $a$ が0となるまで $b$ を引きますが、今回の問題は $a=b$ となった時点で終了するようにしなければいけません。

実装はコンテスト後に見直し

実装: Submission #40555022 - AtCoder Beginner Contest 297

E - Kth Takoyaki Set

個数制限の無い部分和問題の解き方をベースにして解けます。

まず、 $A$ の要素をただ1つ使う場合の部分和問題を考えます。
以下のDPテーブルを考えます。

$dp[i][j]:=$ $A$ の $i$ 番目までを使って $j$ が作れるなら1、作れないなら0

$i$ から $i+1$ への配るDPでの遷移は、

$dp[i][j]$ が1なら $dp[i+1][j]$ を1にする
$dp[i][j]$ が1なら $dp[i][j+A_{i+1}]$ を1にする

です。
次に、個数制限がない場合の部分和問題を考えます。
上記の遷移に対し、以下を追加します。

$dp[i+1][j]$ が1なら $dp[i+1][j+A_i]$ を1にする

この遷移を追加すると、
$dp[i][j]$ が1なら $dp[i][j+A_{i+1}]$ が1になる
$dp[i][j+A_{i+1}]$ が1なら $dp[i][j+2A_{i+1}]$ が1になる
$dp[i][j+2A_{i+1}]$ が1なら $dp[i][j+3A_{i+1}]$ が1になる
...

となるので、 $i+1$ 番目の $j$ が1なら、任意の自然数 $k$ に対して、 $i+1$ 番目の $j+kA_{i+1}$ は全て1になり、個数が無制限である状況が作られます。
なお、 $j$ の小さい方から順にテーブルを更新していく必要があります。

また、この配列は使い回すことができるので、

$dp[j]:=$ $j$ が作れるなら1、作れないなら0

として、 $i=0,1,...,N-1$ のそれぞれについて、 $j=0,1,2,...$ の順に、

$dp[j]$ が1なら $dp[j+A_{i+1}]$ を1にする

をしていけばよいです。

$K$ 番目の最大値が配列に持てる大きさならこのまま解けますが、今回は最大値が $2\times 10^{10}$ なので不可能です。
配列では作成できない値も管理しているため、無駄が多いです。
そこで、作成可能な値そのものを集合で管理するようにします。すると、集合には小さいほうから順に $K$ 個だけ管理すればよいです(0除く)。

そこで、順序付き集合 $S$ (C++ならset)で作成可能な値の集合を管理できないか考えます。

前述のDPの遷移から以下の方法が考えられます。

$S$ の要素の小さい順に $A_{i+1}$ を足した値を $S$ に挿入する

これだと、以下のような問題点が発生します。

$S$ に存在する要素が小さい順に網羅されず、終了時点が不明
$S$ がsetなら、要素の追加により木の構造が動的に変化するため、小さい順に走査するイテレータが正常に機能するか不明(確かめていませんが、問題なく機能するのかもしれません)

そこで、作成可能な値を小さい順に管理する集合 $T$ を追加し、以下のようにします。

$T=\{0\}$ として、 $T$ に値が $K$ 個追加されるまで、以下を繰り返す

$S$ から最小値を取り出し $x$ とする( $x$ は $S$ から削除する)。 $x$ を $T$ に挿入し、 $x+A_{i+1}$ を $S$ に追加する

このようにすると、 $T$ には $S$ の要素及び $A_{i+1}$ で作成可能な値が小さい順に $K$ 個の記録されます。
また、繰り返し部分は $O(K)$ となります。

これで、 $O(NK)$ で問題を解くことができました。

実装: Submission #40502322 - AtCoder Beginner Contest 297

F - Minimum Bounding Box 2

包除原理で解けます。

長方形の縦の長さと横の長さを全探索しても $O(N^2)$ なので、全探索可能です。

縦 $i$ 、横 $j$ 、面積 $m=i\times j$ の長方形 $R$ がグリッド上にできる方法が何通りか考えていきます。

一旦、 $R$ ができる位置は固定して $R$ ができるマスの選び方が何通りあるか考えます。

まず、 $R$ 外のマスが選ばれた場合は $R$ ができないので、以下、マスは全て $R$ 内から選ばれるとします。

この時、 $R$ ができる条件は以下のとおりです。

$R$ の上下左右のそれぞれの辺について、1つ以上選ばれたマスが存在する

となります。
さて、これが成立する条件はかなり複雑です。辺上に選ばれるマスは何個あってもよく、頂点となるマスは2つの辺を共有していることなどが理由です。

そこで、 $R$ とならない数を全体から引くことを考えます。
$R$ とならない条件は、

$R$ の辺について1つ以上、選ばれたマスが0の辺が存在する

よって、以下の計算ができます。

$R$ となる通り数 =
$R$ 内のマスが選ばれる全通り数
- 選ばれたマスが0の辺がちょうど1つの通り数
- 選ばれたマスが0の辺がちょうど2つの通り数
- 選ばれたマスが0の辺がちょうど3つの通り数
- 選ばれたマスが0の辺がちょうど4つの通り数

選ばれたマスが0の辺がちょうど $x$ つの通り数

というのは求めるのが難しいです。
一方で、

選ばれたマスが0の辺が $x$ つ以上の通り数

というのは、求めるのが容易です。

全てを記載すると長くなるので、 $x=2$ の場合についてのみ示します。他も同様に求められます。

"選ばれたマスを0にする辺"に含まれるマスの個数を $k$ とします。残りの $m-k$ 個のマスから $K$ 個のマスを選ぶような、 $_{m-k}C_K$ 通りが、選ばない辺を決めた時の通り数です。

2つの辺の選び方は、(左、上)、(左、下)、(右、上)、(右、下)、(右、左)、(上、下)があります。

(左、上)、(左、下)、(右、上)、(右、下)は、 $k=i+j-1$ です。
(右、左)は、 $k=2j$ です。
(上、下)は、 $k=2i$ です。

この6パターンを合計することで、選ばれたマスが0の辺が2つ以上の通り数を得ることができます。

$x=1,2,3,4$ についてこれらを計算すると、包除原理により、以下のように $R$ となる通り数を計算できます。

$R$ となる通り数 =
$R$ 内のマスが選ばれる全通り数
- 選ばれたマスが0の辺が1つ以上の通り数
+ 選ばれたマスが0の辺が2つ以上の通り数
- 選ばれたマスが0の辺が3つ以上の通り数
+ 選ばれたマスが0の辺が4つ以上の通り数

なお、 $R$ 内のマスが選ばれる全通り数は $_mC_K$ です。

これにより、グリッド内で位置を固定した時に、縦 $i$ 、横 $j$ の長方形 $R$ ができる通り数が求まりました。これを $X$ とします。

グリッド内で $R$ は、 $(H-i+1)(W-j+1)$ 個配置できます。全て同様の計算ができるので、グリッド内で $R$ ができる全通り数は、 $(H-i+1)(W-j+1)X$ 通りです。

また、 $R$ のスコアは $m$ なので、グリッド上でできる $R$ によって得られる全スコアは、 $m(H-i+1)(W-j+1)X$ です。
これを全ての $i,j$ について合計します。それを、グリッド全体から $K$ 個選ぶ通り数 $_{HW}C_K$ で割ったものが求める期待値となります。

実装: Submission #40549600 - AtCoder Beginner Contest 297

2023-04-06

AtCoder Beginner Contest 296 メモ

ABC 出次数1のグラフ

コンテストページ: AtCoder Beginner Contest 296 - AtCoder
コンテスト中AC: A,B,C,(D),E (Dは嘘解法でした)

E - Transition Game

E - Transition Game

出次数1の有向グラフ上を移動すると考えることができます。出次数1のグラフは、「各連結成分について、閉路をただ1つだけ持ち、全ての頂点から有向辺を辿ると閉路に辿り着く」ことが言えます。

そこで、まず高橋くんが青木くんを閉路上の頂点に行かせたい場合を考えます。
$m$ 頂点からなる閉路について、任意の頂点から移動を開始して辿り着いた順に $0,1,\cdots ,m-1$ と番号をつけます。

番号 $s$ から開始して、 $k$ 回移動した場合に最後にいる頂点の番号は、 $(s+k)\ mod\ m$ で計算できます。

青木くんが移動回数 $K_i$ を指定した場合を考えます。高橋くんが移動を開始する頂点番号 $S_i$ を指定し、頂点 $X$ に行かせたいとすると、

$S_i + K_i \equiv X\ mod\ m$

という合同式から、

$S_i$ を $(X-K_i)\ mod\ m$ にすれば良いです。
このことから、閉路上の任意の頂点については、青木くんの指定に対して、高橋くんは青木くんを必ず行かせたい頂点に行かせることが可能です。よって、高橋くんの勝ちとなります。

閉路でない部分の頂点に行かせたい場合を考えます。例えば青木くんが $K_i$ を $10^{100}$ などとすれば必ず閉路に行き着くため、高橋くんは開始の頂点をどのように指定しても勝つことはできず、青木くんが勝ちます。

以上から問題の答えは、各連結成分についての、閉路に属する頂点数の合計です。
閉路に属する頂点数が2個以上なら強連結成分分解で得ることができます。また、頂点数が1個の閉路、すなわち自己ループは、 $A_i = i$ かどうかで判定できます。

ユーザ解説によれば、出次数1の有向グラフをfunctional graphと呼ぶらしいです。

実装: Submission #40244460 - AtCoder Beginner Contest 296

2023-03-30

AtCoder Beginner Contest 295 備忘録

ABC 全組問題

コンテストページ: AtCoder Beginner Contest 295 - AtCoder
コンテスト中AC: A〜D

D - Three Days Ago

便宜上、 $S_0$ が空文字として存在するものとします。なお、以下に示す解法で「文字」と表現したときには空文字は無視し、0,1,2,3,4,5,6,7,8,9を指すものとします。

問題文の $(l,r)$ が満たすべき条件を以下のように言い換えられます。

$S$ の $l$ 文字目から $r$ 文字目までについて、すべての文字の個数が偶数である

更に以下のように言い換えられます。

$S$ の「 $0$ 文字目から $l-1$ 文字目」と、「 $0$ 文字目から $r$ 文字目」について、全ての文字の個数の偶奇が等しい

ここで、10桁の2進数 $f_i$ を定めます。
$f_i$ は、 $S$ の $0$ 文字目から $i$ 文字目までに文字 $j$ が偶数個含まれているなら、 $j$ ビット目が0、奇数個なら1とします。

このようにすると、 $(l,r)$ の条件は更に言い換えられます。

$f_{l-1} = f_r$

そこで、 $i=0,1,2,\cdots ,N$ について、 $f_i$ を計算し、その個数をカウントします。ここから選ばれる2つのインデックスの組は、問題文の条件を満たします。
よって、 $f_i = x$ となるインデックスの個数を $cnt_x$ 個とすれば、 $_{cnt_x}C_2$ 個が条件を満たします。従って、 $x=0,1,\cdots ,2^{10}-1$ の全てについてその総和をとれば、答えとなります。