2022-05-24

AtCoder Beginner Contest 251 参加記録

ABC 少ない状態数構成問題

コンテスト中AC:A〜C,E

E - Takahashi and Animals

E - Takahashi and Animals

グラフの問題として考えていたので、言い換えておきます。

頂点 $0,...,N-1$ について、頂点 $i$ と頂点 $(i+1)\ mod\ N$ の間には辺 $i$ があり、そのコストは $A_i$ です。
ここから、以下の条件を満たすように辺をいくつか削除します。

すべての頂点の次数が1以上

残った辺のコストの総和をスコアとする時、スコアの最小値を求めてください。

辺がある時とない時で状態が2通りしかないので、 $i$ の小さい方から順にdpができないか考えます。

$dp[i][j]:=$ 辺 $i$ の状態が $j$ の時のスコアの最小値。但し、
$j=0$ の時、辺 $i$ は削除されている
$j=1$ の時、辺 $i$ は残っている

遷移について、辺 $i-1$ 番目が決定しているとして、辺 $i$ を考えます。

辺 $i$ を残す場合
辺 $i-1$ は削除されていても残っていてもよいです。従って、
$dp[i][1]\leftarrow min(dp[i-1][0],dp[i-1][1])+A_i$
辺 $i$ を削除する場合
辺 $i-1$ は残っている必要があります。そうしないと、頂点 $i$ の次数が0になります、従って、
$dp[i][1]\leftarrow dp[i-1][1]$

このように遷移していけば解けるかのように思えますが、例えば、 $i=0$ の時の初期値を

$dp[0][1]\leftarrow A_0$
$dp[0][0]\leftarrow 0$

として、 $i=2,...,N-1$ と更新していくと $i=N-1$ で困ったことになります。というのも、

辺 $N-2$ が存在する場合でも、辺 $0$ が存在しない場合には辺 $N-1$ を残さなければならず、前述の遷移通りいきません。

これを解決するためには辺 $0$ が残っているかどうかの情報があれば良いので、DPテーブルに追加します。

$dp[i][j][k]:=$ 辺 $i$ の状態が $j$ であり、かつ、辺 $0$ の状態が $k$ の時のスコアの最小値。但し、
$j=0$ の時、辺 $i$ は削除されている
$j=1$ の時、辺 $i$ は残っている
$k=0$ の時、辺 $0$ は削除されている
$k=1$ の時、辺 $0$ は残っている

遷移は、 $k=0,1$ の両方の場合が必要になるだけで、先程と同じです。

辺 $0$ を初期値とします。
$dp[0][0][0] \leftarrow 0$
$dp[0][1][1] \leftarrow A_0$
$dp[0][0][1] \leftarrow \infty$
$dp[0][1][0] \leftarrow \infty$
としておきます。( $dp[0][0][1],dp[0][1][0]$ は矛盾しており、あり得ない状況です。)

このDPを $1,...,N-2$ まで順に更新します。
辺 $N-1$ の状態は、辺 $0,N-2$ の状態に従います。

辺のいずれか一方が削除されている場合
頂点 $0,N-2$ の少なくとも一方は次数0なので、辺 $N-1$ は残す必要があります。よって、この時は、
$x_1 = min(dp[N-2][0][0],dp[N-2][0][1],dp[N-2][1][0])+A_i$
辺の両方がある場合
頂点 $0,N-2$ の両方とも次数が1なので、辺 $N-1$ は不要です。よって、この時は、
$x_2 = dp[N-2][1][1]$

最終的な答えは、 $min(x_1,x_2)$ です。
提出コード

2022-05-20

ABC250E Prefix Equality(ABC250 参加記録)

ABC 集合の一致判定 Zobrist Hash

コンテスト中AC:A〜D
Eはコンテスト後に解説を読み、自分がコンテスト中に考えていた発想で問題なさそうだったので、その方針でなんとかACできました。
E問題について書いたので、記事のタイトルはEをメインにしました。

E - Prefix Equality
- 自分の実装
- Zobrist Hash

E - Prefix Equality

自分の実装

こちらの解説と多分同じ考え方だと思います。(多分)

方針

大雑把なイメージです。
$(a_1,...,a_i)$ から得られる集合を $S^a_i$ とします。同様に、 $(b_1,...,b_j)$ から得られる集合を $S^b_i$ とします。

$S^a_i$ と等しい $S^b_j$ が存在すると仮定し、その中で最小の $j$ を $l$ とします。

$j=l,l+1,...$ と増加させ、 $b_j$ を追加していくと、そのうち集合として等しくなくなります(但し、便宜上 $b_{N+1}$ に $A$ に含まれない値があるものとします。)。この時の $j$ を $r$ とします。

この時、 $S^a_i$ に対しては、 $l\leq j\lt r$ を満たす $S^b_j$ が全て等しくなります。

よって、各 $i$ について、 $j$ の区間を前計算しておけば、各クエリに $O(1)$ で答えられます。

前計算の計算量

愚直に各 $i$ について、 $j$ の区間を求めようとすると、少なくとも $O(N^2)$ くらいにはなってしまいます。

しかし、実は $i=1,2,..$ と探索していくと、 $j$ の探索範囲も増加するだけになり、結果として $O(N)$ くらいになります。
具体例と共になぜそうなるか書いていきたいと思います。

前計算の処理

以下の数列を例にします。
$A=\{1,2,1,5,2,3\}$
$B=\{2,1,2,1,3,5,-1\}$ (-1は番兵)

以下の集合を定義します。

$S_A$ : $S^a_i$ に含まれ、 $S^b_{j-1}$ ではまだ見つかっていない値の集合
$S_{AB}$ : $S^a_i$ と $S^b_{j-1}$ に共通して存在する値の集合

$i=1,2,...,N$ について、 $A$ の先頭 $i$ 項と $B$ の先頭 $j$ 項が等しくなるような $j$ の区間を求めます。
初め $j=1$ としておきます。

(1) $S_A$ に $a_1=1$ を追加し、これに対応する $j$ の区間を求めます。
$b_1 = 2$ であり、 $S_A$ に一致する値がないので、これに一致する $j$ の区間は存在しません。

(2) $S_A$ に $a_2$ を追加します。 $S_A=\{1,2\}$ です。
$b_1 = 2$ なので、 $S_A$ から $2$ を削除して、 $S_{AB}$ に追加します。 $b_2=1$ も同様です。

ここで、 $S_A$ が空になりました。これは、 $S^a_2 = S^b_2$ となったことを指します。よって、 $i=2$ のときに集合が等しくなる時の下限は $j=2$ です。下限が見つかったため、上限を調べます。

現在、 $S_{AB}=\{1,2\}$ です。
$b_3=2,\ b_4=1$ は $S_{AB}$ に含まれるので、 $S^a_2 = S^b_2 = S^b_3 = S^b_4$ となります。
次の $b_5 = 3$ は $S_{AB}$ に含まれないので、この時点で、 $S^a_2 \neq S^b_5$ となります。従って、半開区間 $[2,5)$ が $i=2$ の時に集合として等しくなる $j$ の区間です。

(3) $a_3=1$ は $S_{AB}$ に含まれ、更に $S_A$ が空です。よって、 $S^a_3$ は一個前の $S^a_2$ と等しく、かつ、 $S^a_2$ には $j$ の区間が存在していることがわかります。

この場合、 $S^a_3 = S^a_2$ であることから、 $i=3$ についての $j$ の区間は $i=2$ の時と同じになります。

(4) $a_4=5$ を $S_A$ に追加します。この時、新たに $j$ の区間を再探索しますが、 $j=5$ からの探索として良いです。
なぜなら、 $b_1,b_2,b_3,b_4$ は $a_1,a_2,a_3$ に含まれるため、 $S^a_4$ を集合として等しくするために必要になるからです。また、 $b_5$ は $a_1,a_2,a_3$ に含まれない最初の値なので、ここから探索を開始する必要があります。

$j$ の区間の探索をしますが、 $b_5=3$ で、これは $S_A$ に含まれません。よって、 $i=4$ と等しい $j$ の区間は存在しません。

(5) $a_5=2$ は $S_{AB}$ に存在するので、既に $S^a_4,S^b_4$ の両方に共通して存在しています。そのため、 $S_A$ には追加しません。
$j$ の区間の探索をしますが、 $b_5=3$ で、これは $S_A$ に含まれません。よって、 $i=5$ と等しい $j$ の区間は存在しません。

(6) $a_6=3$ を $S_A$ に追加し、 $S_A=\{3,5\}$ となります。

$j$ の区間を探索すると、 $b_5 =3,\ b_6=5$ と進めると、両方 $S_A$ に含まれるので、 $S_A$ から削除し、 $S_{AB}$ に追加します。 $j=6$ の時点で $S_A$ が空になったので、 $j=6$ が、 $S^a_6$ と等しくなる下限です。
上限ですが、番兵として入れてある $b_7=-1$ が $S_{AB}$ に含まれないので、 $i=6$ の時は、 $[6,7)$ が該当の区間になります。

以上で、全ての $i$ に対する $j$ の区間が求まりました。

例で示したように、 $j$ は常に、 $A$ の $i$ 項目までに含まれない最初の値を指すようにしておきます。
すると、 $i+1$ 目項までと等しい区間を探す際に $j$ から開始すればよくなります。
なぜなら、 $S^a_{i+1}$ と等しい区間を探す際に、 $S^a_{i+1}$ は $S^a_{i}$ を部分集合として含むため、少なくとも $S^a_{i}$ と共通な値のみを含む $S^b_{j-1}$ が必要となるからです。
これで、 $j$ は増加させるだけでよいことがわかりました。

提出コード

Zobrist Hash

公式解説にあったので解いてみました。

整数 $x$ を乱数に変換します。これを $R_x$ とします。

集合 $S=\{a_1,...,a_m\}$ のハッシュ値を $R_{a_1}\oplus...\oplus R_{a_m}$ と定義します。
また、数列 $A,B$ の $i$ 項目までからなる集合から計算されるハッシュ値をそれぞれ $Z^A_i,\ Z^B_i$ とします。

するとi番目のクエリは、

$Z^A_{x_i} =\ Z^B_{y_i}$ ならyes、そうでなければNo

と判定できます。

$Z^A_i,Z^B_i$ の計算方法については、累積的にXOR和をとっていけばよいのですが、一点注意が必要で、同じ値を2回以上XORを取らないようにします。(偶数回とると、0になるため)

Bonusの問題は、単純に区間のXORをとっても上記の問題を解決できないので、わかりませんでした。

ハッシュの衝突に関してはyoutubeの公式解説では、64bit整数なら $\frac{1}{2^{64}}$ くらいになるそうです。

なお、実装では、 http://vivi.dyndns.org/tech/cpp/random.html

↑を参考に64bitのメルセンヌ・ツイスタに乱数をseed値として与えて生成しました。

提出コード

2022-04-28

ARC139 参加記録

コンテスト中AC:A

A - Trailing Zeros

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桁が考慮すべき最大桁数となると思います。

2022-04-26

ABC249 参加記録

ABC 整数論約数の個数連続する数の約分

コンテスト中AC:A〜D

D - Index Trio

D - Index Trio

$\frac{A_i}{A_j} =A_k$ を変形すると、 $A_i = A_jA_k$ となります。
$A_i$ を固定すると、 $A_j,A_k$ は $A_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）

2022-04-22

ABC248 参加記録

ABC 計算幾何直線ウェーブレット行列

コンテスト中AC:A〜D

D - Range Count Query
E - K-colinear Line

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)$ を通る直線の式はググりました。

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

$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)} で正規化"

$gcd(a,b,c)=1$ にする
以下の2つは同じ式です。
$x+2y-3=0$
$2x+4y-6=0$
これを同一視するため、 $g=gcd(a,b,c)$ として、 $g$ で $a,b,c$ を割ります。
符号を揃える
以下の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$ の式に代入していましたが、外積でいけるようです。

2022-04-15

ARC138 参加記録

ARC RMQ Segment Tree

コンテスト中AC:A

A - Larger Score

A - Larger Score

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

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

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

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

$x_i$ と $y_j$ の入れ替えに必要な最小の操作回数は、 $x_i$ を $K$ 番目に移動させた後、 $y_j$ を $K$ 番目に移動させればよいので、 $x_i$ が $A_s$ 、 $y_j$ が $A_t$ とすると、 $K-s+t-K=t-s$ 回となります。

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

例えば、 $i'\lt i$ である $x_{i'},x_i$ と、 $j\lt j'$ である $y_j , y_{j'}$ を入れ替える場合を考えます。
この時、 $x_i$ と $y_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_i$ 、 $y_j$ について $x_i \lt y_j$ が成立します。

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