naoya_t@topcoder

過去問マラソン(#3):SRM146

過去問マラソン | 19:12 |

過去問マラソン3日目。

Easy(300): RectangularGrid

• Arenaの画面おかしい...と思ったら今のマシンEditorの設定が入ってないからデフォルトだ
• 秒殺問題...と思ったけどwidth==heightの場合に除外することにテストで気づいて１分超
• systest一発OK

typedef long long ll;
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)

class RectangularGrid {
 public:
  long long countRectangles(int width, int height) {
    ll cnt = 0LL;
    FOR(w,1,width){
      FOR(h,1,height){
        if (w!=h) cnt += (1LL+width-w) * (1LL+height-h);
      }
    }
    return cnt;
  }
};

CodeProcessorとかTZTesterとか入れてもう一度

typedef long long ll;
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)

class RectangularGrid {
 public:
  long long countRectangles(int width, int height) {
    ll cnt;
    FOR(w,1,width) FOR(h,1,height) if(w!=h) cnt += (1LL+width-w)*(1LL+height-h);
    return cnt;
  }
};

• 299.11点 (1'32'')...まだ速くできるだろ
• 一見良さそうだしローカルではTest Caseも通るんだけどsystestいきなりこける。何故かというとcntを初期化してないから...orz
• もいちどクリアして挑戦...ローカルテストなしで299.69点(0'54'')...トップの連中はこの位は当たり前？

Medium(600): Masterbrain

• なんか簡単じゃない？
  • results (black/white) は14パターン (00,01,02,03,04,10,11,12,13,20,21,22,30,40)しかない
  • 秘密の数の組み合わせも1-7の４桁なので7^4=2401通りしかない
  • あるguessに対し2401パターン全部試して、可能なパターンのビットを立てておく
  • guessは最大10回。どれかが嘘なので嘘のパターンはnotして、可能なパターンの論理積(and)を各回について取ったのがそのguessから得られる可能なパターンで、それをguess回数分取って論理和(or)を取り、立ってるビットを数えたら終わり
• （途中電話がかかってきたりして数分ブレイクしたが）40'41''...絶対もっともっと速く書ける。ビット列のand,or演算とかライブラリにしておくべき
• systest一発OK

typedef long long ll;
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)

class Masterbrain {
// BEGIN CUT HERE
  string enc(int n){ // for debug
    char s[5] = { '1'+((n/343)%7), '1'+((n/49)%7), '1'+((n/7)%7), '1'+(n%7), 0 };
    return string(s);
  }
// END CUT HERE
  int n;
  int possible(int secret, string guess, int result_b, int result_w){
    int s[4] = { (secret/343)%7, (secret/49)%7, (secret/7)%7, secret%7 };
    int g[4]; rep(i,4) g[i] = guess[i]-'1';
    int b=0, w=0; 
    rep(i,4) if(g[i]==s[i]){ b++; g[i]=s[i]=-1;}
    rep(i,4) rep(j,4) {
      if (i==j || g[i]<0 || s[j]<0) continue;
      if (g[i]==s[j]){ w++; g[i]=-1; s[j]=-1; break; }
    }
    return (b==result_b && w==result_w)?1:0;
  }

  void x_not_and(vector<int>& a, vector<int>& b){ rep(i,2401) a[i] &= (1 - b[i]); }
  void x_and(vector<int>& a, vector<int>& b){ rep(i,2401) a[i] &= b[i]; }
  void x_or(vector<int>& a, vector<int>& b){ rep(i,2401) a[i] |= b[i]; }
  
 public:
  int possibleSecrets(vector <string> guesses, vector <string> results) {
    // secret: 7^4 = 2401 patterns
    n = sz(guesses); // 1..10
    vector<vector<int> > bits(n);
    rep(i,n){
      const char *s = results[i].c_str();
      int b = s[0]-'0', w = s[3]-'0';

      vector<int> bit(2401,0);
      rep(n,2401){
        bit[n] = possible(n,guesses[i],b,w);
      }
      bits[i] = bit;
    }

    vector<int> possibles(2401,0);

    rep(u,n){ // どれを嘘と仮定するか
      vector<int> a(2401,1);
      rep(i,n){
        if(i==u){
          x_not_and(a,bits[i]);
        } else {
          x_and(a,bits[i]);
        }
      }
      
      x_or(possibles,a);
    }

    int bitcnt=0;
    rep(i,2401) bitcnt+=possibles[i];
    return bitcnt;
  }
};

勉強がてらビット列を表現するクラスを作ってみて今では

typedef long long ll;
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)

#include "Bits.h"

string enc(int n){ // n:0..2400 => "1234"
  char s[5] = { '1'+((n/343)%7), '1'+((n/49)%7), '1'+((n/7)%7), '1'+(n%7), 0 };
  return string(s);
}
int dec(string s){ // s:"1234" => (0..2400)
  int res = 0;
  rep(i,4) res = res*7 + (s[i] - '1');
  return res;
}

class Masterbrain {
  int n;
  int possible(int secret_n, string guess, int result_b, int result_w){
    string s = enc(secret_n), g = guess;
    int b=0, w=0; 
    rep(i,4) if(g[i]==s[i]){ b++; g[i]=s[i]=-1;}
    rep(i,4) rep(j,4) {
      if (i==j || g[i]<0 || s[j]<0) continue;
      if (g[i]==s[j]){ w++; g[i]=-1; s[j]=-1; break; }
    }
    return (b==result_b && w==result_w)?1:0;
  }

 public:
  int possibleSecrets(vector <string> guesses, vector <string> results) {
    // secret: 7^4 = 2401 patterns

    n = sz(guesses); // 1..10

    vector<Bits> bits(n, Bits(2401,0));
    rep(i,n){
      int b = results[i][0]-'0', w = results[i][3]-'0';
      rep(j,2401) bits[i].set(j, possible(j,guesses[i],b,w));
    }

    Bits possibles(2401,0);
    rep(u,n){
      Bits a(2401,1);
      rep(i,n){
        if (i==u) a &= ~bits[i];
        else      a &=  bits[i];
      }
      possibles |= a;
    }

    return possibles.popcount();
  }
};

• Bitsクラス（現時点で200行強）は別エントリ立てる

Hard(800): Roundabout

// later