キーエンス プログラミング コンテスト 2020 参加記 + E-Bichromization 解法

やってしまった！Eから解いてWAが出たので茶パフォでした！

しかし、Eの方針に間違いはなくコンテスト後通せました！

レートは大きく下がりましたが変な解き方をしているのが悪いですね。

よく後ろから解くのですが、これは後ろの問題にどうしても惹かれてしまうという性格の問題で戦略的なものではないですし、このままと思います。

900点問題はまだ本番で通せたことがないので解けそうになっただけでも嬉しいですね。

昨年末から沢山問題解いているので成績爆発がどこかのタイミングで来ればなあと思っています。

終了後Dも解いてみましたが難しいですね。解法を見た後も実装に苦戦して数時間かかってしまいました。

せっかくなので自分のE Bichromization解法を晒しました。（嘘があったら恥ずかしいですが）

まず、一番小さいD[v]であるようなvに注目しました。

vと違う色で最短距離にあるuはどのようの性質を持つでしょうか。

まず題意よりv-uの距離はD[v]です。ということはuからみた違う色で最短距離の頂点を考えるとD[u]<=D[v]が成り立ちます。D[v] は最小なのでD[u] = D[v]となります。

また、uとvは隣接している必要があります。

なぜなら最短経路上に他の頂点があるとその頂点と違う色のu or vとの距離がD[v]より小さくなってしまうので矛盾するからです。

ということでD[u] = min(D[v])となるような頂点集合で互いに連結している辺の長さをmin(D[v])とすれば各uに対して条件を満たすようです。

uに隣接している頂点の中にu'=min(D[v])となるu'が存在しなければ諦めましょう。-1出力します。

次にmin(D[v])より１つ大きいD[v]=D2に注目します。

D[v]=D2となる頂点vと最短距離にあり違う色であるuは、D[u]<D2を満たします。先ほどと同じように考えるとvと隣接しているD[u] = min(D[v]) or D2となるuの間の辺をD2にすれば問題ありません。

vに隣接している頂点の中にD[u]<=D2となるuがなければ諦めます。

以上のことをD[v]の小さい順にやっていきます。各頂点vに対して隣接する頂点uでD[u]<D[v]となっているものに重みD[v]の辺を張るのみです。

これに並行して色も適当につければOKです。

上記でD[v]でソートしてD[v]の小さいvから処理をしていったのですが、vからD[v]=D[u]となるuに対してdfsしながら順に親と違う色になるように色をつけていくのです。根であるvは適当に塗って大丈夫です。例外としてvに対してD[u]<=D[v]となるuが全てD[u]<D[v]でかつ同じ色のときはvの色をuと逆にしないといけないです。

ちなみに本番中のWAは色付けでした。同じD[v]で連結しているときに適当に塗ると例えば、1-2-3-4で1,3で違う色を塗ってしまって2が塗れなくなるという事態が起こっていました。