Hatena::Grouptopcoder

hasiの日記

2014-12-15ICFPC2014参加記(今更)

Competitive Programming Advent Calendar 2014の記事です。

\DiamondPrincess!/

@mecha_g3, @shohei909, @hasi_t, @___Johniel の4人でチーム DiamondPrincess として、

ICFP Programming Contest 2014 に参加しました。

もう5ヶ月ほど前ですね。。

問題概要

(省略)

gcc++作成

宿泊しようかという案もあったが結局 @hasi_t 宅に集まることに。

問題文長いと言いつつ4人で問題文を読む。

@hasi_t はひたすらThe Lambda-Man CPU simulatorを触る。


とりあえずラベルを行番号に変換するやつがないと困るので、雑にPerlスクリプトを書く。

(ちなみに、業務でPerlはほとんど書かない)

次に、関数定義と呼び出しを作る。

ここらへんから「if文の書き方がわからん」とぐちりながら、なんとかif文を書けるようにする。

いろいろ動かしてみると、ループがないと使いづらいので、ループを作成。

ここらへんで朝になり、一旦解散。仮眠をとる。

仮眠から起きて、ローカル変数を作る。

そうしてできたgcc拡張 :

関数定義 :
  FUNC funcname [argname ...]
  VAR [varname ...]
    [関数内容]
  RTN ; これは元からある命令

関数呼び出し :
  [引数push]
  CALL funcname

引数をpush :
  PUSH argname

ローカル変数をpush :
  GET varname

ローカル変数にset :
  値push
  SET varname

IF文 :
  条件push
  IF
    [処理]
  ELSE
    [処理]
  ENDIF

ループ :
  DO
    [処理]
    条件push
  BREAK
    [処理]
  LOOP

演算は基本的にgccに元からあるものを使う。

なので書くコードはほとんどgccを直接書く感じに。

でも、こんだけあればとりあえず書けるやろということでAI作成に移行。

AI作成 (lightning round)

とりあえず貪欲にpillを食べるやつを作る。あと逆方向に進まないように。

同じ所をぐるぐる回り続けてしまうので、評価値同じならランダムに選ぶようにする。

ghostに殺されるのでマンハッタン距離でghostを避けるのを実装したところで提出。


提出後は夕食に行き方針を話し合う。

@hasi_tは引き続き Lamda-Man AI を作り、ghost は他の3人に任せることに。

gcc++修正

lightning roundは人力コンパイルつらい、型が欲しい、とぼやきながらのAI実装だった。

しかし、やっぱり人力コンパイルでがんばることに。

ただ、push命令が、引数はPUSH、ローカル変数はGET、定数はLDC

と分かれている状態だけはなんとかしようと思い、汎用push命令 P を追加。

AI作成 (full round)

ひたすらThe Game mechanicsで動かして挙動を見ながらAIを修正する。

タブレットPCではThe Game mechanicsの動作も遅いなあってなった。


クリアボーナス欲しいので、pillを全部取れるように、そして死なないようにしたい。

敵の動きも読みやすいのでいい感じにしたい。

そこで、敵の動きをDFSして進路を避けるのと、BFSでpill探すのを作ることにした。


Hall of Fameが追加。Wow!

fruitの重要性に気づき、fruitが出現したら取りに行くやつを作る。


結局できたロジック :

  1. 必ず動く
  2. 敵の進路から逃げる(power pill状態では評価値反転)
  3. fruit出現時はfruitに近づく
  4. pillに近づく

power pill残り700tickで評価値反転をやめるつもりが、

; if (pow > 700)
P pow
P 0 ; 正しくは P 700
CGT

こんなバグが含まれているのに土壇場で気付き、

classicの点数が8000点台だったのが17200になったところで提出。

ghost は @shohei909 さんのを提出。結局どういうのかよくわかっていない。。

まとめ

コンパイラは作れず、シミュレータも全く書かなかったので、

ひたすら泥臭くアセンブラを書き続けるコンテストでした。

ちょっとしたコードを書くにも時間かかるので、

最終日は時間無いーとひぃひぃ言っていました。

高級言語ってすばらしい。。


提出したコード : https://github.com/hasipon/DiamondPrincess

結果

Third prize!

Perl が not too shabby になってしまった。わははは

2011-12-22

makeのしかた

09:41

Competitive Programming Advent Calendar 22日目の記事です。

GNU makeの使い方です。

一般的にはインストールのときとかに使うものだと思うのですが、

自分がよく使う、インストール以外の使い方を紹介します。

競技的な使い方の一例として参考になったら幸いです。

コンパイル

「make (プログラム名)」だけでコンパイルできます。暗黙のルールが働いています。

$ cat >a.cpp
#include <iostream>
int main() {
	std::cout << "gudapoyo" << std::endl;
}
$ ls
a.cpp
$ make a
g++     a.cpp   -o a
$ ./a
gudapoyo
$ make a
make: `a' is up to date.

Makefile

コンパイルオプションを指定したい。Makefileを使いましょう。

-Wallと-O2をつけてみました。g++のコンパイルオプションはCXXFLAGSで指定できます。

$ cat >Makefile
CXXFLAGS = -Wall -O2
$ ls
Makefile  a  a.cpp
$ rm a
$ make a
g++ -Wall -O2    a.cpp   -o a

並列実行

いわゆる馬鹿パラレル。

makeの-jオプションを使うと簡単に並列実行できます。

Makefileをスクリプトで生成して、「make -j 4」とか「make -j 8」とかで実行します。

Marathonとかでたくさん実行したいときに使っています。

マルチコアだと速くなって楽しい。

$ mkdir out
$ cat >makefile.pl
for $i (1..100) {
        push(@a,"out/$i");
}
print "all:".join(' ', @a)."\n";
for $i (1..100) {
        print "out/$i:\n\t./a -seed $i > out/$i\n";
}
$ perl makefile.pl >Makefile
$ head Makefile
all:out/1 out/2 out/3 out/4 out/5 out/6 out/7 out/8 ... (省略)
out/1:
        ./a -seed 1 > out/1
out/2:
        ./a -seed 2 > out/2
out/3:
        ./a -seed 3 > out/3
out/4:
        ./a -seed 4 > out/4
out/5:
$ make -j 4
./a -seed 1 > out/1
./a -seed 2 > out/2
./a -seed 3 > out/3
./a -seed 4 > out/4
	:
	:
$ ls out
1    14  2   25  30  36  41  47  52  58  63  69  74  8   85  90  96
10   15  20  26  31  37  42  48  53  59  64  7   75  80  86  91  97
100  16  21  27  32  38  43  49  54  6   65  70  76  81  87  92  98
11   17  22  28  33  39  44  5   55  60  66  71  77  82  88  93  99
12   18  23  29  34  4   45  50  56  61  67  72  78  83  89  94
13   19  24  3   35  40  46  51  57  62  68  73  79  84  9   95

NileshNilesh2012/11/14 20:33That hits the tagret perfectly. Thanks!

udjgbdvudjgbdv2012/11/15 12:172ZdjsX <a href="http://agskveituhta.com/">agskveituhta</a>

vdbhzuppevdbhzuppe2012/11/16 10:42JDVP89 , [url=http://gsfuxbicbcnf.com/]gsfuxbicbcnf[/url], [link=http://ffrmhckcshoj.com/]ffrmhckcshoj[/link], http://gkkpgfwblfeu.com/

lcxtnzvtklcxtnzvtk2012/11/17 11:24spbpW3 <a href="http://duybwpglmbcz.com/">duybwpglmbcz</a>

2011-02-11

Last Submission Time日本時間化ブックマークレット

14:47

SRMのsystest待ちの間にMarathon MatchのLast Submission Timeを日本時間に変換するブックマークレット書いてた。

chrome用。夏時間非対応。

javascript:(function(){var i,tr=document.getElementsByTagName("tr");for(i=0;i<tr.length;++i){(function(x){var f=0,t=x,y=x.childNodes,b,d,e,j;for(;t;t=t.parentNode){if(t.className=="statTable"){f=1;break;}}if(f&&y.length==15&&y[7].childNodes.length==1){b=y[7].textContent.split(/[ .:]/);if(b.length==6){d=new Date(Date.UTC(b[2],b[0]-1,b[1],b[3]-0+5,b[4],b[5]));e=[d.getMonth()+1,d.getDate(),d.getHours(),d.getMinutes(),d.getSeconds()];for(j=0;j<5;++j){if(e[j]<10)e[j]="0"+e[j];}y[7].textContent=e[0]+"/"+e[1]+" "+e[2]+":"+e[3]+":"+e[4]+"(JST)";}}})(tr[i]);}})()

2010-11-11

Marathon Match 66 - DigitsPattern

18:14

たまには最終テスト前に。

問題

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14412&pm=11123

手法

たぶんd:id:komiyam:20101110:1289412487と同じ。でもこっちのほうがちょっと速そう。6*7のケースがローカルで2秒ぐらい。でもメモ化とかはしてない。

(追記:辺の向きが逆になってて得意苦手が逆転しているらしい)

アルゴリズムをJavaScriptで可視化してみた。確認用に作った。

http://imoz.jp/temp/mm/mm66.html (chromefirefoxでテスト)

ソース

#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <algorithm>

using namespace std;

typedef pair<int,int> pairint;
#define mp make_pair

const int di[4] = {+1, 0,-1, 0};
const int dj[4] = { 0,+1, 0,-1};

int H, W;
int tar[128][128];
bool unv[128][128];
bool vis[128][128];
vector<pairint> result;
typedef map<pairint, vector<pairint> > P_t;
P_t P;

class DigitsPattern {
public:
    void visit(pairint n) {
        if (vis[n.first][n.second]) return;
        vis[n.first][n.second] = true;
        const vector<pairint>& a = P.find(n)->second;
        for (unsigned i = 0; i < a.size(); ++ i) {
            visit(a[i]);
        }
        result.push_back(n);
    }

    int func(vector<pairint>& Q, P_t& parents) {
        vector<pairint> R;
        int score = 0;
        for (;;) {
            for (unsigned p = 0; p < Q.size(); ++ p) {
                int i = Q[p].first;
                int j = Q[p].second;
                int n = 0;
                for (int k = 0; k < 4; ++ k) {
                    if (unv[ i+di[k] ][ j+dj[k] ]) ++ n;
                }
                if (n == 0) {
                    score += abs(tar[i][j]);
                    unv[i][j] = false;
                } else if (tar[i][j] <= 0) {
                    unv[i][j] = false;
                    score += -tar[i][j];
                    for (int k = 0; k < 4; ++ k) {
                        if (unv[ i+di[k] ][ j+dj[k] ]) {
                            -- tar[ i+di[k] ][ j+dj[k] ];
                            parents[Q[p]].push_back(mp(i+di[k], j+dj[k]));
                        }
                    }
                } else if (tar[i][j] >= n) {
                    unv[i][j] = false;
                    score += tar[i][j] - n;
                    for (int k = 0; k < 4; ++ k) {
                        if (unv[ i+di[k] ][ j+dj[k] ]) {
                            parents[mp(i+di[k], j+dj[k])].push_back(Q[p]);
                        }
                    }
                } else {
                    R.push_back(Q[p]);
                }
            }
            if (Q.size() == R.size()) break;
            Q.swap(R);
            R.clear();
        }
        if (Q.size() != 0) {
            vector< vector<pairint> > clus;
            for (unsigned p = 0; p < Q.size(); ++ p) {
                int i = Q[p].first;
                int j = Q[p].second;
                if (unv[i][j]) {
                    vector<pairint> a;
                    stack<pairint> S;
                    S.push(Q[p]);
                    unv[i][j] = false;
                    while (!S.empty()) {
                        pairint t = S.top();
                        S.pop();
                        a.push_back(t);
                        for (int k = 0; k < 4; ++ k) {
                            pairint s(t.first + di[k], t.second + dj[k]);
                            if (unv[s.first][s.second]) {
                                S.push(s);
                                unv[s.first][s.second] = false;
                            }
                        }
                    }
                    clus.push_back(a);
                }
            }
            for (unsigned p = 0; p < clus.size(); ++ p) {
                score += select(clus[p], parents);
            }
        }
        return score;
    }

    int select(const vector<pairint>& Q, P_t& parents) {
        P_t par0;
        vector<int> tartmp(Q.size());
        for (unsigned p = 0; p < Q.size(); ++ p) {
            int i = Q[p].first;
            int j = Q[p].second;
            tartmp[p] = tar[i][j];
            par0.insert(mp(Q[p], vector<pairint>()));
        }
        int best = 1<<30;
        P_t B;
        for (unsigned p = 0; p < Q.size(); ++ p) {
            for (unsigned q = 0; q < Q.size(); ++ q) {
                int i = Q[q].first;
                int j = Q[q].second;
                unv[i][j] = (p != q);
            }
            int i = Q[p].first;
            int j = Q[p].second;
            P_t par = par0;
            int n = 0;
            for (int k = 0; k < 4; ++ k) {
                if (unv[ i+di[k] ][ j+dj[k] ]) {
                    ++ n;
                    par[mp(i+di[k], j+dj[k])].push_back(Q[p]);
                }
            }
            vector<pairint> QQ = Q;
            QQ.erase(QQ.begin() + p);
            int score = func(QQ, par) + (n - tar[i][j]);
            if (score < best) {
                best = score;
                B = par;
            }
            for (unsigned q = 0; q < Q.size(); ++ q) {
                int i = Q[q].first;
                int j = Q[q].second;
                tar[i][j] = tartmp[q];
            }
            unv[i][j] = true;
        }
        for (P_t::const_iterator i = B.begin(); i != B.end(); ++ i) {
            for (unsigned j = 0; j < i->second.size(); ++ j) {
                parents[i->first].push_back(i->second[j]);
            }
        }
        for (unsigned q = 0; q < Q.size(); ++ q) {
            int i = Q[q].first;
            int j = Q[q].second;
            unv[i][j] = true;
        }
        return best;
    }

    vector <int> recreate(vector <string> targetPattern) {
        H = targetPattern.size();
        W = targetPattern[0].size();
        vector<pairint> Q;
        for (int i = 0; i < H; ++ i) {
            for (int j = 0; j < W; ++ j) {
                if (targetPattern[i][j] != '.') {
                    tar[i+1][j+1] = targetPattern[i][j]-'1';
                    unv[i+1][j+1] = true;
                    Q.push_back(mp(i+1, j+1));
                    P.insert(mp(mp(i+1, j+1), vector<pairint>()));
                }
            }
        }
        func(Q, P);
        for (P_t::const_iterator i = P.begin(); i != P.end(); ++ i) {
            visit(i->first);
        }
        vector<int> r(result.size()*2);
        for (unsigned i = 0; i < result.size(); ++ i) {
            r[2*i]   = result[i].first-1;
            r[2*i+1] = result[i].second-1;
        }
        return r;
    }
};

2010-05-24

Marathon Match 60 - PolymerPacking

00:40

だめだった。

問題

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14264&pm=10918

リンク先の図のような曲線を、折れ曲がったところで鏡像反転して、折れ線の(xmax-xmin)*(ymax-ymin)を小さくしろ、という問題。

ただし、鏡像反転するときに折れ線が交差したり重なったりしてはいけない。

手法

手法その1

幅優先探索っぽい方法。キューじゃなくてランダムに取り出したり、優先度付きキューにしてみたり。

手法その2

訪問済みかどうか記憶させる処理が無駄っぽかったので、手法その1は却下。

何回もランダムに折り曲げて、最も小さくなる操作を記憶。

時間計測

clock使ってたけど、意図した時間が計れなくて悩まされた。sys/time.hのgettimeofday使ったらうまくいった。

結果

51位。Rating: 1769 → 1707