Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2012-01-15TopCoder SRM 529 (Div1)

KingSort (250pt)

18:58 | KingSort (250pt) - capythm@TopCoder を含むブックマーク はてなブックマーク - KingSort (250pt) - capythm@TopCoder KingSort (250pt) - capythm@TopCoder のブックマークコメント

問題の趣旨

  • 王様の名前を辞書順にソートしたい
  • 王様の名前は「Louis VIII」(ルイス8世)などのようになっている。
  • 名前順にソートするが、「VIII」の部分は数字の若い順にソートしたい

http://community.topcoder.com/stat?c=problem_statement&pm=11740&rd=14722&rm=311146&cr=22881961

解法

  • ローマ数字をデコードして、ソートするだけの実装ゲーム
  • "I"かどうか→"II"かどうか→"III"かどうか、の順に比較していくと、"III" でも最初の比較で一致してしまう(バグ)ので、それだけは注意する。
  • 以下のソースコードでは map< string, vector<int> > を使っている。map をイテレータでアクセスする場合、map では自動的にキー順でソートされているので、ソートは不要。

提出したソースコード(汚い)

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

class KingSort{ 
public: 
  vector <string> getSortedList(vector <string> kings){ 
    vector<string> ret; 
    map< string, vector<int> > d; 
    for( int i=0; i<kings.size(); i++ ){ 
      int sp=-1; 
      for( int j=0; j<kings[i].size(); j++ ) 
        if( kings[i][j] == ' ' ){ sp=j; break; } 
      string actualname = kings[i].substr( 0, sp ); 
      int ordinal=0; 
      int p = sp+1; 
      if     ( kings[i].compare( p, 3, "XXX" ) == 0 ){ ordinal+=30; p+=3; } 
      else if( kings[i].compare( p, 2, "XL" )  == 0 ){ ordinal+=40; p+=2; } 
      else if( kings[i].compare( p, 2, "XX" )  == 0 ){ ordinal+=20; p+=2; } 
      else if( kings[i].compare( p, 1, "X"  )  == 0 ){ ordinal+=10; p+=1; } 
      else if( kings[i].compare( p, 1, "L"  )  == 0 ){ ordinal+=50; p+=1; } 
      if     ( kings[i].compare( p, 4, "VIII" ) == 0 ){ ordinal+=8; } 
      else if( kings[i].compare( p, 3, "VII" )  == 0 ){ ordinal+=7; } 
      else if( kings[i].compare( p, 2, "VI" )  == 0 ){ ordinal+=6; } 
      else if( kings[i].compare( p, 1, "V"  )  == 0 ){ ordinal+=5; } 
      else if( kings[i].compare( p, 2, "IV"  )  == 0 ){ ordinal+=4; } 
      else if( kings[i].compare( p, 2, "IX"  )  == 0 ){ ordinal+=9; } 
      else if( kings[i].compare( p, 3, "III"  )  == 0 ){ ordinal+=3; } 
      else if( kings[i].compare( p, 2, "II"  )  == 0 ){ ordinal+=2; } 
      else if( kings[i].compare( p, 1, "I"  )  == 0 ){ ordinal+=1; } 
      d[actualname].push_back( ordinal ); 
    } 
    for( map< string, vector<int> >::iterator i = d.begin(); i!=d.end(); ++i ){ 
      string actualname = i->first; 
      for( int j=0; j< i->second.size(); j++ ){ 
        string s = actualname; 
        s += " "; 
        sort( i->second.begin(), i->second.end() ); 
        switch( i->second[j] / 10 ){ 
        case 1: s+= "X"; break; 
        case 2: s+= "XX"; break; 
        case 3: s+= "XXX"; break; 
        case 4: s+= "XL"; break; 
        case 5: s+= "L"; break; 
        } 
        switch( i->second[j] % 10 ){ 
        case 1: s+= "I"; break; 
        case 2: s+= "II"; break; 
        case 3: s+= "III"; break; 
        case 4: s+= "IV"; break; 
        case 5: s+= "V"; break; 
        case 6: s+= "VI"; break; 
        case 7: s+= "VII"; break; 
        case 8: s+= "VIII"; break; 
        case 9: s+= "IX"; break; 
        } 
        ret.push_back( s ); 
      } 
    } 
    return ret; 
  } 
};

ローマ数字のデコード、エンコードについて

他の人のソースを読んで、なるほどと思ったので、自分で書き直してみました。

上記のソースは実装にかなり時間がかかったので、

ライブラリとして、いつでも使えるようにしておくのがよさそう・・・。

#include <string>
#include <iostream>

using namespace std;

int decode_roman_num( string::iterator begin, string::iterator end )
{
  int ret=0;
  for( string::iterator i = begin; i != end; ++i ){
    switch( *i ){
    case 'I': ret++; break;
    case 'V': ret -= (ret %    5) * 2; ret +=    5; break;
    case 'X': ret -= (ret %   10) * 2; ret +=   10; break;
    case 'L': ret -= (ret %   50) * 2; ret +=   50; break;
    case 'C': ret -= (ret %  100) * 2; ret +=  100; break;
    case 'D': ret -= (ret %  500) * 2; ret +=  500; break;
    case 'M': ret -= (ret % 1000) * 2; ret += 1000; break;
    }
  }
  return ret;
}

string encode_roman_num( int d )
{
  string ret;
  string num2[] = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
  string num1[] = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
  string num0[] = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };
  for( int i=0; i < d/1000; i++ ) ret += "M";
  ret += num2[(d%1000)/100];
  ret += num1[(d%100)/10];
  ret += num0[d%10];
  return ret;
}

int main( void ){
  for( int i=1; i<=2048; i++ ){
    cout << i << " ";
    string s = encode_roman_num( i );
    cout << s << " ";
    int j = decode_roman_num( s.begin(), s.end() );
    cout << j << " ";
    // assertion
    if( i != j ) cout << "+++++++++++++++++++++++ error !!!!";
    cout << endl;
  }
  return 0;
}

MinskyMystery (600pt)

18:58 | MinskyMystery (600pt) - capythm@TopCoder を含むブックマーク はてなブックマーク - MinskyMystery (600pt) - capythm@TopCoder MinskyMystery (600pt) - capythm@TopCoder のブックマークコメント

問題文(ややこしい)

http://community.topcoder.com/stat?c=problem_statement&pm=11739&rd=14722&rm=311146&cr=22881961

(本番では解けなかったので、以下の内容は復習になります)

よくわからないので、まずは紙に書いてビー玉がどう移動するか、シミュレーションをしました。

N=0,1 の場合、終了条件にたどり着かないため、-1が解になります。(説明省略)

それ以外で、Nが偶数の場合、

bag0bag1bag2bag3bag4countbag0bag1bag2bag3bag4count
N00000
N10001
N20002
N-202206(N=2)→002206
N-202217 002217
N-222019 002039(end)
N-4042113(N=4)→0042113
N-4042214 0042214
N-4240216 0020416(end)
N-6062220(N=6)→0062220
N-6062321 0062321
N-6260323 0060523(end)
N-8082327(N=8)→0082327
N-8082428 0082428
N-8280430 0080630(end)

という感じで、差分7の等差数列になっています。2で割り切れない3の倍数の場合を考えると、

N=3では、

bag0bag1bag2bag3bag4count
300000
310001
320002
102206
102217
122019ここまで、N=2と同じ
0131111
0131212
0230213
3200216
3300017Repeat文先頭に戻って、bag1++
0033023
0033124
0030427(end)

N=9 では

bag0bag1bag2bag3bag4count
最初省略
1280430ここまで、N=8と同じ
0191432
0191533
0290534
9200543
9300044Repeat文先頭に戻って、bag1++
6333050
6033151
6330154
3063160
3063261
3360264
0093270
0093371
0090674(end)

というように、bag1=2 のループを回りきった後に、bag1=3 のループを回り始める、という感じになります。

ここまで考察した後、シミュレーションによる実装を行いました(注:大きい値ではTLEする)

#include <iostream>
using namespace std;

class MinskyMystery{
public:
  int computeAnswer(long long N) {
    int bag0=0, bag1=0, bag2=0, bag3=0, bag4=0;
    bag0 = N;
    int ret = 0;
    if( N < 2 ) return -1;
    // count start
    bag1++; ret++;
    while(1){
      bag1++; ret++;
      bag4=0;
      while( bag0 ){
        while( bag0 && bag1 ){
          bag0--; bag1--; bag2++; bag3++; ret+=2;
        }
        bag4++; ret++;
        if( bag0 == 0 && bag1 == 0 ){
          bag4 += bag3; ret+=bag3; bag3=0;
          goto OWARI;
        }
        bag1+=bag3; ret+=bag3; bag3=0;
      }
      bag0+=bag2; ret+=bag2; bag2=0;
    }
  OWARI:
    return ret;
  }
};

int main( void )
{
  cout << 2 << ":" << MinskyMystery().computeAnswer(2) << endl;
  cout << 3 << ":" << MinskyMystery().computeAnswer(3) << endl;
  cout << 4 << ":" << MinskyMystery().computeAnswer(4) << endl;
  cout << 2401 << ":" << MinskyMystery().computeAnswer(2401) << endl;
  cout << 24 << ":" << MinskyMystery().computeAnswer(24) << endl;
  cout << "================" << endl;
  for( int i=2; i<=100; i+=2 ){
    cout << i << ":" << MinskyMystery().computeAnswer(i) << endl;
  }
  for( int i=3; i<=100; i+=3 ){
    if( i % 2 == 0 ) continue;
    cout << i << ":" << MinskyMystery().computeAnswer(i) << endl;
  }
  for( int i=5; i<=100; i+=5 ){
    if( i % 2 == 0 || i % 3 == 0 ) continue;
    cout << i << ":" << MinskyMystery().computeAnswer(i) << endl;
  }
  for( int i=7; i<=100; i+=7 ){
    if( i % 2 == 0 || i % 3 == 0 || i % 5 == 0 ) continue;
    cout << i << ":" << MinskyMystery().computeAnswer(i) << endl;
  }
  return 0;
}

走らせてみると、Nが2の倍数の場合、以下のように2+(7\times\lfloor N/2 \rfloor) という公式が出てきます。

2:9
4:16
6:23
8:30
10:37
12:44

Nが2で割り切れない、かつ3の倍数の場合、以下のように

 2+(7\times\lfloor N/2 \rfloor) + ((N \% 2)*3+2) + N + (10\times\lfloor N/3 \rfloor)

となります。

3:27
9:74
15:121
21:168
27:215

なお、 ((N \% 2)*3+2) + N の部分は、最後の While ループ処理を表しています(先ほどの表と問題文をよくにらめっこするとわかる)。

Nが2,3で割り切れない、かつ5の倍数の場合、以下のように

 2+(7\times\lfloor N/2 \rfloor) + ((N \% 2)*3+2) + N + (10\times\lfloor N/3 \rfloor) + ((N \% 3)*3+2) + N + (13\times\lfloor N/4 \rfloor) + ((N \% 4)*3+2) + N + (16\times\lfloor N/5 \rfloor)

となります。

5:88
25:414
35:576
55:902
65:1065
85:1391
95:1553

つまり、NがK未満で割りきれず、Kで割り切れる場合、以下の式で算出できそうです。

 A = 2 + (K-2)\times (N+2) + \sum_{i=2}^K ( (3i+1)\times\lfloor N/i \rfloor + 3\times(N \% i))

よく見ると、

 (3i+1)\times\lfloor N/i \rfloor + 3\times(N \% i) = 3(i\times\lfloor N/i \rfloor + N \% i) + \lfloor N/i \rfloor = 3N + \lfloor N/i \rfloor

なので、以下のように書き換えられます。

 A = 2 + (K-2)\times (N+2) + \sum_{i=2}^K ( 3N + \lfloor N/i \rfloor )

 A = (4K-5)N + 2(K-1) + \sum_{i=2}^K ( \lfloor N/i \rfloor )

上記考察を行ってコーディングし直すと、以下のようになります。

(先ほどのソースコードと出力値は完全一致します。本当は 「modulo 1,000,000,009」の処理も必要)

#include <iostream>
using namespace std;

class MinskyMystery{
public:
  int computeAnswer(long long N) {
    if( N < 2 ) return -1;
    int ret = 0;
    int i;
    for( i=2; i<=N; i++ ){
      ret += N/i;
      if( N % i == 0 ) break;
    }
    ret += (4*i-5)*N+2*(i-1);
    return ret;
  }
};

int main( void )
{
  for( int i=0; i<=10000; i++ ){
    cout << i << ":" << MinskyMystery().computeAnswer(i) << endl;
  }
  return 0;
}

先ほどのソースよりも劇的に早くなったのですが、N の制限値が 10^{12}以下なので、

10^{12}付近の素数だと TLE してしまいます。やはり、Σの部分のループをなんとかして処理量を減らす必要がありそうです。

 N/2<i の時、\lfloor N/i \rfloor = 1N/3<i<N/2 の時 \lfloor N/i \rfloor = 2というように、iが大きくなってくると、\lfloor N/i \rfloorが同じ値になるiの区間が結構長く連続することを利用してループ回数を減らします。閾値として、\sqrt{N}にして、それまでは普通にループで加算、それ以降は同じ値が続くことを利用する、という感じで挟み撃ちでΣの部分を算出します。そうすると、ループ回数がもともと10^{12}だったのが、高々10^{6}\times 2となり、さらに早く算出可能となります。

上記を考えたソースコードが以下になります。

#include <iostream>
using namespace std;

class MinskyMystery{
public:
  int computeAnswer(long long N) {
    if( N < 2 ) return -1;
    long long md = 1000000009L;
    long long i,ret;
    for( i=2; i*i<=N; i++ ){
      if( N % i == 0 ) break;
    }
    if( i*i > N ){ // N is prime
      long long K = i;
      ret = ((4*N-5)%md)*(N%md)+(2*(N-1))%md;
      ret %= md;
      for( i=2; i<=N/K; i++ ){
        ret += (N/i);
        ret %= md;
      }
      long long prev=N;
      for( i=2; i<=K; i++ ){
        ret += (((prev - N/i)%md) * (i-1));
        ret %= md;
        prev = N/i;
      }
    } else { // N is not prime
      ret = ((4*i-5)%md)*(N%md)+(2*(i-1))%md;
      ret %= md;
      long long K = i;
      for( i=2; i<=K; i++ ){
        ret += (N/i);
        ret %= md;
      }
    }
    return ret;
  }
};

int main( void )
{
  for( int i=0; i<=10000; i++ ){
    cout << i << ":" << MinskyMystery().computeAnswer(i) << endl;
  }
  return 0;
}