2018-04-15

CF 958 E3 - Guard Duty (hard)

問題

問題概要

$N$ 個の白い点と $N$ 個の黒い点の座標が与えられるので、完全二部マッチングをつくりたい。マッチングさせた者同士を線分で結ぶ時に、その線分が交差しないような割り当て方を答えよ。

$1 \le N \le 10000$
$|x|,|y| \le 10000$
2点が同じ位置にある・3点が同じ直線上にのることはない

アイデア

(いきなり)余談だが、このように交差しないマッチングを作ることは必ず出来る。そのようなマッチングとは、線分の長さの合計が最小になるような割り当て方である。仮に、このマッチングに対して交差があるような線分があると仮定する。線分 $B_0 W_1$ と $B_1 W_0$ が交差するとき、これらは $B_0 W_0$ と $B_1 W_1$ の組に繋ぎ替えれば交差はなくなる。そして、この線分の長さの合計は、三角不等式から前者よりも短くなっていることが分かる。

さて、このようなマッチングをどのように構築するかを考える。上で述べたように、白の点と黒の点が同じ個数なら、必ず題意を満たすマッチングを作ることが可能である。よって、1つのマッチングを構成して、それによって出来る線分に対して、領域が2つに分割される時に両方の領域でまた白の点と黒の点が同じ個数になるような線分を常に選び続ける事ができれば、このマッチングは完成する。

今回は、その領域内で、x座標が最小の位置にある点 $b$ とどれをマッチングさせるかを考える。この時に、点 $b$ を基準にして偏角ソートしておき、その順番で点 $b$ を同じなら+1、違うなら-1という風にカウントしていくと、初めはカウンターが0からスタートし、最終的には(領域内には白と黒は同じ個数あり、基準にする点として1つ使っているので)-1でカウンターが止まる。このカウンターが-1になる瞬間に、その点と $b$ を結ぶことにすれば、それより上と下の領域が両方ともまた白の点と黒の点が同じ個数になる。

これを繰り返して、全てのマッチングが終了するまで試せば良い。これは全部で $N$ 回行い、1回の動作の中ではソートをするので、全体として $O(N^2 log N)$ で解くことが出来る。

実装(C++)

2018-04-06

AOJ 2720 - Identity Function

AOJ programming

問題

Identity Function | Aizu Online Judge

問題概要

1より大きい整数 $N$ が与えられる。次のような関数を考える：

$f(a) = a^N \ mod \ N$
$F_1 (a) = f(a)$
$F_{k+1} (a) = F_{k} (f(a)) \ (k = 1,2,3, \ldots)$

この時、 $1 \le a \le N-1$ の $a$ について $F_{k} (a) = a$ が成り立つような最小の $k$ を求めよ。このような $k$ が存在しない時は、-1を出力せよ。

$2 \le N \le 10^9$

アイデア

まず、考察したこととしては、 $N$ が素数の時は、フェルマーの小定理から $f(a) = a$ であることがわかるので素数の時は1が答えになると思った。ただ、素数で無いときにも答えが1になることはあるようでこのような条件を満たす数にはカーマイケル数という名前がついているらしい。

$F_k$ は漸化式の形になっているが、これは帰納的に $F_k (a) = a^{N^k}$ であることが示せる。

$m$ を素数として、 $N = p^2 N'$ のとき、 $p^{N^k} \equiv p (mod \ N)$ となることはない。こうなるということは、 $p^{N^k} = Nx + p$ と書けるということだが、 $Nx + p = p(pxN' +1)$ とくくると、この数は $p$ しか素因数を持たないはずなのに、括弧内の数はどのように $x$ を選んだとしても $p$ の倍数になることはないからである。

つまり、これ以降で考えるべき $N$ としては $N = p_1 p_2 \ldots p_m$ のように、各素因数が1つのみである素数の積の形をしている。

さて、 $a^{N^k} \equiv a (mod \ N)$ が成り立つためには、各素数 $p_i$ でも $a^{N^k} \equiv a (mod \ p_i)$ が成り立っているはずである。さらに、これは $1 \le a \le N-1$ の $a$ について成り立っているので( $a$ と $p_i$ が互いに素なときでも成立しなければならない)、指数の肩に注目すると $N^k - 1 \equiv 0 (mod \ p_i - 1)$ と言い換える事ができる。

これが $1 \le i \le m$ の $i$ について成り立っていて欲しい、ということはLCMを考えて $L = lcm(p_1 -1 , p_2 -1 , \ldots , p_m -1)$ で割り切れて欲しいということになる。よって、この問題は $N^k \equiv 1 (mod \ L)$ を満たす最小の $k$ を見つける、と言う問題になった。

まず、 $N$ と $L$ が互いに素でないならこのような $k$ は存在しない。そして互いに素である場合には、この $k$ はオイラー関数 $\phi (L)$ の約数である(!?)ので、約数を列挙して順番に試せば良い。

とあるが、なんで約数しかみなくていいんだ...ってなったが、もう一度求めたいものをみてみると、この求めたい $k$ というのはまさにカーマイケルのλ関数によって与えられるものであり、それがオイラー関数の約数であることは定義より明らかである(オイラー関数は単純に掛け算しているところで、カーマイケルのλ関数はLCMを取っているので)(参考)。

ただ、今回はNについてのみ成り立ってくれればいいので、やはり約数を小さい方から順にチェックする必要がある。

実装(C++)

裏紙

ほぼ競プロ、たまに日記

CF 958 E3 - Guard Duty (hard)

問題

問題概要

アイデア

実装(C++)

AOJ 2720 - Identity Function

問題

問題概要

アイデア

実装(C++)