AtCoder Regular Contest 076

AtCoder Regular Contest 076

Source codes

• My submissions (AtCoder)
• My source codes (GitHub)

Solutions

C - Reconciled?

$\lvert N - M \rvert \leq 1$ でないと交互に並べようがない。 $\lvert N - M \rvert = 1$ の時は犬猿の並べる順番も決まるので $N! M!$ 通り。 $\lvert N - M \rvert = 0$ の時は犬猿の並べる順番は $2$ 通りあるゆえ $2 N! M!$ 通り。

ポイント

$\mathrm{mod}~ p$ での階乗、組合せ数、逆数はライブラリを貼る。

D - Built?

クラスカル法を使用することを前提に考察する。まず座標 $(a, b)$ と $(c, d)$ の道は、コスト $\lvert a - c \rvert$ 、 $\lvert b - d \rvert$ の両方の辺を張って良い。正解において、この $2$ つの頂点を仮に使用するとすれば、クラスカル法のアルゴリズムにより、小さい方が使用される。つまりコスト $\min(\lvert a - c \rvert, \lvert b - d \rvert)$ の辺が張られ、問題文の操作と一致する。

さて、全ての辺を張ると $O(N^2)$ 個の辺を張ることになる。これは持っておけないので、辺の数を減らす必要がある。クラスカル法のアルゴリズムを思い出すと、 「使われないことがわかっているコストの大きな辺」は削除して良い ことになる。だから、$x$ 軸、$y$ 軸で並べて、隣にくる点同士を繋げて、それだけを辺と見なせば良い。

このことを非自明と思う人もいるだろうし、自明だと思う人もいるだろう。私は最初は非自明だと思ったので証明を考察した：ここで追加した辺以外の辺 $(u, v, c_0)$ を用いたと仮定する。すると、定義より、その$2$点の間には、 $x$ 軸あるいは $y$ 軸で見たときに別の点 $w$ があるはずである。辺の張り方により、$(u, w, c_1)$、$(w, v, c_2)$ に対し $c_0 > c_1, c_2$ が成立する。クラスカル法のアルゴリズムにより、 $(u, v, c_0)$ よりも $(u, w, c_1)$、$(w, v, c_2)$ の方が検討される。 $(u, v, c_0)$ を採用したということは、それより前には $u, v$ を含む木は繋がっていなかったことになる。しかし $(u, w, c_1)$、$(w, v, c_2)$ を両方検討した段階で、 $u, w, v$ は繋がっているはずである。これは矛盾である。したがって仮定が間違っていて、クラスカル法では上で書いた辺だけ使用される。

まぁここまで論理的に考えなくても「$x$, $y$ 軸で見て、近くだけ繋げばいいだろ」とやってしまうのが簡単だと思う。

ポイント

クラスカル法は、重みの少ない辺をできるだけ用いて、「$1$ 頂点からなる木」からなる森を「$1$ 本の木」にする方法である。だから通常は UnionFind を用いる。 そこを失念していた。$N$ 頂点なら $N-1$ 本の辺を使用する。

問題が $1$ 次元ならどうするか？ を考えると後半に気付きやすいと思う。

E - Connected?

少し検討すればわかる通り、問題となる曲線は、盤面の境界上にある $2$ 点を結ぶ曲線である。それ以外のは問題とならない。このことには、与えられる全ての点が異なることも関係している。

さて問題は、クロスすることをどのように言い換えるかである。普通に、外積を使った交点を持つ条件判定やると $O(N^2)$ で間に合わない。試行錯誤して検討していった結果、 盤面の境界をぐるっと $1$ 周したときに、たすき掛けのように数字が出てこないこと が条件である。たすき掛けとは、 $1, 2, 3, 3, 1, 2$ のようなものである。 $i$ が出てきた後から $i$ が出てくるまでに出てきた数字は、必ず $2$ 回(または $0$ 回)出てきていて $1$ 回ではない。このことは stack を使えばシミュレーションできる。

ポイント

自然と思いついた。周をぐるっとするための新しい座標を、サブルーチン化して丁寧に求めた。

F - Exhausted?

まず、右側の条件を忘れて答えよう。つまり $R_i = M+1$ ($i \in [0, N)$) だと仮定しよう。この場合は $L_i$ が小さい方から順番に並べて、左側の椅子から貪欲に割り当てるのが最善であることがわかる。

$R_i$ の条件も加味しよう。基本的には今言った通りのアルゴリズムを実行するが、椅子が割り当てられなかった瞬間の処理がポイントとなる。この時、 今まで検討してきた中で $1$ 人には必ず外れてもらわなければならない 。では誰を外そうか。 今まで検討してきた中で一番 $R_i$ が小さいものに外れてもらうのが最も得をする 。この 2 つの事実から以下が従う：これを繰り返せば、右側の椅子を右側からできるだけ多く使うことができ、残った人も左側から椅子を取る上で最も有利な形で残っている状態になる。この状態で、残った人、残った椅子を左右反転させれば、上記の状態に帰着する。こうして問題が解ける。

実装をする。まず tuple で $(L_i, R_i)$ を昇順でならべかえる。 1 つずつ見ていき、 1 番から順番に椅子を割り当てる。割り当てられなかった時のために、全ての $R_i$ を昇順の priority_queue $Q$ に入れていく。割り当てられなかった人が出てきたら、 $Q$ から $1$ 個取り出して vector $W$ に入れる。「残った人の反転動作」として $W$ を「反転動作」する。ただし「残った椅子」の反転動作も考慮して、

  for (auto it = W.begin(); it != W.end(); ++it) {
    *it = min(M+1 - ind, M+1 - *it);
  }
  sort(W.begin(), W.end());

のように $\min$ を取るがポイントである。あとは貪欲に割り当てる。

ポイント

寝る前に思いついた方法で正解だったが、眠かったので寝た。 以下、間違えたところ。

• 「全ての $R_i$ を昇順の priority_queue $Q$ に入れていく」ところ。折られたやつしか入れてなかった。これは実装ミスに近い。
• 「『残った椅子』の反転動作も考慮 して、$\min$ を取るがポイント」のところ。寝る前には気が付いていたんだけど、起きたあと失念していた。気づいたのは 40.txt で落ちていたところで、その内容は、以下だった。

4 3
0 1
1 2
2 3
3 4

もちろん答えは 1 だが、椅子の反転も考慮していないと 0 になってしまう。

テストケースは全てここで公開されている。全てと言いつつ欠けもある気もする。例えば DDCC とかはない。

Others

このコンテストは、条件が良心的で教育的であったように思う。 E は同じ点が与えられるのを許しても作れるのにそうしなかった。 F は最初から座標圧縮がなされている。 こうすることで、私のスピードでもそこそこ解けたようだ。