Hatena::Grouptopcoder

横道にそれるTopCoder参加記録でもいいじゃないか

|

2013-06-202013-TCO Marathon Match Round 3 参加記録 このエントリーを含むブックマーク

Round1は19位

Round2は時間がなくて参加できず。好きなタイプの問題だったので悲しい。

Round3は暫定13位

Round1では満足するまで時間が取れなかったが、Round3では休日の3日分をまるまる突っ込んだ。平日は1時間ずつくらい。(仕事の帰りが遅い)

そんなわけで、まあ十分に時間をかけたわけだが、結果は・・・満足できなてない。

SRMよりMarathonの方が合っている感じがする(楽しい)ので、赤目指して頑張りたい。


やったことは、yowaさんとほとんど同じ。

http://topcoder.g.hatena.ne.jp/yowa/

そこから点を伸ばした施策は、

1.最初に重みや円の大きさを考慮して並べた後、

  前半の半数(N=250だったら125個)について、ランダムに選んだ1つの円をランダムな配置順に移動して山登りに4秒、

  全部の円について同様に試すのに4秒、と分けた。

  →スコアが1.5%くらい増加

2.配置済みの円に接するように次の円を配置しようとしたとき、重なる円が1つだけだった場合に

  配置しようとした円に接するように移動できないか試した。

  →スコアが2%くらい増加

  (重なる円が2つの場合も試したが、遅くなりすぎてダメだった)

ちなみに提出版で、Greedy配置の実行回数はseed1で前半500回、後半80回程度。スコアは9.75くらい。



ほかにも、

・なんとか途中までの配置に対して評価関数を作って探索できないか

・初期配置を工夫したいけど重さと円の大きさ以外に特徴量はないか

・設置候補位置をもっと絞れないか(いろいろ絞ってNの10倍くらいだった)

 (十分時間があれば5%は伸びそうだった)

・もっと強力なGreedyはないか

などいろいろ考えましたが、全然ダメでした。

2012-09-17

おねえさんのアルゴリズムを考えてみた

12:13 | おねえさんのアルゴリズムを考えてみた - 横道にそれるTopCoder参加記録でもいいじゃないか を含むブックマーク はてなブックマーク - おねえさんのアルゴリズムを考えてみた - 横道にそれるTopCoder参加記録でもいいじゃないか

ニコニコ動画で話題になった

『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!

ですが、効率的なアルゴリズムはどういうアルゴリズムなんでしょうか。

調べてみると解説がありました。

http://www-erato.ist.hokudai.ac.jp/html/php/sub_html.php?id=18

うーん、部分問題に分けて、境界上のどことどこから出入りする、というパターンを掛けあわせて計算するんですかね。


実装するのはむずかしそうなので、かわりにおねえさんのアルゴリズムを考えてみました。

どうやら経路を全部列挙するアルゴリズムのようです。


気になるのは、素直に実装すると途中で閉ループができてしまってゴールにたどり着かないのに無駄な探索をしてしまう点です。

とりあえず、気にせずプログラムを実装してみました。

#include <iostream>
#include <vector>
#include <sys/time.h>

typedef long long LL;
using namespace std;

double now(){
    timeval tv;
    gettimeofday(&tv, 0);
    return tv.tv_sec + tv.tv_usec * 1e-6;
}

LL count_ways_rec(int width, int height, int x, int y, vector<int>& cells){
    if(cells[y*width+x] != 0) return 0;
    if(x < 0 || y < 0 || x >= width || y >= height) return 0;
    if(x == width-1 && y == height-1) return 1;
    LL res = 0;
    cells[y*width+x] = 1;
    for(int move = 0; move < 4; move++){
        const int dx[] = {-1, 0, 1, 0};
        const int dy[] = {0, -1, 0, 1};
        res += count_ways_rec(width, height, x+dx[move], y+dy[move], cells);
    }
    cells[y*width+x] = 0;
    return res;
}

LL count_ways(int width, int height){
    vector<int> cells(width*height, 0);
    return count_ways_rec(width, height, 0, 0, cells);
}

int main(){
    for(int n = 2; n < 10; n++){
        double start_time = now();
        LL res = count_ways(n, n);
        double end_time = now();
        cout << (n-1) << "*" << (n-1) << " : " << res << " ways (" << (end_time-start_time) << "sec)" << endl;
    }
}

結果は・・・

1*1 : 2 ways (8.10623e-06sec)

2*2 : 12 ways (5.96046e-06sec)

3*3 : 184 ways (0.00012207sec)

4*4 : 8512 ways (0.00841594sec)

5*5 : 1262816 ways (1.68881sec)

6*6 : 575780564 ways (977.176sec)


6×6の場合で977秒(16分)かかっていていますが、

一応、スーパーコンピューターに任せる前のところまで計算できました。


次に簡単な閉ループ検知を仕込んでみました。(もっといい方法がないか考えてみましたが思いつきませんでした)

進もうとしている向きに対して、左手と右手のセルのどちらかに同じ向きに進んだ形跡があれば、閉ループができてしまうことになるのでそれを避けるしかけです。

これだけでは防げないパターンもあるようですが、シンプルに。


結果は・・・

1*1 : 2 ways (7.86781e-06sec)

2*2 : 12 ways (5.00679e-06sec)

3*3 : 184 ways (6.38962e-05sec)

4*4 : 8512 ways (0.00296593sec)

5*5 : 1262816 ways (0.447401sec)

6*6 : 575780564 ways (210.572sec)

あんまり速くなりませんでした。

おねえさんのプログラムにはもう少し工夫があったのでしょうか。


あと、正方形だと線対称性を使って計算量を半分にできますね。


閉ループ簡易検知つきのプログラムです。

#include <iostream>
#include <vector>
#include <sys/time.h>

typedef long long LL;
using namespace std;

double now(){
    timeval tv;
    gettimeofday(&tv, 0);
    return tv.tv_sec + tv.tv_usec * 1e-6;
}

typedef enum Direction_tag{
    EMPTY=0, LEFT=1, UP=2, RIGHT=3, DOWN=4
} Direction;

LL count_ways_rec(int width, int height, int x, int y, vector<Direction>& cells){
    if(cells[y*width+x] != EMPTY) return 0;
    if(x == width-2 && y == height-2) return 1;
    LL res = 0;
    for(int move = 1; move < 5; move++){
        const int dx[] = {0, -1, 0, 1, 0};
        const int dy[] = {0, 0, -1, 0, 1};
        if(cells[(y+dx[move])*width+x-dy[move]] == (Direction)(move)) continue;
        if(cells[(y-dx[move])*width+x+dy[move]] == (Direction)(move)) continue;
        cells[y*width+x] = (Direction)(move);
        res += count_ways_rec(width, height, x+dx[move], y+dy[move], cells);
        cells[y*width+x] = EMPTY;
    }
    return res;
}

LL count_ways(int width, int height){
    width += 2; height += 2;
    vector<Direction> cells(width*height, EMPTY);
    for(int y = 0; y < height; y++){
        cells[y*width + 0] = UP;
        cells[y*width + width-1] = UP;
    }
    for(int x = 0; x < width; x++){
        cells[0*width + x] = LEFT;
        cells[(height-1)*width + x] = LEFT;
    }
    return count_ways_rec(width, height, 1, 1, cells);
}

int main(){
    for(int n = 2; n < 10; n++){
        double start_time = now();
        LL res = count_ways(n, n);
        double end_time = now();
        cout << (n-1) << "*" << (n-1) << " : " << res << " ways (" << (end_time-start_time) << "sec)" << endl;
    }
}

2011-10-05

SRM 520 moduloつきコンビネーション数

01:10 | SRM 520 moduloつきコンビネーション数 - 横道にそれるTopCoder参加記録でもいいじゃないか を含むブックマーク はてなブックマーク - SRM 520 moduloつきコンビネーション数 - 横道にそれるTopCoder参加記録でもいいじゃないか

div1 500点問題をみていて、

「ああ、これはコンビネーション数だなっ」と思ったら、そんなものは使わなかったようだ。

そんなことには全く気が付かず、コーディングフェーズ中は

「moduloつきのコンビネーションってどうやって計算するんだ・・・」

ということを考えていたりした。


そんなわけで、問題には関係無かったわけけど、

その部分が気になったので、よく考えてみた。


Comb(k, n)の通常の公式は、割り算があるのでmoduloつきでは上手く計算できない(と思う)。

kが小さければDPでも解けるけど、kが大きいときはどうしよう?

そこで、分割統治法による解法を考えてみた。

例えば、201個から3個を選ぶということは、201個を左から100個、100個、1個に分けて

Comb(201, 3) =

Comb(100,3) * Comb(100,0) * Comb(1,0)

  1. Comb(100,2) * Comb(100,1) * Comb(1,0)
  2. Comb(100,1) * Comb(100,2) * Comb(1,0)
  3. Comb(100,0) * Comb(100,3) * Comb(1,0)
  4. Comb(100,2) * Comb(100,0) * Comb(1,1)
  5. Comb(100,1) * Comb(100,1) * Comb(1,1)
  6. Comb(100,0) * Comb(100,2) * Comb(1,1)

と分解することができる。

これなら、掛け算と足し算しか使わない。計算量はO(log(k) * n * n)

typedef long long LL;

void comb2_rec(LL k, LL n, vector<LL>& res){
    res.clear();
    res.resize(n+1);
    if(k == 1){
        res[1] = (n>=1)?1:0;
        res[0] = 1;
        return;
    }
    vector<LL> next_comb;
    comb2_rec(k/2, n, next_comb);
    for(int i = 0; i <= n; i++){
        LL val = 0;
        for(int j = 0; j <= i; j++){
            val += (next_comb[i-j] * next_comb[j]) % MOD;
            val %= MOD;
        }
        if(k & 1){
            for(int j = 0; j <= i-1; j++){
                val += (next_comb[i-j-1] * next_comb[j]) % MOD;
                val %= MOD;
            }
        }
        res[i] = val;
    }
}

LL comb2(LL k, LL n){
    vector<LL> next_comb;
    comb2_rec(k, n, next_comb);
    return next_comb[n];
}

SigmarSigmar2011/10/07 01:27MODが素数の場合に限りますが、フェルマーの小定理により1/b==b^(MOD-2)となり、a/b==a*b^(MOD-2)で割り算ができます。
なおb^eはbinary methodと呼ばれる手法により、O(log(e))で計算可能です。
従ってcmb(k,n)はO(n*log(MOD))で計算可能です。更にkがある程度小さい場合、階乗をメモ化しておけばk!/n!/(k-n)!で計算できるのでO(log(MOD))で計算できます。
ちなみにTopcoderで良く出てくる1,000,000,007や1,000,000,009は素数ですので上記の手法が適用可能です。
binary mothod → http://ja.wikipedia.org/wiki/%E5%86%AA%E5%89%B0%E4%BD%99#.E9.80.94.E4.B8.AD.E3.81.A7.E5.89.B0.E4.BD.99.E3.82.92.E3.81.A8.E3.82.8B
フェルマーの小定理 → http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86

machy3machy32011/10/07 23:29ご指摘ありがとうございますー。気が付きませんでした・・・。勉強になりました!

2011-09-11

SRM 517 div1 配列エディタ

11:07 | SRM 517 div1 配列エディタ - 横道にそれるTopCoder参加記録でもいいじゃないか を含むブックマーク はてなブックマーク - SRM 517 div1 配列エディタ - 横道にそれるTopCoder参加記録でもいいじゃないか

600点問題はwriterの解法を読んだところ途中までは方針は合っていたようだけど、結局解けなかった。

この問題で1つチャレンジをゲットしたのだが、どうにも配列の入力がめんどくさい。

{2,0,4,1,6,3,8,5,10,7,12,9,14,11,16,13,18,15,20,17,22,19,24,21,26,23,28,25,30,27,32,29,34,31,36,33,38,35,40,37,42,39,44,41,46,43,48,45,49,47}

という配列を入力するのにボタンを50回もクリックしないといけないなんて、なにかおかしい。

きっと何かいい方法があるはず、と思って調べてみたらあった。

http://apps.topcoder.com/wiki/display/tc/The+Problem+Arguments+Window

ここの説明によると、"++"ボタンを使った場合は、カンマで区切られて入力されるんだと。

だから、

2,0,4,1,6,3,8,5,10,7,12,9,14,11,16,13,18,15,20,17,22,19,24,21,26,23,28,25,30,27,32,29,34,31,36,33,38,35,40,37,42,39,44,41,46,43,48,45,49,47

って入力して、"++"ボタンをポチって1回押すだけでいい。

しらなかった・・・"++"は最後に追加するボタンだと思ってたよ。

二重配列や、カンマを含む文字列の場合は"{}"を使うみたいですね。

f:id:machy3:20110911110659p:image:right

2011-07-30

testerを書き換える

01:14 | testerを書き換える - 横道にそれるTopCoder参加記録でもいいじゃないか を含むブックマーク はてなブックマーク - testerを書き換える - 横道にそれるTopCoder参加記録でもいいじゃないか

topcoderではC++を使っており、TZTesterを愛用させていただいていたのですが、

ちょっと直したいところがあって、書き換えてみました。

1.テストケースを1つ追加。Time Limit Exceededになりそうか、自分で確かめたりするために。

2.テストケースの実行時に、毎回クラスをインスタンス化する(メンバ変数が初期化されるように)。

コンパイルには

http://www.topcoder.com/contest/classes/ContestApplet.jar

が必要でした。

*** TZTester.java	2011-07-31 00:52:20.000000000 +0900
--- ../tangentz2/TZTester.java	2011-07-31 00:44:09.000000000 +0900
***************
*** 163,169 ****
          Code.append("¥tvoid run_test(int Case) { ");
  
          // Check which case should be called
!         for (I = 0; I < Cases.length; ++I)
              Code.append("if ((Case == -1) || (Case == " + I + ")) test_case_" + I + "(); ");
          // next
  
--- 163,169 ----
          Code.append("¥tvoid run_test(int Case) { ");
  
          // Check which case should be called
!         for (I = 0; I < Cases.length + 1; ++I)
              Code.append("if ((Case == -1) || (Case == " + I + ")) test_case_" + I + "(); ");
          // next
  
***************
*** 180,185 ****
--- 180,187 ----
          // Generate the individual test cases
          for (I = 0; I < Cases.length; ++I)
              generate_test_case(I, Code, ParamTypes, ReturnType, Cases[I]);
+         // another test case
+         generate_test_case(Cases.length, Code, ParamTypes, ReturnType, Cases[Cases.length - 1]);
          // next
  
          // Insert the cut tags
***************
*** 243,249 ****
          // Generate the output variable as the last variable
          generate_parameter(Inputs.length, Code, ReturnType, Output);
  
!         Code.append("verify_case(" + Index + ", Arg" + Inputs.length + ", " + m_Problem.getMethodName() + "(");
  
          // Generate the function call list
          for (I = 0; I < Inputs.length; ++I)
--- 245,251 ----
          // Generate the output variable as the last variable
          generate_parameter(Inputs.length, Code, ReturnType, Output);
  
!         Code.append("verify_case(" + Index + ", Arg" + Inputs.length + ", " + m_Problem.getClassName() + "()." + m_Problem.getMethodName() + "(");
  
          // Generate the function call list
          for (I = 0; I < Inputs.length; ++I)

AlmenaAlmena2011/08/30 04:51Didn't know the forum rules allowed such blirlaint posts.

iscykmmiscykmm2011/08/30 16:56w88INc <a href="http://wkrtejtyufsu.com/">wkrtejtyufsu</a>

iygjjaiygjja2011/09/01 16:59syvYZq , [url=http://xysovukehcax.com/]xysovukehcax[/url], [link=http://lefcjrrxktqy.com/]lefcjrrxktqy[/link], http://oykqptzmbjwq.com/

llpyvlllpyvl2011/09/03 17:41k5FrLc <a href="http://rmqjlpeoqnbb.com/">rmqjlpeoqnbb</a>

pttazbpbgrpttazbpbgr2011/09/04 01:26kbOwgt , [url=http://whgvvvuvmdar.com/]whgvvvuvmdar[/url], [link=http://jgzilcylwkwk.com/]jgzilcylwkwk[/link], http://lfhlrapjbxxl.com/

|