The First KMCMonthly Contest 解説 - てきとーな日記

参加者の皆様お疲れさまでした。
以下てきとーな解説を

A

Circular-arc graphの最大安定集合を求める問題。
端がつながっていなければ、終了時間でソートして貪欲に使えばよい。
端がつながっている場合、最初に使う区間を決めれば上記の貪欲法を用いることができるので、最初の区間を全通り試してO(N^2)で解くことができる。
このままではもちろんTLEするので、ある区間から始めた場合に何個の区間を使えるかを高速に計算する必要がある。
ある区間を使った後、次にどの区間を使うべきかは簡単に求めることができ、今度はそれを用いて2つ先にどれを用いるか、4つ先に…、というのを計算することができる。
これらを計算しておけば、何個使えるかの計算が二分探索によって行うことができる。
これでO(N log N)で解くことができる。
ちなみにバケツソートすればO(N)の解法もある。

B

おもちゃのカンヅメをM個手に入れるのに買うチョコボールの個数の期待値を求める問題。
まず、銀のエンゼルを基準にして考えることにより、おもちゃのカンヅメをM個手に入れる問題から銀のエンゼルをMN枚手に入れる問題に変形する。
銀のエンゼルが残りi枚必要な時の期待値をaiとすると、
ai=r*a(i-NK)+p*a(i-N)+q*a(i-1)+(1-r-p-q)*ai+1
初項ai=0(i<=0)
という漸化式が得られる。
夏合宿で出題時にはMのサイズが10^5だったのでこのまま順に計算していくことで解くことができる。
今回は10^9で出題したので漸化式を順に計算していくことはできない。
行列で累乗計算を行えばlogMになるが、行列のサイズが1600くらいもあって、これもTLEしてしまう。
しかし、漸化式の計算は行列を経由せずにもっと高速におこなうことができる。(と、きたまさがしきりに主張していたのできたまさ法と呼ぶことにする)
漸化式がa(i+n)=Σkj*a(i+j)+dであったとする。
amが初項であるa0からa(n-1)の和で、am=Σbiai+bndと表されたとすると、
a(2m)=Σbia(m+i)+bnd=Σbi(Σbja(i+j)+bnd)+bnd=ΣΣbibja(i+j)+(Σbi+1)bnd
となり、a(2m)をa0からa(2n-2)の和で表すことができる。
anからa(2n-2)をa0からa(n-1)の和で表すことはO(n^2)で可能であるので、これを用いて繰り返し二乗法を行うことにより、先の漸化式はO((NK)^2 log M)で計算可能である。
また、今回のように{ki}が疎な場合、anからa(2n-2)をa0からa(n-1)の和で表すことはO(n)でできる。
さらに、ΣΣbibja(i+j)は畳込みであるから、FFTを用いてO(n log n)で計算できる。
これらを用いると、O(NK log NK log M)で計算することも可能である。

C

上・前・横から見たときの形から積まれている最小のコンテナ数を求める問題。
まず、上から見たときにコンテナのある位置に、前から見たときと横から見たときで少ない方の個数だけ置いてみて、条件を満たしているか調べれば、解の存在判定はできる。
次に、最小個数で積むことを考える。
高いhから順に積む場所を決めていったとする。
高さh>1に積める場所は、上から見てコンテナが存在し、前からみても横から見ても高さh以上である場所である。
前から見ても横から見ても高さがhより大きい場所には高さhで置く利点がないので置く必要がない。
そうでない場所にはそれより高くコンテナを置くことができないので、まだコンテナは積まれていない。
解が存在するならば、このような個所はそれぞれ、高さhである行・列について1つ以上は存在しており、少なくともそのような行の個数+列の個数箇所に置けば条件を満たせるはずである。
行・列に対する条件を同時に満たせればその分だけ置く場所が少なくて済むので、ようするに最大マッチングを求めればよいことになる。

D

グラフの辺を破壊しながら、二点が同じ連結成分に含まれるか判定する問題。
クエリを後ろから見ていくと、グラフに辺を追加していくだけなので、UnionFindで連結判定をすればよい。

E

MPを消費してドアを開けながら最短の時間で移動する問題。
まず、MPに上限がないので回復は一番最初に必要な分やってしまうのが一番なのは明らか。
最初にどれだけMPを回復すればよいかも、魔法陣の上でどれだけMPを消費すればいいかもわからないが、1MP=1sで換算できるので、状態を現在地とちょうどその時間に閉じたドアの集合だけにまとめることができる。よって、状態数たかだか30^2*2^8のダイクストラに帰着できる。
具体的には、k種類のドアがぎりぎり開いている状態の時、1マス移動するのに、時間をさかのぼってスタート地点でk回MP回復をし、各ドアを開けた魔法陣の上でもう1ずつ余分にMPを消費していたことにできるので、(k+1)sかけてドアをぎりぎり開けた状態のまま移動できる。

F

区間のXORの最大値を求める問題。
まず、Si=a1^...^aiとすると、as^...^at=S(s-1)^Stである。
よって、SiのペアでそのXORが最大となるものを探す問題に帰着される。
Siのペアでちょうどある値Vになるものが存在するかの判定は、簡単に行うことができる。
具体的には、Si^Sj=VはSj=V^Siであるので、各Siに対してSi^VとなるSjが存在するか判定すればよく、これは最初にSiの出現をbool配列にでも入れておけばO(N)でできる。
ちょうどVになるかの判定ができるので、あとは上位ビットから順に作れるか判定していくことで最大値を求めることができる。
以上よりO((N + M) log M)の解法が得られる。 (M=max{ai})
また、上位jビットの種類は高々2^j個しかないので、各Siの上位jビットの種類から上位(j-1)ビットの種類を構成していくことでO(M)で解くこともできる。
最大値が求まれば、そのような辞書順最小の区間を求めるのも簡単だが、最大が0になる場合には注意しないといけない。

G

等速直線運動する点集合の中で、ある時刻に原点からマンハッタン距離で一番遠い点までの距離を求める問題。
初期位置(x,y)、速度(vx,vy)の点を考える。
時刻tにおける位置は(x+vxt, y+vyt)であり、原点からの距離はd(t)=|x+vxt|+|y+vyt|である。
d(t)は三直線の上部をつなげてもの(上側エンベロープ)であり、点の集合に対するmaxも同じく上側エンベロープである。
直線の集合に対し、上側エンベロープを求めることは、双対変換して下側凸包を求めることに等しくO(N log N)でできる。
あとは各時刻に対し、どの直線が最大値を与えるかを二分探索で調べるだけでよいので、合わせてO((N + M) log N)の解法が得られる。

H

k乗してbになる置換aの存在判定と、唯一判定を行う問題。
まず、長さxの巡回をk乗すると、長さx/(x,k)の巡回(x,k)個に分裂する。
今、k乗した置換に長さyの巡回がn個あったとする。
nをx/(x,k)=yであるようなxの列を用いてn=Σ(x,k)と表せるか調べたい。
k=Πpi^ki、x=Πpi^xi、y=Πpi^yiと表すと、
(x,k)=Πpi^min(xi, ki)であり、x/(x,k)=Πpi^max(0, xi-ki)である。
y=x/(x,k)より、yi=max(0, xi-ki)であるので、
xi=0〜ki(yi=0), xi=yi+ki(yi>0)となる。
よって、z=Πpi^zi、zi=0(yi=0), zi=yi+ki(yi>0)とすると、(x,k)は全て(z,k)の倍数となり、(z,k)|nであるかを調べるだけでよいことが分かる。
長さNの置換に含まれる異なるサイズの巡回の個数はO(√N)であり、それぞれに対して、上記のzはO(√N)で構成できるので、全体でO(N)で存在可能性の判定ができる。
長さxの巡回d個をまとめて長さxdの巡回にすることを考える。
dを上で求めた(z,k)とすれば、(x,k/d)=1であるから、m*(k/d)=1(mod x)であるようなmが求まり、i番目の巡回の位置jからi+1番目の巡回の位置jへ、d番目の巡回の位置jから1番目の巡回の位置j+mへ移動するような巡回にすればよい。
次に唯一性の判定を行う。
二つ以上の巡回をくっつけることができるのなら、そのつなげ方に一意性がないので唯一でない。
逆に、どの巡回もくっつけれらないのなら唯一である。
巡回をくっつけることができるのは、上の式で、d>=2のときと、n>=(kの最小の素因数)のとき。
kが大きいので最小の素因数の計算が大変だが、nより大きいことが分かった時点で止めてよいので、結局これもO(N)でできる。

I

正方形が集まってできた図形の穴の個数を求める問題。
有効な辺の上を移動しながら回転方向で穴かどうかの判定を行う、もしくはオイラーの多面体公式によって面の数を数えるという方針がある。
後者の場合は連結成分の個数の計算も忘れてはいけない。

J

カードをシャッフルしていく途中における上半分のカードの和の最大値を求める問題。
よーく考えるとシャッフルと言いながらただの巡回シフトをしているだけなので、あとはてきとーにやるだけ。