geam1113’s diary

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

ARC139 参加記録

コンテスト中AC:A

A - Trailing Zeros

説明のため、二進数10桁しかないと仮定します。

例えば、T_i = 3の時、??????1000となり、?の部分が未確定です。
この時、??????の部分は、000000〜111111があり得ます。

000000, 000001, ...と増加させていくと、ある境でA_{i-1}\lt A_iとなり、以降全てこれが成立します。
よって、この境界は二分探索可能です。

最大何桁目まで考慮するかですが、問題文にも特に言及はなかったので64bit整数に収まるだろうと推測し、60桁としました。
ACできたので、問題なかったようです。

提出コード

コンテスト後に最大桁数について考えてみました。
A_Nが最大となるのは、N=10^5かつ、T_iがいずれも40の場合だと思います。

100...0が0〜41桁目までありますが、一旦無視して42桁目以降を考えます。

Aの42桁目以降は、{00...001, 00...010, 00...011,...}という感じで+1ずつ増やしていけばA_Nが最小となるので、A_Nの42桁目以降は10^5-1の二進数表記となっているはずです。

従って、A_Nの最大は、
99999の二進数表記 11000011010011111の17桁

10000000000000000000000000000000000000000の41桁

を連結させた数になります。

従って、58桁が考慮すべき最大桁数となると思います。

ABC249 参加記録

コンテスト中AC:A〜D

D - Index Trio

 \frac{A_i}{A_j} =A_kを変形すると、A_i = A_jA_kとなります。
A_iを固定すると、A_j,A_kA_iの約数の組に限定されます。
よって、A_1,...,A_Nについて、1\leq d \leq \lfloor \sqrt{A_i} \rfloorである約数dについてのみ調べれば良く、各A_iについて、O(\sqrt{A_i})で全探索できます。

計算量は、Aの最大値をA_{max} として、O(N\sqrt{A_{max}})となり、間に合うか微妙なところですが大丈夫でした。

A_i=d\times \frac{A_i}{d}となる組が何通りあるかですが、
cnt_{x}Aに出現するxの個数とすると、

cnt_{d} \times cnt_{ \frac{A_i}{d}}

となります。
これは、A_j = dとなる全てのA_jに対して、A_k =  \frac{A_i}{d}となるA_kと組を作ることができるためです。

1\leq d \leq \lfloor \sqrt{A_i} \rfloorであるdについて組を計算するわけですが、 d\neq  \frac{A_i}{d}である場合、組の順序を入れ替えると別の組になるので、2倍します。
逆に、d =  \frac{A_i}{d}の場合は入れ替えてできる組は同じなので、2倍しません。

提出コード Submission #31196140 - Monoxer Programming Contest 2022(AtCoder Beginner Contest 249)

なお、計算量を落とすことが可能です。
1,2,...,A_{max}の全てについて、エラトステネスの篩と同じ方法で、試し割り不要で約数が記録された二次元配列を得ることが可能です。
計算量はO(A_{max}logA_{max})となり、二次元配列のサイズも同様にA_{max}logA_{max}となると考えられます。

組の計算にかかる計算量ですが、

blog.hamayanhamayan.com

上記に高度合成数の言及がありますが、ある整数X以下の約数の個数が最大となるのが高度合成数です。
A_{max}が全て2\times 10^5以下の高度合成数Kであった場合が最悪となり、O(NK)です。

高度合成数の一覧 (10^18 以下) | アルゴ式

上記によれば2\times 10^5以下の高度合成数の約数の個数は160個なので、問題ないです。

Submission #31257209 - Monoxer Programming Contest 2022(AtCoder Beginner Contest 249)

ABC248 参加記録

コンテスト中AC:A〜D

D - Range Count Query

ウェーブレット行列が使えます。
ウェーブレット行列には以下の関数があります。

計算量は、今回の場合Aの要素の最大値A_{max}をとって、O(logA_{max})です。

各クエリは、quantile(L,R+1,X,X+1)とすることで答えられます。
よって、すべてのクエリをO(QlogA_{max})で計算できます。

ウェーブレット行列の構築にO(NlogA_{max})かかるので、全体でO((N+Q)logA_{max})です。
提出コード

E - K-colinear Line

K=1の時は無限に存在するので、"Infinity"です。

そうでない時、2点を決めれば直線を一意に定められるので2点を全探索します。

悩んだのが、同じ直線を2回以上使わないようにする処理です。

色々調べたことを書いておきます。

まず、2点(x_i,y_i),(x_j,y_j)を通る直線の式はググりました。

二点を通る直線の方程式の3タイプ | 高校数学の美しい物語

y-y_i = \frac{y_j - y_i}{x_j - x_i}(x-x_i)

ax+by+c=0(a,b,c)で管理

式変形すると、

-(y_j  - y_i)x+(x_j - x_i)y + y_i(x_j - y_i) - x_1(y_j - y_i)=0

なので、

a = -(y_j - y_i)
b = x_j - x_i
c = y_i(x_j - x_i) - x_i(y_j - y_i)

であり、これを管理します。

↓のtwitterで言及されていましたが、一意性を保つために正規化する必要があります。

熨斗袋 on Twitter: "格子点を通る直線は ax + by = c の形式で管理するのが楽なんじゃないかなと思う。"

熨斗袋 on Twitter: "gcd で割ったあと、min {(a, b, c), (-a, -b, -c)} で正規化"

  1. gcd(a,b,c)=1にする
    以下の2つは同じ式です。
    x+2y-3=0
    2x+4y-6=0
    これを同一視するため、g=gcd(a,b,c)として、ga,b,cを割ります。

  2. 符号を揃える
    以下の2つは同じ式です。
    x+2y-3=0
    -x-2y+3=0
    これを同一視するため、(表現が正しいかわかりませんが、)符号を揃えます。
    先程のツイートで言うところの、min({a,b,c}, {-a,-b,-c})を採用するのと同じだと思います。

下記実装では、構造体を作ってみました。
提出コード

y=\frac{d}{e}x+\frac{f}{g}(d,e,f,g)で管理

d = y_j - y_i
e = g = x_j - x_i
 f =y_1(x_j - x_i) - x_1(y_j-y_i)

となります。小数での管理は誤差が心配なので、分数で管理します。

分数\frac{p}{q}でも気をつける点があります。

  • gcd(p,q)=1にする。すなわち、gcd(p,q)p,qを割る
  • 符号を揃える。(正,正)なら(負,負)に、(正,負)にする。(これもmin({p,q},{-p,-q})で良さそうです)

また、この実装では、e=g=0のパターン、すなわち、y軸に平行な直線の場合は例外処理が必要です。
x = x_iとして、y軸に平行な直線のx座標を別に管理しておけば良いです。

これも構造体を作ってみました。

提出コード

あと、公式解説と他の方の実装についても書いておきます。

探索済みの点対を管理

公式解説の方法です。

P_i = (X_i , Y_i)とします。

flag[i][j]を点iと点jが探索済みならtrue、そうでなければfalseとします。
初め、全てfalseにします。

ある同一直線上にある全ての点の集合を、Sとします。Sに含まれるすべての点対(P_i,P_j)に対して、
flag[i][j] = true
とします。
こうすることで、全探索の際にflag[i][j]=falseである点対だけ直線を求めればよいことになります。

基準となる2点を管理

他の方の実装を参考にした時によく見られました。

直線は2点によって一意に定めることができるので、先程の集合Sを何らかの基準でソートして、小さい方の2点を記録すること等で管理可能です。

点が直線上にあるかの判定

直線上であるかどうかの判定は、直線ax+by+c=0の式に代入していましたが、外積でいけるようです。

ARC138 参加記録

コンテスト中AC:A

A - Larger Score

一応、考察した内容ですが、あまり自信はないです。

K番目までのAから順番を保ったまま抜き出した部分列をx=\{x_1,\cdots , x_m\}、同様にK+1番目以降の要素から得られる部分列をy=\{y_1,\cdots , y_m\}とします。

また、任意のx_iK+1番目以降に移動させ、任意のy_jK番目以内に移動させる操作を入れ替えと呼ぶことにします。

入れ替えに必要な操作回数

x_iy_jの入れ替えに必要な最小の操作回数は、x_iK番目に移動させた後、y_jK番目に移動させればよいので、x_iA_sy_jA_tとすると、K-s+t-K=t-s回となります。

複数個入れ替える場合に必要な操作回数

例えば、i'\lt iであるx_{i'},x_iと、j\lt j'であるy_j , y_{j'}を入れ替える場合を考えます。
この時、x_iy_jを入れ替えてから、x_{i'}y_{j'}を入れ替える必要があります。つまり、K番目に近いもの同士から順に入れ替えます。

そうでない場合、操作回数はこれより増えます。
なぜなら、例えば、x_{i'}を先にK番目に移動させると、x_iは1つ前に出るため、必要な操作回数が1回増えます。

問題の条件を満たすのに必要な操作回数

まず、明らかにx_i \lt y_jを満たすもの1組を入れ替えると達成可能です。

では、複数個入れ替えて最適になる場合があるか考えます。
今、K以下とK+1以上からm個選び、それらが、以下の条件を満たすとします。

x_1+\cdots +x_m \lt y_1+\cdots +y_m

ここで、x_i \geq y_jとなる組を取り除いても、条件は満たされます。

取り除けるだけ取り除くと、結局、任意のx_iy_jについてx_i \lt y_jが成立します。

取り除いた後の個数をm'すると、前述したとおり、x_{m'},x_{m'-1},\cdots , 1y_1,y_2,\cdots ,y_{m'}を順に入れ替えしていくのが最適です。
ここで、x_{m'}y_1を交換した時点で問題文の条件を満たすので、結局1個だけの交換を考慮するだけでよくなります。

また、x_{m'} = A_s,\ y_1 = A_tであったとします。この時、t'\lt tかつA_s \gt A_{t'}を満たすようなA_{t'}A_tの代わりにすると操作回数がより少なくなります。

結局、必要な最小回数の求め方は、i=1,2,\cdots  ,Kについて、A_iA_jを入れ替える際に必要な交換回数を求め、その中の最小が答えとなります。但し、jj\geq K+1かつA_j \gt A_iを満たす中で最小のものです。

jは、座標圧縮して、Segment Treeで計算しました。
提出コード

ABC243G Sqrt

自力AC

解をf(X)とします。

まず、\sqrt{x}以下の最大の整数は二分探索により、O(logx)で得られます。ここでは、sqrt(x)とします。

X\leq 10^6くらいの場合

dp[i]:=iが与えられた時に生成可能な数列の種類数

と定義すると、

dp[i]\leftarrow dp[1]+dp[2]+\cdots + dp[sqrt(i)]と求められます。

ここで、dpの累積和S_{dp}をとっておけば、

dp[i]\leftarrow S_{dp}[sqrt(i)]

と求められるので、sqrt(x)の計算も含め、小さい方からDPテーブルをO(XlogX)で計算できます。
なお、数列の項が1になった時点で1が延々と続くだけなので、初期値はdp[1] \leftarrow 1です。

この時の解は、f(X)=dp[X]です。

X\leq 10^{12}くらいの場合

f(X)=S_{dp}[sqrt(X)]となります。
前述した通り、10^6までのDPテーブルは計算できるので、解を得られます。

X\leq 9\times 10^{18}の場合

  • f(X)=dp[1]+dp[2]+\cdots + dp[sqrt(i)]

であり、

  • dp[i]=S_{dp}[sqrt(i)]

であるので、

  • f(X) = S_{dp}[sqrt(1)]+S_{dp}[sqrt(2)]+\cdots + S_{dp}[sqrt(sqrt(X))]

とおけます。
これより、sqrt(x)yとなる個数をg(y)とし、k=sqrt(sqrt(X))とすると、

f(X)=S_{dp}[1]\times g(1)+\cdots +S_{dp}[k-1]\times g(k-1)+S_{dp}[k]\times Z

とできます。
Zsqrt(X)以下でsqrt(x)kとなるものの数です。

g(x)は、x^2 \leq i \lt  (x+1)^2を満たすiの個数として求められます。

dp_2[i] = S_{dp}[i]\times g(i)

とすれば、O(N)でDPテーブルを計算できます。

また、S_{dp_2}dp_2の累積和とすると、

f(X)=S_{dp_2}[k-1]+S_{dp}[k]\times Z

とおけます。

後は、Zの求め方ですが、

Z=sqrt(X) - k^2 +1

で求められます。

提出コード

ABC246 参加記録

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

コンテスト全体の感想

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)

より、Xg(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)

より、Xg(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\}とします。

  1. ans=0とする
  2. S空集合を除く全部分集合Tについて、3,4を行う
  3. Tに含まれるS_iの積集合を、Uとする
  4. Tの要素数が奇数ならansg(U)を足す。偶数なら引く

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

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

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

ABC245 参加記録

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

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となる最小のiposとします。

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 となります。

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

従って、i=1,2,\cdots ,Nの順に調べる時、 チョコレートiSに追加された箱は、チョコレート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を開始すれば良いです。

提出コード