Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【AGC002-C Knot Puzzle】典型的誤解法の反例

C - Knot Puzzle

この問題を間違えましたが、自分の解答がどう間違ってるか反例を見つけるのに時間がかかりました。他の人の解答を見ても、同じように間違えてる人が多いですから、これを共有します。

問題

ロープがN本繋いである。長さL以上連続していればその中の任意の結び目で切ることが出来る。最終的にバラバラにすることは出来るか?出来るなら順番を示せ。

正しい方針

最終状態を考えると、2つ並んだロープの和がL以上になっている。そして、そこがLである以上、そこから左と右は順に外側からとってしまっていく手が、常に長さL以上を満たすことが出来る(最後の2本を含むから)。このような順でロープを切ればよい。

典型的誤方針

一番左と一番右のロープを見て、小さい方から切っていく。小さい方から切っていって残りがLを下回るようなことがあればだめ。

この方針だと7つWAします。

反例

a, b, c, dと並んでいるとします。

そして、c < a < d < bとして、a+bがぎりぎりLであるとします。

誤方針では、最後に残るのはbとcですが、a+bがぎりぎりLなので、これはLより小さいです。従って死にます。

想定解法だとa+bをまず確保して、d,cと落としていくので、バラバラにすることが出来ます。