URL
https://community.topcoder.com/stat?c=problem_statement&pm=13846&rd=16548
概略
$R \times C$ のマス全てをちょうど $K$ 回だけ通るような一筆書きの経路は存在するか？
方針
$K = 1$ で巡回路が作れれば，$K > 1$ についても構築可能です．巡回できないケースは $R$ と $C$ の両方が奇数の場合のみです．これが真に構築不能であることの証明ができなかったので参考リンクを貼っておきます．
- 巡回路ができないことの証明
- 構築不能であることの証明
[展開する]
反省
そこそこ自信はあったが証明はできていないので，本番ですぐに提出できるかは微妙．
Tweet comments powered by Disqus