Firefox->Chrome

ChromeのEvernoteのWebクリッパーがよいので，クリップするときだけChromeを使ってたのだけど，切り替えするのがめんどくさくなってきたのでFirefoxから乗り換えることにした．
Firefoxはvimperatorのために使っているところがあって，その代替アドオンがあるのかが不安だったのだけど，Vichromeというのが割と良い感じだった．
ほかには，AutoPatchWorkやはてなブックマークやPocketなんかを入れてる．あんまり入れても重くなるだけだしこれぐらいで十分だろう.

■

日記

土曜日曜と遊びまわったせいで，体がだるい．こういう日は，一日家にこもって休んでいたい気分になるのだけど，そうもいかず，必修のレポートを出すためだけに学校に行った．レポートのためだけに外に出るのはもったいないので，マクドナルドで新発売のチキンクリスプとホットコーヒーをいただいた．Twitterで「チキンクリスプが辛い」とつぶやいたら，味覚がおかしいとの評価を受けたけど，そんなことはない．その後，ローソンで20%引きのシュークリームを買って帰った．

1140 : Cleaning Robot

AOJ

幅優先探索 + ビットDP
汚れたマスを都市とした巡回セールスマン問題と見なせる。（ただしスタート地点に戻る必要はない)
事前に汚れたマス同士の距離を幅優先探索で計算し、あとはビットDPで計算。

int w,h;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
//p1->p2 の最短距離
int calc(vector<string> grid, P p1, P p2){
  int used[20][20];
  memset(used, -1, sizeof(used));
  queue<P> que;
  que.push(p1);
  used[p1.first][p1.second] = 0;
  while(!que.empty()){
    P st = que.front(); que.pop();
    if(st == p2) return used[st.first][st.second];
    REP(r,4){
      int cost = used[st.first][st.second];
      int ny = st.first + dy[r];
      int nx = st.second + dx[r];;
      if(0<=ny && ny<h && 0<=nx && nx<w){
        if(used[ny][nx] == -1 && grid[ny][nx] != 'x'){
          used[ny][nx] = cost + 1;
          que.push(P(ny,nx));
        }
      }
    }
  }
  return INF;
}

int main(){
  while(cin>>w>>h,w){
    vector<string> grid(h);
    REP(i,h)cin>>grid[i];
    P start; //初期位置
    vector<P> target; //汚れたマス
    REP(y,h)REP(x,w){
      if(grid[y][x]=='o'){
        start = P(y,x);
      }else if(grid[y][x] == '*'){
        target.push_back(P(y,x));
      }
    }

    int n = target.size();
    int d[10][10] = {}; //d[i][j]: target[i]とtarget[j]の距離
    REP(i,n)REP(j,n){
      d[i][j] = (i!=j)?(calc(grid,target[i],target[j])):0;
    }

    //dp[S][i] 最短距離: iは最後に到達したマス。Sは到達済みマスをbitであらわす。
    int dp[1<<10][10];
    REP(i,1<<n)REP(j,n)dp[i][j] = INF;
    //startからtarget[i]までの移動を最初に行う
    REP(i,n)dp[1<<i][i] = calc(grid, start, target[i]);
    REP(s,1<<n)REP(from,n){
      REP(to,n){
        dp[s|1<<to][to] = min(dp[s|1<<to][to], dp[s][from] + d[from][to]);
      }
    }

    int ans = INF;
    REP(i,n)ans = min(ans, dp[(1<<n)-1][i]);
    if(ans == INF) ans = -1;
    cout<<ans<<endl;
  }
  return 0;
}

python+NetworkX+matplotlibでグラフ描画

プログラミングコンテストではしばしばグラフの問題が出題されます。そういう問題を解くのに、いちいちグラフを紙に書くのはめんどくさいですね。そういう時にNetworkXが便利です。

#networkxとpyplotをimportする
import networkx as nx
import matplotlib.pyplot as plt

#グラフを作成
G = nx.Graph()

#辺を追加する
G.add_edge(1,2)

#リストからも追加できる
edges = [(1,3), (2,4), (2,5), (1,4), (4,6)]
G.add_edges_from(edges)

#グラフを描画
nx.draw(G)
plt.show()

こういうグラフが完成します
f:id:ichyo:20120402104507p:plain

moses

わけあって、最近機械翻訳の勉強をしている。
昔は人力で翻訳ルールを記述する手法が主流だったのだけど、最近は統計的機械翻訳という手法が主流になりつつあるらしい。統計的機械翻訳というのは、翻訳規則を手作業で作るかわりに、大量のデータからパラメータを学習する方法で、google翻訳はこれを採用してる（エキサイト翻訳はどうやってるんだろう)。翻訳のツールはMosesなどがある。Mosesのチュートリアルは、トップページからたどれるStep-by-Step Guideが詳しい。

「新版暗号技術入門-秘密の国のアリス」をよんだ

図などが多く説明も丁寧で読みやすく、さらりと読むことができた。深い内容までは触れられてないが、概要を知るにはいい本だと思う。

新版暗号技術入門　秘密の国のアリス

新版暗号技術入門　秘密の国のアリス