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

naoya_t@hatenablog

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

2014 TopCoder Open Algorithm Round 1B〈タイムシフト参戦記〉

TopCoder Programming Contest

registerしておきながら寝倒したので、翌朝Practice Roomでタイムシフト参戦してみた記。
Round1Cでお会いしましょう。

200-600-900て何

Easy (200) SpamChecker

問題ちゃんと読んでなかった。一瞬でもスコアが負になったらSPAMでいいのね。

600を通してたのが300人ちょいなので、事実上この200の早解き勝負だったと思う。
Practice Roomで195.77点。本番の950位相当なので予選通過ならず。

#include <string>
using namespace std;
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);++var)

class SpamChecker {
 public:
  string spamCheck(string judgeLog, int good, int bad) {
    int score=0,n=sz(judgeLog);
    rep(i,n){
      switch(judgeLog[i]){
        case 'o': score += good; break;
        case 'x': score -= bad; break;
        default: break;
      }
      if (score < 0) return "SPAM";
    }
    return "NOT SPAM";
  }
};

Medium (600) WolvesAndSheep

時間内には解けず。
壁の位置を総当たり?間に合わないよね

水平壁パターンを総当たりして、それぞれの垂直壁候補を出しておいて、それを全て満たす位置に垂直壁を引けばよさげ
という所まで辿り着いて、実装を始めたところで時間切れ。

以下、2回WAして3度目に通せたコード。
WAの原因は「それを全て満たす位置」を探す際のパターンの網羅ミス。

#line 2 "WolvesAndSheep.cpp"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#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(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define cons(x,y) make_pair((x),(y))

class WolvesAndSheep {
  int H, W;
  vector<string> f;

  string reduce(int ys, int ye, bool& b) {
    vector<char> r(W, '.');
    rep(x,W) {
      int wc=0, sc=0;
      for (int y=ys; y<=ye; ++y) {
        switch(f[y][x]) {
          case 'W': wc++; break;
          case 'S': sc++; break;
        }
      }
      if (wc*sc) { r[x]='X'; b=true; }
      else if (wc) r[x]='W';
      else if (sc) r[x]='S';
    }

    return string(all(r));
  }

  vector<pair<int,int> > line(string& s){
    vector<pair<int,int> > ans;

    char last = '|';
    int last_ix = -1;
    for (int i=0; i<W; ++i) {
      if (last == '|') {
        if (s[i] == '.') {
          // |.....
          continue;
        } else {
          // |...[SW]
          last = s[i];
          last_ix = i;
        }
      } else {
        if (s[i] == '.') {
          // last_ix = i-1;
          continue;
        } else if (s[i] == last) {
          last_ix = i;
          continue;
        } else {
          // printf(" !%d %c|%c\n", i, last, s[i]);
          ans.pb(cons(last_ix, i-1));
          last = s[i];
          last_ix = i;
        }
      }
    }
    return ans;
  }

  map<vector<pair<int,int>>,int> mm;

  int row(vector<pair<int,int> >& ss) {
    if (found(mm,ss)) return mm[ss];

    int singles = 0;
    vector<pair<int,int>> doubles;

    int lscore = 0;
    // x-x
    tr(it, ss){
      int s = it->first, e = it->second;
      if (s == e) {
        singles |= (1 << s);
        ++lscore;
      } else {
        ;
      }
    }
    // x-y
    tr(it, ss){
      int s = it->first, e = it->second;
      if (s == e) {
        ;
      } else {
        bool already = false;
        for (int i=s,m=1<<s; i<=e; ++i,m<<=1) {
          if (singles & m) { already = true; break; }
        }
        if (!already)
          doubles.pb(*it);
      }
    }

    if (sz(doubles) == 0) {
      return mm[ss] = lscore;
    }

    int rscore = sz(doubles);
    int P = 1 << (W-1);
    for (int p=0; p<P; ++p) {
      if (p & singles) continue;
      bool bad = false;
      tr(it, doubles) {
        int s = it->first, e = it->second;
        //printf(" (%d %d)", s,e);
        bool covered = false;
        for (int x=s,m=1<<s; x<=e; ++x,m<<=1) {
          if (p & m) { covered = true; break; }
        }
        if (!covered) { bad = true; break; }
      }
      if (!bad) {
        int bp = __builtin_popcount(p);
        if (bp < rscore) rscore = bp;
      }
    }

    return mm[ss] = lscore + rscore;
  }

 public:
  int getmin(vector<string> field) {
    f.assign(all(field));
    H = sz(field); W = sz(field[0]);

    vector<vector<string> > red(16, vector<string>(16));
    vector<vector<vector<pair<int,int>>>> redp(16, vector<vector<pair<int,int>>>(16));
    vector<vector<bool>> bads(16, vector<bool>(16, false));

    for (int ys=0; ys<H; ++ys) {
      for (int ye=ys; ye<H; ++ye) {
        bool bad=false;
        red[ys][ye] = reduce(ys,ye,bad);
        if (bad) {
          bads[ys][ye] = true;
          redp[ys][ye] = vector<pair<int,int>>();
        } else {
          redp[ys][ye] = line(red[ys][ye]);
        }
      }
    }

    int best_score = (H-1) + (W-1);

    int P = 1 << (H-1);
    for (int p=0; p<P; ++p) {
      vector<int> cut(1, 0);

      int last = 0;
      bool bad = false;

      for (int y=1,m=1; y<H; ++y,m<<=1) {
        if (p & m) {
          cut.pb(y);
          if (bads[last][y-1]) { bad = true; break; }
          last = y;
        }
      }
      cut.pb(H);
      if (bads[last][H-1]) { bad = true; }
      if (bad) continue;

      set<pair<int,int>> ss;
      for (int i=0,c=sz(cut)-1; i<c; ++i) {
        int s = cut[i], e = cut[i+1];
        tr(i, redp[s][e-1]) {
          ss.insert(*i);
        }
      }

      vector<pair<int,int>> ssv(all(ss));

      int score = (sz(cut)-2) + row(ssv);

      if (score < best_score) best_score = score;
    }

    return best_score;
  }
};