geam1113’s diary

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

ABC244 参加記録

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

コンテスト中AC:A〜E

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]です。
提出コード

ARC137 参加記録

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

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

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}が最大となるもの選んだ場合です。

よって、i=1,\ 2,\ \cdots ,\ Nについて、S^0_i - S^1_{i}を順次計算し、最大値と最小値を管理しておくことで、O(1)で各iを末尾とした時の連続した部分列のS^0 - S^1の最大・最小を求められます。

以上から、S_{min},S_{max}をO(N)で求められます。

提出コード

ABC242G Range Pairing Query

ABC Mo

解説AC

問題へのリンク
解説へのリンク

初Mo's Algotithm
Mo's Algorithmの適用可能条件は以下の通りです。

  1. 配列が不変
  2. クエリ先読み可
  3. 区間を+1, -1ずつ伸縮しても値の再計算が容易

1,2は満たすので3が満たせればよく、以下の方法で容易に計算できることがわかります。

cnt[i]:区間内のiの出現数
とします。最大のペア数ansは、以下のように計算できます。

  • 区間を伸長した時
    新たに区間内となるものをA_iとすると、伸長前にcnt[A_i]が奇数なら、ペアを新たに作れるのでansを+1する。

  • 区間を短縮した時
    新たに区間外となるものをA_iとすると、短縮前にcnt[A_i]が偶数なら、ペアが1つ減るのでansを-1する。

よって、Mo's AlgorithmによりO((N+Q\sqrt{N})で解けます。

Mo's Algorithmは公式解説のリンクなど見れば良いですが、自分でも別記事に簡単にまとめました。
Mo's Algorithm

提出コード

Mo's Algorithm

Mo ABC アルゴリズム

AtCoder Biginner Contestに出題されたので、実装してみました。

解説へのリンク(ネタバレ注意)

解説に書かれている以下のリンクに詳細があるので、アルゴリズムについては要約して書きます。

概要

数列A=\{A_0, A_1,\ \cdots ,\ A_{N-1}\}についてのQ個の閉区間[l_i,\ r_i]のクエリにO((N+Q)\sqrt{N})で答える。
やっていることはクエリの平方分割。

条件

  • Aは不変
  • クエリ先読み可
  • [l_i,\ r_i]から区間を伸縮しても、値を簡単に計算できる

アルゴリズム

  • ブロック番号\lfloor \frac{l_i}{\sqrt{N}} \rfloorの昇順、同ブロック内ではr_iの昇順でクエリをソートする
  • ソート済みのクエリを左から順に区間を伸縮して値を計算していく

計算量

  • 左端はほとんどがブロック内での移動なので、Q\sqrt{N}回
  • 右端は同ブロック内で高々N回の移動なので、N\sqrt{N}回
  • 上記を併せてO((N+Q)\sqrt{N})

例

Aのサイズを9とします。
ブロックサイズb=\sqrt{9}=3

与えられるクエリ
[5,7]
[1,3]
[3,5]
[4,4]
[7,8]
[2,5]
[0,8]
[7,7]

まず、クエリをソートします。
l_iが属するブロックを第一キーに、r_iを第二キーとして昇順にソートします。
l_iが属するブロックは\lfloor \frac{l_i}{b} \rfloorにより求められます。

ソート後(ブロック毎に区切ってあります。)
[1,3]
[2,5]
[0,8]

[4,4]
[3,5]
[5,7]

[7,7]
[7,8]

ソート後に順にクエリを処理します。
例えば、予め[2,5]の値は計算されていると仮定して[2,5] -> [0,8]を計算するときは、

  1. 右端を、[2,5] -> [2,6] -> [2,7] -> [2,8]という風に、+1ずつ区間を右に伸長しながら値を更新する
  2. 左端を、[2,5] -> [1,5] -> [0,5]という風に、-1ずつ区間を左に伸長しながら値を更新する

という感じです。

ABC243 参加記録

ABC 二分木

コンテスト中AC:A〜D

D - Moves on Binary Tree

公式解説の解法1とほぼ同じでした。

まず、根からXへの移動方法の文字列Tを得ます。具体的には、

Xが1となるまで以下を行う。

Tの末尾に、Xが偶数なら'L'を、奇数なら'R'を追加。
X\leftarrow \lfloor \frac{X}{2}\rfloorと更新。

上記が終了したら、Tを反転させる。

その後、i=1,2,...,Nについて、以下を行います。

S_iが'U'なら、Tの末尾から文字を一つ取り除く。
そうでないなら、S_iをTの末尾に追加。

これによって、Tは根から答えのノードまでの移動方法の文字列となります。あとはこれに従って、根(番号1)から計算していけば良いです。

計算量は、Xまでの文字列の大きさがlogXで、最終的なTの大きさもlog(10^{18})を超えないことから、O(N)だと思います。

提出コード

書いていて気づきましたが、最終的にTは'U'を含まないので、答えの番号を求めるときの分岐は不要でした。

解法2の考え方も思いついたのですが、ビットシフトしなければいけないと思い断念しました。
単純に末尾に末尾への追加・削除だけで良いことを思いつけなかったです。

ABC242D ABC Transform

ABC 二分木 再帰

解説AC

問題へのリンク
公式解説へのリンク

テキストとyoutubeの解説の自分用まとめです。特に新しいことはありません。公式を見た方が詳細です。

二分木として考える

各文字が2つの文字になることを順に図示すると、二分木の構成になります。

よって、この問題は、

S^{(0)}_0,\ S^{(0)}_1,\ \cdots S^{(0)}_{N-1}を根とする二分木における、深さtでk番目の文字を求めよ

という問題と見ることができます。

mod\ 3における0,1,2をA,B,Cに対応させます。
Aの左子ノードがB、右子ノードがCであるとします。
左子ノードに進むことは、mod\ 3において+1すること、右子ノードに降りることは+2することと同じです。B,Cにおいても同様に考えることができます。

よって、親の文字がわかれば子の文字を求めることができます。

以降、+xするという表現はmod\ 3上での操作を指します。

親と子の番号の関係

深さtにおいて、k番目である場合、その子は、深さt+1において、左子ノードが2k番目、右子ノードが2k+1となります。

以下が理由です。
深さtにおいてk番目である場合、自分より前には0,...,k-1までのk個のノードが存在する。
深さt+1には、それらの子ノードが2個ずつ存在し、その数は2k個となる。それらの番号は、0,...,2k-1となるから。

これより、

  • 親がk番目なら、子の番号は左が2k、右が2k+1
  • 子の番号がkなら親の番号は、\lfloor \frac{k}{2} \rfloor

が言えます。
また、

  • 子の番号が偶数なら親の左子ノード、奇数なら右子ノード

も言えます。

tが小さい場合

解説にならって、S^{(t)}のk番目の文字を求める関数をf(t,k)とおきます。

以下のように再帰的に求められます。

f(t-1,\lfloor \frac{k}{2} \rfloor )を求め、kが偶数なら+1、奇数なら+2します。
tが十分小さい場合、再帰の過程でt=0となります。この時、f(0,k')をS^{(0)}_{k'}として返せばよいです。

tが大きい場合

深さが1増えると子の数は2倍になります。
深さdから、60回深いところに進むと、0,...,2_{60}-1番目の文字は全てS^{(d)}_0の子孫であることがわかります。

kの最大値は10^{18} \lt 2^{60}-1であることから、tから60回ほど親を遡ったところをt'とすれば、深さtのk番目の文字は全てS^{(t')_0}の子孫となります。

ある深さdにおけるS^{(d)}_0は、全てS^{(0)}_0の左子ノードをd回進んだ文字であるので、S^{(0)}_0+dすることで求められます。

以上より、再帰においてkを1/2していくと、高々60回ほどで、k=0となります。このとき、f(t',0)をS^{(0)}_0+t'として返すようにすればよいです。
提出コード(公式とほぼ同じ)

ABC241 参加記録

ABC 出次数1の有向グラフ 双方向連結リスト Loop 鳩の巣原理

コンテスト中AC:A〜C,E
コンテスト後、Dは自力AC

2022/07/06追記
Eの実装に単射や同値類という記載がありますが、誤りです。 無視してください。

D - Sequence Query

実装が複雑になりましたが、自作双方向連結リストでACしました。

  • 出現した整数の昇順ソートされた順序集合S (set)
  • 初めて出現した整数が双方向連結リストに何番目に挿入されたかを記録するハッシュマップM (unordered_map)
  • 双方向連結リストD

を準備します。
それぞれにあらかじめ、-\infty , \inftyを入れておきます(番兵)。
Dには昇順に値が挿入されていくように処理します。

具体的には、i番目のクエリは以下のように処理します。

クエリ1 x

  1. xがDに初めて挿入される場合、MにDの何番目に挿入されたかを記録する。
  2. xより大きい最小の整数yをSから二分探索で得る。
  3. yがDの何番目に挿入されたかをMから得る。これをj番目とする。
  4. Dにおいて、j番目に挿入された値(y)の後ろにxを挿入する。

クエリ2 x k

  1. xより大きい最小の整数yをSから二分探索で得る。
  2. yがDの何番目に挿入されたかをMから得る。これをj番目とする。
  3. Dにおいて、j番目に挿入された値(y)から後ろにk回辿る。この時、途中または最後に-\inftyにたどり着いた場合、-1とする。そうでない場合、辿った先を答えとして出力する。

クエリ3 x k

  1. xより大きい最小の整数yをSから二分探索で得る。
  2. yがDの何番目に挿入されたかをMから得る。これをj番目とする。
  3. Dにおいて、j番目に挿入された値(y)から前にk-1回辿る。この時、途中または最後に\inftyにたどり着いた場合、-1とする。そうでない場合、辿った先を答えとして出力する。

multisetを使うとイテレータの増減だけでいいようです。今更ながら勉強になりました。

提出コード

E - Putting Candies

i\rightarrow (i+A_i)\ mod\ Nに移動すると考えます。
常に移動先は同じなので、鳩の巣原理によって、多くともN回くらい移動すると、同じ場所が2回現れ、その後ループします。

あとは、K回の移動で何回iから移動するかをカウントすれば答えを計算できます。

それを自作ライブラリ化してあったので、よければ参考にしてください。
実装はコンテスト後に少し修正してあります。

なお、この問題は各頂点が有向辺を1つだけもつグラフとも捉えられます。
そのようなグラフは閉路を１つだけ持ち、すべての頂点は閉路に属するか、閉路へ向かうように向きづけられています。
(ここで一応証明してみてあります。AtCoderの過去問の記事なのでネタバレ注意)

提出コード