beet's soil

競プロのことなど

AGC017 - E Jigsaw

自分用メモ

O(N N!)が自明なのでオーダーを落とす問題
ピースを頂点としてみると適切に辺を張った時に有向ハミルトンパスが存在するかという問題に帰着できる
ハミルトンパスはNP-completeなので相当強い性質がないと無理そう

Hが小さいのがなんかありそうだったけどなかった(つらい)

自明な場合分けを考えているといくつかのパス+いくつかの閉路に分割できそうなことがわかる
パスは1本しかダメだと思っていたがサンプルをみると複数でもいいことがわかる
パスに閉路を貪欲にくっつける解法が生えたので帰納法をすると正しそうな雰囲気を感じる→WA
ループにループをくっつけるケースが抜けていた→AC

結局ピースを辺としたオイラー路を求めることをしていた 面白い
合計3時間くらいかかったので本番だときついなあ 
この辺の難易度の速解き、どうすればいいのかわからず(そもそも数をこなせるほどないし)