$1$ から $N$ までの整数の番号がついた、男または女の生徒が合計 $N$ 人おり、 $N$ 人にはそれぞれ「ペアになりたい人」が $1$ 人いる。 $i$ 番目の人の 「ペアになりたい人」は、 $F_i$ 番目の人である。
但し、 $A$ さんの「ペアになりたい人」が $B$ さんだとして、 $B$ さんの「ペアになりたい人」が必ずしも $A$ さんであるとは限らない。
性別についての情報は数列 $S$ で与えられ、 $S_i=1$ ならば $i$ 番目の人は男、 $S_i=2$ ならば $i$ 番目の人は女である。
この $N$ 人について、以下の条件を満たすようなペアリングする。
- $A$ さんと $B$ さんがペアになっている場合、以下の条件の少なくとも一方を満たす。
- $A$ さんの「ペアになりたい人」は、 $B$ さんである。
- $B$ さんの「ペアになりたい人」は、 $A$ さんである。
- ペアの数が、可能な最大数である。 このようなペアリングが複数考えられる場合、異性同士のペアの数が最大である。
このようなペアリングについて、「ペアの数」「異性同士のペアの数」を求めたうえで、ペアリングを $1$ つ構築せよ。
制約
- $2 \le N \le 10^5$
- $i \neq F_i (1 \le i \le N)$
サンプル
in
5
5 2
3 2
5 1
2 1
4 2
out
2 2
5 3
4 2
サンプル画像
太線が、出力に対応するペアリング
(JOIっぽい問題な気がしたので、せっかくなので小課題をつけておきます。)
条件 $\alpha$ : 頂点 $1,2,...,N$ からなり、全ての整数 $1\le i \le N$ について、辺 $( i - F_i )$ のみを含んだ無向グラフが、連結である。
小課題1(4点) : $N \le 16$
小課題2(8点) : $N \le 3000$ かつ条件 $\alpha$ を満たす。
小課題3(12点) : $S_i=1 (1 \le i \le N)\ ,\ F_1=2\ ,\ F_2=1$かつ条件 $\alpha$ を満たす。
小課題4(20点) : 条件 $\alpha$ を満たす。
小課題5(20点) : ペアリングを復元しなくてよい。
小課題6(36点) : 追加の制約はない。
とりあえず、 $N$ 頂点 $N$ 辺のマッチングであることはわかる。
$N$ 頂点 $N$ 辺、ということは、(連結成分ごとに)環がちょうどひとつある。
環のうち、ある頂点 $x$ を決めると、$x$ につながる環の辺のうちどちらか一方は確実にいらないので、木を $2$ 通り試せばよさそう。
木に問題が帰着できれば、あとは
dp[頂点 $v$][ $v$ の使用済みフラグ] = make_pair(ペアの数,異性ペアの数)
をしてやればよさそう。
う～～～～ん、実装が、地獄!!!!!
やることを整理します
- 入力を受け取る
- グラフを連結成分ごとにバラす
- 連結成分内の環を検出し、木を $2$ 通り作る。
- 木DPをする
- 木DPの復元をする
強 実 装 確 定 演 出
です。対戦ありがとうございました。今回の記事は終わりにしたいと思いm(
今回は、この強実装、魂の216行を行うにあたって、気をつけたことをまとめていきたいと思います。
<グラフを連結成分ごとにバラす部分>
ここは、UFを使ってやればよいでしょう。僕は、DeComp()で連結な頂点集合の集合を求める実装にしました。
<連結成分内の環を検出し、木を $2$ 通り作る部分>
ここは、solve(部分集合)で連結成分ごとに問題を解く実装です。
とりあえず、頂点番号が $0,1,...,($部分集合のサイズ-1$)$ の木に置き換えることを考えます。番号の付け替え自体は (unordered_)map でやってやればokです。
環を検出するパートが最初の山でしょうか。グラフから葉をどんどん取り除いて環に含まれる頂点が検出される実装にしたのですが、ここで、「除去する辺は環の中に含まれるある同じ頂点に繋がる $2$ 通り」でないとマッチングが壊れることに注意して実装します。ここが壊れていると最大マッチングが正しく求まらない可能性があります。
<木DPとその復元をする部分>
dp[頂点 $v$][ $v$ の使用済みフラグ] = make_pair(ペアの数,異性ペアの数)
をします。(僕の実装だとkey2つを $2 \times v+(0/1)$ として1つにしています)
僕の今回の木DPの実装は、最初に頂点 $0$ からDFSをやって探索順を帰りがけ順として確定させ、探索順によって親子を区別するようなやり方です。
木DPの詳細については、実装を参照してください。( $v$ をマッチングに使用せず、使用済みフラグを立てるだけの方が最善であるような場合の遷移も忘れずに。)
復元について、復元は先ほど前もって決めた探索順を逆にたどっていきます。
木DPの探索順を順向きにたどっているときに、 rest[頂点 $v$] = {$v$ であれば、最善ケースは $v$ をマッチングに使用しないのが最善、そうでなければ $v$ とペアにするべき頂点番号が格納されている} として、最善の結果を格納していきます。
探索順を逆向きに辿っていきながら、まだ頂点 $v$ と rest[ $v$ ] の双方が相異なり、かつ双方ともに未使用である場合、この両者を使用済みにして、ペアとして記録します。以上で復元は可能です。
僕はここまですべてを丁寧にやって、3WAしました。
<おまけ : もし JOI だったら & 小課題解説>
JOIだったら難易度いくつ付くんだろうな、11弱くらいになりそうだけどこれが10だとしたら相当恐ろしい時代だなこれ… 代表レースに加わるなら落としたくないところか。(解法ができても、デバッグが壊滅的にしんどそう…)
小課題1 : bitDPなり適当に焼くなり、お好きにどうぞ
小課題2 : 消す辺を全探索可能。
小課題3 : 木の最大マッチングなので貪欲でいけます、ここを参照。
小課題4 : 全体が連結なので、「消す辺を2通り試して木DP」だけ書けばok。
小課題5 : 復元がバグっててもok。デバッグのヒント。
小課題6 :
もう二度と実装したくねぇ…
