読者です 読者をやめる 読者になる 読者になる

SRM 581 Div2 Medium SurveillanceSystem

問題

SRM 581 - TopCoder Wiki

倉庫にコンテナが一列のセグメント上に並べてあって,カメラで監視している. カメラはLセグメント分だけ監視できていて,カメラ同士は同じポジションにいない. カメラがどこに配置されているかわからないが,コンテナの位置と,カメラが見ているコンテナの数は分かる. この時,カメラがある位置について確定なら'+'を可能性としてあり得るなら'?',そうでないなら'-'で表して返す.

解答

ややこしい. コンテストの結果も,正解者がとても少ない.

  • 各位置について,もしここにあったらコンテナはいくつ見えるかという計算をする
  • これで,あるコンテナの数を答えるカメラの台数が分かる
  • 見えているコンテナの数がxだと答えるカメラについて見えている位置について+1する.
  • そうすると,各位置についてどれだけ重複しているのか分かる.
  • もし,カメラの数から重複している数を引いた数が,入力でコンテナの数がxと答えるカメラの数より小さかった場合.必ずその位置はカメラに映ることになる.
  • そうでなくて1以上ならば見える可能性がある,0の場合その可能性は絶対にない.
  • 同様のことを取りうるコンテナの数毎に計算する
using namespace std;

class SurveillanceSystem
{
public:
  string getContainerInfo(string containers, vector <int> reports, int L)
    {
      int n = containers.size();
      vector<int> camera = vector<int>(L+1, 0);
      vector<int> num = vector<int>(L+1, 0);
      int i, j, l;
      for(i = 0; i < reports.size(); i++) camera[reports[i]]++;
      vector<vector<int> >count = vector<vector<int> >(L+1, vector<int>(n, 0));
      for(i = 0; i < n - L + 1; i++) {
        int c = 0;
        for(l = 0; l < L; l++) {
          if (containers[i+l] == 'X') c++;
        }
        num[c]++;
        for(l = 0; l < L; l++) {
          count[c][i+l]++;
        }
      }
      vector<char> res = vector<char>(n, '-');
      for (i = 0; i <= L; i++) {
        if (camera[i] > 0){
          for(j = 0; j < n; j++){
            if (num[i] - count[i][j] < camera[i]) {
              res[j] = '+';
            }else if (count[i][j] > 0){
              if (res[j] != '+') {
                res[j] = '?';
              }
            }
          }
        }
      }
      return string(res.begin(), res.end());
    }
};