hotpepsiの練習帳

SRM 581

23:05

Div1 Easy (250) SurveillanceSystem

問題

• N個の区画に分割された倉庫があり、そこからコンテナを盗み出したい
• 何台かの監視カメラが設置されている
• コンテナがある位置と、監視カメラが監視しているコンテナの数が与えられる
• カメラの位置は全て異なる
• 各区画の監視状態を求める

方針

• 位置毎に試す
• だめぽ
• (終了後)
• kojingharangさんのを読む
• 置かれる可能性のある場所について+1していく
• A台監視するカメラがB台あり、その場所の候補の個数をCとする
• 置かれる可能性のある場所の個数が全部でC個しかない場合は全て確定(監視されている)
• B-1台のカメラが設置済だとして、残りの候補地は(C-(B-1))通りある
• このとき、C-B+1通り以上設置される可能性のある場所は確定
• そのほか、1回でも置かれる可能性のある場所は?に設定
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_581/SurveillanceSystem.cpp

結果

--- 0pt 1299 -> 1265 (-34)

難しかった。この問題は何系なのだろう。判定系?