一時間
■問題 SRM567 Div1 Easy "PenguinSledding"
グラフが渡された時、二次元空間上にどのようにマッピングしても（vertexをどこに置いても）edgeが重なる事の無いように、edgeを消したい。
何パターンありえるか？
要は、有効な形は意外と少なく、「edgeなし」「edge一本だけ」「あるvertexから星形にedgeが出ている」だけ。
（実はこれは間違いで、三角形というパターンもあった）
なのでこれらを一つ一つ数えるだけ。
1st submit:
自分に設けた１時間の時間制限を超えたため、最後のsampleが間違っていたもののsubmit。
単純な、1,{1,2,3},{2,3,1}ケースを間違えていたことで三角形のパターンもあると気づいた。
2nd submit:
OK
■Editorial
チラ見しかしてないが、大体同じ解き方。
自分がΣ[2<=i<=n] nCi みたいな計算をわざわざしていたところを(2^n)として計算していて愕然とした。なるほど。
■反省
・今回は、優しいsample caseに救われた（結局駄目だったけど）
→L字型だけ考えればいいのかと思ったら＊型もあることにsample3で気づく
→かと思いきや、三角形のケースが含まれるsampleにつまずく
・ここまで優しいsampleが用意されている問題は少ないが、どうしたら網羅的に考えられたんだろう？
■筋トレ記録
勝率50% (3/6)
0 件のコメント:
コメントを投稿