Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-12-30

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

| 12:00 | 過去問マラソン(#6続き):SRM149 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#6続き):SRM149 - naoya_t@topcoder 過去問マラソン(#6続き):SRM149 - naoya_t@topcoder のブックマークコメント

Medium(500): MessageMess

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

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

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091230

2009-12-29

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

| 21:35 | 過去問マラソン(#6):SRM149 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#6):SRM149 - naoya_t@topcoder 過去問マラソン(#6):SRM149 - naoya_t@topcoder のブックマークコメント

Easy(250): BigBurger

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

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

| 15:18 | 過去問マラソン(今日こそ#5):SRM148 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(今日こそ#5):SRM148 - naoya_t@topcoder 過去問マラソン(今日こそ#5):SRM148 - naoya_t@topcoder のブックマークコメント

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

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091229

2009-12-28

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

| 00:53 | 過去問マラソン(#5):SRM148 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#5):SRM148 - naoya_t@topcoder 過去問マラソン(#5):SRM148 - naoya_t@topcoder のブックマークコメント

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

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091228

2009-12-27

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

| 11:44 | 過去問マラソン(#4):SRM147 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#4):SRM147 - naoya_t@topcoder 過去問マラソン(#4):SRM147 - naoya_t@topcoder のブックマークコメント

四日(坊主)目。

昨日も一昨日も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でおk

Hard:

//

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

23:45 | Fraction - 分数を表現するクラス - naoya_t@topcoder を含むブックマーク はてなブックマーク - Fraction - 分数を表現するクラス - naoya_t@topcoder Fraction - 分数を表現するクラス - naoya_t@topcoder のブックマークコメント

  • テンプレート
  • TにBignum(自家製)を入れても動く(けどまあ遅いね)
  • 続きを読む

Bignum

23:45 | Bignum - naoya_t@topcoder を含むブックマーク はてなブックマーク - Bignum - naoya_t@topcoder Bignum - naoya_t@topcoder のブックマークコメント

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

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091227

2009-12-26

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

| 19:12 | 過去問マラソン(#3):SRM146 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#3):SRM146 - naoya_t@topcoder 過去問マラソン(#3):SRM146 - naoya_t@topcoder のブックマークコメント

過去問マラソン3日目。

Easy(300): RectangularGrid

  • Arenaの画面おかしい...と思ったら今のマシンEditorの設定が入ってないからデフォルトだ
  • 秒殺問題...と思ったけどwidth==heightの場合に除外することにテストで気づいて1分超
  • 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の4桁なので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 | Bits - naoya_t@topcoder を含むブックマーク はてなブックマーク - Bits - naoya_t@topcoder Bits - naoya_t@topcoder のブックマークコメント

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

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

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

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091226

2009-12-25

過去問マラソン(#2):SRM145

| 12:45 | 過去問マラソン(#2):SRM145 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#2):SRM145 - naoya_t@topcoder 過去問マラソン(#2):SRM145 - naoya_t@topcoder のブックマークコメント

過去問マラソン2日目。

Easy(250): Bonuses

  • 前にも見たかなあ
  • Sample caseで答えが合わず悩んでたら、小数点以下を切り捨てたパーセンテージで上から数えててたorz
  • 12'32''遅すぎ
  • systest一発
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)

class Bonuses {
 public:
  vector<int> getDivision(vector<int> points) {
    int n=sz(points);
    int sum=0;rep(i,n)sum+=points[i];

    vector<int> pd(n);
    int left=100;
    rep(i,n){pd[i]=100*points[i]/sum;left-=pd[i];}

    vector<int> added(n,0);
    while (left>0) {
      int maxpt=0,maxat=-1;
      // rep(i,n){if(added[i]==0&&maxpt<pd[i]) maxpt=pd[i],maxat=i;} // !oops
      rep(i,n){if(added[i]==0&&maxpt<points[i]) maxpt=points[i],maxat=i;}
      added[maxat]++; left--;
    }
    rep(i,n) pd[i]+=added[i];
    return pd;
  }
};

てか後半はソートを使って簡単に書きたい。やり直し

  • ソート順が小さい順(昇順)なことを感覚的に捉えられてなくて、テスト動かしてみて確認してるのが時間もったいない
#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()

typedef pair<int,int> i_i;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)

class Bonuses {
 public:
  vector<int> getDivision(vector <int> points) {
    int n=sz(points);
    int sum=0;rep(i,n)sum+=points[i];

    vector<int> pd(n);
    int left=100;
    rep(i,n){pd[i]=100*points[i]/sum;left-=pd[i];}

    vector<i_i> pp(n);
    rep(i,n)pp[i]=cons(-points[i],i);
    sort(all(pp));
    rep(i,left) pd[cdr(pp[i])]++;
    return pd;
  }
};

Medium(600):VendingMachine

  • 見たことある気もする
  • 実装するだけなんですが
    • コード書き始めるのはもうちょっと問題を咀嚼してからでいいかも。焦っても意味ない
  • max_element()で何か変な値が出るので延々悩んでたら、カラムの数にprices[0].size() が入ってた。これはカラム数ではなく文字数!
    • ちょっとiteratorの扱いに慣れてきたぞ
  • しかし74'38''...遅い
  • systestは一発
    • Easyすっ飛ばしてこれだけ解いてsubmitすれば218.51点はとれた計算
    • Easy, Mediumともに解ける問題なので、2問とも時間内にぜひともクリアしたい
vector<string> split(string str, int delim=' '); // 略

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

int stoi(string s){ return atoi(s.c_str()); }

class VendingMachine {
 public:
  int motorUse(vector <string> prices, vector <string> purchases) {
    int n_shelves=sz(prices), n_columns;
    // n_columns = sz(prices[0]); // !oops
    vector<vector<int> > table(n_shelves);
    vector<int> pricesum;
    rep(sh,n_shelves){
      table[sh] = map_atoi(split(prices[sh])); // sh[i][s>=3] : 1..10000
      if (sh==0) {
        n_columns = sz(table[sh]);
        pricesum.resize(n_columns); rep(i,n_columns) pricesum[i]=0;
      }
      rep(col,n_columns) pricesum[col] += table[sh][col];
    }

    int motorrun = 0;
    int last_t = 0;

    // autorot
    int curr_col = 0, new_col, diff;

    {
      vector<int>::iterator max_at = max_element(all(pricesum));
      new_col = max_at - pricesum.begin();
      diff = abs(new_col - curr_col);
      motorrun += min(diff, n_columns-diff);
      curr_col = new_col;
    }

    set<i_i> boughts;
    rep(i,sz(purchases)){
      vector<string> a1 = split(purchases[i],':'), a0 = split(a1[0],',');
      int shelf=stoi(a0[0]), column=stoi(a0[1]), time=stoi(a1[1]);

      int lapse = time - last_t;
      if (lapse>=5) {
        // autorot at last_t
        vector<int>::iterator max_at = max_element(all(pricesum));
        new_col = max_at - pricesum.begin();
        diff = abs(new_col - curr_col);
        motorrun += min(diff, n_columns-diff);
        curr_col = new_col;
      }

      {
        new_col = column;
        diff = abs(new_col - curr_col);
        motorrun += min(diff, n_columns-diff);
        curr_col = new_col;
      }
      
      i_i key = cons(shelf,column);
      if (found(boughts,key)) return -1;
      boughts.insert(key);

      pricesum[column] -= table[shelf][column];
      table[shelf][column] = 0;
      
      last_t = time;
    }

    // last autorot
    {
      vector<int>::iterator max_at = max_element(all(pricesum));
      new_col = max_at - pricesum.begin();
      diff = abs(new_col - curr_col);
      motorrun += min(diff, n_columns-diff);
      curr_col = new_col;
    }

    return motorrun;
  }
};

Hard(1000): HillHike

(to be continued)

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091225

2009-12-24

来年の為に

23:57 | 来年の為に - naoya_t@topcoder を含むブックマーク はてなブックマーク - 来年の為に - naoya_t@topcoder 来年の為に - naoya_t@topcoder のブックマークコメント

今年はSRM皆勤したけどほとんど練習出来なかった。Easyがsubmitできないなんて色々終わってるので過去問で練習したい。

  • Practice Roomにある過去問はSRM144から
  • 毎日1回分解いてたら1年で終わる量
  • やった事のある問題も当然あるけど何度でもやる。というか前より速くなってるべき

というわけでSRM144から。方針はDIV1の

  • Easyは必須
  • Mediumも解く
  • Hardも問題は読む

という感じで始めたい。

過去問マラソン(#1):SRM144

| 23:57 | 過去問マラソン(#1):SRM144 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#1):SRM144 - naoya_t@topcoder 過去問マラソン(#1):SRM144 - naoya_t@topcoder のブックマークコメント

得点配分が今と違う感じ

Easy(300): BinaryCode

  • 前にやった記憶あり
  • こういうのすぐにコーディングすると空中分解するタイプ
  • とりあえず解けるんだけどchar[]で解いてるしここはSTL使ってなんとかしたい。で
  • を今頃知った。
  • 入力長が1,2の場合が例外的なので気をつけて
    • pの両側に門番(0)をつけた方が条件分岐なくて良いので楽。最後のpに非0が来たら"NONE"
#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()

class BinaryCode {
 public:
  string guess(string m,int p0){
    int n=sz(m);
    vector<char> q(all(m)), p(n+2);
    rep(i,n) q[i]-='0'; p[0]=0, p[1]=p0;//, p[n+1]=0;
    FOR(i,1,n+1) p[i+1]=q[i-1]-p[i]-p[i-1];
    if (p[n+1]!=0) return "NONE";
    
    FOR(i,1,n) { if(p[i]<0||1<p[i]) return "NONE"; else p[i]+='0'; }
    return string(p.begin()+1, p.end()-1);
  }
  vector <string> decode(string message) {
    vs ans;
    ans.pb( guess(message,0) );
    ans.pb( guess(message,1) );
    return ans;
  }
};

Medium(550): Lottery

  • 前にも見たかも
  • 文字列パース。というかsplit
  • sortedはDP
  • わりとすんなり書けた(と言っても25'16'')
  • system test一発OK
typedef long long ll;
typedef vector<string> vs;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
typedef pair<int,int> i_i;

// 自作split
vector<string> split(string str, string delim) {
  // 略
}
vector<string> split(string str, int delim=' ') {
  // 略
}

bool atob(string s){ return s[0]=='T'; }

ll pow(int x,int y){ // x^y
  ll ans=1LL; rep(i,y) ans *= (ll)x; return ans;
}
ll fac(int x,int y){ // x!/(x-y)!
  ll ans=1LL; rep(i,y) ans *= (ll)(x--); return ans;
}
class Lottery {
  map<i_i,ll> m1, m2;
  ll sub_sorted_unique(int choices,int blanks){ // 1 2 3 ...
    if (blanks==0) return 1;
    i_i key=cons(choices,blanks);
    if(found(m1,key)) return m1[key];
    ll sum=0LL;
    rep(i,choices){
      sum += sub_sorted_unique(choices-i-1,blanks-1);
    }
    m1[key]=sum;
    return sum;
  }
  ll sub_sorted(int choices,int blanks){ // 1 1 2 ...
    if (blanks==0) return 1;
    i_i key=cons(choices,blanks);
    if(found(m2,key)) return m2[key];
    ll sum=0LL;
    rep(i,choices){
      sum += sub_sorted(choices-i,blanks-1);
    }
    m2[key]=sum;
    return sum;
  }
  ll num(string name, int choices, int blanks, bool sorted, bool unique) {
    // number of valid lottery tickets for that game...
    // choices: 10-100 ... [1..choices]
    // blanks: 1-8
    ll cnt = 0LL;

    if (sorted) {
      if (unique) {
        // 1 2 3 4 5
        cnt = sub_sorted_unique(choices,blanks);
      } else {
        // 1 1 2 3 3
        cnt = sub_sorted(choices,blanks);
      }
    } else {
      if (unique) {
        // 3 2 1 5 4
        cnt = fac(choices,blanks);
      } else {
        // 3 3 1 2 1
        cnt = pow(choices,blanks); // 1e2 ^ 8 = 1e16
      }
    }
/*   
    printf("name:%s choices:%d blanks:%d sorted:%s unique:%s => %lld\n",
           name.c_str(), choices, blanks, sorted?"YES":"NO", unique?"YES":"NO",
           cnt);
*/
    return cnt;
  }
 public:
  vector <string> sortByOdds(vector<string> rules) {
    m1.clear(); m2.clear();
    
    vector<pair<ll,string> > res;
    tr(rules,st){
      vs a1 = split(*st,": ");
      string name = a1[0];
      vs a2 = split(a1[1],' ');
      int choices = atoi(a2[0].c_str()), blanks = atoi(a2[1].c_str());
      bool sorted = atob(a2[2]), unique = atob(a2[3]);

      res.pb(cons(num(name,choices,blanks,sorted,unique),name));
    }
    sort(all(res));// reverse(all(res));
    vs ans;
    tr(res,it) ans.pb(it->second);
    return ans;
  }
};

Hard(1100): PenLift

  • プロッタ懐かしい
  • とか言ってる場合じゃなくて
  • とりあえずグラフに変換
    • 同じ向きの繋がった(or 重なった)線分を検出し、union-findしといて後でまとめる
    • 線分を交差点で区切り、nodeとarcを抽出
    • union-findして島分割
    • n回重ね書きするのでarcの本数を各n倍にする
    • それぞれの島が何筆書きになるか、で行ける
      • (ここまでで3時間半。sample case#5がちゃんと解けてない!intersection判定にバグあり?)
    • 結局4時間半かかって解けた
    • system test一発OK
    • 以下駄コード
      • cons,car,cdr,caar,cadr,cdar,cddrとかまあ気にしないで
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;
typedef pair<ll,ll> ll_ll;
typedef pair<double,double> d_d;
typedef pair<int,pair<int,int> > i_ii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define caar(x) (x).first.first
#define cdar(x) (x).first.second
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

vector<string> split(string str, int delim=' ')
{
  vector<string> result;

  const char *s = str.c_str();
  if (delim == ' ') {
    for (const char *p=s; *p; p++) {
      if (*p == delim) s++;
      else break;
    }
    if (!*s) return result;

    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        if (s < p) {
          string a(s,p-s);
          result.push_back(a);
        }
        s = p + 1;
      }
    }
    if (*s) result.push_back(s);
  } else {
    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        string a(s,p-s);
        result.push_back(a);
        s = p + 1;
        if (*s == '¥0') result.push_back("");
      }
    }
    if (*s) result.push_back(s);
  }

  return result;
}

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

typedef pair<int,int> point;
typedef pair<point,point> segment;

vector<segment> segments;
vector<bool> deleted;
vector<int> dirs;

int dir(const segment& s){
  point p1 = car(s), p2 = cdr(s);
  if (p1==p2) return -1;
  if (car(p1)==car(p2)) // x1=x2
    return (p2.second > p1.second)?1:3;
  else
    return (p2.first > p1.first)?0:2;
}
segment rev(const segment& s){
  return cons(cdr(s),car(s));
}

segment joint(int i, int j){
  segment s1 = segments[i], s2 = segments[j];
  int dir = dirs[i]; // assume dirs[i]=dirs[j]
  if (dir==0) { // horizontal
    int y = cdar(s1);
    int x0 = min( caar(s1),caar(s2) ),
        x1 = max( cadr(s1),cadr(s2) );
    return cons(cons(x0,y),cons(x1,y));
  } else {
    int x = caar(s1);
    int y0 = min( cdar(s1),cdar(s2) ),
        y1 = max( cddr(s1),cddr(s2) );
    return cons(cons(x,y0),cons(x,y1));
  }
}

point cross(int i, int j){
  segment s1 = segments[i], s2 = segments[j];
  int d1 = dirs[i], d2 = dirs[j];
  if (d1==1 && d2==0) return cross(j,i);
  int y=cdar(s1);
  if (cdar(s2) <= y && y <= cddr(s2)) {
    FOR(x,caar(s1),cadr(s1)) {
      // x,y
      if(x==caar(s2)) return cons(x,y);
    }
  }
  return cons(INT_MAX,INT_MAX);
}

bool oddp(int n){
  return (n & 1)? true : false;
}

class UnionFind {
  vector<int> data;
 public:  
  UnionFind(int size) : data(size, -1) { }
  
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

class PenLift {
 public:
  int numTimes(vector<string> segs, int n) {
    int N = sz(segs);
    segments.resize(N);
    deleted.resize(N);
    dirs.resize(N);
    
	rep(i,N){ // segment_id
      vector<int> t = map_atoi(split(segs[i]));
      segment s = cons(cons(t[0],t[1]), cons(t[2],t[3]));
      if (dir(s) >= 2) s = rev(s);
      segments[i] = s; deleted[i] = false;
      dirs[i] = dir(s);
    }
    
    // joint
    UnionFind uf0(N); set<int> jointed;
    FOR(i,0,N-2){
      FOR(j,i+1,N-1){
        if (dirs[i]==dirs[j]) {
          if (dirs[i]==0) { // h
            int yi = cdar(segments[i]), yj = cdar(segments[j]);
            if (yi != yj) continue;
            int x0 = caar(segments[i]), x1 = cadr(segments[i]),
                x2 = caar(segments[j]), x3 = cadr(segments[j]);
            if (x0>x2) { swap(x0,x2); swap(x1,x3); } // x0 <= x2
            if (x2 <= x1) {
              uf0.unionSet(i,j);
              jointed.insert(i); jointed.insert(j);
            }
          } else { // v
            int xi = caar(segments[i]), xj = caar(segments[j]);
            if (xi != xj) continue;
            int y0 = cdar(segments[i]), y1 = cddr(segments[i]),
                y2 = cdar(segments[j]), y3 = cddr(segments[j]);
            if (y0>y2) { swap(y0,y2); swap(y1,y3); } // y0 <= y2
            if (y2 <= y1) {
              uf0.unionSet(i,j);
              jointed.insert(i); jointed.insert(j);
            }
          }
        }
      }
    }
    map<int,set<int> > joint_isle;
    tr(jointed,it){
      int root = uf0.root(*it);
      if (!found(joint_isle,root)) {
        set<int> s;
        joint_isle[root] = s;
      }
      //if (*it != root)
      joint_isle[root].insert(*it);
    }

    tr(joint_isle,it) {
      int root=it->first;
      if (dirs[root] == 0) { // horizontal
        int y = cdar(segments[root]);
        int xmin = INT_MAX, xmax = INT_MIN;
        tr(it->second,jt) {
          segment s = segments[*jt];
          int x0 = caar(s), x1 = cadr(s);
          if (x0 > x1) swap(x0,x1);
          xmin = min(xmin,x0);
          xmax = max(xmax,x1);
          deleted[*jt] = true;
        }
        segments[root] = cons(cons(xmin,y),cons(xmax,y));
        deleted[root] = false;
      } else { // vertical
        int x = caar(segments[root]);
        int ymin = INT_MAX, ymax = INT_MIN;
        tr(it->second,jt) {
          segment s = segments[*jt];
          int y0 = cdar(s), y1 = cddr(s);
          if (y0 > y1) swap(y0,y1);
          ymin = min(ymin,y0);
          ymax = max(ymax,y1);
          deleted[*jt] = true;
        }
        segments[root] = cons(cons(x,ymin),cons(x,ymax));
        deleted[root] = false;
      }
    }
    // cross
    vector<set<point> > seps(N,set<point>());
    FOR(i,0,N-2){
      if (deleted[i]) continue;
      
      FOR(j,i+1,N-1){
        if (deleted[j]) continue;
        
        if (dirs[i]!=dirs[j]) {

          point nx = cross(i,j);
          if (car(nx)==INT_MAX) continue;
          seps[i].insert(nx);
          seps[j].insert(nx);
        }
      }
    }

    rep(segment_id,N) {
      int sepsz = sz(seps[segment_id]);
      if (sepsz > 0) {
        deleted[segment_id] = true;
        
        if (dirs[segment_id]==0) { // horizontal
          int y = cdar(segments[segment_id]);
          set<int> xs;
          xs.insert(caar(segments[segment_id]));
          xs.insert(cadr(segments[segment_id]));
          tr(seps[segment_id],it) xs.insert(it->first);
          vector<int> xsv(all(xs));
          sort(all(xsv));
          rep(k,sz(xsv)-1) {
            segment sk = cons(cons(xsv[k],y),cons(xsv[k+1],y));
            segments.pb(sk); deleted.pb(false);
          }
        } else { // vertical
          int x = caar(segments[segment_id]);
          set<int> ys;
          ys.insert(cdar(segments[segment_id]));
          ys.insert(cddr(segments[segment_id]));
          tr(seps[segment_id],it) ys.insert(it->second);
          vector<int> ysv(all(ys));
          sort(all(ysv));

          rep(k,sz(ysv)-1) {
            segment sk = cons(cons(x,ysv[k]),cons(x,ysv[k+1]));

            segments.pb(sk); deleted.pb(false);
          }
        }
      }
    }

    // 両端登録
    map<point,set<int> > nodes; // points[point] = { segment_ids }

    rep(segment_id,sz(segments)){
      if (deleted[segment_id]) continue;
      vector<point> n(2);
      n[0]=car(segments[segment_id]);
      n[1]=cdr(segments[segment_id]);

      rep(node_id,2) {
        if(found(nodes,n[node_id])) {
          nodes[n[node_id]].insert(segment_id);
        } else {
          set<int> s; s.insert(segment_id);
          nodes[n[node_id]] = s;
        }
      }
    }

    UnionFind uf(sz(segments));

    tr(nodes,nt){
      set<int> arcs = nt->second;
      vector<int> av(all(arcs)); FOR(i,1,sz(av)-1) uf.unionSet(av[0],av[i]);
    }

    map<int,int> isles;
    rep(i,sz(segments)) {
      if (deleted[i]) continue;
      int root = uf.root(i);
      if (!found(isles,root)) isles[root] = 0;
    }

    // again
    tr(nodes,nt){
      point node = nt->first;
      set<int> arcs = nt->second;
      vector<int> av(all(arcs));
      int root = uf.root(av[0]);
      if (oddp(sz(arcs)*n)) isles[root]++;
    }
    tr(isles,it) { it->second /= 2; }

    int ans = sz(isles)-1;
    tr(isles,it) {
      if (it->second == 0) continue;
      ans += it->second - 1;
    }
   
    return ans;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091224

2009-12-23

SRM456 Hard: FunctionalEquation

| 17:38 | SRM456 Hard: FunctionalEquation - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM456 Hard: FunctionalEquation - naoya_t@topcoder SRM456 Hard: FunctionalEquation - naoya_t@topcoder のブックマークコメント

寝る前にちょっと考えた

  • f(x)=ax+b な形だとa=1,b=(C-1)/2になってしまってCが偶数のときにf(x)がintegerにならなくてアウト
  • f(x)=ax^2 + bx + c な形だとa=0で結局同上
  • f(x)=Σa_ix^i で考えると... 寝落ち

SRM456 Medium: CutSticks

| 20:46 | SRM456 Medium: CutSticks - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM456 Medium: CutSticks - naoya_t@topcoder SRM456 Medium: CutSticks - naoya_t@topcoder のブックマークコメント

  • なんか最初単峰性の何かを想像してて、どこで最大になるか求めようとしていた
  • 既存の棒の長さを順番に試していって、どこまで行けるか(というか求める値がどことどこの間か)という問題に脳内修正
  • ということは要は任意の値でどこまで行けるか、に脳内修正
  • ま、二分探索さ。最初から分かっていたさw
  • どこまで「何が」行けるかの計算に悩んでてごにょごにょしてるうちに時間切れ
  • Challenge Phase無視
  • Practice room
    • 最初の棒の本数(N)が多いときに変な値が出る → 二分探索の最小値が小さすぎて、割り算した結果がINT_MAXより大きくなる → 無限大表現に INT_MAX/N を使うか(※素直にlong longにしとけばいいものを)
    • 最初の本数が少ないときに小さい値が出る → 大きい棒を切ることで順位が変わるのにstick[K](※並べ替え済)を返していた。お馬鹿
    • Cが大きいときに変な値が出る →そろそろlong longにしないと無理ですか
    • 答えが1e8みたいに大きくなる時に二分探索が止まらない → 終了条件がhi-lo>1e-9とか駄目ですってば
    • 5度目の正直でpassed
    • 続きを読む

SRM456 Easy: SilverDistance

| 20:46 | SRM456 Easy: SilverDistance - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM456 Easy: SilverDistance - naoya_t@topcoder SRM456 Easy: SilverDistance - naoya_t@topcoder のブックマークコメント

  • 45度傾けたら超簡単だった
  • 格子点以外への行き方が1通りしかない
  • マンハッタン距離 + 格子点でなければ+1
  • 続きを読む

SRM455 Easy(300): DonutsOnTheGridEasy

| 22:00 | SRM455 Easy(300): DonutsOnTheGridEasy - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM455 Easy(300): DonutsOnTheGridEasy - naoya_t@topcoder SRM455 Easy(300): DonutsOnTheGridEasy - naoya_t@topcoder のブックマークコメント

  • 問題激しく読み違えてた...ドーナツが幾つ取れるか数えようとしてた。重箱状の階層の深さの最大を求めるだけだった。
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)

// memoize..
char z[50][50][51][51], mp[50][50][51][51];

class DonutsOnTheGridEasy {
  vector<string> gr;
  int R,C;
  
  int isZeroShape(int r,int c,int h,int w){
    if (h<3 || w<3) return 0;
    if (z[r][c][h][w]>=0) return z[r][c][h][w]; // memo

    int re=1;
    
    rep(j,h) { int y=r+j;
      if (gr[y][c]=='.') {re=0; goto end;}
      if (gr[y][c+(w-1)]=='.') {re=0; goto end;}
    }
    rep(i,w) { int x=c+i;
      if (gr[r][x]=='.') {re=0; goto end;}
      if (gr[r+(h-1)][x]=='.') {re=0; goto end;}
    }
 end:
    return z[r][c][h][w] = re;
  }

  int sub(int r,int c,int h,int w){
    if (h<3 || w<3) return 0;
    if (mp[r][c][h][w]>=0) return mp[r][c][h][w]; // memo

    int ct=0; if (isZeroShape(r,c,h,w)) ct=1+sub(r+1,c+1,h-2,w-2);
    FOR(hj,1,h-1) ct = max(ct, max(sub(r,c,hj,w),sub(r+hj,c,h-hj,w)));
    FOR(wj,1,w-1) ct = max(ct, max(sub(r,c,h,wj),sub(r,c+wj,h,w-wj)));

    mp[r][c][h][w] = ct;
    return ct;
  }
 public:
  int calc(vector<string> grid) {
    R=sz(grid), C=sz(grid[0]);
    gr = grid;

    // clean up
    memset(z,255,sizeof(z)); memset(mp,255,sizeof(mp));

    return sub(0,0,R,C);
  }
};

SRM456

13:53 | SRM456 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM456 - naoya_t@topcoder SRM456 - naoya_t@topcoder のブックマークコメント

12.23.2009

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 SilverDistance 諦めたので試合終了 - -
1 450 CutSticks 間に合わず - - -
1 1050 - 開いてない -

rng_58rng_582009/12/24 19:36C = 2 のとき、奇数なら1を足す関数
f(x) = x + ((x%2 == 0) ? 0 : 1)
とかが条件を満たします

n4_tn4_t2009/12/25 11:49問題作成者様直々にコメントありがとうございます!!
なるほどそういうのもアリですね。頭固かったです。

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091223

2009-12-18

Member SRM455

13:55 | Member SRM455 - naoya_t@topcoder を含むブックマーク はてなブックマーク - Member SRM455 - naoya_t@topcoder Member SRM455 - naoya_t@topcoder のブックマークコメント

12.17+.2009

あとで書く書く

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 easy x a - -
1 medium y b - - -
1 hard z c -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091218

2009-12-06

SRM454

12:26 | SRM454 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM454 - naoya_t@topcoder SRM454 - naoya_t@topcoder のブックマークコメント

12.05+.2009

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 DoubleXor o - passed 195.66
1 500 NumbersAndMatches 間に合わず - - -
1 1000 - 開いてない -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091206