AtCoder Beginner Contest 117

atcoder.jp

C問題は最適の場合は複数のピースが重なることもないし、来た道を戻ることもないということが分かる。そうすると各ピースに閉区間（始点と終点が同じ場所でも良い）を割り当てれば良いということになる。割り当てられた閉区間の合計の長さが短くなれば良いので、区間の長さをソートして長いほうからN-1個の区間は通らないということにすれば良い。考察を丁寧にしたので、12分くらいかかった。

D問題。実装するだけなのだが、なぜかopen caseは全部通ったのにhidden caseは全部WAになった。これの原因が分からなくてやめてしまったのだが、後から見てみたら意味不明なミスをしていた。説明が難しいが、全くもって非本質的なミスだった。こういうことをコンテストでしないようにしたい。