Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-10-27

SRM486

02:08 | SRM486 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM486 - naoya_t@topcoder SRM486 - naoya_t@topcoder のブックマークコメント

とりあえずregisterしたものの疲れたしあーもういいや寝ちゃおう寝ちゃおうと思って不参加を決め込んだつもりが0:02過ぎて部屋覗いたらcafelierさんとかsemiexpさんが跋扈していらっしゃったので参戦することにしたRoom11

総括

300: 90.0/passed system test

450: 321.07/passed system test

1000: Opened

411.07p + 0p

  • 1000点問題をちょっと考えてあと10分強では書ききれないと悟り300+450を確実に取りに行こうと考えた。
  • 300で(1,4)で"/+*"を返すような間抜けな落とし穴があったので終了15秒前ぐらいにresubmitして塞ぐなどした。

http://gyazo.com/122d34490e7a276b105ea99983a7737a.png

Room: #9/20

DivI: #192/774

Rating: 1582→1649 自己ベスト更新キター

脳内解説

珍しく3問開いたので3問分書かねば…

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20101027

2010-10-21

SRM485

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

久しぶり(9/9以来)の参加。Room1, with Petr

http://gyazo.com/38cd4e5ae334c1c8e2173b3b12178d89.png

総括

250: 145.80/passed system test

500: Opened

1000: Unopened

145.80p + 0p

Room: #11/19

DivI: #304/659

Rating: 1577→1582 上げ止まり感

脳内解説

ネタバレになるほど書いてない残念回

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20101021

2010-09-09

SRM481

23:54 | SRM481 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM481 - naoya_t@topcoder SRM481 - naoya_t@topcoder のブックマークコメント

総括

250: 161.83/passed system test

500: 217.42/passed system test

900: Unopened

--------------

379.25p + 0p

Room: #2/19

DivI: #90/704

Rating: 1436→1577 前々回より上がってるからよしとしよう

脳内解説

ネタバレになる程度には書いた

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100909

2010-08-27

SRM480

12:36 | SRM480 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM480 - naoya_t@topcoder SRM480 - naoya_t@topcoder のブックマークコメント

x x - 0pt

ケアレスすぎて死にたい(特にMedium!)ので、通すためのdiffをまず晒す。黄色にとどまるための課題はハッキリ見えている。

経験則:再提出がちらほら見られる問題は自分も再提出しないと多分死ぬ。

  • 問題よく読め
  • あちこちでassertしたほうがよさげ
  • if文には必ずブロックを使うオレオレコーディング規約とか

Easy(250): InternetSecurity

  • 問題がなかなか頭に入ってこないけど
  • 多分やるだけぽ
  • 170.05 → challenged.
    • 辞書逆順で書いてたけどそんな問題と違った。これは早とちり
@@ -94,8 +94,8 @@
       if (sz(ss)==sn) break;
     }
     
-    vector<string> ans_(all(ans));
-    sort(all(ans_)); reverse(all(ans_));
+    vector<string> ans_;
+    rep(i,N) if(found(ans,address[i])) ans_.pb(address[i]);
     return ans_;
   }
 };

Medium(450): NetworkSecurity

  • サーバ1台ずつ別々に考えてよさそう
  • クライアントをトポロジカルソートして逆に見ていけばいいよね
  • 211.26 → failed system test...おや?
    • トポロジカルソートした結果の長さがN以上とか何それバグってる、と思ったら…orz
@@ -30,7 +30,7 @@
      set<int> s;
      rep(o,N){
        bool hi=false;
-       rep(i,N){if(clientCable[i][o]=='Y')hi=true;break;}
+       rep(i,N) if(clientCable[i][o]=='Y'){hi=true;break;}
        if(!hi) s.insert(o);
      }
      while(!s.empty()){

提出全コード

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100827

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 のブックマークコメント

  • pythonで書いてみた。慣れないので汚いですが
  • エラーメッセージ読んでなかったので無駄に試行錯誤した
  • realm入れるの忘れてた。(エラーメッセージに書いてあった!)→入れたらあっさり200
  • 続きを読む

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で書いた肝の部分のみアップ
  • 続きを読む

しりとり

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前後までしか伸びない…
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100823