EmK repo

2006 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2009 | 01 | 03 | 04 | 06 | 08 | 09 | 10 | 12 |
2010 | 04 | 05 | 07 |
2011 | 04 |

W × H の2次元グリッドが与えられる。
そのうちP%のマスは、質が悪いので、使用することができない
その後、orderCnt個のブロック形状とその価値がクエリとして与えられる。
ただしクエリの情報を事前に知ることはできない
各ピースごとに、質が悪い部分を含まないように切り出すとそのブロックの価値がポイントとして手に入る。スキップすることもできる
切り出したブロックの合計がスコア

Visualizer

戦略

以下、ピースを置けない場所を「壁」と表記する。

おおまかな流れ

価値がしきい値より低いピースはスキップする
- これによって全体の7割ぐらいのピースをスキップすることになるので高速化にもなる
- しきい値は、[残りスペース数] / K * [残りピース数] * [最近10回のピース切り出し成功率(スキップは除く）] * 100
スキップしなかった場合、与えられたピースで配置可能なパターンについて、評価値を出して最良のものを選択する

評価の基準

ピースを配置したとき、壁に隣接している箇所が多いほど高い評価
４隅からのマンハッタン距離が低いほど高い評価
- そうすることで周りから配置されやすくなり、連結成分が分断されづらくなる。
配置したピースに隣接する空きマスの連結成分についてペナルティポイントを計算して、評価値から引いていく（次項参照）
上記連結成分でサイズが K + 1 以上のものができるだけ少ないほど高い評価

空きマスの連結成分のペナルティポイントの計算

無駄になる空きマスの期待値が多いほど、ペナルティポイントが高くなるというポリシーで策定

連結成分のサイズ N が K 未満の場合
- その N マスにはピースを置くことができないので、Nに比例したペナルティポイント
連結成分のサイズ N が K または K + 1の場合
- [残りのターンで配置可能なピースが出る確率] * N に比例したペナルティポイント（嘘数式）
連結成分のサイズ N が K + 2 以上 2 * K 以下の場合
- 全ての K - オミノについて、その連結成分に配置可能であるかどうかを調べて、それまでにそのピースが出現した回数で重みをつけて、次にその連結成分に配置可能なピースが出るだいたいの確率を求める。
- [上記で求めた確率 × N] ^ 2 に比例したペナルティポイントを与える
- この処理は非常に重いので、残り時間が少なくなったら実行しないようにする。
  - 初サブミット時は、この処理によってタイムオーバーしていて、スコアが減っていた
  - この処理を入れたのが１位になれた一番のポイントだと思う
- 二乗しているのは、そうするとなぜかスコアがあがるから。なんとなく累乗して重みを付けるのはマラソンではよくやること。
連結成分のサイズ N が 2 * K + 1 以上の場合
- ペナルティは特になし

高速化

現在計算中の評価値が最大の評価値を下回ったら、計算を打ち切る
配置するピースのバウンディングボックスの範囲内の空きマスが K 未満である場合は評価値計算はスキップする
- ピースが置けないため。なお、空きマスの計算はSummed area tableで行う。
配置するピースのバウンディングボックスの範囲内および外周に壁がない場合は評価計算せず、無条件でピースを置かない。
- なにひとつ壁に隣接しないところにピースを配置してもメリットがないため（私見）
各ターンごとに K 未満の連結成分は壁で埋めておく
ピースの回転および鏡像で同じ形になるパターンは一回しか評価値計算しないようにする

結果

2回目の単独1位。

初サブミット時は、スコアが97点台でうわああとなったけれど、時間オーバーしそうなところを修正＆高速化したら、あっという間に１位になった。実地テストは大切。みなさん余裕のあるSubmit計画を。

2425 -> 2502

Permalink | コメント(0) | トラックバック(0) | 20:31

2010年07月10日

■ boost::math::quaternionでUTPC2010 G問題を解いてみた

問題URL：http://www.utpc.jp/2010/problems/G.html

四元数を使うと意外とあっさり書けた。

コード

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<functional>
#include<complex>
#include<bitset>
#include<cassert>

#include<boost/math/quaternion.hpp>

using namespace std;

#define FOR(i,n)  for(int i=0;i<(int)(n);i++)

double PI = 4.0*atan(1.0);

int days[] = {31,29,31,30,31,30,31,31,30,31,30,31};

typedef boost::math::quaternion<double> Q ; 

// ベクトル q を軸に theta 分回転させる
Q rotate(Q p , double theta , Q q){
  Q r = cos(theta/2) + q/abs(q)*sin(theta/2);
  return r * p * conj(r);
}

Q earth(double latitude ,double longitude)
{
  // Y , Z が問題設定と逆になるので注意
  return boost::math::cylindrospherical(0.0 , 1.0 , longitude/180.0*PI , latitude/180.0*PI);  
}

bool check(double longitude , double latitude , double rotate_arg)
{
  Q hokkyoku = earth(43.2 , 0);   // 北極星
  Q p = earth(latitude,longitude);// 星の位置
  // 原点-北極星を軸に回転
  return rotate(p , rotate_arg , hokkyoku).R_component_4() > 0 ; 
}

int main()
{
  int month,day,hh,mm;
  scanf("%d/%d %d:%d",&month,&day,&hh,&mm);
  int mm_sum = 0 ; 
  FOR(i,month-1){
    mm_sum += days[i]*24*60;
  }
  mm_sum += (day-1) * 24 * 60+hh*60+mm;
  double rot = mm_sum / 24.0 / 60 * (1+1/365.24) * 2 * PI ; 
  int n;
  cin>>n;
  FOR(_,n){
    string name ; int m ;
    cin>>name>>m;
    bool ok = true;
    FOR(i,m){
      double a,h;
      cin>>a>>h;
      if(check(a,h,rot)==false){
        ok = false;
      }
    }
    if(ok) cout<<name<<endl;
  }
  return 0;
}

参考URL

http://hooktail.sub.jp/mathInPhys/quaternion/

Permalink | コメント(0) | トラックバック(0) | 19:53

2010年07月08日

■TCO 2010 Marathon Match Round 2

問題内容

セルオートマトンの状態遷移ルールと初期状態が与えられるので、

高々N個のマスを反転させて、Kステップ後の黒マスの個数を大きくせよ。

戦略

一マスずつ反転していく形の疑似焼き鈍し法
あとは高速化

それだけ。

高速化手法

インラインアセンブラやMMX、SSEは、どうやればいいのかのノウハウがなかったので、結局使わなかった。

また、ローカルで速度が上がっても、TopCoderサーバー上だとあまり効果ないこともしばしば。

以下、効果があったであろう順。

セルオートマトンのシミュレーション

１マスだけ反転した場合は、Kステップ後の盤面に対して、高々(K*2+1)^2 マスにしか影響がないので、反転のあったマスのバウンディングボックスを求めて、必要最低限の領域だけ再計算する。

C# -> C++ に書き直す

（ｒｙ

gettimeofdayを極力呼ばないようにする

理由は、TopCoderサーバー上だと非常に遅いため。

適当に、今からタイムアウトまでの焼き鈍し法による反復数を見積もって、その反復数/10回後にまた同じことをする、という感じの処理で高々２００回ぐらいしか呼ばないようにした。

深いループのIF文を除去（１）

before

bool new_state = false;
char ch = RULES[count];
if (ch == '-') ;
else if (ch == '+') new_state = true;
else if (ch == '=') new_state = board[id];
else new_state = !board[id]; // 'X'

after

new_state = NEXT[count][board[id]] ; //NEXTは事前計算

深いループのIF文を除去（２） / loop unrolling

ローカルだと効果あったけれど、サーバー実機だとそんなことはなかった。

before

for(int i=0;i<=K;i++)
{  
  for(...
     for(...
         // 重い処理とかループとか
         if(i==K) score += INC[b];
}

after

Kステップ目だけ分離

i=0;
for(;i<K;i++)
{  
  for(... for(... // 重い処理やループ
}
{ // i == K 
  for(... for(... // 重い処理やループ
     score += INC[b];
}

剰余、かけ算は事前に計算結果をテーブルに格納しておく

x % R , x % C , x * C は使う頻度が高いので。

FOR(i,SIZE){
 ::MODR_TABLE[i] = (i-SIZE/2+10000*R)%R;
 ::MODC_TABLE[i] = (i-SIZE/2+10000*C)%C;
 ::MULC[i]=i*C;
}

exp をマクローリン展開

before

inline bool anneal(double temperature, double difference)
{
  if (difference >= 0) return true;
  return NextDouble() < exp(difference/temperature) ;
}

after


inline bool anneal(double temperature, double difference)
{
  if (difference >= 0) return true;
  difference /= temperature;
  return NextDouble() < 1 + (1 + difference*(0.5+difference/6.0)) * difference ;
}

他

配列はポインタを使って、添え字を極力なくす
グローバル変数を一旦ローカル変数に移す（最適化されやすくなるらしい）
const , inline はできるだけつけておく
焼き鈍しのパラメタははじめの100msで時間計測して自動調整

結果

50.39で暫定15位。後半ぜんぜんスコアが伸びなかった…。

Permalink | コメント(0) | トラックバック(0) | 21:49

2010年05月05日

■[TopCoder] Marathon Match 59(2)

最終結果は4位だった。今までで暫定順位から一番上がったほうだと思う。

2401 -> 2455

そういえば、前回のエントリで書かなかったけれど、当初、本棚に入れていく本の順番は

単位幅あたりの価値 value/width

が高い順にしていた。

ここから少しいじって

value/pow(width,0.9)

にしたらそこそこ良くなったので、最終的にはこちらを採用してた。

（seed 1-1000のスコア合計が 4747774 から 4748521 ぐらいへ上昇）

どうしてスコアが良くなるのかはよく分かっていない。

Permalink | コメント(0) | トラックバック(0) | 12:09

2010年05月03日

■[TopCoder] TopCoder Open 2010 Algorithm Qualification Round 1

Algorithm系の参加記録は久しぶりだったので、形式と書き方を変更してみた。

250 GirlsAndBoys

G*B*かB*G*の形式(正規表現)にすればいいので、両方に場合について試すだけ
GとBの寄せ方に必要なスワップ回数にバブルソートを実装しようかなと一瞬思ったけれど、単純なループで実装できた。
サンプル通ったので送信

500 RobotSimulation

どうみても全部シミュレーションしたらTLE
ただよく考えると、ある程度反復処理したら、それ以降はマス数は同じだけ増えていくよね。
適当にまず高々500回ためして、それ以降は500回目で増えた到達マス数だけ増えると決めつけるようにして送信。

1000 SequenceMerger

二部探索だということはすぐわかる
でも入力がlong longオーバー可能な仕様になっている
いろいろパターン分けするのが面倒なので多倍長演算で処理処理…。
サンプルは通ったが、サンプル１で100msとか非常に遅い。このままではTLE
ボトルネックになっているところをメモ化でadhoc最適化
終了直前に送信

Challenge Phase

一回成功一回失敗

System Test

1000落ちた。
- 部分的にlong longを使っていたところでオーバーフローしてたみたい
- そこを直しても多倍長演算が重いのかTLE
- そもそも1000000000より大きい数字は1000000000+1000とかにすれば多倍長演算必要ないよね
- 全部書き直したら通った。

結果

o o x で45位。通過圏内。

1000 (終了後)

Permalink | コメント(0) | トラックバック(0) | 11:43

2010年04月29日

■[TopCoder] Marathon Match 59

TCO2010 MM Round1（4 weeks）に参加するのがしんどいので参加。

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14227&pm=10885

問題概要

本棚がひとつ与えられるので、与えられる本からいくつか選んで、本の価値の合計が最大になるように本棚を入れてください。

入力

本棚のサイズ W , H
各々の本のサイズと価値 width , height , value

条件

本棚をn段にするには高さ10の仕切りをn個設置する必要がある。
制限時間2秒
最大メモリ1024M

Visualizer

戦略

あらかじめ本の高さに10を足しておけば、仕切りを考える必要がなくなって少し楽になる。

その１

以下を制限時間まで繰り返す。

ランダムに本棚の段数を決める。（1000回以上繰り返したら、最高スコアの棚の段数を常に採用する）
ランダムに各段の高さを決める。（なるべく高さが偏らない程度にランダム）
単位幅あたりの価値 value/width が高い本から順番に、できるだけ高さが小さい段に貪欲に入れていく。
1～3で、一番良かった解を返す。

これで暫定スコア 468213（初Submit）。

その２

いくつか改良して、

前半は「戦略その１」をそのまま適用
後半は焼きなましっぽい方法でそれまでの最大解の本棚の高さを少し変えた近傍の状態について、貪欲法で評価しながら探索していく。
1～2で得られた上位十数件の解の本棚について以下のDPを適用する
1. 一番高さが低い棚について価値が最大になるような本の入れ方をナップサックDPを使って求める
2. 以降も同様、まだ使っていない本を低い棚から順番にDPを使って本を入れていく。
  - この方法だと貪欲法と比べて性能が良く、スコアがたいてい1～10は上がるが速度が非常に遅いので、一番最後に貪欲法で良いスコアな解についてまとめて適用するようにしている。

これで468700ぐらい。

あとはパラメタ調整、バグ修正を繰り返して終了。結果暫定8位。

Permalink | コメント(0) | トラックバック(1) | 18:12

2009年12月22日

■[TopCoder] Marathon Match 57

問題概要

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14162&pm=10679

long hash(str){
    long hash = 5381;
    for(i = 0; i<str.length; i++)
        hash = (hash * 33) ^ str[i]; // '^' denotes XOR
    return hash;
}

上記のハッシュ関数に変換された長さ４～２０の文字列のハッシュ値が与えられる。そのハッシュ値と同じ値を返すような文字列を求めよ。文字列の文字コードは33～126の範囲。

やったこと

C#で、ハッシュ関数の逆関数（？）を探索使って実装すると

string inverse_hash_dfs(ulong hash)
{        
    if (hash < 5381) return null;
    if (hash == 5381) return "";
    ulong lower = hash & (~(0xffUL));
    lower = lower + (33 - lower % 33) % 33;
    ulong upper = lower | (0xffUL);
    String ret = null;
    for (ulong i = lower; lower <= i && i <= upper; i+=33)
    {
        ulong ch = i ^ hash;
        if (33 <= ch && ch <= 126)
        {
            String sub = inverse_hash_dfs(i / 33);
            if (sub == null) continue;
             if (ret == null || ret.Length > sub.Length + 1)
            {
                ret = sub + (char)ch ;
            }
        }
    }
    return ret;
}

これで、ハッシュ関数内で64bitでオーバーフローしない10文字以下の文字列のハッシュ値については、すべて逆算できるようになる。さらにメモ化すると一瞬で計算が終わる。

11文字以降については、オーバーフローによって65bit以降の情報が失われているものの、20文字の場合でも高々128bitを超えないので、自作で128bitクラスを描いてみる。

あとは、失われた上位64bitを1から順番試して、復元できたらそれを返すようにすればよさそう。でも計算量の関係で、長さ15ぐらいが限度かなー、と思っていたらすべてのテストケースについて一瞬で復元が成功するようになった。

いろいろ試してみるとどうやら、長さが14以上の文字列のハッシュ値は、長さが13以下の文字列に復元できてしまうらしい。

10000ケーステストしてみて、失敗することがなさそうだったのでサブミットしたところ1位タイになった。これはどうみても最適解っぽい。

些細なバグを修正した段階ですることがなくなったのでそのままCoding Phase 終了。

結果

最終結果も1位。1位が77人いるという異様な結果に。。。

Ratingのほうは、1位タイが大量にいるので65ほど減るはずだったけれど、今回は特別処置として1上がることになった。

2400 -> 2401

Permalink | コメント(0) | トラックバック(0) | 18:59

2009年10月16日

■[TopCoder] Marathon Match 56

問題概要

二次元空間上に存在するいくつかの点について、面積の総和が小さくなるように高々M個の円を配置してそれらの点を全て覆ってください。

Visualizer

やってみたこと

K-means++ で点集合を M 個のグループに分ける
各々のグループごとに最小包含円を配置する
各々の点についてスコアが上がるよう貪欲に所属するグループを変更していく。
1～3を何度も繰り返して、一番いいスコアになる配置を返す。

これで、seed 1-100のスコアの合計が20500ぐらい。

第一週の土日でここまで組んだけれど、それ以降エレガントな方法が思いつかず、Submitせずにそのまま終了。

Permalink | コメント(2) | トラックバック(0) | 08:03

2009年10月15日

■[program] Google Code Jam 2009 Round 3

今回は箇条書きで書いてみる。

D

問題読んでみる
入力の高いので簡単には解けなさそう。

B

最初、線形だと勘違いして事前計算でなんとかなるのでは？　と思って時間を10分ぐらい浪費
smallは全探索でなんとかなりそうなのでコーディング開始
書き終わる。でも最悪ケースで2秒ぐらいかかる。
定数倍高速化を施し、small入力ファイルをダウンロードして実行
最悪ケースばかりでかなり時間かかる。。。2分弱で実行完了。
いざ送信。AC
これは高速化しなかったらまず間に合わなかった。

A

英文長い。
図や題目からして倉庫番＝幅優先探索
プレイヤーの初期位置はどうなるのだろうかと英文をよく読んでみたら、プレイヤーはテレポートできるらしい
なら普通の倉庫番より簡単そう、ということで普通に幅優先で組みはじめる
ブロックの連結判定はUnion-Findで実装。
実装問題にもかかわらず、珍しく25分ぐらいで書き終えて、サンプルも通ったので、そのまま small と largeを送信

C

点彩色問題。
DPかな、と思ったけれど全く思いつかない。

D

考えても見てもやはりよく分からない。
なにか勘違いしたのか区間内の回文数の個数を出すプログラム書いたけれど全く意味がなかった。

結果

21点 78位で通過ならず。Round2と同じようなパフォーマンスだったけれどそこそこ順位がよかった。

Permalink | コメント(0) | トラックバック(0) | 22:50

2009年09月27日

■[program] Google Code Jam 2009 Round 2

問題：http://code.google.com/codejam/contest/dashboard?c=204113#

A-small , A-large

N * N の 0-1 行列が与えられる。隣接行を入れ替えて、全ての1を対角部分以下に移すときの最小スワップ回数を求めよ。

上の行であるほど制約が厳しいので、貪欲に上から確定していけばよい。

D-small

植物の位置と大きさが与えられる。全ての植物に水が行き渡るように、円状に水を撒くスプリンクラーを２つ配置するとき、スプリンクラーが水を撒く円の半径の最小値を求めよ。

smallは 1 <= N <= 3 であるので場合分けで終わり。

C-small

N個の折れ線グラフを互いに交わらないように、複数のチャートに分けて書くとき、必要なチャートの個数を求めよ。

折れ線グラフは半順序関係を満たすので、DAGを作ってトポロジカルソートしたうえで、

状態数 2^16(配置済みの折れ線情報) * 16(着目している折れ線) * (16+1)(一つ前に置いた折れ線) でメモつき探索した。

ただ、バグを入れまくって、さらにDAGを作る部分をミスって一回WA貰ったorz。

Largeは dilworth's theorem より、二部マッチングで解けるらしい。

B-small , B-large

ブロックを掘ったり、左右に移動したり、飛び降りたりして一番下の階層に行くとき、掘る必要があるブロックの最小個数を求めよ。

結局全部最小値問題かー、と思いながら考える。

smallは 10*6(位置情報) * 2^10(今いる階層の状態) * 2^10(一つ下階層の状態)でメモ付き探索すればよさそう。だが、またビットDPする体力がなかった。

少し考えると(位置情報) * (その位置から左側何個分ブロックが削られているか) * (その位置から右側何個分ブロックが削られているか) = 50^4 の状態数で順位優先探索（＝ダイクストラ）すれば large も解けそうなので、組み始める。

でも実装が重く、バグ入れまくって、間に合わなかった。。。

結果

28点 498位で奇跡的に通過圏内。危なさすぎ。とりあえず T-Shirt ゲットできそうなので満足しておきます。

Permalink | コメント(0) | トラックバック(0) | 12:01

■[TopCoder] Marathon Match 65

Visualizer

戦略

おおまかな流れ

評価の基準

空きマスの連結成分のペナルティポイントの計算

高速化

結果

■ boost::math::quaternionでUTPC2010 G問題を解いてみた

コード

参考URL

■TCO 2010 Marathon Match Round 2

問題内容

戦略

高速化手法

セルオートマトンのシミュレーション

C# -> C++ に書き直す

gettimeofdayを極力呼ばないようにする

深いループのIF文を除去（１）

深いループのIF文を除去（２） / loop unrolling

剰余、かけ算は事前に計算結果をテーブルに格納しておく

exp を マクローリン展開

他

結果

■[TopCoder] Marathon Match 59(2)

■[TopCoder] TopCoder Open 2010 Algorithm Qualification Round 1

250 GirlsAndBoys

500 RobotSimulation

1000 SequenceMerger

Challenge Phase

System Test

結果

1000 (終了後)

■[TopCoder] Marathon Match 59

問題概要

入力

条件

Visualizer

戦略

その１

その２

■[TopCoder] Marathon Match 57

問題概要

やったこと

結果

■[TopCoder] Marathon Match 56

問題概要

Visualizer

やってみたこと

■[program] Google Code Jam 2009 Round 3

D

B

A

C

D

結果

■[program] Google Code Jam 2009 Round 2

A-small , A-large

D-small

C-small

B-small , B-large

結果

exp をマクローリン展開