Hatena::Grouptopcoder

CKomakiの日記

 | 

2014-12-02

マラソンマッチにおける頻出Q&Aと小技

05:54

これはCompetitive Programming Advent Calendar 20142日目の記事です。

マラソンマッチの問題は機械学習系と最適化系の2種類からなります。本記事はTCOでも出題される最適化系について書かれています。みんなで最適化してTCOに行きましょう。


"こまか~い"



マラソンマッチにおける問題は多岐に渡るものの、使われるアルゴリズムは焼き鈍しかビームサーチであることが多いため、実際に過去問を解いたりコンテストに出たりして練習を積めば強くなれる競技だと僕は思っています。

しかし、マラソンマッチは回答があるわけでもないので過去の問題を解いてみても新しい知識が入るわけではなく、ちゃんと練習になっているのかわからず少し辛いものがあります。なので、本記事では1人では気づきにくいちょっとしたコツや僕なりのやり方等を軽く纏め、これから練習しようという人の手助けが出来ればと思います。巷には素晴らしい記事が溢れているので詳細な個々のトピックについては触れません。あくまで道中の看板程度です。



本記事は、以下の記事をきっちり読みんだうえで少しマラソンマッチに触った後に、軽く眺めておくくらいが有用だと思います。

マラソンマッチの始め方

マラソンマッチの取り組み方

MarathonMatchトレーニングのための過去問レビュー









何を勉強すればいいのかわからない

山登りと焼き鈍しとビームサーチが必須になります。

高速化が重要になることが多いため累積和(いわゆるimos法)も時たま使います。

ほとんどの場合これらしか使わないにも関わらず、強い人は概ねいつも強いのでこれらを練習を通して身につけることが大切そうです。



言語はどれがいいのか

高速に動作するという点ではC++が圧倒的に有利です。

ただ、C++以外を使う強いコンテスタントもいますので何か利点があるのかもしれません。

ちなみに、そういった人々も速度が重要な問題では途中からC++を使い始めることが多いです。



Topcoderサーバー上では時間取得関数が非常に遅い

Topcoderサーバー上では、時間を取得する関数(timeやgettimeofday)はローカルの数千倍、数万倍遅いため、

これらの関数をあまり呼び出しすぎない工夫が必要となります。

ただしC++だとサーバー上でも高速に動作するrdtscを使用することにより、これを回避することができます。

rdtscはクロック数を取得する命令なので、TCサーバー上で一秒間に何回クロックが振動するかを測定する必要があります。

double getTime(unsigned long long int begin_cycle)
{
  return (double)(getCycle() - begin_cycle) / cycle_per_sec;
}

unsigned long long int getCycle()
{
  unsigned int low, high;
  __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
  return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}


Topcoderサーバー上でうまく動かないor劇的に得点が下がる

九分九厘C++におけるメモリ外アクセスのせいです。

配列のメモリ外アクセスを検知するコンパイルオプション-fsanitize=addressをつけると自動で検知してくれます。

また、STLデバッグモードにするコンパイルオプション-D_GLIBCXX_DEBUGもつけると安心です。

以下のようなaliasを設定しておくと幸せかもしれません。

alias g++0x='g++ -std=c++0x -D_GLIBCXX_DEBUG -fsanitize=address -D "KOMAKI_LOCAL" -O2'


これ以上改善できそうにない(貪欲や山登りを使ってる)

貪欲や山登りを使っている場合は大抵焼き鈍しやビームサーチ等に変えることにより大幅に得点を伸ばすことができます。

そうでなくとも、同じアルゴリズムパラメーターを変えて何度も実行して一番いい結果を出力することにより改善はできます。

なので、とりあえず時間を使い切るタイプのアルゴリズムに変えるのがよさそうです。



これ以上改善できそうにない(時間は使いきってる)

ビジュアライザを眺めていると改善案が浮かびやすいです。

プログラムの出力よりもよい解を人力で見つけることができたら、そこをカバーできるようにプログラムを変えれば大抵スコアは上がります。

実際ビジュアライザを改造する人も多く、強い人ほどビジュアライザに力を入れる気がしてます。



これ以上改善できそうにない(ビジュアライザを見てもどうしようもない)

上位陣との開きが小さい場合は案外改善できるので諦めずに頑張りましょう。

小さい改善をむりやり繰り返しながら何かに気づくのをぼちぼち待つのもありかもです。

高速化、特定パターン用の実装(小さいケースのみ高速に動作するアルゴリズム等)、最終回答に対する最後の山登り等があります。

上位陣との開きが大きい場合は自分なりの楽しみ方を見つけましょう。



いいアイディアがあったので実装したがスコアが伸びなかった

プログラムもしくは考えが間違ってることが多いです。

プログラムが間違っていれば直して点数があがり、考えがおかしい時はちゃんと考え直す機会を得ることとなります。

どちらにせよスコアをあげるチャンスなので原因はきちんと明らかにしておいた方がいいです。





評価関数はどんなものがあるか

大抵「問題のスコアリング + 良さそうな状態にボーナスポイント」という形になります。

また、極偶に「ランダムプレイアウト」などを使用します。



評価関数ボトルネックになっている時

評価関数が重いということはよくあります。

しかし、評価関数の近似値を求めるだけであれば高速な実装も可能であることが多いです。

例えば「n個の物質の静電気力の総和」という評価関数の場合、正確に計算するとあまりにも重いです。

そこで、ある程度遠い物質間の力は無視することにより高速な擬似評価関数が作れます。

しかし、この擬似評価関数は高速ですが不正確です。

なので実際には速さと精度のトレードオフを追求することになる。



乱数を質のよいものに換える

広く使われている乱数用の関数線形合同法を使っていることが多いですがあまりよくないらしいです。

マラソンでは一般にXorshiftが使われますが、メルセンヌツイスターなども有名です。

僕は基本はXorshiftを使い、最終提出時に一応いくつか試してみて一番いいのを使ってます。

class XorShift{
public:
  static int rand();
private:
  static unsigned int x;
  static unsigned int y;
  static unsigned int z;
  static unsigned int w;
  static unsigned int t;
};
unsigned int XorShift::x = 123456789;
unsigned int XorShift::y = 362436069;
unsigned int XorShift::z = 521288629;
unsigned int XorShift::w = 88675123;
unsigned int XorShift::t = 1;

int XorShift::rand()
{
  t = x ^ (x << 11);
  x = y;
  y = z;
  z = w;
  w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
  return w & 0x7fffffff;
}


条件分岐がバグっていて一度も実行されていない行があることに気づいた

コード網羅率という概念がテスト技法にあります。

お手軽な方法として、gccを使っていれば以下のコマンドで簡単にどの行が何回呼び出されたか調べることもできます。

> g++ --coverage tmp.cpp -o tmp
> ./tmp
> gcov tmp.gcda
> gedit tmp.cpp.gcov

tmp.cpp.gcovはこんな感じになります

        -:  130:
        1:  131:int main()
        -:  132:{
        1:  133:  int total = 0;
       11:  134:  for(int i = 0; i < 10; ++i){
       30:  135:    for(int j = 0; j < 2; ++j){
       20:  136:      ++total;
        -:  137:    }
        -:  138:  }
        1:  139:  cout << total << endl;
        4:  140:}


p[i]%の確率でfunc[i]を実行したい時とか

コード1ようなものはよく見ますが、制御が難しくなって思い通り調整できなくなってくるのでコード2の方がいいように思ます。

コード1

if(rand() % 5 <= 1){ 
  func_0(); 
}else if(rand() % 2 == 0){ 
  func_1(); 
}else{
  func_2();
}

コード2

static vector<int> bag;
for(int i = 0; i < 40; ++i) bag.push_back(0);
for(int i = 0; i <  6; ++i) bag.push_back(1);
for(int i = 0; i < 54; ++i) bag.push_back(2);
int func_id = bag[rand() % sz(bag)];
if(func_id == 0) func_0();
if(func_id == 1) func_1();
if(func_id == 2) func_2();
 |