naoya_t@topcoder

2008-12-25

SRM399 Div1 Easy: AvoidingProduct

走査範囲が狭くてシステムテスト落ち。書き直しの刑。（書き直しなのに6分17秒もかかったorz）

class AvoidingProduct {
public:
  vector<int> getTriple(vector<int> a, int n) {
    int dmin = 1000;
    int uplim = 2000+a[0]+1; //2000あれば大丈夫っぽい
    
    set<int> s; tr(a,it) s.insert(*it); // NGリスト

    int amin=1001;
    for(int i=1;i<=1000;i++) {
      if (s.find(i)==s.end()) {amin=i;break;}
    }
    int am3=amin*amin*amin;
    if (am3>n) { vector<int> ans(3,amin); return ans; }

    vector<int> ans(3,-1);

    for(int x=1;x<=uplim;x++){
      if (s.find(x)!=s.end()) continue;
      for(int y=x;y<=uplim;y++){
        if (s.find(y)!=s.end()) continue;
        int xy = x*y;
        if(xy>uplim) break;
        for(int z=y;z<=uplim;z++){
          if (s.find(z)!=s.end()) continue;
          int xyz = xy * z;
          if(xyz>uplim) break;
          int d = abs(n-xyz);
          if (d<dmin) {
            dmin = d;
            ans[0]=x; ans[1]=y; ans[2]=z;
          }
        }
      }
    }
    return ans;
  }
};

SRM400 Div1 Easy: StrongPrimePower

過去問, 練習 | 18:04 |

ある数が素数の累乗(２乗以上）かを調べる。pow()とか出てこなくて12分ぐらいかかった。（けれど一発で通った）

素数判定にはMiller-Rabinを使っている。


template <typename T> T expt(T x, int n) // x^n
{
  T y=1; for(int i=0;i<n;i++) y*=x; return y;
}

////
long long random(long long n)
{
  return (long long)rand() % n;
}
long long check_nontrivial_sqrt_1(long long m, long long a)
{
  long long r = (a * a) % m;
  return (1LL < a && a < m-1 && r == 1)? 0LL : r;
}
long long expmod(long long base, long long exp, long long m)
{
  if (exp == 0)
    return 1LL;
  else if (!(exp & 1))
    return check_nontrivial_sqrt_1(m,expmod(base,exp/2,m));
  else
    return (base*expmod(base,exp-1,m)) % m;
}
bool miller_rabin_test(long long n)
{
  return expmod((1LL+random(n-1)),n-1,n) == 1LL;
}
bool fast_prime(long long n, int times)
{
  if (n == 1) return false;
  if (n == 2) return true;
  else if (!(n & 1)) return false;
  
  for (int i=times; i>0; i--)
        if (!miller_rabin_test(n)) return false;
  return true;
}
////

class StrongPrimePower {
public:
  vector<int> baseAndExponent(string n) {
    long long n_ = 0; // 2-10^18=1000^6<2^60
    for(int i=0;i<n.length();i++) {n_*=10; n_+=n[i]-'0';}

    for (int q=59;q>=2;q--) {
      double q_ = 1.0 / q;
      double d_ = pow(n_,q_); long long p = (long long)(d_ + 0.0001);
      if (p == 0) continue;
      if (!fast_prime(p,3)) continue;
      if (expt(p,q)==n_) {
        vector<int> ans(2);
        ans[0]=p; ans[1]=q; return ans;
      }
    }
    vector<int> ans; return ans;
  }
};

SRM401 Div1 Easy: FIELDDiagrams

過去問, 練習 | 18:04 |

DP。単純な問題だが手間取っている。DPでいきなりコーディングは空中分解しがち。

#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++)

class FIELDDiagrams {
public:
  int fo;
  vector<long long> memo;

  long long sub(int last,int fieldOrder){
    int ceil = min(last,fieldOrder);
    if (ceil == 0) { return 1;}

    int key=(ceil<<5)|fieldOrder;
    if (memo[key]>=0) return memo[key];
    long long count=1LL;
    for(int ai=ceil;ai>0;ai--){
      count += sub(ai,fieldOrder-1);
    }
    return memo[key] = count;
  }
  
  long long countDiagrams(int fieldOrder) {
    fo = fieldOrder;
    memo.resize(1024); fill(all(memo),-1);

    long long count = 0LL;
    for (int a1=fieldOrder;a1>0;a1--) {
      count += sub(a1, fieldOrder-1);
    }
    return count;
  }
};

SRM402 Div1 Easy: RandomSort

過去問, 練習 | 18:04 |

DP的問題。メモ化しないとTLE。状態の数はn^nあるが、vector<double>だとメモリ64MB制限に引っかかる。map<int,double>で必要なものだけメモ化するのが吉。

#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++)

template <typename T> T expt(T x, int n) // x^n
{
  T y=1; for(int i=0;i<n;i++) y*=x; return y;
}

class RandomSort {
  int n;
  vector<int> perm;
  //vector<double> memo;
  map<int,double> memo;

  int sig() {
    int s=0;
    tr(perm,it) s=s*n+(*it-1);
    return s;
  }
  double sw(){
    int key=sig();
    // if(memo[key]>=0) return memo[key];
    if(memo.find(key)!=memo.end()) return memo[key];

    set<pair<int,int> > s;
    rep(i,n){
      int p = perm[i];
      for(int j=i+1;j<n;j++){
        int q = perm[j];
        if (p>q) s.insert(make_pair(i,j));
      }
    }
    if (s.size() == 0) return memo[key] = 0;
    
    double cnt=0;
    tr(s,it){
      int i=it->first, j=it->second;
      int p=perm[i], q=perm[j];
      perm[i]=q; perm[j]=p;
      cnt += 1 + sw();
      perm[i]=p; perm[j]=q;
    }

    cnt /= s.size();
    return memo[key] = cnt;
  }
public:
  double getExpected(vector<int> permutation) {
    n=sz(permutation);
    perm = permutation;
    return sw();
  }
};

SRM403 Div1 Easy: TheLuckyNumbers

過去問, 練習 | 18:04 |

10^9のループではTLEになるであろう数え上げ系。すこし手間取った(141.71points)。

こういうので200点以上とれるようになりたい。

int c(int n, int r)
{
  if (n == 0 || r == 0 || r == n) return 1;
  if (r > n-r) r = n-r;
  return n * c(n-1,r-1) / r;
}
int expt(int x,int n){
  int v=1; rep(i,n) v*=x; return v;
}

class TheLuckyNumbers {
public:
  int s_(int k,int n){
    int cnt=0;
    rep(i,1<<k){
      int u=0,m=1<<(k-1);
      rep(j,k){u*=10; u+=(i&m)?7:4; m>>=1;}
      if (n>=u) cnt++; else break;
    }
    return cnt;
  }
  int s(int k){
    return expt(2,k);
  }
  int lns(int n){
    if (n<4) return 0;
    if (n<7) return 1;
    if (n<44) return 2;
    if (n>777777777) n=777777777;

    int k=0,t=0,o=1;
    int n_=n;
    while(n_>0){ t=n_; n_/=10; o*=10; k++; }
    o = (o-1)/9;
    int o4=o*4, o7=o*7;
    int kt=k;
    int cnt=0;
    if (n<o7) {
      kt--;
      if (n>=o4) {
        cnt += s_(k,n);
      }
    }
    rep(i,kt) cnt+=s(i+1);
    return cnt;
  }
  int count(int a, int b) {
    return lns(b)-lns(a-1);
  }
};

SRM404 Div1 Easy: RevealTriangle

過去問, 練習 | 18:04 |

覆面算的な問題、と思ったけどそう難しくない。逆三角形の下から解いて行ける。

class RevealTriangle {
public:
  vector<string> calcTriangle(vector<string> questionMarkTriangle) {
    int rows=questionMarkTriangle.size(); //1-50

    vector<vector<int> > v(rows);
    rep(row,rows){
      v[row].resize(rows-row);
      rep(i,rows-row){
        int c = questionMarkTriangle[row][i]-'0';
        v[row][i] = (c < 0||9<c)?-1:c;
      }
    }

    for(int row=rows-1;row>=0;row--){
      int l=rows-row;
      string qmt= questionMarkTriangle[row];
      rep(z,l){
        rep(i,l) {
          if (v[row][i]<0) {
            if (i>0 && v[row][i-1]>=0) {
              v[row][i] = (10 + v[row+1][i-1] - v[row][i-1])%10;
            } else if (i+1<l && v[row][i+1]>=0) {
              v[row][i] = (10 + v[row+1][i] - v[row][i+1])%10;
            }
          }
        }
      }
    }
    vector<string> result(rows,"");
    rep(row,rows){
      stringstream ss;
      rep(i,rows-row) ss << (char)(48+v[row][i]);
      result[row] = ss.str();
    }
    return result;
  }
};

SRM405 Div1 Easy: RelativePath

過去問, 練習 | 18:04 |

カレントパスをもとに絶対パスから相対パスを求める問題。

class RelativePath {
public:
  string makeRelative(string path, string currentDir) {
    vector<string> vp = split(path,'/'), vcd = split(currentDir,'/');
    int lp=sz(vp), lcd=sz(vcd);
    int common=0;
    if(currentDir=="/") { lcd=1; common=0;}
    else
      for(int i=1;i<min(lp,lcd);i++){
        if(vp[i]!=vcd[i]) break;
        common++;
      }
    string dest=""; rep(i,lcd-1-common) dest+="../";
    for(int i=1+common;i<lp;i++) {dest+=vp[i];if(i<lp-1)dest+="/";}
    return dest;
  }
};

SRM406 Div1 Easy: SymmetricPie

過去問, 練習 | 18:04 |

next_permutationを使ってBrute Force

class SymmetricPie {
public:
  int getLines(vector<int> dogs) {
    int N=sz(dogs);
    sort(all(dogs));
    int maxcnt=0;
    while(1) {
      int cnt=0;
      vector<int> ac(N+1,0); ac[0]=0;
      for(int i=0;i<N;i++) ac[i+1]=ac[i]+dogs[i];
      for(int i=0;i<N;i++) {
        if (ac[i]<50){
          for(int j=i+1;j<=N;j++) {
            if (ac[j]-ac[i]==50) cnt++;
          }
        }
      }
      if (maxcnt<cnt) maxcnt=cnt;
      if (!next_permutation(all(dogs))) break;
    }
    return maxcnt;
  }
};

SRM407 Div1 Easy: CorporationSalary

過去問, 練習 | 18:04 |

再帰的に計算。メモ化。

class CorporationSalary {
  int N;
  vector<long long> salary;
  vector<vector<bool> > t;

  long long decide_salary(int id){
    if (salary[id] > 0) return salary[id];
    long long s=0LL;
    rep(j,N){
      if(t[id][j]) s+=decide_salary(j);
    }
    if (s==0LL) s=1LL;
    return salary[id] = s;
  }
public:
  long long totalSalary(vector<string> relations) {
    N = relations.size(); //1-50

    t.resize(N); tr(t,it) it->resize(N);
    rep(i,N) rep(j,N) t[i][j]=(relations[i][j]=='Y');

    salary.resize(N); tr(salary,it) *it=0;

    long long total=0LL;
    rep(i,N) total+=decide_salary(i);
    return total;
  }
};

SRM408 Div1 Easy: OlympicCandles

過去問, 練習 | 18:04 |

超簡単・・・なはずがSTLの操作でつまづく。

vector<int>から値が0の要素を削除するだけの簡単な仕事で。

tr(candles,it) if(!*it) candles.erase(it); →Segmentation Fault
remove(all(candles),0); →消えてないっぽい。なんで？

ゴミを消さないと駄目らしい。従って

class OlympicCandles {
public:
  int numberOfNights(vector<int> candles) {
    for(int nights=1;;nights++){
      sort(all(candles),greater<int>());
      if(candles.size() < nights) return nights-1;

      for(int i=0;i<nights;i++) candles[i]--;
      candles.erase(remove(all(candles),0),candles.end());
    }
  }
};

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

2008-12-24SRM431

SRM431 祝☆YellowCoder

12.23+.2008 (今年最終)

DIV	level	問題名	競技中	備考
1	250	LaserShooting	◎	235.94点
1	500	MegaCoolNumbers	間に合わず
1	1000

250点問題: LaserShooting

数分でできた。（自己最速？）

システムテストも通って235.94点。

#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++)

class LaserShooting {
public:
  double numberOfHits(vector <int> x, vector <int> y1, vector <int> y2) {
    int n=x.size();
    double rate=0;
    for(int i=0;i<n;i++){
      double r1=atan2((double)y1[i],(double)x[i]),
        r2=atan2((double)y2[i],(double)x[i]);
      if (r1>r2) { double tmp=r1;r1=r2;r2=tmp;}
      rate += (r2-r1)/3.141592653589793238462643383279;
    }
    return rate;
  }
};

円周率手打ちです。acos(-1)とかM_PIとか使った方が打鍵数少なくて良いのですが思いつかなくて。すみませんすみません。

500点問題: MegaCoolNumbers

たっぷり（１時間超）時間が使えたけど解けなかった。

あとで続きを考えよう。

部屋で１人もsubmitしていなかった。チャレンジすらできないとは。

［追記］Div1全体でも19人しか通ってない！

1000点問題

開いてない

もしかしたら1000点問題に挑戦してもよかったのかも・・・解けそうかどうか開いてみるだけでも・・・

235.94点で119/526位。

レーティング：1456→1577 祝☆Yellow Coder昇格

これは素敵なクリスマスプレゼント（≒自分へのご褒美）。

次回SRM（来年）ではとりあえず黄色防衛したいので、確実に２問解ける実力（特にスピード）を身につけないと。

来年はRedを目指す！！

SRM410 Div1 Easy: AddElectricalWires

過去問, 練習 | 18:07 |

これ250点問題だけどちょっと難しい。サンプルケースが通った程度では安心できない。通過率も53.71%でMediumより低い。

gridに繋がっているノードをまとめる
- いちばん多く繋がっているgridはどれか
gridに繋がっていないノードは全て、いちばん多く繋がっているgridに繋げる
各gridについて、同じgridに繋がるノードは全て繋ぐ
最初からあるコネクションの数を引く

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#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++)

class AddElectricalWires {
  vector<vector<bool> > w;
  vector<int> gC;
  int nw, ngc;

  void turn(int orig,int dest) {
    rep(i,nw) if (gC[i]==orig) gC[i]=dest;
  }

public:
  int all_connections(int n) { return (n>=2) ? n*(n-1)/2 : 0; }
    
  int maxNewWires(vector<string> wires, vector<int> gridConnections) {
    nw = wires.size(); // 1-50
    ngc = gC.size(); // 1-50

    gC.resize(nw); rep(i,nw) gC[i]=-i-1;
    tr(gridConnections,it) gC[*it]=*it;

    int conn = 0;
    w.resize(nw); tr(w,it) it->resize(nw);
    rep(i,nw) rep(j,nw) {
      w[i][j] = (wires[i][j]=='1');
      if (i<j && w[i][j]) {
        conn++;
        turn(min(gC[i],gC[j]), max(gC[i],gC[j]));
      }
    }
    rep(i,nw) if (gC[i]<0) gC[i] = -1;

    vector<int> count(nw+1,0);
    rep(i,nw) count[1+gC[i]]++;

    int maxc = 0, maxc_at = -1;
    for (int i=1;i<=nw;i++)
      if (count[i] > maxc) {
        maxc = count[i]; maxc_at = i;
      }
    if (maxc_at < 0) {
      return all_connections(nw) - conn;
    } else {
      count[maxc_at] += count[0];
      int ans = 0;
      for (int i=1;i<=nw;i++) ans += all_connections(count[i]);
      return ans - conn;
    }
  }
};

SRM409 Div1 Easy: OrderedSuperString

過去問, 練習 | 18:07 |

酩酊状態で解いたら１時間かかった。バグっててシステムテスト１つ通らず。（→直った）

class OrderedSuperString {
public:
  int getLength(vector<string> words) {
    int n=words.size();

    string w0=words[0];
    int l0=w0.length();
    if(n==1) return l0;
    int a0=0;

    for (int i=1;i<n;i++) {
      string wi=words[i];
      int li=wi.length();
      if (l0>=li) {
        for(int a=a0;a<=l0-li;a++) {
          if(w0.substr(a,li)==wi) {a0=a; goto next;}
        }
      }
      for(int w=min(l0,li-1);w>0;w--){
        if(l0-w<a0)continue;
        if (w0.substr(l0-w,w)==wi.substr(0,w)) {w0+=wi.substr(w,li-w);a0=l0-w;l0+=li-w;goto next;}
      }
      a0 = l0; w0 += wi; l0 += li;
    next:
      ; 
    }
    return l0;
  }
};

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

2008-12-22レーティングはどのように算出されているか

アルゴリズム・コンペティションにおけるレーティングのしくみ

以下、Algorithm Competition Rating Systemからのコピペ（の拙訳）。

まとめると、参加前のレーティングから全体のスコア分布に基づいて推定されるパフォーマンスをどれだけ上回って（あるいは下回って）いるかを調べ、その差分をレーティングに重みつきで（参加歴が浅ければ大きく、長ければ小さく）反映する仕組み、といったところだろうか。

詳しくは以下を読んでほしい。

----

各々のコーダーに関する以下の統計情報が保管されている：

レーティング
変動率（Volatility）
過去にレーティングされた回数

参戦前の新規メンバーのレーティングは暫定的なものである。

コンペティションの後、参加者に対し以下のアルゴリズムが適用される。最初に、過去に参戦したことのあるメンバーのレーティングが計算される。ここでは新規参戦者のパフォーマンスは考慮されない。

次に、新規参戦者のレーティングが、コンペティション参加者全体での個々の相対的なパフォーマンスに基づいて付与される。

コーダーのハンドル名はコンペティション・アリーナ内での各々のレーティングに基づいて色付けされる

各コンペティションの後、参加したコーダー各は以下のアルゴリズムに基づいて再レーティングされる。アルゴリズム・コンペティションでは、同じ問題セットを共有するコーダーのみが互いにレーティングされる点に留意されたい*1。マラソンマッチでは、コーダーは何らかの投稿（exampleもしくはfull）をもってイベントに参加したものとみなされる。イベントに登録しただけではレーティング対象にはならない。コンペティションに参加した全員の平均レーティング（AveRating）が計算される：

ここで NumCoders はコンペティションの参加コーダー数、Rating は各参加コーダーのコンペティション前の変動率を除いたレーティングを表す。

コンペティション係数（CF）の計算：

ここで Volatility は参加コーダーのコンペティション前の変動率（volatility）を表す。

勝利確率（WP）推定アルゴリズム：

ここで Rating1 と Vol1 は比較対象となるコーダーのレーティングおよび変動率、Rating2 と Vol2 は勝利確率を計算するコーダーのレーティングおよび変動率を表す。Erf は「誤差関数*2」。

コンペティションにおいて当該コーダーが他のコーダーより高いスコアを得る確率（WPi|1≦i≦NumCOders）が推定される。

コーダーの期待ランク（ERank）の計算：

コーダーの期待パフォーマンス（EPerf）の計算：

ここで*3は標準正規分布関数の逆関数*4。

各コーダーの実パフォーマンス（APref）の計算：

ここで ARank はコンペティションでのスコアに基づいたコーダーの実ランク（首位なら 1、末位なら NumCoders）を表す。他のコーダーと同点の場合、同点コーダー全員によってカバーされている順位の平均値が用いられる。

コーダーのperformed asレーティング（PerfAs）の計算：

コーダーにとってのコンペティションの重み（Weight）の計算：

ここで TimesPlayed はコーダーがこれまでにレーティングを受けた回数を表す。高レーティングのメンバーを安定させるため、レーティングが2000〜2500のメンバーのウェイトは10%減、レーティング2500超のメンバーのウェイトは20%減とする。

［訳注］参加0回→1.5, 1回→0.6393, 2回→0.47, 3回→0.3986, 4回→0.3587, 5回→0.3333, ... 20回→0.25, ... →9/41=0.21951に収束

変動上限（Cap）の計算：

［訳注］参加0回→900, 1回→650, 2回→525, 3回→450, 4回→400, 5回→364.28, 6回→337.5, 7回→316.6, 8回→300, ... 13回→250, 28回→200, ... →150に収束。*5

コーダーの新しい変動率（NewVolatility）の計算：

コーダーの新しいレーティング（NewRating）の計算：

新レーティングと旧レーティングの差が Cap を超える場合、差が最大でも Cap に収まるように新レーティングが調整される。

SRM417 Div1 Easy: TemplateMatching

過去問, 練習 | 18:08 |

当時Div2の500点問題として解いたけどシステムテストで通らなかった問題。

１から解き直したけどそんなに難しくない。落ち着いて問題を読めば解ける。

250点問題はSTLの練習。沢山解いてスピードをつけたい。

DP、というか再帰とメモ化で解けるパターンを見つける練習が必要。

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#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++)

string strsort(const string &str) {
  vector<char> buf(all(str));
  sort(all(buf));
  string sorted(all(buf));
  return sorted;
}

class SentenceDecomposition {
private:
  int score(string orig, string word) {
    if (strsort(orig) != strsort(word)) return -1;
    int d = orig.length();
    for (int i=d-1; i>=0; i--) if (orig[i] == word[i]) d--;
    return d;
  }
public:
  int len;
  string sent;
  vector<string> valids;
  vector<int> memo;

  int sub(int len) {
    if (len==0) return 0;
    if (memo[len] < INT_MAX) return memo[len];
    int min_score = INT_MAX;
    tr(valids,it) {
      int vl = it->length(); if (vl > len) continue;
      int subsc = sub(len-vl); if (subsc == INT_MAX) continue;
      int sc = score(*it,sent.substr(len-vl,vl)); if (sc == -1) continue;
      sc += subsc; if (sc < min_score) min_score = sc;
    }
    memo[len] = min(memo[len], min_score);
    return min_score;
  }

  int decompose(string sentence, vector<string> validWords) {
    sent = sentence; len = sentence.length();
    valids = validWords;
    memo.resize(len+1); fill(all(memo),INT_MAX);

    int topscore = sub(len);
    return (topscore == INT_MAX)? -1 : topscore;
  }
};

以下、最初に書いたコード。このコードで（何度か修正した末）システムテストも全て通るようになったが、TopCoderの統計情報を見たらこの問題はDPに分類されているので、書き直して上のコードになった。

#include <string>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;

#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++)

bool greater_by_length(const string& s1, const string& s2 )
{
  return s1.length() > s2.length();
}
template <typename T> struct better : binary_function<T,T,bool> {
  bool operator()(const T& X, const T& Y) const{
    // at, score
    if (X.first >= Y.first) return X.second < Y.second;
    return false;
  }
};

string strsort(const string &str) {
  vector<char> buf(all(str));
  sort(all(buf));
  string sorted(all(buf));
  return sorted;
}

class SentenceDecomposition {
private:
  bool abc[26];
  bool usable(const string &str) {
    rep(i,str.length()) if (!abc[str[i]-'a']) return false;
    return true;
  }


  int score(string orig, string word) {
    int d = orig.length();
    for (int i=d-1; i>=0; i--) if (orig[i] == word[i]) d--;
    return d;
  }
public:
  int decompose(string sentence, vector<string> validWords) {
    int l=sentence.length();

    rep(i,26) abc[i] = false;
    rep(i,l) abc[sentence[i]-'a'] = true;

    set<string> s;
    tr(validWords,wt) if (usable(*wt)) s.insert(*wt);

    vector<string> valids(all(s));
    sort(all(valids),greater_by_length);

    int n=valids.size();
    vector<string> words(n);
    rep(i,n) {
      words[i] = strsort(valids[i]);
    }
    priority_queue<pair<int,int>, vector<pair<int,int> >, better<pair<int,int> > > pq;

    vector<int> said(l+1,INT_MAX);

    rep(i,n) {
      int wl = words[i].length();
      if (0+wl <= l) {
        string ss = sentence.substr(0,wl);
        if (strsort(ss) == words[i]) {
          int sc = score(valids[i],ss);
          if (sc < said[wl]) {
            pair<int,int> p = make_pair(wl,sc);
            pq.push(p);
            said[wl] = sc;
          }
        }
      }
    }

    int topscore = INT_MAX;

    while (!pq.empty()) {
      int at = pq.top().first, pt = pq.top().second;
      pq.pop();

      if (at == l) {
        topscore = min(topscore,pt);
        continue;
      }

      rep(i,n) {
        int wl = words[i].length();
        if (at+wl <= l) {
          string ss = sentence.substr(at,wl);
          if (strsort(ss) == words[i]) {
            int newscore = pt+score(valids[i],ss);
            if (newscore < topscore) {
              if (newscore < said[at+wl]) {
                pair<int,int> p = make_pair(at+wl,newscore);
                pq.push(p);
                said[at+wl] = newscore;
              }
            }
          }
        }
      }
    }

    return (topscore == INT_MAX)? -1 : topscore;
  }
};

*1：DIV1,DIV2の区別のことか

*2：error function

*3：Φ

*4：the inverse of the standard normal function

*5：初回暫定レーティングが1200なので、Petrを抜くのに必要な最短参加回数は４回（1200→2100→2750→3275→3725）。そんな強者がいればの話だが

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

2008-12-21SRM430

SRM430

12.20+.2008

システムの異常で誰もentryできないまま数分が経過したため、今日のSRMは５分延長。

DIV	level	問題名	競技中	後で	System Test	通過率	備考
1	250	BitwiseEquations	◎			74.89%
1	500	TwinTowns	間に合わず	o	passed	19.69%	12/21 https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081221/p2
1	1000	(PickingUp)	-			24.19%

250点問題: BitwiseEquations

→OK。186.96点

そう難しい問題ではないが、オーバーフローが怖くて変な所で切ってしまっていたため数が合わず若干手間取る。

500点問題: TwinTowns

→未提出

題意は理解した。

全パターン探索でいいかなと思ってコーディング。

パターン生成が狂っていて焦る。時間切れ。

今日はチャレンジタイムが大荒れ。室内の500点は全滅。

System Testが通って、結果は全体で365/742位。１問しか解けなかったけど真ん中より少し上。

レーティングは微上昇：1425→1456

SRM430 Div1 Medium: TwinTowns

過去問, 練習 | 18:09 |

とりあえず500点問題をちゃんと解いてみる

あれこれ試行錯誤した末、各都市の姉妹都市提携数（あるいは提携可能な余地）を状態として持つDPで書き直した。

全n都市の中から都市を１つ選ぶ
残りのn-1都市の中からk個の都市（0≦k≦(maxPartners-その都市が既に提携している都市の数)）を選ぶ各組合せについて、
各都市の姉妹都市提携数にこの組合せを加えたものをもとに、
都市数が１つ少ない場合について、提携最大数および最短合計距離を算出する。
算出結果（提携最大数、最短合計距離）に、この都市からの姉妹提携都市関係を加えて返す。

最初は vector<int> で回していたが、高速化＆メモ化のために long longにパックして回すようにした。

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;

#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++)

inline int get_at(long long arcs, int idx)
{
  return (arcs >> (idx * 2)) & 0x3;
}
inline long long set_at(long long arcs, int idx, int val)
{
  long long mask = 3LL << (idx * 2);
  long long vall = (long long)val << (idx * 2);
  return (arcs & (~mask)) | vall;
}

class TwinTowns {
  int n, maxP;
  int distance[10][10];
  bool available[10][10];

  map<long long,int> memo;

private:
  int findMaximum(long long arcs, int till) {
    if (till == 0) return 0;

    long long key = (arcs << 4) | till;
    if (memo.find(key) != memo.end()) return memo[key];

    int pmax = 0, dmin = INT_MAX;//D_INFTY;
    int count = get_at(arcs,till);

    long long arcs_ = arcs;

    int pat_max = (1 << till) - 1;
    int c_max = maxP - count;

    int arcs_mask = (1 << (till*2)) - 1;

    for (int pat=0; pat<=pat_max; pat++) {
      int c = __builtin_popcount(pat);
      if (c > c_max) continue;

      int d = 0;
      for (int i=0,m=1;i<till;i++,m<<=1) {
        if ((pat & m) == 0) continue;
        if (! available[till][i]) goto next_pat;
        if (get_at(arcs_,i) == maxP) goto next_pat;

        arcs_ = set_at(arcs_, i, get_at(arcs_,i) + 1);
        d += distance[till][i];
      }

      {
        int ans = findMaximum(arcs_ & arcs_mask, till-1);
        int ans_p = c + (ans & 31), ans_d = d + (ans >> 5);
        if (ans_p > pmax) {
          pmax = ans_p; dmin = ans_d;
        } else if (ans_p == pmax) {
          if (ans_d < dmin) dmin = ans_d;
        }
      }
    next_pat:
      arcs_ = arcs;
    }

    int ans = (dmin << 5) | pmax;
    memo[key] = ans;
    return ans;
  }
  
public:
  vector<int> optimalTwinTowns(vector<int> x, vector<int> y, int maxPartners, int minDistance) {
    n = x.size();
    if (n == 1) {
      vector<int> ans(2,0);
      return ans;
    }

    maxP = min(maxPartners,n-1);
    rep(i,n) rep(j,n) available[i][j] = false;

    rep(j,n) {
      rep(i,n) {
        if (i == j) continue;
        int dist = abs(x[i]-x[j]) + abs(y[i]-y[j]); // 1-2000
        if (dist >= minDistance) {
          distance[i][j] = distance[j][i] = dist;
          available[i][j] = available[j][i] = true;
        }
      }
    }

    int a = findMaximum(0, n-1);
    vector<int> ans(2,0);
    ans[0] = a & 31; ans[1] = a >> 5;
    return ans;
  }
};

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

2008-12-12SRM429

SRM429：祝・２問通過

12.11+.2008 http://blog.livedoor.jp/naoya_t/archives/51086650.html

DIV	level	問題名	競技中	後で	備考
1	250	SubrectanglesOfTable	◎		91.41%
1	500	IngredientProportions	◎
1	1000		-	-

250点問題: SubrectanglesOfTable

→OK。202.35点

これは簡単。~

初めて１時間超を残して500点問題に臨む。

500点問題: IngredientProportions

→OK。199.65点

やるべき事は分かる。~

9^10 > 2^31-1 なので怖いから long long で計算。unsigned int でもいいと思うけど。~

６分ぐらい残して提出。残り時間でチャレンジのネタを考える。~

しかしチャレンジできそうな人がいない。とりあえず撃墜は免れた。

System Test... 初めて２問通過。合計402.0点で226/678位。レーティング上昇確実！

レーティング：1314 → 1425

黄色には届かなかったけれどこの調子で。

教訓

直前の１時間に過去問を解くのはよいウォーミングアップ

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

		2020/01
日	月	火	水	木	金	土
			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

2008-12-24SRM431

250点問題: LaserShooting

500点問題: MegaCoolNumbers

1000点問題

2008-12-22レーティングはどのように算出されているか

新しいレーティングは以下のように算出される：

コンペティション係数（CF）の計算：

勝利確率（WP）推定アルゴリズム：

コーダーの期待ランク（ERank）の計算：

コーダーの期待パフォーマンス（EPerf）の計算：

各コーダーの実パフォーマンス（APref）の計算：

コーダーのperformed asレーティング（PerfAs）の計算：

コーダーにとってのコンペティションの重み（Weight）の計算：

変動上限（Cap）の計算：

コーダーの新しい変動率（NewVolatility）の計算：

コーダーの新しいレーティング（NewRating）の計算：

2008-12-21SRM430

250点問題: BitwiseEquations

500点問題: TwinTowns

2008-12-12SRM429

250点問題: SubrectanglesOfTable

500点問題: IngredientProportions

教訓