kojingharangの日記

SRM 581 Div1 250 SurveillanceSystem (追記)

23:03 |

• 連続した N 個の区画があって各区画に荷物が最大 1 個入っている。
• 連続した L 個の区画を監視できるカメラがいくつかあって、各カメラが観測した荷物の個数が与えられる。
• 各カメラが監視する範囲は重複しない。
• 各区画について、確実に監視されているなら '+', 確実に監視されていないなら '-', 監視されている可能性があるなら '?', のどれかを求める問題。
• N≦50, 1≦L≦N

• カメラが観測した箱の数→その個数 と集計しておく
• 観測した数が異なればその候補の区間も異なるので、観測した箱の数ごとに独立に考える。

• 候補の区間全てについて区間に含まれる箱のとこを+1していくと、...
• ある箱が何回使われたか分かる。
• カメラの個数＞カメラの位置候補数-箱が使われた回数 なら、その箱を避けることはできないので + にする。
• そうでなくて1回でも使われてたら - だった場合に限り ? にする。

X---X-- {2,2} L=3の場合
1コのカメラの置き方の候補は4通り
ooo----
--ooo--
---ooo-
----ooo
1122321

（Naiveなやり方）
実際には{2,2}なので2コのカメラを置く必要がある。
置き方は4C2通り
ooooo--
oooooo-
ooo-ooo
--oooo-
--ooooo
---oooo
結果
????+??

...なんだけど、上記の方法だと40C20通りとかになる場合があって終わらない。

（工夫すると）
1コのカメラの置き方の候補からなんとかする。
ooo----
--ooo--
---ooo-
----ooo
1122321

4通りから異なる2個を選べばいい
→どう選んでも3のとこは1個以上のカメラに使われる＝監視されるので +
→2以下のとこは適切な選び方をすると監視されるようにもされないようにできるので ?
なので
????+??
みたいな

• accepted
• ↓簡潔にした版(passed in practice room)

class SurveillanceSystem {
	public:
	string getContainerInfo(string C, vector <int> R, int L) {
		map<int, int> hi;
		int N=C.size();
		string ans(N, '-');
		REP(i, R.size()) hi[R[i]]++;
		FOR(e, hi) {
			int match=0;
			VI w(N);
			REP(i, N-L+1) {
				if(count(&C[i], &C[i+L], 'X')==e->first) {
					match++;
					REP(j, L) w[i+j]++;
				}
			}
			REP(i, N) {
				if(w[i]>=match-(e->second-1)) ans[i]='+';
				else if(w[i]>0 && ans[i]!='+') ans[i]='?';
			}
		}
		return ans;
	}
};

ツイートする