Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2008-12-30

SRM382 Div1 Easy: CollectingRiders

| 03:01 | SRM382 Div1 Easy: CollectingRiders - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM382 Div1 Easy: CollectingRiders - naoya_t@topcoder SRM382 Div1 Easy: CollectingRiders - naoya_t@topcoder のブックマークコメント

問題読み違えてた。これ本番に1時間15分で解けるだろうか。

続きを読む

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

2008-12-29

SRM383 Div1 Easy: Planks

| 23:55 | SRM383 Div1 Easy: Planks - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM383 Div1 Easy: Planks - naoya_t@topcoder SRM383 Div1 Easy: Planks - naoya_t@topcoder のブックマークコメント

Plankとは厚い板のこと。

続きを読む

SRM384 Div1 Easy: Library

| 23:39 | SRM384 Div1 Easy: Library - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM384 Div1 Easy: Library - naoya_t@topcoder SRM384 Div1 Easy: Library - naoya_t@topcoder のブックマークコメント

簡単。split()は自前

続きを読む

SRM385 Div1 Easy: UnderscoreJustification

| 23:10 | SRM385 Div1 Easy: UnderscoreJustification - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM385 Div1 Easy: UnderscoreJustification - naoya_t@topcoder SRM385 Div1 Easy: UnderscoreJustification - naoya_t@topcoder のブックマークコメント

これは速解き系なんだろうな。

最近、慣れてきたのかコードが汚くなってきた。(スペースの数が減ったりとか)

続きを読む

SRM386 Div1 Easy: CandidateKeys

| 17:52 | SRM386 Div1 Easy: CandidateKeys - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM386 Div1 Easy: CandidateKeys - naoya_t@topcoder SRM386 Div1 Easy: CandidateKeys - naoya_t@topcoder のブックマークコメント

(statistics)

問題の意味がなかなか掴めなくて悩む。

サンプルのTest Caseは通るけどシステムテストが通らない←いまここ

後でやり直そう。

続きを読む

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

2008-12-26

SRM387 Div1 Easy (300points): MarblesRegroupingEasy

| 19:55 | SRM387 Div1 Easy (300points): MarblesRegroupingEasy - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM387 Div1 Easy (300points): MarblesRegroupingEasy - naoya_t@topcoder SRM387 Div1 Easy (300points): MarblesRegroupingEasy - naoya_t@topcoder のブックマークコメント

どう解いたらよいのかぱっとは思いつかない。

全てのmarblejoker boxに放り込む(move回数はN-1)のが手数としては最大になるのかな、というところまで。あとで考えよう。

SRM391 Div1 Easy: IsomorphicWords

| 09:42 | SRM391 Div1 Easy: IsomorphicWords - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM391 Div1 Easy: IsomorphicWords - naoya_t@topcoder SRM391 Div1 Easy: IsomorphicWords - naoya_t@topcoder のブックマークコメント

問題を読み違えていて問題文のTest Caseすら通らず焦る。

続きを読む

SRM392 Div1 Easy: TwoStringMasks

| 08:46 | SRM392 Div1 Easy: TwoStringMasks - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM392 Div1 Easy: TwoStringMasks - naoya_t@topcoder SRM392 Div1 Easy: TwoStringMasks - naoya_t@topcoder のブックマークコメント

文字列操作。split()は自前

続きを読む

split()

| 08:51 | split() - naoya_t@topcoder を含むブックマーク はてなブックマーク - split() - naoya_t@topcoder split() - naoya_t@topcoder のブックマークコメント

私家版split()関数。

まずはデリミタがintのもの。

省略時には空白をデリミタとして認識する。

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

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;
}

次は文字列(string)をデリミタに取るもの。

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

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

  if (str.length() == 0) return result;

  if (delim.length() == 0) {
    int len = str.length();
    result.resize(len);
    for (int i=0; i<len; i++) result[i] = str.substr(i,1);
    return result;
  }

  int since = 0, at;
  while ((at = str.find(delim, since)) != string::npos) {
    result.push_back(str.substr(since, at-since));
    since = at + delim.length();
  }
  result.push_back(str.substr(since));

  return result;
}

自由に使っていいけど無保証。ご利用は計画的に。

おまけ

googletestもつけとくよ。

#include <gtest/gtest.h>

// テストケースを単体の関数として実装する
TEST(SplitTest, Split1)
{
  vector<string> result;

  result = split("", "<>");
  EXPECT_EQ( 1, result.size() );
  
  // "a","<>" => ["a"]
  result = split("a", "<>");
  EXPECT_EQ( 1, result.size() );
  EXPECT_EQ( "a", result[0] );
  
  // "a<>b<>c","<>" => ["a","b","c"]
  result = split("a<>b<>c", "<>");
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  EXPECT_EQ( "c", result[2] );
  
  // "a<>b<>c<>","<>" => ["a","b","c",""]
  result = split("a<>b<>c<>", "<>");
  EXPECT_EQ( 4, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  EXPECT_EQ( "c", result[2] );
  EXPECT_EQ( "" , result[3] );
  
  // "<>a<>b<>c","<>" => ["","a","b","c"]
  result = split("<>a<>b<>c", "<>");
  EXPECT_EQ( 4, result.size() );
  EXPECT_EQ( "" , result[0] );
  EXPECT_EQ( "a", result[1] );
  EXPECT_EQ( "b", result[2] );
  EXPECT_EQ( "c", result[3] );
  
  // "<>a<>","<>" => ["","a",""]
  result = split("<>a<>", "<>");
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "" , result[0] );
  EXPECT_EQ( "a", result[1] );
  EXPECT_EQ( "" , result[2] );
  
  // "a<><>b","<>" => ["a","","b"]
  result = split("a<><>b", "<>");
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "" , result[1] );
  EXPECT_EQ( "b", result[2] );
  
  // "<>","<>" => ["",""]
  result = split("<>", "<>");
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "", result[0] );
  EXPECT_EQ( "", result[1] );
  //
  result = split("", "");
  EXPECT_EQ( 0, result.size() );
  
  // 特殊用法 "abc".split('')
  result = split("abc", "");
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  EXPECT_EQ( "c", result[2] );
  // EXPECT_TRUE_EQUAL( 2, 2 );
}

TEST(SplitTest, Split2)
{
  // cout << "test_split()" << endl;
  // dump_vs(result);
  vector<string> result;

  // "" => []
  result = split("");
  EXPECT_EQ( 0, result.size() );
  // "a" => ["a"]
  result = split("a");
  EXPECT_EQ( 1, result.size() );
  EXPECT_EQ( "a", result[0] );
  // "a b c" => ["a","b","c"]
  result = split("a b c");
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  EXPECT_EQ( "c", result[2] );
  // "a " => ["a"]
  result = split("a ");
  EXPECT_EQ( 1, result.size() );
  EXPECT_EQ( "a", result[0] );
  // " a" => ["a"]
  result = split(" a");
  EXPECT_EQ( 1, result.size() );
  EXPECT_EQ( "a", result[0] );
  // " a " => ["a"]
  result = split(" a ");
  EXPECT_EQ( 1, result.size() );
  EXPECT_EQ( "a", result[0] );
  // "a b" => ["a","b"]
  result = split("a b");
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  // "a  b" => ["a","b"]
  result = split("a  b");
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  
  // "a b c",'b' => ["a "," c"]
  result = split("a b c",'b');
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "a ", result[0] );
  EXPECT_EQ( " c", result[1] );
  
  // "a,b",',' => ["a","b"]
  result = split("a,b", ',');
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  // "a,,b",',' => ["a","","b"]
  result = split("a,,b", ',');
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "" , result[1] );
  EXPECT_EQ( "b", result[2] );
  // ",a",',' => ["","a"]
  result = split(",a", ',');
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "" , result[0] );
  EXPECT_EQ( "a", result[1] );
  // "a,",',' => ["a",""]
  result = split("a,", ',');
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "" , result[1] );
  // ",a,",',' => ["","a",""]
  result = split(",a,", ',');
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "" , result[0] );
  EXPECT_EQ( "a", result[1] );
  EXPECT_EQ( "" , result[2] );
}

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

  return RUN_ALL_TESTS();
}

SRM393 Div1 Easy: InstantRunoffVoting

| 06:39 | SRM393 Div1 Easy: InstantRunoffVoting - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM393 Div1 Easy: InstantRunoffVoting - naoya_t@topcoder SRM393 Div1 Easy: InstantRunoffVoting - naoya_t@topcoder のブックマークコメント

問題文のルールを素直にコーディングしたら解ける問題。のはずがちょっと手間取り。

続きを読む

SRM395 Div1 Easy: StreetWalking

| 05:19 | SRM395 Div1 Easy: StreetWalking - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM395 Div1 Easy: StreetWalking - naoya_t@topcoder SRM395 Div1 Easy: StreetWalking - naoya_t@topcoder のブックマークコメント

これは速解き問題。Test Caseが親切。(斜め/\に進んだほうが速いケースとか)

class StreetWalking {
public:
  long long minTime(int X, int Y, int walkTime, int sneakTime) {
    if(X>Y)swap(X,Y);
    long long a=Y-X, b=X, h=a/2, m=a%2;
    long long t = min(b*2*walkTime, b*sneakTime) 
      + min(a*walkTime, h*2*sneakTime+m*walkTime);
    return t;
  }
};

SRM396 Div1 Easy: DNAString

| 04:46 | SRM396 Div1 Easy: DNAString - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM396 Div1 Easy: DNAString - naoya_t@topcoder SRM396 Div1 Easy: DNAString - naoya_t@topcoder のブックマークコメント

よくわからないままコーディングしてたらTest Case全て通ったので投稿。システムテストも1発。12分前後。

続きを読む

SRM398 Div1 Easy: CountExpressions

| 03:20 | SRM398 Div1 Easy: CountExpressions - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM398 Div1 Easy: CountExpressions - naoya_t@topcoder SRM398 Div1 Easy: CountExpressions - naoya_t@topcoder のブックマークコメント

夜中ですが。目がさめたので練習でもするかと思い

続きを読む

2008-12-25

SRM399 Div1 Easy: AvoidingProduct

| 18:04 | SRM399 Div1 Easy: AvoidingProduct - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM399 Div1 Easy: AvoidingProduct - naoya_t@topcoder SRM399 Div1 Easy: AvoidingProduct - naoya_t@topcoder のブックマークコメント

走査範囲が狭くてシステムテスト落ち。書き直しの刑。(書き直しなのに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 | SRM400 Div1 Easy: StrongPrimePower - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM400 Div1 Easy: StrongPrimePower - naoya_t@topcoder SRM400 Div1 Easy: StrongPrimePower - naoya_t@topcoder のブックマークコメント

ある数が素数の累乗(2乗以上)かを調べる。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 | SRM401 Div1 Easy: FIELDDiagrams - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM401 Div1 Easy: FIELDDiagrams - naoya_t@topcoder SRM401 Div1 Easy: FIELDDiagrams - naoya_t@topcoder のブックマークコメント

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 | SRM402 Div1 Easy: RandomSort - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM402 Div1 Easy: RandomSort - naoya_t@topcoder SRM402 Div1 Easy: RandomSort - naoya_t@topcoder のブックマークコメント

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 | SRM403 Div1 Easy: TheLuckyNumbers - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM403 Div1 Easy: TheLuckyNumbers - naoya_t@topcoder SRM403 Div1 Easy: TheLuckyNumbers - naoya_t@topcoder のブックマークコメント

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 | SRM404 Div1 Easy: RevealTriangle - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM404 Div1 Easy: RevealTriangle - naoya_t@topcoder SRM404 Div1 Easy: RevealTriangle - naoya_t@topcoder のブックマークコメント

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

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 | SRM405 Div1 Easy: RelativePath - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM405 Div1 Easy: RelativePath - naoya_t@topcoder SRM405 Div1 Easy: RelativePath - naoya_t@topcoder のブックマークコメント

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

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 | SRM406 Div1 Easy: SymmetricPie - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM406 Div1 Easy: SymmetricPie - naoya_t@topcoder SRM406 Div1 Easy: SymmetricPie - naoya_t@topcoder のブックマークコメント

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 | SRM407 Div1 Easy: CorporationSalary - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM407 Div1 Easy: CorporationSalary - naoya_t@topcoder SRM407 Div1 Easy: CorporationSalary - naoya_t@topcoder のブックマークコメント

再帰的に計算。メモ化。

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 | SRM408 Div1 Easy: OlympicCandles - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM408 Div1 Easy: OlympicCandles - naoya_t@topcoder SRM408 Div1 Easy: OlympicCandles - naoya_t@topcoder のブックマークコメント

超簡単・・・なはずが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());
    }
  }
};

2008-12-24SRM431

SRM431 祝☆YellowCoder

SRM431 祝☆YellowCoder - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM431 祝☆YellowCoder - naoya_t@topcoder SRM431 祝☆YellowCoder - naoya_t@topcoder のブックマークコメント

12.23+.2008 (今年最終)

DIVlevel問題名競技中後でSystem Test通過率備考
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

たっぷり(1時間超)時間が使えたけど解けなかった。

あとで続きを考えよう。

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

[追記]Div1全体でも19人しか通ってない!

1000点問題

開いてない

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

235.94点で119/526位。

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

http://gyazo.com/29e256dea7aafcd74cc4c46955a6f4e0.png

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

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

来年はRedを目指す!!

SRM410 Div1 Easy: AddElectricalWires

| 18:07 | SRM410 Div1 Easy: [http://www.topcoder.com/stat?c=problem_statement&pm=8817&rd=12182:title=AddElectricalWires] - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM410 Div1 Easy: [http://www.topcoder.com/stat?c=problem_statement&pm=8817&rd=12182:title=AddElectricalWires] - naoya_t@topcoder SRM410 Div1 Easy: [http://www.topcoder.com/stat?c=problem_statement&pm=8817&rd=12182:title=AddElectricalWires] - naoya_t@topcoder のブックマークコメント

これ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 | SRM409 Div1 Easy: OrderedSuperString - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM409 Div1 Easy: OrderedSuperString - naoya_t@topcoder SRM409 Div1 Easy: OrderedSuperString - naoya_t@topcoder のブックマークコメント

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

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;
  }
};

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

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

アルゴリズム・コンペティションにおけるレーティングのしくみ - naoya_t@topcoder を含むブックマーク はてなブックマーク - アルゴリズム・コンペティションにおけるレーティングのしくみ - naoya_t@topcoder アルゴリズム・コンペティションにおけるレーティングのしくみ - naoya_t@topcoder のブックマークコメント

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

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

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

----

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

  • レーティング
  • 変動率(Volatility)
  • 過去にレーティングされた回数

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

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

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

http://www.topcoder.com/wiki/download/attachments/4587791/Key.jpg

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

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

レーティングはどのように算出されているか - naoya_t@topcoder を含むブックマーク はてなブックマーク - レーティングはどのように算出されているか - naoya_t@topcoder レーティングはどのように算出されているか - naoya_t@topcoder のブックマークコメント

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

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

http://www.topcoder.com/wiki/download/attachments/4587791/avg.gif

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

コンペティション係数(CF)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/cf.gif

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

勝利確率(WP)推定アルゴリズム:

http://www.topcoder.com/wiki/download/attachments/4587791/wp.gif

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

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

コーダーの期待ランク(ERank)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/er.gif

コーダーの期待パフォーマンス(EPerf)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/ep.gif

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

各コーダーの実パフォーマンス(APref)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/ap.gif

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

コーダーのperformed asレーティング(PerfAs)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/pa.gif

コーダーにとってのコンペティションの重み(Weight)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/wt.gif

ここで 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)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/cap.gif

[訳注]参加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)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/nv.gif

コーダーの新しいレーティング(NewRating)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/nr.gif

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


SRM417 Div1 Easy: TemplateMatching

| 18:08 | SRM417 Div1 Easy: TemplateMatching - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM417 Div1 Easy: TemplateMatching - naoya_t@topcoder SRM417 Div1 Easy: TemplateMatching - naoya_t@topcoder のブックマークコメント

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

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

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

SRM414 Div1 Easy: Embassy

| 18:08 | SRM414 Div1 Easy: Embassy - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM414 Div1 Easy: Embassy - naoya_t@topcoder SRM414 Div1 Easy: Embassy - naoya_t@topcoder のブックマークコメント

formを埋めるのに必要な時間を1日の長さで割った剰余、そして開庁時間によっていくつかのパターンに分かれ・・・るけど1日の長さは高々1000000ユニットなのでBrute Forceで開始時刻を全部試せばいいじゃん・・・で解決。BruteForce万歳!

SRM413 Div1 Easy: ArithmeticProgression

| 18:08 | SRM413 Div1 Easy: ArithmeticProgression - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM413 Div1 Easy: ArithmeticProgression - naoya_t@topcoder SRM413 Div1 Easy: ArithmeticProgression - naoya_t@topcoder のブックマークコメント

テストケース全部通ればOKな感じ。解がない場合に-1を返す件について問題を読み飛ばしていてサンプルケースを見て???となっていた件

SRM412 Div1 Easy: ForbiddenStrings

| 18:08 | SRM412 Div1 Easy: ForbiddenStrings - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM412 Div1 Easy: ForbiddenStrings - naoya_t@topcoder SRM412 Div1 Easy: ForbiddenStrings - naoya_t@topcoder のブックマークコメント

Project Eulerにありそうな問題。解法は思いつくのであとはスピード。

SRM411 Div1 Easy: SentenceDecomposition

| 18:08 | SRM411 Div1 Easy: SentenceDecomposition - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM411 Div1 Easy: SentenceDecomposition - naoya_t@topcoder SRM411 Div1 Easy: SentenceDecomposition - naoya_t@topcoder のブックマークコメント

最初プライオリティキューとか駆使して探索していたが(※2つ目のコード。ちゃんと書かないと全テスト通過できないので、250点にしては難しめでは?と思ったけど)これはDPで書くと超簡単に解ける例。

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を抜くのに必要な最短参加回数は4回(1200→2100→2750→3275→3725)。そんな強者がいればの話だが

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

2008-12-21SRM430

SRM430

SRM430 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM430 - naoya_t@topcoder SRM430 - naoya_t@topcoder のブックマークコメント

12.20+.2008

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

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

250点問題: BitwiseEquations

→OK。186.96点

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

500点問題: TwinTowns

→未提出

題意は理解した。

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

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


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


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


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

http://gyazo.com/e8d7e301ab2c64450dc2e8749f0b8588.png

SRM430 Div1 Medium: TwinTowns

| 18:09 | SRM430 Div1 Medium: TwinTowns - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM430 Div1 Medium: TwinTowns - naoya_t@topcoder SRM430 Div1 Medium: TwinTowns - naoya_t@topcoder のブックマークコメント

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

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

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

最初は 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;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20081221

2008-12-12SRM429

SRM429:祝・2問通過

SRM429:祝・2問通過 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM429:祝・2問通過 - naoya_t@topcoder SRM429:祝・2問通過 - naoya_t@topcoder のブックマークコメント

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

DIVlevel問題名競技中後でSystem Test備考
1 250 SubrectanglesOfTable 91.41%
1 500 IngredientProportions
1 1000 - -

250点問題: SubrectanglesOfTable

→OK。202.35点

これは簡単。~

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

500点問題: IngredientProportions

→OK。199.65点

やるべき事は分かる。~

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

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

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


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


レーティング:1314 → 1425

http://gyazo.com/ccb89894c36c77791bf6a0ce09ab918a.png

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

教訓

  • 直前の1時間に過去問を解くのはよいウォーミングアップ
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20081212

2008-12-11

SRM428 Div1 Medium: TheLongPalindrome

| 18:09 | SRM428 Div1 Medium: TheLongPalindrome - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM428 Div1 Medium: TheLongPalindrome - naoya_t@topcoder SRM428 Div1 Medium: TheLongPalindrome - naoya_t@topcoder のブックマークコメント

  • 奇数長のpalindromeは、それより1つ長い(偶数長の)palindromeと同数のパターンを持つ
  • 剰余計算

まずはナイーブな実装。

#include <vector>
using namespace std;

const long long H = 1234567891LL;
inline long long sub_(long long a, long long b) {
  return (a + H - (b % H)) % H;
}
inline long long add_(long long a, long long b) {
  return (a + b) % H;
}
inline long long mul_(long long a, long long b) {
  return ((long long)(a % H) * (b % H)) % H;
}

long long c_(int n, int r)
{
  if (n == 0 || r == 0 || r == n) return 1;
  if (r > n-r) r = n-r;
  return (c_(n-1,r-1) * n / r) % H;
}
long long expt_(int n, int k) { // n ^ k
  long long p = 1LL;
  for (int i=0; i<k; i++) p = mul_(p, n);
  return p;
}
long long fac_(int n) { // n !
  long long p = 1LL;
  for (int k=n; k>1; k--) p = mul_(p, k);
  return p;
}

class TheLongPalindrome {
private:
  long long f_(int k, int len) {
    if (k == 1) return 1;
    if (k == len) return fac_(k);
    long long t = 0;
    for (int j=k,pm=1; j>=1; j--,pm=-pm)
      t = (t + pm * expt_(j,len) * c_(k,j)) % H;
    return t;
  }

public:
  int count(int n, int k) {
    vector<int> expts(27,1);

    int h = (n + 1) / 2, m = n % 2;
    if (k > h) k = h;

    long long c = 0LL;
    for (int len=1; len<=h; len++) {
      // i:何文字長?
      int k_ = min(len,k); // 字種数
      long long o = 0LL;
      for (int j=1; j<=k_; j++)
        o = add_(o, mul_(c_(26,j), f_(j,len))); // o += 26Cj x f(j,len)
      c = (len == h && m == 1)? add_(c,o) : add_(c,o*2);
    }
    return (int)c;
  }
};
  • サンプルケース4つは通るが、n=1000000000とか渡したら死ぬのは目に見えている
  • 長さlen/2(奇数長の場合は(len+1)/2)の文字列で、1〜k種類の文字が使われる、とは言っても len/2 < k の場合、一度に使える文字数はlen/2種類
  • というわけで len/2 = k の上と下で場合分け
  • 累乗の計算を速いやつに置き換える

ここで関数 f_() がどのように展開されるかを分析し、パラメータから結果が直接得られるような式が書けないか考える。結論から言うと、len/2 > k の部分については、len/2 = [k+1..n/2] の範囲で

26C1 x { 25C0 - 25C1 + 25C2 - ... ± 25C(k-1) } x 1^(len/2)

  1. 26C2 x { 24C0 - 24C1 + 24C2 - ... ± 24C(k-2) } x 2^(len/2)
  2. ...
  3. 26Ck x k^(len/2)

の総和を求めればよい。(len/2 <= k の部分は最初のやり方で構わない)

ここで係数 26C1 x { 25C0 - 25C1 + 25C2 - ... ± 25C(k-1) } の部分は文字列長に関わらず一定なので計算は一度だけ行い、これに Σk^(len/2) を掛け合わせる。等比数列の和とか・・・20年来使っていない式を活用。計算量は...O(k^2*log(len))かな。


最終的なコードはこんな感じ:

#include <vector>
using namespace std;

const long long H = 1234567891LL;

inline long long sub_(long long a, long long b) {
  return (a + H - (b % H)) % H;
}
inline long long add_(long long a, long long b) {
  return (a + b) % H;
}
inline long long mul_(long long a, long long b) {
  return ((a % H) * (b % H)) % H;
}

long long fast_expt(long long r, long long n) { // r^n % H
  if (n == 1) return r;
  if (n % 2 == 0)
    return fast_expt(mul_(r,r), n/2);
  else
    return mul_(fast_expt(r,n-1), r);
}

inline long long div_(long long a, long long b) {
  return mul_(a, fast_expt(b,H-2));
}

long long geo(int r, int n) {
  // 1,r,r^2,...,r^n
  if (r == 1) return n % H;

  return div_(fast_expt(r,n+1)-1, r-1);
}

long long C(int n, int r)
{
  if (n == 0 || r == 0 || r == n) return 1;
  if (r > n-r) r = n-r;
  return C(n-1,r-1) * n / r;
}

long long fac_(int n) { // n !
  long long p = 1LL;
  for (int k=n; k>1; k--) p = mul_(p, k);
  return p;
}

vector<long long> coeffs_(int k) {
  vector<long long> cs(k+1, 1LL); cs[0] = 0;
  
  for (int j=1; j<=k; j++) {
    long long t = 0;
    for (int i=0,pm=1; i<=k-j; i++,pm=-pm) {
      t += C(26-j, i) * pm;
    }
    cs[j] = C(26, j) * t;
  }
  return cs;
}

class TheLongPalindrome {
  long long f_(int k, int len) {
    if (k == 1) return 1;
    if (k == len) return fac_(k);
    
    long long t = 0;
    for (int j=k,pm=1; j>=1; j--,pm=-pm) {
      if (pm >= 0)
        t = add_(t, fast_expt(j,len) * C(k,j));
      else
        t = sub_(t, fast_expt(j,len) * C(k,j));
    }
    return t;
  }

public:
  int count(int n, int k) {
    int h = (n + 1) / 2, m = n % 2;
    if (k > h) k = h;

    vector<long long> expts(k+1, 1LL); expts[0] = 0;
    vector<long long> coeffs = coeffs_(k);

    long long c = 0LL;
    for (int len=1; len<=k; len++) {
      int k_ = len;
      long long o = 0LL;
      for (int j=1; j<=k_; j++)
        o = add_(o, mul_(C(26,j), f_(j,len))); // o += 26Cj x f(j,len)
      c = (len == h && m == 1)? add_(c,o) : add_(c,o*2);
    }

    if (h > k) {
      long long o = 0LL;
      for (int r=1; r<=k; r++) {
        long long co = coeffs[r];

        if (co >= 0)
          o = add_(o, mul_(co, sub_(geo(r,h-1), geo(r,k))));
        else
          o = sub_(o, mul_(-co, sub_(geo(r,h-1), geo(r,k))));
      }
      c = add_(c, o*2);

      o = 0LL;
      for (int r=1; r<=k; r++) {
        long long co = coeffs[r];
        if (co >= 0)
          o = add_(o, mul_(co, fast_expt(r,h)));
        else
          o = sub_(o, mul_(-co, fast_expt(r,h)));
      }
      c = (m == 1) ? add_(c, o) : add_(c, o*2);
    }

    return (int)c;
  }
};

最後の要素で、全体長が偶数の場合の加算を忘れていたためにCase 3の数値が合わず、剰余演算のミスかと思って小一時間悩んだ。

このコードでは、n=1000000000な最悪ケースでも(コンテストサーバ時間で)3msec以内で演算が終了する。

当然ながら問題は、このコードを75分の間に書いてsubmitできるか、である・・・><

追記

(r^(n+1)-1)/(r-1)%1234567891 の計算で使うdiv_() のコードは、fast_expt()で法にあたる数値を引数の1つとして余分に取るものを使った別の書き方をしていた。が剰余演算のミスかと思って悩んだ間に差し替えた。原因はここではなかったが良い勉強になった。よい機会なので剰余系のライブラリを整備しておこう。


SRM416 Div1 Easy: NextNumber

| 18:09 | SRM416 Div1 Easy: NextNumber - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM416 Div1 Easy: NextNumber - naoya_t@topcoder SRM416 Div1 Easy: NextNumber - naoya_t@topcoder のブックマークコメント

今夜のSRMまで少し時間があるので過去問タイム。

本戦までTopCoder初挑戦の時に撃沈されたDIV2 500点問題(DIV1では250点)に再挑戦。

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

#define all(c)  (c).begin(),(c).end()

class NextNumber {
public:
  int getNextNumber(int N) {
    vector<int> v(32,0);

    for (int n=31; n>0; n--) {
      if (N == 0) break;
      v[n] = N % 2;
      N /= 2;
    }

    next_permutation(all(v));

    int r = 0;
    for (int i=0; i<32; i++) r = r*2 + v[i];
    return r;
  }
};

next_permutationを使って5分ちょいで解けてしまったw。システムテストも通った。

SRM415 Div1 Easy: ShipLoading

| 20:04 | SRM415 Div1 Easy: ShipLoading - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM415 Div1 Easy: ShipLoading - naoya_t@topcoder SRM415 Div1 Easy: ShipLoading - naoya_t@topcoder のブックマークコメント

テスト通らず何度か挑戦

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

2008-12-05

TopCoder部員のレーティング推移グラフ

TopCoder部員のレーティング推移グラフ - naoya_t@topcoder を含むブックマーク はてなブックマーク - TopCoder部員のレーティング推移グラフ - naoya_t@topcoder TopCoder部員のレーティング推移グラフ - naoya_t@topcoder のブックマークコメント

いそっちノートより拝借

ニュートリノのように突き抜けて行ったcafelier氏も追加

自分のやつだけ表示

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

2008-12-04TZTester をどうにかするブーム

nitoyonさん,cafelierさんの改造を参考にしつつ

というかcafelier版をベースに改造

  • 実行時間を計測して表示
Test Case #0...PASSED (0.201 msec)
Test Case #1...PASSED (0.04 msec)
Test Case #2...FAILED (0.001 msec)
Expected: "728"
Received: "-1073744361"
Test Case #3...FAILED (0.002 msec)
Expected: "240249781"
Received: "-1073744409"
  • 返り値がdoubleの場合、期待値との差分が1e-9未満かどうかのチェックに差し替える

cafelier版とのdiff:

--- CFLCustom-TZTester.java	2008-12-04 04:01:21.000000000 +0900
+++ tangentz/TZTester.java	2008-12-04 05:51:06.000000000 +0900
@@ -32,7 +32,7 @@
     private static final String k_PROBLEM       = "$PROBLEM$";
     private static final String k_RUNTEST       = "$RUNTEST$";
     private static final String k_TESTCODE      = "$TESTCODE$";
-    private static final String k_VERSION       = "\n// Powered by TZTester 1.01 [25-Feb-2003] customized by cafelier";
+    private static final String k_VERSION       = "\n// Powered by TZTester 1.01 [25-Feb-2003] customized by cafelier, timer support by naoya_t";
     
     // Cut tags
     private static final String k_BEGINCUT      = "// BEGIN CUT HERE\n";
@@ -154,6 +154,13 @@
         TestCase[] Cases = m_Problem.getTestCases();
         StringBuffer Code = new StringBuffer();
 
+        // <<modified by naoya_t>> : timer
+        Code.append("#include <time.h>\n");
+        Code.append("clock_t start_time;\n");
+        Code.append("void timer_clear() { start_time = clock(); }\n");
+        Code.append("string timer() { clock_t end_time = clock(); double interval = (double)(end_time - start_time)/CLOCKS_PER_SEC; ostringstream os; os << \" (\" << interval*1000 << \" msec)\"; return os.str(); }\n");
+        Code.append("\n");
+
         // <<modified by cafelier>> : new test code template
 
         // Generate the vector output function
@@ -227,8 +234,13 @@
         Code.append("cerr << \"Test Case #\" << Case << \"...\"; ");
 */
         // Print "PASSED" or "FAILED" based on the result
-        Code.append("if (Expected == Received) cerr << \"PASSED\" << endl; ");
-        Code.append("else { cerr << \"FAILED\" << endl; ");
+		if (TypeString.equals("double")) {
+			Code.append("double diff = Expected - Received; if (diff < 0) diff = -diff; ");
+			Code.append("if (diff < 1e-9) cerr << \"PASSED\" << timer() << endl; ");
+		} else {
+			Code.append("if (Expected == Received) cerr << \"PASSED\" << timer() << endl; ");
+		}
+        Code.append("else { cerr << \"FAILED\" << timer() << endl; ");
 
         if (ReturnType.getDimension() == 0)
             {
@@ -264,6 +276,7 @@
 
         // <<modified by cafelier>> : new test code template
         Code.append("int Test_(Case_<" + Index + ">) {\n");
+        Code.append("\ttimer_clear();\n");
         // Generate each input variable separately
         for (I = 0; I < Inputs.length; ++I) {
             Code.append("\t");

FileEdit の CodeTemplate はこんな感じ:

$BEGINCUT$
/*
$PROBLEMDESC$
*/
$ENDCUT$

#line $NEXTLINENUMBER$ "$FILENAME$"
#include <string>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <algorithm>
$BEGINCUT$
#include <iostream>
#include "cout.h"
$ENDCUT$
#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++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())

class $CLASSNAME$ {
	public:
	$RC$ $METHODNAME$($METHODPARMS$) {
		
	}
};

$TESTCODE$

(間違えてJavaのやつを載せてました。C++のやつに差し替えました。12/5)

cout.h - デバッグ時にcoutに色々放り込むために

| 23:15 | cout.h - デバッグ時にcoutに色々放り込むために - naoya_t@topcoder を含むブックマーク はてなブックマーク - cout.h - デバッグ時にcoutに色々放り込むために - naoya_t@topcoder cout.h - デバッグ時にcoutに色々放り込むために - naoya_t@topcoder のブックマークコメント

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;

ostream& operator<<(ostream &s, vector<string> v)
{
  int cnt = v.size();
  s << "[ ";
  for (int i=0; i<cnt; i++) {
	if (i > 0) s << ", ";
	s << '"' << v[i] << '"';
  }
  return s << " ]  // " << cnt << " item" << (cnt >= 2 ? "s" : "");
}

template <typename T> ostream& operator<<(ostream &s, vector<T> v)
{
  int cnt = v.size();
  s << "[ ";
  for (int i=0; i<cnt; i++) {
	if (i > 0) s << ", ";
	s << v[i];
  }
  return s << " ]  // " << cnt << " item" << (cnt >= 2 ? "s" : "");
}

template <typename T> ostream& operator<<(ostream &s, list<T> ls)
{
  int cnt = 0;
  s << "( ";
  for (typeof(ls.begin()) it=it.begin(); it!=it.end(); it++) {
	if (it != it.begin()) s << ", ";
	s << *it;
	cnt++;
  }
  return s << " )  // " << cnt << " item" << (cnt >= 2 ? "s" : "");
}

template <typename T> ostream& operator<<(ostream &s, deque<T> st)
{
  int cnt = st.size();
  s << "[ ";
  for (typeof(st.begin()) it=st.begin(); it!=st.end(); it++) {
	if (it != st.begin()) s << ", ";
	s << *it;
  }
  return s << " ]  // " << cnt << " item" << (cnt >= 2 ? "s" : "");
}

template <typename T1, typename T2> ostream& operator<<(ostream &s, map<T1,T2> m)
{
  int cnt = m.size();
  s << "{ ";
  for (typeof(m.begin()) it=m.begin(); it!=m.end(); it++) {
	if (it != m.begin()) s << ", ";
	s << it->first << " => " << it->second;
  }
  return s << " }  // " << cnt << " item" << (cnt >= 2 ? "s" : "");
}

template <typename T> ostream& operator<<(ostream &s, set<T> st)
{
  int cnt = st.size();
  s << "[ ";
  for (typeof(st.begin()) it=st.begin(); it!=st.end(); it++) {
	if (it != st.begin()) s << ", ";
	s << *it;
  }
  return s << " ]  // " << cnt << " item" << (cnt >= 2 ? "s" : "");
}

template <typename T1, typename T2> ostream& operator<<(ostream &s, pair<T1,T2> p)
{
  return s << "(" << p.first << "," << p.second << ")";
}

2008-12-02SRM428

SRM428

SRM428 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM428 - naoya_t@topcoder SRM428 - naoya_t@topcoder のブックマークコメント

12.02.2008

今回はchokudaiさんcafelierさんw(2人ともred目前)と同じ部屋。

DIVlevel問題名競技中後でSystem Test備考
1 250 TheLuckyString 91.30%
1 500 TheLongPalindrome 開いた o passed 12/11 http://topcoder.g.hatena.ne.jp/n4_t/20081211/p1
1 1000 - -

250点問題: TheLuckyString

→OK。95.12点

最初さらさらと書いたコードでサンプルケースが通らない。

(next_permutationだと最悪ケースで間に合わないかなと思って敬遠したけど勘違いだった。10文字なら最大10!パターンではないですかorz

なぜ通らないのかなかなか気づかず、他の(頭の悪い)方法をいくつも試していて残り時間が蝕まれて行く。

焦る。

最初のコードが同じ文字列を複数回カウントしていたこと、カウントの重複回数は容易に算出できることに気づいたのは残り十数分頃。そこからは瞬殺。

教訓

パターン数がある程度以下なのが分かっている場合はnext_permutationを迷わず使え

500点問題: TheLongPalindrome

開いただけ。

Project Eulerチックな問題。こっちを選んでいれば良かったと思った。時間なくて無念。


レーティング下降:1373 → 1311

http://gyazo.com/01c7fa55caa77572cd094eaf3e653feb.png


ps.某cafelier氏は順調にRedCoderに昇進。(飽きないで続けてくれたらいいな)

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