ある点から到達できる点のグループは、グループ内のどの点から出発しても同じグループに到達できる。
なので、Union-Find(Disjoint Set Union)を使えばよさそう。
ただ問題は、行き来できる点をどのように見つければよいか。
各点から、他の点が移動できる点かどうかを全て確かめていては $O(N^2)$ で無理。
$x,y$ 座標が大きい点の方から、小さい方向に移動できる点を探す。
↙● ● ● ↙● ● ↙ ● ● x 1234567
まず点を $x$ 座標でソートし、その順に、該当する点を探していく。
自分より後に処理される点は、当然 $x$ 座標が大きいので、該当する点ではあり得ない。
自分より前に処理された中で、$y$ 座標が小さい点に対して、Uniteすればよい。
これは、std::set
やFenwick Tree などで管理できる。
ただ、この方法も、以下のようなケースではUniteする対象がどんどん増え、結局 $O(N^2)$ かかってしまう。
... ● ● ● ● ● x 1234567
$x=5$ まで処理された時点では、$x=1~4$ の点は既にUniteされているので、5から辺を張りに行くのはどれか1点でよい。
そう考えると、一番左下の点のみ残しておけばいい具合に無駄を減らせそう。
「$x$ 座標も $y$ 座標も自分より小さい点が無い点」のみをFenwickTreeに登録し、探索対象とする。
その点がハブとなってくれて、Uniteされるグループは正しいまま、探す対象が少なくなる。
・ ● ● ・ ● ● ● x 1234567
(Pythonでは std::set
が無いから代用とは言え)
いきなりA問題から FenwickTreeとUnionFindの合わせ技が出てくるのは飛ばしてるなあ、と思ったけど、
実は使わなくても解ける方法があるらしい。先入観よ。
シンプルですごい。
まずパッと見、$(1+2+...+k)=\dfrac{k(k+1)}{2}$ と式変形できる。
よって、「$k(k+1)$ が $2N$ の倍数となる」と言い換えられるのだが、
ここで重要なのは $k$ と $k+1$ は互いに素であるということ。
つまり、$2N$ が $2^a3^b5^c$ などと素因数分解されたとして、$k$ と $k+1$ の両方に2や3が素因数として入ることは無い。
$2^a$ も $3^b$ も $5^c$ も、それぞれ $k$ と $k+1$ のどちらかに全入れしなければならない。
素因数のユニークな個数なんて、素数を小さい方からかけていってもまぁ15個もしない内に $10^{15}$ を越えるので、 たかだか15個の数についてどっちに入れるか、$2^{15}$ 通り試すのは十分可能である。
さて、$k$ が $A=2^a5^c$ の倍数、$k+1$ が $B=3^b$ の倍数と割り振ったとして、これについての答えを求める。
(ここでの割り振りは一例であって、重要ではない)
中国剰余定理の考え方を使って、以下のように求められる。
$k+1=Bm$($m$:整数)と表すとして、これを $k \equiv 0 \mod{A}$ に代入すると、$Bm \equiv 1 \mod{A}$ となる。
ここで、$A$ と $B$ は互いに素なので、$B$ は逆元 $B^{-1}$ を持つ。これを使えば $m \equiv B^{-1} \mod{A}$ となり、 $m$ は、$B^{-1}$ をベースとして、それに $A$ の倍数を足し引きした数に絞られる。
正整数の中での最小値を求めたいので、$0 \le m \lt A$ である $m$ を使って $k+1$ を求めればよい。
ただし、$A=1$ や $B=1$ の場合は、うまく逆元を計算できない(というか、何でもよい)ので、個別に考える。
$A=1$ の時、$k \equiv 0 \mod{1}$ かつ $k+1 \equiv 0 \mod{2N}$ である。よって、$k=2N-1$ が最小となる。
$B=1$ も同様に考えると、$k=2N$ となる。
.
が空きマスo
がコマ(複数個あり得る)#
が壁どのコマをどのマスで終わらせるか、の組み合わせで最小費用流。
各コマは右も下も外周か #
のマス(以降、「行き止まりマス」)のいずれかを目指すんだけど、
同じマスを目指すコマが複数あると、1つ以外は手前で止まって移動回数を減らさざるを得ない。
最終状態は、行き止まりマスの多くにはコマが置かれ、その周辺にも溢れたコマが密集している形となる。
その「周辺」がたとえば1本道だと、ちょっとのコマが集まっただけで詰まってしまい、より手前で止まらねばならず、移動回数の損失は大きくなる。
一方、周辺が開けていると、多くのコマが集まっても比較的、損失の増え方は小さい。
はじめ「コマ と 目指す行き止まりマス」の対応を考えたが、それだとこの違いを上手く吸収できない。
「コマ と 最終的なマス」の対応を考えることで、1対1のマッチングを求めればよくなり、最小費用流に持ち込める。
o
の数だけ)、各マス($N \times M$)、の分だけ頂点を作る
最大スコアを最小費用流によって求めたいときは、正負を逆転させれば使えるようになる。
これで始点から終点に、コマの個数分の流量を流したときの最小費用を求めれば、それが答えとなる。
負辺ができてしまうが、始点から終点への全ての経路で負辺(コマ→マスに張られる辺)を通るのは1回固定なので、適当に下駄を履かせておけばよい。
ところで、この方針ではコマ同士の、途中経路での衝突が考慮されていない。
「あるコマから到達できるマスであっても、他のコマを考慮すると邪魔されて動けなくなることはないか?」という点が気になる。
初期状態 最終状態 このような実際は不可能な ①②.... → ....②① マッチングが発生してしまう
が、衝突する場合はマッチング結果の対応を入れ替えると解消でき、総移動回数は変わらないので問題ない。
適宜入れ替えれば問題ない、ということが言えたので、実際に矛盾しないマッチングを求める必要は無い。
コマ1つ1つについて各マスへのコストを求めなくても、 通常のグリッド問題のように、隣接するマスにコスト $-1$ の辺を張る方法でも、最小費用流が可能である。
そうすると各コマで辺を共有できるので、高速になる。
ただ、その場合、負辺を防ぐために下駄を履かせたくても、各コマによって負辺を通る回数が違う=足される下駄の回数が異なるので、正しく求められない。
以下のように考えると下駄の回数を統一した上で辺を非負にできる。
これは、以下のように実装する。