Codeforces Round #605 (Div. 3) - E.Nearest Opposite Parity - Senの競技プログラミング備忘録

概要

長さnの数列が与えられる。それぞれの要素a_i(1 <= a_i <= n)である。場所iにいるとき、i - a_iの場所とi + a_iの場所へ飛ぶことができる。ただし、とんだ先が[1, n]に含まれてる必要がある。
さて、すべての1 <= i <= nについて、iから(a_i % 2) != (a_j % 2)となるようなjへ飛ぶ最小の手数を答えよ。不能なら"-1"と出力せよ。

制約：1 <= n <= 2 * 10^5

ACするまで

1. グラフっぽいなぁー。辺を張る
2. スタートごとに探索し始めると計算量的につらい。どうしよう。
3. コンテスト時間切れの壁

4. いくつかの始点(終点)を持つタイプは、逆からたどれ！逆からダイクストラをする。
5. よくよく考えるとすべての辺のコストは1固定、ダイクストラをする必要すらなく、BFSすれば解ける。
6. AC!

考察

この問題、それぞれの点から遷移できるのは、一定ではなくa_i依存なので、グラフをまず張ってみる。
i番目からj番目へ行けることで、頂点i -> 頂点jにコスト1の辺を張る。
この時、愚直に最短路問題を解くことを考える。
始点1つごとに最短路問題を解き、その計算量は $O(N log N)$ (ダイクストラなら)、すべてのコストが1であることに気づいてもBFSをすることで $O(N)$ になる。(最短路問題は、すべての辺のコストが一定ならば、BFSで $O(N)$ でできる)これだと、全体計算量は $O(N^2 log N)$ か $O(N^2)$ になり、TLEする。

しかし、この問題では次の構造をもってる。

始点(終点)、今回は終点だがが複数個存在し、そのうちのいずれかへの最小距離が答え

このタイプの問題は、始点が複数個持っているのならば、複数個の始点をpriority_queueに入れてダイクストラでもすればよい。終点を複数個持っているのならば、辺を逆にして、終点を始点とみなしてダイクストラをすればよい。
このような操作をすると、愚直にやるとき、毎回の最短路問題では計算しなおす必要があったが、これは再利用しながら計算することができるため、オーダーが一つ落ちる。

先ほどはpriority_queueといったが、今回の問題はすべての辺のコストが一定なので、BFSをすればよい。

先ほどの考えで $O(N)$ かけて始点を試す必要がなくなり、 $O(N)$ で多始点最短経路問題(コスト1限定)が解けるので、 $O(N^2)$ から $O(N)$ の計算量になり、問題が解ける。

以下のソースコードでは、あらかじめ終点を全部queueに入れてBFSしてる。この時、queueに入れる情報として、「どこの頂点にいるか」と「スタートのバイナリ」である。

ACソースコード：
Submission #66773304 - Codeforces

また、始点を一気に全部入れるのではなく、1つ1つ試して始点にして最短路を計算することでも上の目的は達成できる。しかしこの場合は計算する回数がよりかさみ遅くなる。実際、上のコードは327msに対して、下は1000msオーバーである。
ACソースコード：
Submission #66762521 - Codeforces

一言

こういう問題をあぶりだせてるのでコドフォっていいなぁ。