naoya_t@hatenablog

いわゆるチラシノウラであります

ICFPC2013参戦メモ

ぼっち参戦しました。
ICFP Programming Contest 2013
今年のホストはMicrosoft Researchさん。

チーム名「Я⦿Ж⦿R」でエントリしています。ケロン軍です。

総括


問題自体は楽しめる要素が多かったと思うのだけれど

  • MSなんとか
  • leaderboardの不在
  • (英文読解力の欠如なのだろうけれど)主催者の意図を掴みきれずにサーバ仕様をあちこち読み違えていて問題を難しくしていた

という3つの(主に心理的な)障壁を乗り越えるところまで行けませんでした。

(72時間のうち、合計参戦時間より合計睡眠時間の方がはるかに長かったです・・・)

kinabaさん他みなさんによるtogetterまとめ:ICFPC 2013 おつかれさまでしたー

続きを読む

PRML wednesday順調

週1回水曜開催で、順調に第3回まで来た。

狭い会議室で、2時間とちょっとで、ちびちび進んでいる。
第2回から2章に入り、1人2ページずつの担当制になったけれどまだ1周回ってない。
ディリクレ分布の紹介を済ませ、ガウス分布の話題に入ったところ。

みんなと少しずつ数式展開を噛み締めながら、個人的には演習問題コンプリートを目指しながら(時には解答を写経しながら)読み進めている。

PRML wednesdayキックオフ

今日から毎週水曜の夜に原宿で #prmlwednesday と称してPRMLを読むことになりました。

別名「PRML平日レーン」「わるぷるむるの夜」
雨上がりの蒸し暑い夜でしたが、定員12人の会議室に13人入ってPRMLをまた1章から読み始めました。

今日は自己紹介と、今後の進め方の相談と、1章でここだけは読むべきという §1.2〜1.2.3 を読んだ(というか本レーン、社内勉強会、と時間遡行を繰り返し今ではPRML同人作家でもあるshuyoさんの有難いトークを1時間延長で聞いて帰りました)。
ポイントを押さえた非常に分かりやすい解説をどうもありがとうございました。

今日覚えて帰るべき(というか覚えてはいけない)大事なこと:「ベイズ公式は覚えちゃダメ」


参加者の顔ぶれは
https://twitter.com/search/realtime?q=%23prmlwednesday
または
https://twitter.com/naoya_t/prmlwednesday
で見られます。

※定員いっぱい(というか超過)なので参加者公募はありません。超高校級PRMLer*1揃いなので、どなたかが卒業されて空席が発生した折には公募あるかもです。

あと、主催者権限で(半ば講師ツッコミ役的な立ち位置の)スカウトはあるかもです。

平日PRML開催が決まってから、今度こそ演習問題をコンプリートするぞーとか思って1章から見なおしてみた(1章残りあと数問)のですが、分かった気になって先に進んでいた所を蒸し返して改めて苦悶しています…

・・・

というわけで、来週は2章でお会いしましょう!(発表全員回るかな?)

ホワイトボードが無いと(それも語り部がshuyoさんの時に!)致命的に困るので、来週からはホワイトボード(60x90)が来る予定です。

*1:高校で習った範囲の数学は分かっているものという前提です!

PRML復々習レーン#12

に参加しました&発表しました

@who_you_me さん会場係&遅刻者サルベージ等ありがとうございます
@Prunus1350 さん運営ありがとうございます
@sleepy_yoshi さん前回のあらすじ毎度ありがとうございます
発表者の皆さん・その他参加者の皆さんもありがとうございます

今回は @shuyo さん @takmin さんが来られて

§8.3.3発表しました
http://naoyat.github.io/slides/prml/8.3.3/slide.html

内容的には
http://naoyat.hatenablog.jp/entry/2013/06/23/190000
を整理・加筆したものですが


(あとでもうちょっと書く)

2-SATと強連結成分分解

ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。(ちなみにSRM464には出場している

SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみのあれです

(x_0 ∨ ¬x_1) ∧ (¬x_0 ∨ ¬x_3) ∧ ...
みたいな論理式(乗法標準形)を満たす真偽値 x_0, x_1, ... の組み合わせが存在するか否か。(存在する場合、その組み合わせを知りたかったりする)

上の例ではすべての節が(高々)2変数なので2-SATと呼ばれる。
2-SATは線形時間で解けるらしい)。

  • 論理和 x ∨ y が論理包含 ¬x⇒y (または ¬y⇒x)に書き換え可能なことを利用して、論理式を有向グラフに変換してみたり
  • 出来上がったdagを強連結成分分解してみる
  • 同じ強連結成分に含まれるノード(が表すリテラル、すなわちxなり¬yなり)は同じ真偽値をもつ。ということは、xと¬xが同じ強連結成分に含まれたらアウト。

2-SATも強連結成分分解も、蟻本§4-3「グラフマスターへの道」(p.285〜) で解説されている(のを以前読んだがすっかり忘れている。p.286のグラフをノートに書いてscc()を手動トレースして一度は納得したはずなのだが)。

Medium ("ColorfulDecoration", 550)

この問題で何が x ∨ y にあたるのか思いつかない…orz

http://d.hatena.ne.jp/komiyam/20110925/1316920692 を見たら、
「x と y が共存できない」¬(x ∧ y) が ¬x ∨ ¬y に等しいことを利用すればいいらしい。

するとこれは 「x⇒¬y かつ y⇒¬x」に書き直すことができる。

書いてみたコード

  • 強連結成分分解ではなく、x から ¬x に行く経路(とその逆)が存在するかをWFで求めている。O(n^3)ですけど。
  • passed system test
#include <vector>
using namespace std;

#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define mid(x,y) ((x)+((y)-(x))/2)
#define ev(v1,v2,n) for(int v1=0;v1<(n)-1;++v1)for(int v2=v1+1;v2<(n);++v2)

vector<int> xa_, ya_, xb_, yb_;
vector<vector<int> > arc;
int n;

inline bool intersects(int xi, int yi, int xj, int yj, int d){
  int dx = abs(xi - xj), dy = abs(yi - yj);
  return (dx < d && dy < d);
}

inline void add_edge(int i, int j) {
  // ¬(i ∧ j)
  // ¬i ∨ ¬j
  // (i ⇒ ¬j) かつ (j ⇒ ¬i)
  arc[i][j<n ? j+n : j-n] = 1;
  arc[j][i<n ? i+n : i-n] = 1;
}

bool po(int d){
  if (d == 0) return true;

  arc.assign(n*2, vector<int>(n*2, 10000));
  rep(i,n*2) arc[i][i] = 0;

  ev(i,j,n) {
    if (intersects(xa_[i],ya_[i], xa_[j],ya_[j], d)) { // i && j が駄目
      add_edge(i, j);
    }
    if (intersects(xa_[i],ya_[i], xb_[j],yb_[j], d)) { // i && ¬j が駄目
      add_edge(i, n+j);
    }
    if (intersects(xb_[i],yb_[i], xa_[j],ya_[j], d)) { // ¬i && j が駄目
      add_edge(n+i, j);
    }
    if (intersects(xb_[i],yb_[i], xb_[j],yb_[j], d)) { // ¬i && ¬j が駄目
      add_edge(n+i, n+j);
    }
  }

  rep(k,n*2) rep(i,n*2) rep(j,n*2){
    arc[i][j] = min(arc[i][j], arc[i][k] + arc[k][j]);
  }

  rep(i, n) {
    if (arc[i][n+i] < 10000 && arc[n+i][i] < 10000) return false;
  }

  return true;
}

class ColorfulDecoration {
 public:
  int getMaximum(vector<int> xa, vector<int> ya, vector<int> xb, vector<int> yb) {
    n = xa.size();
    xa_ = xa; ya_ = ya; xb_ = xb; yb_ = yb;

    int lo = 0, hi = INT_MAX;
    while (true) {
      int mi = mid(lo, hi);
      if (mi == lo) break;
      if (po(mi))
        lo = mi;
      else
        hi = mi;
    }
    return lo;
  }
};

さて。
強連結成分分解をちゃんとやってみよう。

dagの強連結な部分集合:「有向グラフの部分集合のうち、それに含まれる任意の2頂点u, vを取った時 uからvへ辿り着く有向路が存在する」
強連結成分:強連結な部分集合のうち、これ以上頂点を付け足したら強連結でなくなってしまうもの

最大クリーク(無向グラフで、あらゆる2つの頂点を繋ぐ辺が存在する集合(=クリーク)のうち、これ以上頂点を付け足したらクリークでなくなってしまうもの)に似ている。

vector<vector<int> > arc;
vector<vector<int> > arc_r;
vector<int> cmp; // 属する強連結成分の、グラフ全体におけるトポロジカル順序

vector<bool> visited;
vector<int> vs; // post-order

void dfs(int v) {
  visited[v] = true;
  tr(it, arc[v]) {
    if (!visited[*it]) dfs(*it);
  }
  vs.push_back(v); // 帰りがけにvを記録。グラフの末端に近いものから並ぶ
}
void rdfs(int v, int k) {
  visited[v] = true;
  cmp[v] = k;
  tr(it, arc_r[v]) {
    if (!visited[*it]) rdfs(*it, k);
  }
}

int scc() { // 強連結成分分解
  vs.clear();

  visited.assign(n*2, false);
  rep(i,n*2) {
    if (!visited[i]) dfs(i);
  }

  visited.assign(n*2, false);
  int k=0;
  reverse(all(vs)); // グラフの末端から遠いものから始めたい
  tr(it, vs) {
    if (!visited[*it]) rdfs(*it, k++);
  }
  return k;
}

bool po(int d){
  if (d == 0) return true;

  arc.assign(n*2, vector<int>());
  arc_r.assign(n*2, vector<int>()); // 追加
  cmp.assign(n*2, -1); // 追加

  ev(i,j,n) {
    if (intersects(xa_[i],ya_[i], xa_[j],ya_[j], d)) {
    ...
  }

  scc(); // 強連結成分分解

  rep(i, n) {
    // x と¬x が同じ強連結成分に属してしまったらアウト
    if (cmp[i] == cmp[n+i]) return false;
  }

  /* 
  // 式を満たす具体的な真偽値を求める方法。
  //「 x を含む強連結成分のトポロジカル順序 cmp[x] が、¬x を含む強連結成分のトポロジカル順序 cmp[¬x] よりも後ろ」⇔「xは真」
  vector<bool> ans(n);
  rep(i, n) {
    ans[i] = (cmp[i] > cmp[n+i]);
  }
  cout << ans << endl;
  */

  return true;
}

ショートコーディング「世界を革命する力を」

ふとしたツイートからコードゴルフ大会が勃発

続きを読む

MacBook Airの電源アダプタが断線すると読書が捗る

でMacが使えなかったので、週末は「きつねさんでもわかるLLVM」とか「Real World OCaml」とか読んでました。

Real World OCaml
Real World OCaml
posted with amazlet at 13.07.01
Jason Hickey Anil Madhavapeddy Yaron Minsky
Oreilly & Associates Inc
売り上げランキング: 31,941

Real World OCamlはβ版(HTML、無料)のやつですけど。


電源アダプタは互換品をポチりました。