Hatena::Grouptopcoder

shnyaの参戦記録

2011-05-29練習

負け癖がついちゃってますね。どうしたものやら。

最近競技プログラミング系では凹むことばっかりですが、まぁ結果が伴わないことも多いのは、今に始まったことでもなし。


誰かに読まれることをあまり想定しない日記になってますが記録のために残しておきます。

問題ページはタイトルにリンクしてますので、気になった方はタイトルを踏んでください。


REPマクロは最近なんとなく捨てました。

SRM 433 Div1 Easy 02:48  [http://www.topcoder.com/stat?c=problem_statement&pm=10195&rd=13695:title=SRM 433 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10195&rd=13695:title=SRM 433 Div1 Easy] - shnyaの参戦記録

next_permutationが重複するものに使えないとばかり思っていて自分で再帰使って書きました。

でも実際は、インデックスを保存したvector<int>を使ってnext_permutationを使えばいいということを指摘されて、

なぜ思いつかなかったし、と凹む。


class MagicWords
{
  void permute0(size_t i, vector<int> &used, vector<int> &path, const vector<int> &v, vector<vector<int> > &result){
    if(i == v.size()){
      result.push_back(path);
      return;
    }
    for(int j = 0; j < int(v.size()); j++){
      if(used[j] != 1){
        used[j] = 1;
        path.push_back(v[j]);
        permute0(i+1,used,path,v,result);
        path.pop_back();
        used[j] = 0;
      }
    }
  }

  void permute(const vector<int> &v, vector<vector<int> > &result){
    vector<int> path, used(v.size());
    permute0(0,used,path,v,result);
  }

public:
  int count(vector <string> S, int K)
  {
    vector<vector<int> > result;
    vector<int> v(S.size());
    for(int i = 0; i < int(S.size()); ++i){
      v[i] = i;
    }
    permute(v,result);
    //debug(result);
    int res = 0;
    for(int i = 0; i < int(result.size()); ++i){
      vector<int> &vv = result[i];
      string s;
      for(int j = 0; j < int(vv.size()); ++j){
        s += S[vv[j]];
      }
      if(int(s.size()) % K != 0) return 0;
      int siz = s.size();
      for(int j = 1; j <= siz/ K; ++j){
        if(siz % j != 0) continue;
        string res2 = s.substr(0,j);
        for(int k = 1; k < int(s.size())/j; ++k){
          if(res2 != s.substr(j*k,j)){
            goto fail;
          }
        }
        if(j == int(s.size())/K){
          res++;
          break;
        }else{
          goto fail2;
        }
      fail:;
      }
    fail2:;
    }
    return res;
  }

SRM 433 Div1 Medium 02:48  [http://www.topcoder.com/stat?c=problem_statement&pm=10191&rd=13695:title=SRM 433 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10191&rd=13695:title=SRM 433 Div1 Medium] - shnyaの参戦記録

あれ?簡単じゃね?とか思ってやったら数が合わずに断念。

斜めの場合を考慮できてなかった模様。

結局下記URLを読んで解き方を理解しました。

http://d.hatena.ne.jp/ogiekako/20100103/p3

http://topcoder.g.hatena.ne.jp/wata_orz/20090122/1232607135

自分で解いたわけじゃないけど、忘れないようにはっておきます。

class SettingTents {
public:
  int countSites( int N, int M ) {
    int res = 0;
    for(int i = 1; i <= max(N,M); i++){
      for(int j = 0; j < i; j++){
        res += max(0, (N - i + 1)) * max(0, (M - i + 1));
        for(int k = 1; 2 * k < i; k++){
          if((i - 2 * j) * k % i == 0){
            int h = max(i-2*k,abs(i-2*j));
            if(h<= N && i <= M) res += (N-h+1)*(M-i+1);
            if(h<= M && i <= N) res += (M-h+1)*(N-i+1);
          }
        }
      }
    }
    return res;
  }
};

SRM 469 Div1 Easy 02:48  [http://www.topcoder.com/stat?c=problem_statement&pm=10898&rd=14152:title=SRM 469 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10898&rd=14152:title=SRM 469 Div1 Easy] - shnyaの参戦記録

10億x10億も座席があるという映画館なんてねーよとか思いながら解く。

#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(a) int((a).size())

class TheMoviesLevelOneDivOne {
public:
  long long find( int n, int m, vector <int> row, vector <int> seat ) {
    multimap<LLI,LLI> s;
    REP(i,SZ(row)){
      s.insert(make_pair(row[i],seat[i]));
    }
    SORT(row);
    row.erase(unique(ALL(row)),row.end());
    if(m < 2) return 0;
    LLI res = 0;
    REP(i,SZ(row)){
      vector<LLI> v;
      for(multimap<LLI,LLI>::iterator itr = s.lower_bound(row[i]);
          itr != s.upper_bound(row[i]); itr++){
        v.push_back(itr->second);
      }
      SORT(v);
      LLI k = 1;
      REP(i,SZ(v)){
        if(v[i] - k > 1){
          res += v[i] - k - 1;
        }
        k = v[i] + 1;
      }
      if(m - v.back() > 1){
        res += m - v.back() - 1;
      }
    }
    res += (n - (LLI)SZ(row)) * (m - 1);
    return res;
  }
};

SRM 469 Div1 Medium 02:48  [http://www.topcoder.com/stat?c=problem_statement&pm=10900&rd=14152:title=SRM 469 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10900&rd=14152:title=SRM 469 Div1 Medium] - shnyaの参戦記録

映画を見た順序を答える問題。全探索は全ての経路を求める場合はO(n!)。

こういう問題は、範囲DP, ソートしてDP, ビットDPのどれかかなぁと思っていて、それぞれ考えてみる。範囲DPに落とせそうな部分的な構造はない。ということで、並び替え頑張ればなんとかならないかなーと思ったけど、無理っぽかった。


結局bitDPに。O(2^20)。最初はvector<signed char>を値にもつメモ化を考えたけど、それだと遅すぎてTLE

配列でやり直したけど、他の人の回答見たら、値を深さでもって、2回再帰すればよかったかなぁとも思ったり。この問題はきつかった。

int setbit(int x, int n){
  return x | 1 << n;
}

int clearbit(int x, int n){
  return x & ~(1 << n);
}

bool testbit(int x, int n){
  return (x & 1 << n) != 0;
}

void printbit(int x){
  for(size_t i = 0; i < sizeof(int) * 8; i++){
    cout << testbit(x,i);
  }
}
typedef signed char uc;
signed char dp[1<<20][21];
signed char depth[1<<20];
int maxn,maxd;

class TheMoviesLevelTwoDivOne {

  void rec(int n, const vector<int> &len, const vector<int> &scary){
    if(n == (1 << len.size()) - 1) return;
    if(depth[n] != -1) return;
    depth[n] = 1;

    int level = 74;
    int cnt = 0;
    for(size_t i = 0; i < len.size(); i++){
      if(testbit(n,i)){
        level += 47;
        level -= len[i];
        cnt++;
      }
    }

    for(size_t i = 0; i < len.size(); i++){
      if(!testbit(n,i)){
        if(level - scary[i] >= 0 && level + 47 - len[i] >= 0){
          int newbit = setbit(n,i);
          if(maxd < cnt + 1){
            maxn = newbit;
            maxd = cnt + 1;
          }
          if(dp[newbit][cnt] == -1){
            for(int j = 0; j < cnt; j++){
              dp[newbit][j] = dp[n][j];
            }
            dp[newbit][cnt] = i;
          }
          rec(newbit, len, scary);
        }
      }
    }
    return;
  }

public:
  vector <int> find( vector <int> length, vector <int> scary ) {
    memset(depth, -1, sizeof(depth));
    memset(dp,-1,sizeof(dp));
    maxn = 0; maxd = 0;
    rec(0, length, scary);
    vector<int> res;
    for(int i = 0; i < maxd; ++i){
      res.push_back(dp[maxn][i]);
    }
    for(int i = 0; i < int(length.size()); i++){
      if(!testbit(maxn,i)){
        res.push_back(i);
      }
    }

    return res;
  }
};

SRM 507 Div1 Easy 02:58  [http://www.topcoder.com/stat?c=problem_statement&pm=11315&rd=14436:title=SRM 507 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11315&rd=14436:title=SRM 507 Div1 Easy] - shnyaの参戦記録

あー、グラフ彩色問題だー、Easyで出るとは思わなんだと思って最初は、wikipediaとかいろいろ調べてみる。すぐにはわからないことがわかったので、とりあえずダメ元で問題に向き直ってみる。


最低3色*2あれば色塗りできるのか。一度3色塗って、残りの色で塗れるか試せばよさそう。まぁまぁ、これは間違うことないだろと思ったらミスしてた。。。

class CubeStickers {
public:
  string isPossible( vector <string> sticker ) {
    map<string,int> m;
    for(int i = 0; i < int(sticker.size()); ++i){
      m[sticker[i]]++;
    }
    vector<int> v;
    for(typeof(m.begin()) itr = m.begin();itr != m.end(); ++itr){
      v.push_back(itr->second);
    }
    sort(v.begin(),v.end(),greater<int>());
    if(v.size() < 3){
      return "NO";
    }
    for(int i = 0; i < 3; i++)
      v[i]--;
    v.erase(remove_if(v.begin(),v.end(),bind2nd(equal_to<int>(),0)),v.end());
    if(v.size() < 3){
      return "NO";
    }
    return "YES";
  }
};

ちなみに本番で書いたコードはこちら。頭の中では上のコードをイメージしてたのに、なんでこう書いちゃったのやら。。。

Challengeにどうぞ。

class CubeStickers {
public:
  string isPossible( vector <string> sticker ) {
    map<string,int> m;
    for(int i = 0; i < int(sticker.size()); ++i){
      m[sticker[i]]++;
    }
    vector<int> v;
    for(typeof(m.begin()) itr = m.begin();itr != m.end(); ++itr){
      v.push_back(itr->second);
    }
    sort(v.begin(),v.end());
    if(v.size() < 3){
      return "NO";
    }
    for(int i = 0; i < 3; i++)
      v[i]--;
    v.erase(remove_if(v.begin(),v.end(),bind2nd(equal_to<int>(),0)),v.end());
    if(v.size() < 3){
      return "NO";
    }
    return "YES";
  }
};

SRM 470 Div1 Easy 05:15  [http://www.topcoder.com/stat?c=problem_statement&pm=10915&rd=14153:title=SRM 470 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10915&rd=14153:title=SRM 470 Div1 Easy] - shnyaの参戦記録

貪欲にシミュレーションする問題。けど、とにかく大変。

本番だったら絶対撃墜されていた。


class DoorsGame {
public:
  int determineOutcome( string doors, int trophy ) {
    string a = doors.substr(0,trophy);
    string b = doors.substr(trophy);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    a.erase(unique(a.begin(), a.end()),a.end());
    b.erase(unique(b.begin(), b.end()),b.end());
    set<char> ma,mb,mall;
    set_intersection(a.begin(), a.end(),
                     b.begin(), b.end(), inserter(mall,mall.begin()));
    set_difference(a.begin(), a.end(),
                   b.begin(), b.end(), inserter(ma,ma.begin()));
    set_difference(b.begin(), b.end(),
                   a.begin(), a.end(), inserter(mb,mb.begin()));
    int res = 0;
    while(1){
      char af = a[0];
      if(ma.size() == 0){
        af = *(mall.begin());
        mall.erase(mall.begin());
      }else{
        af = *(ma.begin());
        ma.erase(ma.begin());
      }
      a.erase(remove(a.begin(), a.end(),af),a.end());
      b.erase(remove(b.begin(), b.end(),af),b.end());
      res++;
      if(a.size() == 0 && b.size() == 0) return 0;
      if(a.size() == 0) return res;
      if(b.size() == 0) return -res;

      char bf = b[0];
      if(mb.size() == 0){
        bf = *(mall.begin());
        mall.erase(mall.begin());
      }else{
        bf = *(mb.begin());
        mb.erase(mb.begin());
      }
      a.erase(remove(a.begin(), a.end(),bf),a.end());
      b.erase(remove(b.begin(), b.end(),bf),b.end());
      res++;
      if(a.size() == 0 && b.size() == 0) return 0;
      if(b.size() == 0) return -res;
      if(a.size() == 0) return res;
    }
    return res;
  }
};