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

naoya_t@hatenablog

いわゆるチラシノウラであります

SRM581

TopCoder Single Round Match Practice Room 過去問探訪

朝、起き抜けにやってみた

Easy ("SurveillanceSystem", 250)

鳩ノ巣原理みたいなやつ。なんか時間かかった

答え合わないなー、問題文に読み落としてる制約とかあるのかなー、
と思ってうんうん唸ってた

朝食後に見直したらExpected:とReceived:を逆に解釈してた。脳にブドウ糖重要。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>

using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

class SurveillanceSystem {
 public:
  string getContainerInfo(string containers, vector<int> reports, int L) {
    int N = sz(containers);
    vector<int> xs(N);
    rep(i, N) xs[i] = (containers[i] == 'X') ? 1 : 0;

    int P = N - (L-1);
    vector<int> cnt(P, 0); // cnt[i] = 位置iからのLセクタにいくつコンテナがあるか
    int c = 0; rep(i, L) c += xs[i];
    rep(i, P){
      cnt[i] = c0;
      if (i==P-1) break;
      c = c - xs[i] + xs[i+L];
    }

    map<int,vector<int> > cams; // cams[c] = コンテナがc個見える位置をすべて保持
    rep(i, P){
      int c = cnt[i];
      cams[c].pb(i);
    }

    map<int,int> reps; // reps[c] = c個のコンテナが見えているカメラの数
    tr(reports, it) ++reps[*it];

    vector<int> wd(N, 0), pd(N, 0); // +になるセクタ, ?になるセクタ

    tr(cams, it){
      int c = it->first;
      vector<int> v = it->second;
      int s = sz(v);

      int repc = reps[c];
      if (repc == 0) continue;

      vector<int> tmp(N, 0);
      // 4箇所のために4人いる -> 1で十分
      //              3          2
      //              2          3?
      int lim = s; //箇所
      int mq = s - repc; // 不足
      lim = mq+1;

      if (repc == s) {
        tr(v, jt) {
          rep(k, L) wd[*jt+k]++;
        }
      } else {
        tr(v, jt) {
          rep(k, L) tmp[*jt+k]++;
        }
        rep(i, N) {
          if (!tmp[i]) continue;
          if (tmp[i] >= lim) wd[i]++;
          else pd[i]++;
        }
      }
    }

    vector<char> ans(N, '-');
    rep(i, N) if (pd[i]) ans[i] = '?';
    rep(i, N) if (wd[i]) ans[i] = '+';
    return string(all(ans));
  }
};