topcoder

naoya_t@topcoder

2009-12-30

過去問マラソン(#6続き):SRM149

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

Medium(500): MessageMess

最悪ケースがぱっと思いつかなくて処理量を過小評価しがちなので何とかしたい。

1投目(21'15'') ... failed system test
- IMPOSSIBLEな時に全部なめててTLE
- メモ化ちゃんとしないと
2投目 ... failed
- まだぜんぜん遅い
- 同じところまで２度来たら、１度目の結果次第でIMPOSSIBLE!かAMBIGUOUS!を返すように
3投目 ... passed

続きを読む

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

2009-12-29

過去問マラソン(#6):SRM149

過去問マラソン | 21:35 |

Easy(250): BigBurger

夕食前にすこし時間があったので先にSRM149のEasyを解く。
結果が0ばかり出ておかしいなーと思ってたらwait=arrival[i]-t って書いてたりとか
5'20'', passed system test
もっと速く解きたい

続きを読む

過去問マラソン(今日こそ#5):SRM148

過去問マラソン | 15:18 |

昨日は戦闘環境再構築に時間を取られてしまったので気を取り直して５日目。

続きを読む

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

2009-12-28

過去問マラソン(#5):SRM148

過去問マラソン | 00:53 |

// 会社にマシン返却してしまったので戦闘環境を再構築中。出来次第５日目。

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

2009-12-27

過去問マラソン(#4):SRM147

過去問マラソン | 11:44 |

四日(坊主)目。

昨日も一昨日もHardは問題名しか見てない...けどとりあえず先に進むよ。

// 先に昨日試作したビット列処理クラスのエントリを書くなどしたよ

Easy(350): PeopleCircle

なぜ350点
それはさておき
簡単な実装問題なはずなのに18分...orz

using namespace std;
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class PeopleCircle {
 public:
  string order(int numMales, int numFemales, int K) {
    int n=numMales+numFemales, rest=n;
    vector<char> ring(n,'M');
    K--;
    int here=0;
    rep(i,numFemales){
      // skip K men
      int skipped=0;
      while(skipped<K){
        if(ring[(here++)%n]=='M') skipped++;
      }
      // skip Fs // ←これが入ってなくて答えが合わず悩んだ
      while (1){
        if(ring[(here)%n]=='F') here++; else break;
      }
      ring[here%n] = 'F';
      rest--;
    }
    return string(all(ring));
  }
};

Medium(500): Dragons

問題自体は平易。
分数を表現するクラスが欲しい
45ラウンドやった時の分子と分母の最大がlong longに収まるか ... Bignumが要るか要らないか →Test case見てると要らないみたい

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

// Fraction class definition here...

class Dragons {
 public:
  string snaug(vector<int> initialFood, int rounds) {
    vector<vector<Fraction> > bowl(2,vector<Fraction>(6));
    rep(i,6) {
      bowl[0][i].init(initialFood[i]);
      bowl[1][i].init(0,1);
    }
    enum { FR=0, BK,UP,DN,LF,RG };
    
    rep(r,rounds){
      int i0=r%2, i1=(r+1)%2;

      bowl[i1][FR] = (bowl[i0][UP] + bowl[i0][DN] + bowl[i0][LF] + bowl[i0][RG])/4;
      bowl[i1][BK] = (bowl[i0][UP] + bowl[i0][DN] + bowl[i0][LF] + bowl[i0][RG])/4;
      bowl[i1][UP] = (bowl[i0][FR] + bowl[i0][BK] + bowl[i0][LF] + bowl[i0][RG])/4;
      bowl[i1][DN] = (bowl[i0][FR] + bowl[i0][BK] + bowl[i0][LF] + bowl[i0][RG])/4;
      bowl[i1][LF] = (bowl[i0][FR] + bowl[i0][BK] + bowl[i0][UP] + bowl[i0][DN])/4;
      bowl[i1][RG] = (bowl[i0][FR] + bowl[i0][BK] + bowl[i0][UP] + bowl[i0][DN])/4;
    }
    return bowl[rounds%2][UP].desc();
  }
};

分子が0の時に "0" ではなく "0/xxxx" な表記になっててsystest failed x 1
Fractionクラスは別エントリにて。submit時には必要最小限に削らないと30%ルールに引っかかるよ
各面のinitialFoodを0〜3にして45ラウンド回してみたら分母の最大は70368744177664 (=2^46) だった。55ラウンドなら72057594037927936 (=2^56)。
- 要するに 2^(ラウンド数+1)...0ラウンドで1, 1ラウンド回すと4、次から2倍ずつ
- というわけでlong longでおｋ

Hard:

//

Fraction - 分数を表現するクラス

23:45 |

テンプレート
TにBignum（自家製）を入れても動く（けどまあ遅いね）

続きを読む

Bignum

23:45 |

前に作ったやつに少し手を加えた

続きを読む

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

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

2009-12-26

過去問マラソン(#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

Bits

11:59 |

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

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

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

続きを読む

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

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