2009-12-26

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

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

Bits

11:59 |

ビット列の論理演算クラスを試作。

AND,OR,XOR,NOTとか。今日の問題が通る程度の実装。

内部でメモリを確保して、8ビット最密充填
演算子オーバーロードを使えば配列的記法で（a=bits[201];みたいに）特定ビットの内容を取って来ることはできるが、代入（bits[201]=1; みたいな）ができないのが残念。で、代入やられると危険なのでオーバーロードしてない。

//
// Bits.h - (c)2009 by naoya_t
//
// ライセンスは NYSL 0.9982に従います http://www.kmonos.net/nysl/
//
#include <string>
#include <iostream>
#include <sstream>
using namespace std;

class Bits {
  unsigned char *data;
  int data_bytesize;
  int data_size;

public:
  Bits() { data = NULL; data_size = 0; }
  Bits( int size, int initial_value=0 ) { data = NULL; init(size,initial_value); }
  Bits( const Bits& bits ) { data = NULL; init(bits); }
  virtual ~Bits() { dealloc_data(); }

  const int size() { return data_size; }
  const int popcount();

  void dealloc_data() { if (data) { free((void*)data); data = NULL; } }

  Bits &init( int size, int initial_value=0 );
  Bits &init( const Bits& bits );
  Bits &operator=( const Bits& bits ) { dealloc_data(); return init( bits ); }

  void set( int offset, int value=1 );
  void unset( int offset );
  int get( int offset );

  Bits &operator&=(const Bits& other);
  Bits &operator|=(const Bits& other);
  Bits &operator^=(const Bits& other);

  Bits &operator+=(const Bits& other); //concat

  Bits operator&(const Bits& other) { Bits result(*this); result &= other; return result; }
  Bits operator|(const Bits& other) { Bits result(*this); result |= other; return result; }
  Bits operator^(const Bits& other) { Bits result(*this); result ^= other; return result; }
  Bits operator‾();

  Bits operator+(const Bits& other) { Bits result(*this); result += other; return result; }

  string desc();
};

const int
Bits::popcount()
{
  int cnt = 0;
  int fullsize = data_size >> 3;
  for (int i=0; i<fullsize; i++)
    cnt += __builtin_popcount(data[i]);
  if (fullsize < data_bytesize) {
    int rest_bitsize = data_size % 8; // 1..7
    int mask = 127 >> (7 - rest_bitsize); // 1...127
    cnt += __builtin_popcount((int)data[fullsize] & mask);
  }
  return cnt;
}

Bits &
Bits::init( int size, int initial_value )
{
  dealloc_data();
  data_size = size; data_bytesize = (size + 7) >> 3;
  data = (unsigned char *)malloc( data_bytesize );
  memset( data, initial_value ? 255 : 0, data_bytesize );
  return *this;
}
Bits &
Bits::init( const Bits& bits )
{
  dealloc_data();
  data_size = bits.data_size; data_bytesize = bits.data_bytesize;
  data = (unsigned char *)malloc( data_bytesize );
  memcpy( data, bits.data, data_bytesize );
  return *this;
}

void
Bits::set( int offset, int value )
{
  if (offset < 0 || data_size <= offset) return; // invalid.
  if (!data) return;

  int byteofs = offset >> 3, bitofs = offset % 8;
  if (value)
    data[byteofs] |= (1 << bitofs);
  else
    data[byteofs] &= (~(1 << bitofs));
}
void
Bits::unset( int offset )
{
  if (offset < 0 || data_size <= offset) return; // invalid.
  if (!data) return;

  int byteofs = offset >> 3, bitofs = offset % 8;
  data[byteofs] &= (~(1 << bitofs));
}
int
Bits::get( int offset )
{
  if (offset < 0 || data_size <= offset) return -1; // invalid.
  if (!data) return -1;

  int byteofs = offset >> 3, bitofs = offset % 8;
  return (data[byteofs] & (1 << bitofs)) ? 1 : 0;
}

Bits &
Bits::operator&=(const Bits& other)
{
  if (data_size < other.data_size) {
    // 自分.size < 相手.size
    for (int i=0; i<data_bytesize; i++) data[i] &= other.data[i];
    // 残りは捨てられる
  } else {
    // 自分.size >= 相手.size
    int fullsize = other.data_size >> 3;
    for (int i=0; i<fullsize; i++)
      data[i] &= other.data[i];
    if (fullsize < other.data_bytesize) {
      int rest_bitsize = other.data_size & 7;
      int mask = 127 >> (7 - rest_bitsize);
      int rest = other.data[fullsize] & mask;
      data[fullsize++] &= rest;
    }
    // 足りない分はzero
    for (int i=fullsize; i<data_bytesize; i++) data[i] = 0; // data[i] &= 0;
  }
  return *this;
}

Bits &
Bits::operator|=(const Bits& other)
{
  if (data_size < other.data_size) {
    // 自分.size < 相手.size
    for (int i=0; i<data_bytesize; i++) data[i] |= other.data[i];
    // 残りは捨てられる
  } else {
    // 自分.size >= 相手.size
    int fullsize = other.data_size >> 3;
    for (int i=0; i<fullsize; i++)
      data[i] |= other.data[i];
    if (fullsize < other.data_bytesize) {
      int rest_bitsize = other.data_size % 8;
      int mask = 127 >> (7 - rest_bitsize);
      int rest = other.data[fullsize] & mask;
      data[fullsize++] |= rest;
    }
    // 足りない分は放置
    // for (int i=fullsize; i<data_bytesize; i++) data[i] |= 0;
  }
  return *this;
}

Bits &
Bits::operator^=(const Bits& other)
{
  if (data_size < other.data_size) {
    // 自分.size < 相手.size
    for (int i=0; i<data_bytesize; i++) data[i] ^= other.data[i];
    // 残りは捨てられる
  } else {
    // 自分.size >= 相手.size
    int fullsize = other.data_size >> 3;
    for (int i=0; i<fullsize; i++)
      data[i] ^= other.data[i];
    if (fullsize < other.data_bytesize) {
      int rest_bitsize = other.data_size % 8;
      int mask = 127 >> (7 - rest_bitsize);
      int rest = other.data[fullsize] & mask;
      data[fullsize++] ^= rest;
    }
    // 足りない分は放置
    // for (int i=fullsize; i<data_bytesize; i++) data[i] ^= 0;
  }
  return *this;
}

Bits
Bits::operator~()
{
  Bits not_this(*this);
  for (int i=0; i<data_bytesize; i++) not_this.data[i] = ‾not_this.data[i];
  return not_this;
}

Bits &
Bits::operator+=(const Bits& other)
{
  unsigned char *old_data = data; data = NULL;
  int old_data_size = data_size, old_data_bytesize = data_bytesize;
  init( old_data_size + other.data_size );
  memcpy( data, old_data, old_data_bytesize );
  for (int i=0; i<other.data_size; i++)
    set( old_data_size + i, ((Bits)other).get(i) );
  free( (void*)old_data );
  return *this;
}

string
Bits::desc()
{
  stringstream s;
  for (int i=0; i<data_size; i++) s << get(i);
  return s.str();
}

ostream& operator<<(ostream &s, Bits bits)
{
  s << bits.desc();
  return s;
}

テスト

googletestで

% g++ Bits-test.cc -lgtest

% ./a.out

#include <gtest/gtest.h>
#include "Bits.h"
//#include <string>
//using namespace std;

TEST(Bits,ctor)
{
  Bits z(1), a(3,1), b(5,1), c(7,0), d(9), e(11,1);

  EXPECT_EQ("0", z.desc() );
  EXPECT_EQ("111", a.desc() );
  EXPECT_EQ("11111", b.desc() );
  EXPECT_EQ("0000000", c.desc() );
  EXPECT_EQ("000000000", d.desc() );
  EXPECT_EQ("11111111111", e.desc() );
}

TEST(Bits,set)
{
  Bits a(10);
  EXPECT_EQ("0000000000", a.desc() );
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) a.unset(i);
  EXPECT_EQ("0010100010", a.desc() );
  for (int i=0; i<10; i+=5) a.set(i,1);
  EXPECT_EQ("1010110010", a.desc() );
  for (int i=0; i<10; i+=2) a.set(i,0);
  EXPECT_EQ("0000010000", a.desc() );
}

TEST(Bits,and)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  EXPECT_EQ("1001001001", b.desc() );

  Bits a_and_b = a & b;
  EXPECT_EQ("1000001000", a_and_b.desc() );
  // a, b が不変であること
  EXPECT_EQ("1010101010", a.desc() );
  EXPECT_EQ("1001001001", b.desc() );

  a &= b;
  EXPECT_EQ("1000001000", a.desc() );
}

TEST(Bits,or)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  EXPECT_EQ("1001001001", b.desc() );

  Bits a_or_b = a | b;
  EXPECT_EQ("1011101011", a_or_b.desc() );
  // a, b が不変であること
  EXPECT_EQ("1010101010", a.desc() );
  EXPECT_EQ("1001001001", b.desc() );

  a |= b;
  EXPECT_EQ("1011101011", a.desc() );
}

TEST(Bits,xor)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  EXPECT_EQ("1001001001", b.desc() );

  Bits a_xor_b = a ^ b;
  EXPECT_EQ("0011100011", a_xor_b.desc() );
  // a, b が不変であること
  EXPECT_EQ("1010101010", a.desc() );
  EXPECT_EQ("1001001001", b.desc() );

  a ^= b;
  EXPECT_EQ("0011100011", a.desc() );
}

TEST(Bits,not)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  EXPECT_EQ("1001001001", b.desc() );

  Bits not_a = ~a, not_b = ~b;
  EXPECT_EQ("0101010101", not_a.desc() );
  EXPECT_EQ("0110110110", not_b.desc() );
}

TEST(Bits,concat)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  EXPECT_EQ("1001001001", b.desc() );

  Bits a_b = a + b, b_a = b + a;
  EXPECT_EQ("10101010101001001001", a_b.desc() );
  EXPECT_EQ("10010010011010101010", b_a.desc() );
  // a, b が不変であること
  EXPECT_EQ("1010101010", a.desc() );
  EXPECT_EQ("1001001001", b.desc() );

  a += b;
  EXPECT_EQ("10101010101001001001", a.desc() );
}

TEST(Bits,count)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  // EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  // EXPECT_EQ("1001001001", b.desc() );

  EXPECT_EQ(10, a.size());
  EXPECT_EQ(10, b.size());

  Bits c1(1,1), c2(2,1), c3(3,1), c4(4,1), c5(5,1), c6(6,1), c7(7,1), c8(8,1), c9(9,1), d(2401,1);
  EXPECT_EQ(1, c1.size());
  EXPECT_EQ(2, c2.size());
  EXPECT_EQ(3, c3.size());
  EXPECT_EQ(4, c4.size());
  EXPECT_EQ(5, c5.size());
  EXPECT_EQ(6, c6.size());
  EXPECT_EQ(7, c7.size());
  EXPECT_EQ(8, c8.size());
  EXPECT_EQ(9, c9.size());
  EXPECT_EQ(2401, d.size());
}

TEST(Bits,popcount)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  //EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  //EXPECT_EQ("1001001001", b.desc() );

  EXPECT_EQ(5, a.popcount());
  EXPECT_EQ(4, b.popcount());

  Bits c1(1,1), c2(2,1), c3(3,1), c4(4,1), c5(5,1), c6(6,1), c7(7,1), c8(8,1), c9(9,1), d(2401,1);
  EXPECT_EQ(1, c1.popcount());
  EXPECT_EQ(2, c2.popcount());
  EXPECT_EQ(3, c3.popcount());
  EXPECT_EQ(4, c4.popcount());
  EXPECT_EQ(5, c5.popcount());
  EXPECT_EQ(6, c6.popcount());
  EXPECT_EQ(7, c7.popcount());
  EXPECT_EQ(8, c8.popcount());
  EXPECT_EQ(9, c9.popcount());
  EXPECT_EQ(2401, d.popcount());
}

int main(int argc, char** argv)
{
  testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20091226

naoya_t@topcoder - [過去問マラソン]過去問マラソン...

		2009/12
日	月	火	水	木	金	土
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

naoya_t@topcoder

2009-12-26

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

Easy(300): RectangularGrid

Medium(600): Masterbrain

Hard(800): Roundabout

Bits

テスト