Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-08-23

GDD10 DevQuiz参戦メモ

13:09 | GDD10 DevQuiz参戦メモ - naoya_t@topcoder を含むブックマーク はてなブックマーク - GDD10 DevQuiz参戦メモ - naoya_t@topcoder GDD10 DevQuiz参戦メモ - naoya_t@topcoder のブックマークコメント

〜8/23

基本週末のみ(最後のほうはCPU時間があいてる時にいつでも自動探索)で割と楽しめた。

http://gyazo.com/33057a9bfd8fe02d3f923527722c707d.png

以下メモ(思い出しながらちまちま追記)

基本問題

15:03 |  基本問題 - naoya_t@topcoder を含むブックマーク はてなブックマーク -  基本問題 - naoya_t@topcoder  基本問題 - naoya_t@topcoder のブックマークコメント

  • ぐぐったり
  • 停止していたBuzzを再開したり
  • Android実機(GDDふぉんですが)を引っ張りだしてきたりとか

2-legged OAuth

15:03 |  2-legged OAuth - naoya_t@topcoder を含むブックマーク はてなブックマーク -  2-legged OAuth - naoya_t@topcoder  2-legged OAuth - naoya_t@topcoder のブックマークコメント

import httplib,urllib,urllib2
import oauth
 
url = "http://gdd-2010-quiz-japan.appspot.com/oauth/########################"

params = { 'hello': 'world' }

consumer_key = '########################'
secret_key   = '########################'
 
consumer = oauth.OAuthConsumer(consumer_key, secret_key)

request  = oauth.OAuthRequest.from_consumer_and_token(consumer, http_method='POST', http_url=url, parameters=params)
request.sign_request(oauth.OAuthSignatureMethod_HMAC_SHA1(), consumer, None)

print request.to_url()
print request.to_header()

conn = httplib.HTTPConnection("gdd-2010-quiz-japan.appspot.com")
conn.request("POST", "/oauth/########################", urllib.urlencode(params), request.to_header('devquiz'))
response = conn.getresponse()
print response.status, response.reason
data = response.read()
conn.close()
print data

MAPS API

15:03 |  MAPS API - naoya_t@topcoder を含むブックマーク はてなブックマーク -  MAPS API - naoya_t@topcoder  MAPS API - naoya_t@topcoder のブックマークコメント

  • A地点を出発し、A地点に戻ってくる
  • A地点→B地点, B地点→A地点 では所要時間が異なる場合がある(と問題文で教えてくれていた)
  • 全部で最大10地点 → 経路候補は全部で9!通りしかない。permutation全部調べても余裕でしょ →Gaucheで簡単なスクリプトを書いた
  • APIから所要時間を引っ張ってくるのが面倒だった
  • xmlきれいなのでsedで抜いてきたとか
  • ソース全部まとめてアップロードしてエラーが起きないとは思えなかった(ZIPバイナリをだらだらと表示しかねないと思った)ので、gaucheで書いた肝の部分のみアップ

APIを叩いて結果をXMLで取得するAWKスクリプト

BEGIN {
  M=0
#  awk -f lookup.awk -v level=1 < level1.dat
#  awk -f lookup.awk -v level=2 < level2.dat
#  awk -f lookup.awk -v level=3 < level3.dat
}

{
  split($0,ar," ")

  name[M] = ar[1]
  lat[M] = ar[2]
  long[M] = ar[3]

  M++
}

END{
  for(i=0;i<M;i++){
    for(j=0;j<M;j++){
      if (i==j) continue;
      cmd = sprintf("wget \"http://maps.google.com/maps/api/directions/xml?origin=%9.6f,%10.6f&destination=%9.6f,%10.6f&language=ja&sensor=false\" -O level%d_from%02d_to%02d.xml", lat[i],long[i], lat[j],long[j], level,i,j)
      system(cmd)
      print cmd
    }
  }
}
  • XMLから必要なデータを抽出しS式化する過程はsedのワンライナーで書いた(そして忘れた)ので省略
(use srfi-1)
(use util.combinations)

;;
;; level 3
;;
(define cities
        #(
                ("東京タワー" 35.658570 139.745484)
                ("首里城" 26.216991 127.719362)
                ("松山城" 33.842035 132.764806)
                ("青葉城跡" 38.251127 140.855294)
                ("五条大橋" 34.995682 135.767890)
                ("日光東照宮" 36.758051 139.598899)
                ("日本銀行" 35.686839 139.771438)
                ("海ほたる" 35.464380 139.874407)
                ("日本科学未来館" 35.619415 139.776550)
                ("東京大学" 35.712940 139.759590)
                ))

;;
;; 各点間の所要時間は別スクリプトでAPIを呼び出して調べました。
;;
(define durations-data
        '(
        ((0 . 1) . 150131)
        ((0 . 2) . 40217)
        ((0 . 3) . 18011)
        ((0 . 4) . 21655)
        ((0 . 5) . 9716)
        ((0 . 6) . 821)
        ((0 . 7) . 2365)
        ((0 . 8) . 1071)
        ((0 . 9) . 1314)
        ((1 . 0) . 150327)
        ((1 . 2) . 121112)
        ((1 . 3) . 165946)
        ((1 . 4) . 129338)
        ((1 . 5) . 158930)
        ((1 . 6) . 150307)
        ((1 . 7) . 151256)
        ((1 . 8) . 150658)
        ((1 . 9) . 150769)
        ((2 . 0) . 40689)
        ((2 . 1) . 121187)
        ((2 . 3) . 56308)
        ((2 . 4) . 19700)
        ((2 . 5) . 49292)
        ((2 . 6) . 40669)
        ((2 . 7) . 41618)
        ((2 . 8) . 41020)
        ((2 . 9) . 41131)
        ((3 . 0) . 18369)
        ((3 . 1) . 166422)
        ((3 . 2) . 56508)
        ((3 . 4) . 37946)
        ((3 . 5) . 14511)
        ((3 . 6) . 18114)
        ((3 . 7) . 20094)
        ((3 . 8) . 18732)
        ((3 . 9) . 18043)
        ((4 . 0) . 21981)
        ((4 . 1) . 129354)
        ((4 . 2) . 19440)
        ((4 . 3) . 37600)
        ((4 . 5) . 30584)
        ((4 . 6) . 21961)
        ((4 . 7) . 22910)
        ((4 . 8) . 22312)
        ((4 . 9) . 22423)
        ((5 . 0) . 9730)
        ((5 . 1) . 159016)
        ((5 . 2) . 49102)
        ((5 . 3) . 14135)
        ((5 . 4) . 30540)
        ((5 . 6) . 9475)
        ((5 . 7) . 11455)
        ((5 . 8) . 10093)
        ((5 . 9) . 9404)
        ((6 . 0) . 937)
        ((6 . 1) . 150406)
        ((6 . 2) . 40492)
        ((6 . 3) . 17702)
        ((6 . 4) . 21930)
        ((6 . 5) . 9407)
        ((6 . 7) . 2379)
        ((6 . 8) . 1085)
        ((6 . 9) . 854)
        ((7 . 0) . 2658)
        ((7 . 1) . 151693)
        ((7 . 2) . 41779)
        ((7 . 3) . 19913)
        ((7 . 4) . 23217)
        ((7 . 5) . 11618)
        ((7 . 6) . 2559)
        ((7 . 8) . 2291)
        ((7 . 9) . 3112)
        ((8 . 0) . 1189)
        ((8 . 1) . 150658)
        ((8 . 2) . 40744)
        ((8 . 3) . 18444)
        ((8 . 4) . 22182)
        ((8 . 5) . 10149)
        ((8 . 6) . 1090)
        ((8 . 7) . 1912)
        ((8 . 9) . 1643)
        ((9 . 0) . 1170)
        ((9 . 1) . 150703)
        ((9 . 2) . 40789)
        ((9 . 3) . 17837)
        ((9 . 4) . 22227)
        ((9 . 5) . 9542)
        ((9 . 6) . 681)
        ((9 . 7) . 2816)
        ((9 . 8) . 1522)
                ))

(define M (vector-length cities))

(define shortest-time 999999999999999999)
(define shortest-route '())

(permutations-for-each
 (lambda (p)
;;       (print p) maybe 1 minute
   (let1 route (cons 0 (append p '(0)))
     (let loop ((a (car route)) (rest (cdr route)) (res '()))
       (if (null? rest)
           (let1 time (apply + (reverse! res))
             (when (< time shortest-time)
               (set! shortest-time time)
               (set! shortest-route route)))
                 (let* ((key (cons a (car rest)))
                        (dur (cdr (assoc key durations-data))))
                   (loop (car rest) (cdr rest) (cons dur res)))))))
 (iota (- M 1) 1))

(format #t "~a\t~d\n"
  (string-join
    (map (lambda (ix) (car (vector-ref cities ix))) shortest-route)
    " ")
  shortest-time)

しりとり

15:03 |  しりとり - naoya_t@topcoder を含むブックマーク はてなブックマーク -  しりとり - naoya_t@topcoder  しりとり - naoya_t@topcoder のブックマークコメント

  • 一応プログラム
  • けどlevel 3のグラフ構造は読み切れないのでlevel3のグラフは手書き
  • level 1, 2 は適当にやっても勝てるけど、level 3は向こうも勝ちに来るので
  • これまでの履歴と、相手が出してきた手から最善手を教えてくれるっぽいプログラムを書いた
  • level 3 はなんというかステージ1、ステージ2があって、ステージ1から先に抜けた方が負け、な感じ
    • ステージ1: d,e,f,g,i,j,q,s,w の中での移動
  • なのでステージ1の語だけ拾いだして上のプログラムを適用
  • (ステージ2に行ったら同じ文字に追い込めば勝てる!)
//...
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())
#define lastc(str) (*((str).end()-1))
#define RFOR(var,from,to) for(int var=(to);var>=(from);var--)

//#include "cout.h"

typedef pair<char,char> cc;

int arc[26][26];
long long trial=0LL;

typedef pair<int,int> ii;

#define LIM 5000000LL

int sub(int now, vector<int>& route)
{
  trial++; //if (trial%5000000LL == 0) printf("[%lld]\n", trial);
  if (trial >= LIM) {
    if (trial == LIM) printf("too deep. break.\n");
    return 0;
  }

  int way=0, res=0;
  rep(next,26){
    if (arc[now][next]){
      way++;
      arc[now][next]--;
      res = sub(next, route);
      arc[now][next]++;

      if (res < 0) {
        route.pb(-1);
        route.pb(now); return next;
      }
    }
  }
  if (way==0) {
    route.clear(); route.pb(now);
    return -1;
  }

  route.pb(now);
  return res ? -1 : 0;
}

void dump(int last)
{
  printf("\n%c.. ", 'a'+last);
  rep(c,26) printf(" %c", 'a'+c);
  printf("\n");
  
  rep(r,26){
    printf("%c ->", 'a'+r);
    rep(c,26){
      if (arc[r][c])
        printf(" %d", arc[r][c]);
      else
        printf(" -");
    }
    printf("\n");
  }
  printf("\n");
}

main(int argc, char **argv)
{
  rep(i,26) rep(j,26) arc[i][j]=0;
  int wn=0;

  if (argc != 2) {
    printf("usage: %s <word-list>\n", argv[0]);
    return 0;
  }
  FILE *fp = fopen(argv[1], "r"); if (!fp) return 0;
  char buf[256], first_str[256];
  while (fgets(buf,256,fp) != NULL) {
    //string s; cin >> s;
    int len = strlen(buf);
    while (len>0 && buf[len-1]<' ') buf[--len]=0;
    int b=buf[0]-'a', e=buf[len-1]-'a';
    if (wn == 0) strcpy(first_str, buf);
    arc[b][e]++; wn++;
  }
  fclose(fp);
  
  set<int> candidates;
  int last = 0, b, e;
  
  for (int wi=wn; wi>0; wi-=2) {
    if (wi < wn) {
      candidates.clear();
      rep(i,26) if (arc[last][i]) candidates.insert(i);
      if (candidates.empty()) {
        printf("YOU WIN!!\n"); break;
      }
    }
    printf("[%d] Which word did Google consume? ", wi);
    if (wi == wn) {
      printf("(%s) ", first_str);
    } else {
      printf("%c..[", 'a'+last);
      tr(candidates,it) printf("%c,", 'a'+*it);
      printf("] : "); fflush(NULL);
    }
    fflush(NULL);
    string s; cin >> s;
    switch (sz(s)) {
      case 0:
        b=last;
        rep(i,26) if (arc[last][i]) { e=i; break; }
        break;
      case 1:
        b=last; e=s[0]-'a'; break;
      case 2: default:
        b=s[0]-'a', e=lastc(s)-'a'; break;
    }
    arc[b][e]--;
    
    dump(last=e);

    vector<int> route; trial = 0LL;
    int res = sub(last, route);
    if (res) {
      if (sz(route)>0) route.pop_back();
      reverse(all(route));
      tr(route,it) printf(" -> %c", 'a' + *it);
    }
    
    candidates.clear();
    rep(i,26) if (arc[last][i]) candidates.insert(i);
    if (candidates.empty()) {
      printf("GOOGLE WINS!!\n"); break;
    }
    printf("\n[%d] Your choice (input last char): %c..[", wi-1, 'a'+last);
    tr(candidates,it) printf("%c,", 'a'+*it);
    printf("] : "); fflush(NULL);
    cin >> s;
    b = last, e = s[0]-'a'; arc[b][e]--;

    dump(last=e);
  }
}

pac-man

15:03 |  pac-man - naoya_t@topcoder を含むブックマーク はてなブックマーク -  pac-man - naoya_t@topcoder  pac-man - naoya_t@topcoder のブックマークコメント

  • SuperHackerコースの目玉。総当りで行けるのはLevel1までか
  • 探索順をランダムに
    • ステップ毎に、移動可能な方向(不動を含む)をシャッフルしてDFS
    • と思ったけどあまり伸びないので
    • えさを食えるかどうか(目先の利益)で優先度を変えるだけで伸びた。(食欲的な意味で)貪欲法
  • 一定の探索ステップ数に達したら中断
    • 探索打ち切り数はT*1.3〜1.5ぐらいで適当にやってた
  • ラップタイム毎の最高スコア(後に4位まで)を得たルートを記憶しておいて、時々(ランダムに)、過去に保存したあるラップタイム(ランダム)の保存ルートから再開する
    • これはちょっとGAっぽい
  • 移動可能な方向を毎回ステップ毎に調べてるのは馬鹿なので、
  • グラフ構造を把握して、ある点からある点への距離(ステップ数)をdijkstraか何かで全部調べておく
    • Level3だとちょっと時間がかかるので、この距離テーブルはファイルに保存しておく
  • 目先にえさがない場合、残りのえさ全てからの「重力」の合計の大きい方からDFS
    • この程度のことで500は簡単に行くようになった。
  • しかし520前後までしか伸びない…
    • 結果: 41, 248, 523

問題ファイル例 (level2)

300
20 17
####################
###.....L..........#
###.##.##.##L##.##.#
###.##.##.##.##.##.#
#.L................#
#.##.##.##.##.##.###
#.##.##L##.##.##.###
#.................L#
#.#.#.#J####J#.#.#.#
#L.................#
###.##.##.##.##.##.#
###.##.##R##.##.##.#
#................R.#
#.##.##.##.##R##.###
#.##.##.##.##.##.###
#@....R..........###
####################

最後の頃のコード

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
//#include "cout.h"
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

const int infty = 987654321;

template <typename T> T infsum(T a, T b){
  return (a == infty || b == infty)? infty : (a + b);
}

#include <stdlib.h>
#include <libgen.h>

#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

#define DEFAULT_STEP_LIMIT 5000
#define DEFAULT_RAND_FREQ 20
#define DEFAULT_VH_WEIGHT 0 //.003

int rand_freq = DEFAULT_RAND_FREQ, step_limit = DEFAULT_STEP_LIMIT, hiscore = 0;
double vh_weight = DEFAULT_VH_WEIGHT;

vector<string> rawmap;
int T, H, W;
int meIdx, t=0, score=0, timebonus=0, esamax=0;

int dirx[5] = { 0, -1, 0, 1, 0 }, diry[5] = { 1, 0, -1, 0, 0 }; // CW: 下 左 上 右  .
char dirt[5] = { 'j', 'h', 'k', 'l', '.' };

vector<int> aIdx, aType, aToggle, ldir; int aN;
vector<int> hist;

char map_name[128];

int N; // number of nodes
vector<int> esa;
vector<char> trans;
vector<vector<int> > route;
vector<int> route_cnt;
vector<int> ord_to_idx, idx_to_ord;
vector<vector<int> > arc, distances;

class Frame {
 public:
  int _meIdx, _t, _score, _aN;
  vector<int> _aIdx, _aType, _aToggle, _ldir, _hist;
  vector<int> _esa;
 public:
  Frame(){
    _meIdx = meIdx; _t = t; _score = score;
    _aN = aN;
    _aIdx.assign(all(aIdx)); _aType.assign(all(aType)); _aToggle.assign(all(aToggle));
    _ldir.assign(all(ldir)); _hist.assign(all(hist));
    _esa.assign(all(esa));
  }
  void call() {
    meIdx = _meIdx; t = _t; score = _score;
    aN = _aN;
    aIdx.assign(all(_aIdx)); aType.assign(all(_aType)); aToggle.assign(all(_aToggle));
    ldir.assign(all(_ldir)); hist.assign(all(_hist));
    esa.assign(all(_esa));
  }
  ~Frame() {
    _aIdx.clear(); _aType.clear(); _aToggle.clear();
    _ldir.clear(); _score = score;
    _esa.clear();
  }
  string dump() {
    stringstream ss;
    ss << "t=" << _t << ", score=" << _score;
    return ss.str();
  }
};

int steps;
vector<int> hihi, memo_i;

Frame *memo[701][4], *frame_for_reset;
bool random_mode = false;


inline bool coince(int m0, int m1, int a0, int a1) {
  return (a1==m1 || (a0==m1 && a1==m0));
}
inline double drand(){
  return 1.0 / 65536 * (rand() % 65536);
}

vector<int> dijkstra(int start_v)
{
  vector<int> distance(N, infty);
  //vector<int> predecessor(N, -1);
  set<int> S;

  S.insert(start_v);
  distance[start_v] = 0;

  rep(v,N){
    if (v == start_v) continue;
    if (arc[start_v][v] == infty) continue;
    
    distance[v] = arc[start_v][v];
    //predecessor[v] = start_v;
  }
  
  while (S.size() < N) { // 各点へ
    // find v* from V\S with distance(v*) = min{distance(v):v from V\S}
    int v_ = -1;
    int d_ = infty;
    rep(v,N){
      if (found(S,v)) continue;
      // V\S
      if (distance[v] < d_) { d_ = distance[v]; v_ = v; }
    }
    if (v_ == -1) break;
    S.insert(v_);

    rep(v,N){ // FOR ALL v from V\S DO
      if (found(S,v)) continue;
      // V\S
      int d_ = infsum(distance[v_], arc[v_][v]);
      if (d_ < distance[v]) {
        distance[v] = d_;
        //predecessor[v] = v_;
      }
    }
  }
  return distance;
}

// MONITOR
void mon_(FILE *oport)
{
  fprintf(oport, "\n%d score=%d timebonus=%d\n", T-t, score, timebonus);
  vector<vector<char> > screen(H,vector<char>(W,'+'));
  rep(idx,N){
    int ord=idx_to_ord[idx], c=ord%W, r=ord/W;
    screen[r][c] = esa[idx] ? '.' : ' ';
    rep(i,aN){
      if (idx==aIdx[i]) screen[r][c] = aType[i];
    }
    if (idx==meIdx) screen[r][c] = '@';
  }
  rep(r,H){
    rep(c,W) fputc(screen[r][c], oport);
    fputc('\n', oport);
  }
  fprintf(oport, "> ");
  rep(i,t) fputc(hist[i], oport);
  fputc('\n', oport);
}

void mon()
{
  mon_(stdout);
}

void save()
{
  if (!map_name[0]) return;
  
  char path[256];
  // ここではmkdirしないので先に自分で作ってね
  sprintf(path, "ans/%s/%03d.scr", map_name, score+timebonus);
  printf("path: %s\n", path);
  FILE *fp = fopen(path, "wx"); // exclusive!!
  if (fp != NULL) {
    mon_(fp);
    fclose(fp);
  }
}

//
// 地図をファイルから読み取り
//
bool load_rawmap(char *path)
{
  FILE *fp = fopen(path, "r");
  if (fp == NULL){
    cerr << "Read Error" << endl;
    return false;
  }
  int dm0 = fscanf(fp, "%d%d%d", &T,&W,&H);

  char rowbuf[256], *dm1;
  dm1 = fgets(rowbuf,256,fp); // eat a crlf
  rep(r,H){
    dm1 = fgets(rowbuf,256,fp);
    rawmap.pb(string(rowbuf));
  }
  fclose(fp);

  //
  esa.clear(); esamax = 0;
  trans.clear();
  route.clear(); route_cnt.clear();
  ord_to_idx.assign(H*W,-1); idx_to_ord.clear();

  aIdx.clear(); aType.clear(); // aToggle.clear();
  aN = 0;
  
  int idx = 0;
  rep(r,H) rep(c,W) {
    char ch = rawmap[r][c];
    if (ch == '#') continue;

    trans.pb(ch);

    int ord = r*W + c;
    idx_to_ord.pb(ord); ord_to_idx[ord] = idx;

    bool esa_p = false;
    switch (ch) {
      case '.': esa_p = true; esamax++; break;
      case ' ': break;
      case '@': meIdx = idx; break;
      default:
        aIdx.pb(idx); aType.pb(ch); aN++; break;
    }
    esa.pb(esa_p ? 1 : 0);

    route.pb(vector<int>(4,-1)); int cnt=0;
    // CW: 下 左 上 右  .
    if (rawmap[r+1][c] != '#') { route[idx][0] = ord+W; cnt++; }
    if (rawmap[r][c-1] != '#') { route[idx][1] = ord-1; cnt++; }
    if (rawmap[r-1][c] != '#') { route[idx][2] = ord-W; cnt++; }
    if (rawmap[r][c+1] != '#') { route[idx][3] = ord+1; cnt++; }
    route_cnt.pb(cnt);
    
    idx++;
  }
  N = idx;

  aToggle.assign(aN,0);
  ldir.resize(aN);
  
  // ord(y*W+x)-> idx
  rep(i,N) {
    rep(d,4) if (route[i][d] >= 0) route[i][d] = ord_to_idx[route[i][d]];
  }
  // arc
  arc.assign(N, vector<int>(N,infty)); distances.clear();
  rep(i,N) arc[i][i]=0;
  rep(i,N){
    rep(d,4){
      int j = route[i][d];
      if (j>=0) arc[i][j] = arc[j][i] = 1;
    }
  }

  mon(); // 初期状態マップを表示。dijkstraを待ってる間の退屈しのぎ

  string path_d(path); path_d += ".d";
  int fd_d = open(path_d.c_str(), O_RDONLY);
  if (fd_d != -1) {
    short N_;
    int e = read(fd_d, &N_, sizeof(short));
    short *buf = (short *)malloc(sizeof(N_)*N*N);
    if (buf != NULL) {
      e = read(fd_d, buf, sizeof(short)*N*N);
      distances.assign(N,vector<int>(N,infty));
      rep(i,N) distances[i][i] = 0;
      for(int i=0;i<N-1;++i)
        for(int j=i+1;j<N;++j) {
          short v = buf[i*N+j];
          if (v >= 0) distances[i][j] = distances[j][i] = v;
        }
      free(buf);
    }
    close(fd_d);
  } else {
    // 各ノード間の距離(総当り)を求める。dijkstraですが。
    rep(i,N) {
      distances.pb(dijkstra(i));
      printf("\rdijkstra #%3d/%d...", 1+i,N);
      fflush(stdout);
    }
    printf("\r                    \r");

    fd_d = creat(path_d.c_str(),0644);// open(path_d.c_str(), O_CREAT|O_WRONLY|O_TRUNC, 0644);
    if (fd_d != -1) {
      short N_ = N, *buf = (short *)malloc(sizeof(N)*N*N);
      int e = write(fd_d, &N_, sizeof(short));
      if (buf != NULL) {
        rep(i,N) rep(j,N) {
          int v = distances[i][j];
          buf[i*N+j] = (v == infty)? -1 : (short)v;
        }
        e = write(fd_d, buf, sizeof(short)*N*N);
        free(buf);
      }
    }
    close(fd_d);
  }
  return true;
}

void reset(){
  frame_for_reset->call();
}

//
// 敵機(全部)の動きを計算; ax[], ay[], ldir[]
//
int teki()
{
  int me_ord=idx_to_ord[meIdx], me_x=me_ord%W, me_y=me_ord/W;
  rep(i,aN){
    int idx=aIdx[i], ord=idx_to_ord[idx], x=ord%W, y=ord/W;
    if (t==0) {
      /// t==0; 下、左、上、右
      rep(d,4){
        if (route[idx][d]<0) continue;
        aIdx[i] = route[idx][d]; ldir[i] = d;
        break;
      }
    } else {
      /// t>=1
      int rcnt = route_cnt[idx];
      if (rcnt == 1) {
        // 行き止まりマス
        rep(d,4){
          if (route[idx][d]<0) continue;
          aIdx[i] = route[idx][d]; ldir[i] = d;
          break;
        }
      } else if (rcnt == 2) {
        // 通路マス
        int ng_dir = (ldir[i]+2)%4;
        rep(d,4){
          if (route[idx][d]<0) continue;
          if (d == ng_dir) continue;
          aIdx[i] = route[idx][d]; ldir[i] = d;
          break;
        }
      } else {
        //交差点マス
        int dx=me_x - x, dy=me_y - y;
        int ux=dx?(dx>0?1:-1):0, uy=dy?(dy>0?1:-1):0;
        int dir_x = ux>0?3:1, dir_y = uy>0?0:2;
        int at=aType[i];
        aToggle[i]++;
        switch (at){
          case 'V':
            if (dy != 0 && route[idx][dir_y]>=0) {
              aIdx[i] = route[idx][dir_y];
              ldir[i] = dir_y;
            } else if (dx != 0 && route[idx][dir_x]>=0) {
              aIdx[i] = route[idx][dir_x];
              ldir[i] = dir_x;
            } else {
              rep(d,4){
                if (route[idx][d]<0) continue;
                aIdx[i] = route[idx][d];
                ldir[i] = d;
                break;
              }
            }
            break;
          case 'H':
            if (dx != 0 && route[idx][dir_x]>=0) {
              aIdx[i] = route[idx][dir_x];
              ldir[i] = dir_x;
            } else if (dy != 0 && route[idx][dir_y]>=0) {
              aIdx[i] = route[idx][dir_y];
              ldir[i] = dir_y;
            } else {
              rep(d,4){
                if (route[idx][d]<0) continue;
                aIdx[i] = route[idx][d];
                ldir[i] = d;
                break;
              }
            }
            break;
          case 'L': goto mode_l;
          case 'R': goto mode_r;
          case 'J': if (aToggle[i] & 1) goto mode_l; else goto mode_r;
            //default: break;
          mode_l:
            {
              int dz[3] = { (ldir[i]+3)%4, ldir[i], (ldir[i]+1)%4 };
              rep(j,3){ int d=dz[j];
                if (route[idx][d]<0) continue;
                aIdx[i] = route[idx][d];
                ldir[i] = d;
                break;
              }
            }
            break;
          mode_r:
            {
              int dz[3] = { (ldir[i]+1)%4, ldir[i], (ldir[i]+3)%4 };
              rep(j,3){ int d=dz[j];
                if (route[idx][d]<0) continue;
                aIdx[i] = route[idx][d];
                ldir[i] = d;
                break;
              }
            }
            break;
        }
      }
    }
  }
}


ptrdiff_t myrandom(ptrdiff_t i){ return rand()%i; }
ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;

int sub()
{
  if (++steps >= step_limit) return -2; // ABORT
  if (steps % 10000 == 0) { printf("\r[%d] t=%d score=%d  ",steps,t,score); fflush(stdout); }

  if (score==esamax) {
    timebonus = T - t;
    if (score+timebonus > hiscore) {
      mon(); save();
      hiscore = score+timebonus;
      steps = -step_limit*3;
      printf("t=%d (CLEARED), score=%d+%d/%d (NEW RECORD)\n", t, score,timebonus,hiscore);
    }
    return -3;
  } else if (t==T) {
    //printf("!!TIME UP!!\n");
    if (score > hiscore) {
      timebonus = 0;
      mon(); save();
      hiscore = score;
      steps = -step_limit*3;
      printf("t=%d (TIME UP), score=%d/%d (NEW RECORD)\n", t, score,hiscore);
    }
    return 1;
  }
  if (hihi[t] <= score) {
    hihi[t] = score;
    if (t < 0 || 700 < t) {
      printf("OUT OF BOUNDS... t=%d\n", t);
      return -3;
    }
    // int j = rand() % 4;
    int j = memo_i[t]++ % 4;
    if (memo[t][j]) delete memo[t][j];
    memo[t][j] = new Frame();
  }

  // 敵の動きをrollbackする為のもの。当たり判定にも利用
  vector<int> aIdx_keep(all(aIdx)), aToggle_keep(all(aToggle)), ldir_keep(all(ldir));
  // 先に敵の動きを決めれる
  teki();

  int safecount=0;

  vector<int> tmp1, tmp0;
  rep(d,4){
    int nextIdx = route[meIdx][d]; if (nextIdx<0) continue; // SAFETY
    if (esa[nextIdx]) tmp1.pb(d); else tmp0.pb(d);
  }

  vector<int> choices;
  if (sz(tmp1) > 0) {
    random_shuffle(all(tmp1), p_myrandom);
    tr(tmp1,it) choices.pb(*it);

    if (sz(tmp0)) {
      random_shuffle(all(tmp0), p_myrandom);
      tr(tmp0,it) choices.pb(*it);
    }
    choices.pb(4);
  } else {
    vector<pair<double,int> > cx;

    int denom = esamax - score; if (denom == 0) denom = 1;

    double dist_here = 0.0;
    rep(idx,N) {
      if (idx == meIdx) continue;
      int d_ = distances[meIdx][idx];
      if (esa[idx]) dist_here += 1.0 / d_ / d_; //denom;
    }

    rep(i,aN){
      if (aType[i]!='V' && aType[i]!='H') continue;
      int d_ = distances[meIdx][aIdx[i]];
      dist_here -= vh_weight / d_ / d_;
    }


    rep(d,4){
      int nextIdx = route[meIdx][d]; if (nextIdx<0) continue; // SAFETY

      double dist = 0.0;
      rep(idx,N) {
        if (idx == nextIdx) continue;
        int d_ = distances[nextIdx][idx];
        if (esa[idx]) dist += 1.0 / d_ / d_; //denom;
      }

      rep(i,aN){
        if (aType[i]!='V' && aType[i]!='H') continue;
        int d_ = distances[nextIdx][aIdx[i]];
        dist -= vh_weight / d_ / d_;
      }


      double dist_score = (dist - dist_here);
      if (dist_score > .5) dist_score = .5;
      if (esa[nextIdx]) dist_score += 0.75;
      dist_score += 0.01 * drand();
      
      cx.pb(make_pair(-dist_score,d));
    }
    cx.pb(make_pair(1.0, 4));
    if (random_mode || (rand() % rand_freq == 0)) {
      // cx.pb(make_pair(0.005-.00001*(rand() % 1000), 4));
      tr(cx,it) it->first += 0.1 * drand();
    }

    sort(all(cx));
    tr(cx,it) choices.pb(it->second);
  }

  tr(choices,ct){
    int d=*ct;
    int lmeIdx = meIdx; // 現時点(lme_x,lme_y)で生きている
    if (d<4) meIdx = route[meIdx][d]; // MODIFIED (me_x,me_y)

    bool safe=true;
    rep(i,aN){
      if (coince(lmeIdx, meIdx, aIdx_keep[i], aIdx[i])) { safe=false; break; }
    }

    if (safe) {
      safecount++;

      int eaten=0;
      if (esa[meIdx]) { score++; eaten=1; esa[meIdx]=0; }
      
      hist[t++] = dirt[d];
      int res = sub();
      t--;
      if (res <= -2) {
        return res; // abort
      }

      if (eaten) { esa[meIdx]=1; score--; }
    } else {
      ;
    }
    meIdx = lmeIdx; // ROLLBACK (me_x,me_y)
  }

  if (safecount==0) {
    if (score > hiscore) {
      mon(); save();
      hiscore = score;
      printf("t=%d (GAMEOVER), score=%d/%d (higher)\n", t, score,hiscore);
    } else {
      ;
    }
  }
  
  // 敵の動きをrollback
  aIdx.assign(all(aIdx_keep));
  aToggle.assign(all(aToggle_keep));
  ldir.assign(all(ldir_keep));

  return safecount ? safecount : -1;
}


main(int argc, char **argv)
{
  if (argc < 4){
    printf("usage: %s <map_file> <hi_score> <step_limit> [<rand_freq> <vh_weight%%>]\n", basename(argv[0]));
    // map_file には地図ファイルのpathを。(eg. problem/pacman_1)
    // hi_score を設定しておくとそれ未満のものを表示しない。最初は0でok
    // step_limit は試行打ち切り回数。大体T以上の値を設定。800〜1000とか
    // 結果は画面表示だけでなく ans/pacman_1/41.scr のようなファイルにも保存される
    return 0;
  }
  
  srand( (unsigned)time(NULL) );

  if (!load_rawmap(argv[1])) return 0;

  frame_for_reset = new Frame();
  
  strcpy(map_name, basename(argv[1]));

  hihi.assign(T+1,0); memo_i.assign(T+1,0);
  rep(z,701) rep(j,4) memo[z][j] = NULL;

  hiscore = atoi(argv[2]); if (hiscore < 0) hiscore = 0;
  step_limit = atoi(argv[3]); if (step_limit < 0) step_limit = DEFAULT_STEP_LIMIT;
  if (argc >= 5) {
    rand_freq = atoi(argv[4]); if (rand_freq < 0) rand_freq = DEFAULT_RAND_FREQ;
  }
  if (argc >= 6) {
    int vh_weight_percent = atoi(argv[5]); vh_weight = 0.01 * vh_weight_percent;
  }
  

  for (int trial=0; ;++trial){
    steps = 0; // step_limit = 500000;

    bool inited=false;
    if (trial % 2 == 0) {
      int z = rand() % T;
      if (2<z && hihi[z]) {
        int j = rand() % 4;
        if (z < 0 || 700 < z) {
          printf("OUT OF BOUNDS... t=%d\n", z);
          return -3;
        }
        if (memo[z][j]) {
          memo[z][j]->call(); // resume
          inited = true;
        }
      }
    }
    if (!inited) {
      reset();
      hist.resize(T); t=0, score=0, timebonus=0;
    }

    random_mode = (rand() % rand_freq == 0);

    int res = sub();
    printf("\r// steps=%d, t=%d, score=%d+%d/%d ", steps,t,score,timebonus,hiscore ); fflush(stdout);
  }

  // dealloc
  rep(z,701) rep(j,4) if (memo[z][j]) delete memo[z][j];
  delete frame_for_reset;
}
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100823