◇◇CS Academy - IOI 2016 Training Round #1◇◇

https://csacademy.com/contest/ioi-2016-training-round-1/summary/

横の長さが$N$、縦の長さが$M$の長方形で表される廊下があり、この廊下の左下の角を原点とする。この廊下には$K$個の障害物があり、$i$番目の障害物の座標は($x_i, y_i$)である。この廊下に左から入って右へ通過できるような円の半径の最大値を出力せよ。

すべての障害物と上下の壁を頂点とみなした重み付き完全グラフを考える。ここで、各辺の重みは障害物間のユークリッド距離(片方が壁の場合は壁と障害物もしくは壁と壁の距離)である。左から廊下に入った円が右に通り抜けることは、上述のグラフにおいて下の壁から上の壁へのあり得るpathすべてを横切ることであると言い換えることができる。あるpathを半径$r$の円が「通り抜けられない」条件は、そのpathを構成するエッジの重みがすべて$r$未満である場合であって、このようなpathが存在するとき、半径$r$の円は廊下を通り抜けることができず、逆にこのようなpathが一つもないときに限り廊下を通り抜けることが可能である(障害物の間を円が通り抜けられずに引っかかるとき、あり得るpathのうち必ずどれかに引っかかっている)。

重みが$r$未満の辺のみから構成されるpathがあるかどうかを調べることは容易であって、$r$未満の辺だけを使ってBFSを行い、下の壁に対応する頂点から上の壁に対応する頂点への到達可能性を判定すればよい。$r$を二分探索すれば時間計算量はO($K^2\log{M}$)であるが、この問題では$K\leq5000, M\leq10^6$と大きく、かつ制限時間が1000msしかないので間に合わない。

高速な方法として、最短経路の代わりに辺の重みの最大値の最小値をダイクストラ法で求めることによってこの問題をO($K^2$)で解くことができる。

解説AC。幾何だと思っていたらグラフ問題だった。自分での考察では全く手が出なかった。

$N$頂点の凸多角形がある。この多角形を、頂点間を線同士が交差しないように結ぶ($K-1$本の線を引く)ことで$K$個に分割する方法の数を$10^9+7$で割った余りを出力せよ。

凸$N$角形の隣り合わない頂点どうしを線で結ぶと2つの凸多角形に分かれるが、これまでに引いた線と交差しないように次の線を引くことは新たにできた凸多角形の隣り合わない頂点どうしを線で結ぶことと言い換えることができて、これは元の問題の$N$および$K$が小さい場合になっている。ここで、DPテーブルを

$DP[i][j]=$凸$i$角形の頂点同士を線が交差しないように結び、$j$個の凸多角形に分けるときの線の引き方の順列の数

のようにとる。DPテーブルの更新順序は$i$の昇順であり、求める答えは順列ではないので、$\frac{DP[N][K]}{(K-1)!}$を出力すればよい。

凸$i$角形を$j$個に分割したいとして、最初に1本線を引く方法を考える。引いた線は$i$角形を2つの凸多角形に分け、このとき分けられた片方が$k(\geq3)$角形であればもう片方は$i-k+2(\leq i-1)$角形となる。ここで、凸$i$角形を$k$角形と$i-k+2$角形に分ける線の引き方は$i$通りだが、$k=i-k+2$である場合に限り$\frac{i}{2}$通りしかない。

最終的に$j$個の領域を作りたいので、今できた2つの多角形をそれぞれ何個の領域に分割するかを振り分ける。片方を$l$個に分割するとき、もう片方は$j-l$個に分割することになる。それぞれの場合はより小さい問題の答えになっている。

以上のことから、DPテーブルの更新は以下のようになる。 $$DP[i][j]=\sum_{k=3}^{\frac{i+2}{2}}\sum_{l=1}^{j-1} DP[k][l]\times DP[i-k+2][j-l]\times (i\;or\;\frac i2)\times _{\{(l-1)+(j-l-1)\}}C_{l-1}$$ これは、上述のあり得る分け方をすべて足し合わせたものである。$DP[k][l]$と$DP[i-k+2][j-l]$をただ掛けただけでは順列の数にならないので、最後に二項係数を掛けている。

自力AC。解法自体はすぐに思いついたが、実装に少し手間取った。$N\leq 125$でO($N^4$)なので間に合うか多少不安だったが、蓋をあけてみればかなり余裕だった。なお問題の性質上、DPテーブルをそのまま埋め込めばO(1)も可能。

自然数$N$に対応するFarey数列$F_N$とは、区間$(0, 1)$にあるすべての既約分数のなかで分母が$N$以下であるようなものを昇順に並べた数列であり、たとえば $$F_5=\frac15,\frac14,\frac13,\frac25,\frac12,\frac35,\frac23,\frac34,\frac45$$ となる。自然数$N, K$が与えられるので、$N$に対応するFarey数列$F_N$の$K$番目を出力せよ。

$\frac XN$と$\frac{X+1}{N}$の間に$K$番目の要素を含むような$X$を見つけて、この間の区間のみFarey数列を実際に構成することでこの問題を解くことができる。

Farey数列$F_N$のなかで分数$\frac XN$が何番目の要素かということを調べる方法は以下である。DPテーブルを

$DP[i]=F_N$のなかで、$\frac XN$以前にある分母が$i$の要素の数

のようにとる。ある分数$\frac AB$が約分できるならFarey数列の要素ではないので、$DP[B]$は$\frac AB \leq \frac XN$であるような$\frac AB$のなかでGCD($A, B$)$=1$であるような$A$の数と言い換えることができる。ある分数$\frac AB$が約分できる場合、約分したあとの分数が$B$より小さい分母で既に現れているはずなので $$DP[B]=\left\lfloor \frac{XB}{N} \right\rfloor-\sum_D DP[D]$$ と表せる。ここで、$D$は$B$の約数である。このDPの更新はエラトステネスの篩の要領で行うことができて、$DP[i]$を決定したあと$i$の倍数すべてから$DP[i]$を引くことを繰り返せば全体でO($N\log{N}$)となる。これをすべて足し合わせたものが求めるindexである。

以上の方法を使って二分探索を行えば$\frac XN$と$\frac{X+1}{N}$の間に$K$番目の要素を含むような$X$を見つけることができるので、次にこの区間内のFarey数列を実際に構築する。

Farey数列$F_N$において、分母が$B\;(\lt N)$の分数は$\frac XN$と$\frac{X+1}{N}$の間に自明に高々1つしかない。分母$B$について、そのような分数の分子の候補$A$は$\frac XN\leq\frac AB$となるような最小の分子 $$A=\left\lceil \frac{XB}{N} \right\rceil$$ であり、$\frac AB \leq \frac {(X+1)}N$かつGCD($A, B$)$=1$の場合のみ$F_N$の要素となる。

以上のようにして実際に$F_N$の一部が構成できたら、ソートして$K$番目の要素を数えて出力すればよい。

解説AC。二分探索っぽい雰囲気は結構感じていたが、分数で二分探索するのが難しく諦めてしまった。

戻る