CODE FESTIVAL 2017 qual B：C - 3 Steps(500)
問題
https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_c
考え方
距離 の頂点間に辺を張ることでもともとの距離が
縮まる。よって、もともとの頂点間のパスの長さが奇数長である頂点間の距離を
にすることができ、任意の奇数長の頂点間に辺を張ることができる。
もともとのグラフに奇サイクルが存在する場合、奇サイクル上の頂点を利用して任意の頂点間に辺を張ることができる。これは editorial のとおりだが、任意の頂点の組 、
を奇サイクル上の頂点とすると
という順に頂点を訪問するパスが存在する。このパスの長さが偶数であった場合は奇サイクル上の点を用いて長さ
だけ迂回して
に訪問することができ、よって奇数長のパスとすることができるためである。
「グラフが奇サイクルを持たない 二部グラフ」という性質から、もとのグラフが二部グラフであるかどうかが重要である。もとのグラフが二部グラフである場合は、完全二部グラフにできる。そうでない場合は完全グラフにすることができる。
Submission #4050374 - CODE FESTIVAL 2017 qual B
どこに着目して考察するべきだったか
距離 の頂点間に辺を張るという操作によってどんなことができるのか考える必要がある。この場合は距離を
縮めることができるので距離が奇数の頂点間の距離を
にできるということに気づくことが重要な気がする。
何がバグっていたか
得た知見(典型ポイント)
- グラフが奇サイクルを持たない
二部グラフ
- 奇サイクルをもつ場合は、奇サイクル上の頂点を用いると頂点間のパスの長さを偶数にすることもできるし、奇数にすることもできるというイメージ