SRM621
SRM621の500で閃いたアルゴリズムがちょい面白い気がしたのでメモっておく。
問題自体の解法に直接は触れないので、解説が見たい方は別のところを参照してください。
以下の問題を考えます。
木をDFS的に探索する。
ある頂点を見ている時に、その頂点から下向きに出ているある枝に対してその枝より下に付いている頂点の集合をSとする。
(上下関係は木の根が上、葉が下とする)
任意の頂点pに対してpがSに含まれるかどうかをO(1)で判定する。
というのを時間的なオーバヘッドほぼ無しで行いたい。
bool isChild(int node){ // nodeが今見ている枝よりも下にいるか return ???; } void task(){ // isChild(???)をめっちゃ呼びたい } void dfs(int pos){ for(int child : childs[pos]){ // pos <-> child の枝を見ている dfs(child); task(); } }
最初はsetで集合を管理していたが遅すぎてTLEだったので別の方法が必要に。
DFSしながら、ノードにIDを振っていくとできる。
int memo[N]; // IDを振っていく。-1で初期化されているとする int current = 0; // 次のID int lowId; // これ以上のIDがふられていれば子供に含まれる bool isChild(int child){ // nodeが今見ている枝よりも下にいるか return memo[child] >= lowId; } void task(){ // isChild(???)をめっちゃ呼びたい } void dfs(int pos){ for(int child : childs[pos]){ // pos <-> child の枝を見ている lowId = current; dfs(child); task(); } memo[pos] = current++; }
DFSしながらやることを前提にしているが、枝に対してlowId(とhighIdみたいなの)を覚えさせておけば一旦DFSしたあとに好きな枝に対してクエリが投げられる(と思う)
いわゆる転職エントリ
本日付けで会社退職しました。
1週間ほどニートした後に次の仕事はじめます。
早くニートになりたい人よりも先にニートになれました。
研修期間を除くと1年と4ヶ月ほどいたことになると思います。
転職の動機はいろいろありますが、開発志望で入ったのに開発をさせてもらえずモチベーションが保てなくなったといったところがメインです。
周りの友人や先輩にはとても恵まれていたと思っていますが、やりたいことを優先して決めました。
おそらく傍からみるともったいない転職なのでしょうが、まあ転職して良かったと思えるように全力で頑張るだけですね。
転職はCodeIQ経由で声かけてもらってそのまま決めた感じです。
とてもおもしろそうな会社だと思っているのでいまのところ満足しています。
Rubyインストール
書籍「RailsによるアジャイルWebアプリケーション開発」のインストール中の話。
Ubuntuで以下のコマンドが失敗する。
$ sudo rvm install 1.9.2
以下で対処。
$ sudo emacs /var/cache/ruby-rvm/src/ruby-1.9.2-p180/ext/openssl/ossl_ssl.c
以下をコメントアウト
/*
OSSL_SSL_METHOD_ENTRY(SSLv2),
OSSL_SSL_METHOD_ENTRY(SSLv2_server),
OSSL_SSL_METHOD_ENTRY(SSLv2_client),
*/とりあえずインストールできるけど、あってるのかは不明。
レッドコーダー
先日TopCoderのAlgorithmでレーティングが2200を超え、赤コーダーになりました。
あと1,2年はかかると思っていたので、自分でもびっくりしています。
http://community.topcoder.com/tc?module=MemberProfile&cr=22881459
2010年の7月から始めたみたいなので3年半くらいかかったようです。
まあ、競技プログラミング自体はもう3年くらい前からやっていたわけですが。
Code Forcesの方もあと少しで赤ですが、こちらはその少しが大分遠そう。
しかし最近は解く問題数がどんどん減っているのに何でこんなに一気にレーティングが上がったのかよくわかりません。
あえて探すとすると最近は
あたり。そこが効いたとしか…
データ構造とか大分弱いので、これから勉強していきたいですね。
PKUとかがいいのかなぁ…
次の目標はyasuhさんのレーティング超え
Boost.Coroutineのローカル変数の寿命
Boost1.53.0リリースされてましたね。
個人的に気になっているのはCoroutine。
pythonのyeildみたいなことが出来るライブラリ。
ローカル変数の寿命が気になったのでちょいと調べた。
#include <boost/coroutine/coroutine.hpp> #include <iostream> typedef boost::coroutines::coroutine<int()> coroutine_type; class Test{ public: Test(){ std::cout << "Test: constructor" << std::endl; } ~Test(){ std::cout << "Test: destructor" << std::endl; } }; void func(coroutine_type::caller_type &yeild){ Test t; std::cout << "Function: start" << std::endl; for (int i = 0; i < 3; i++){ std::cout << "Function: yield " << i << std::endl; yeild(i); } std::cout << "Function: end" << std::endl; } int main(){ std::cout << "Main: start" << std::endl; coroutine_type c(func); while(c){ std::cout << "Main: get " << c.get() << std::endl; c(); } std::cout << "Main: end" << std::endl; return 0; }
出力は以下
Main: start Test: constructor Function: start Function: yield 0 Main: get 0 Function: yield 1 Main: get 1 Function: yield 2 Main: get 2 Function: end Test: destructor Main: end
ふむふむ、コルーチンのオブジェクト(呼び方あってるか知らんが)の寿命じゃなくて、関数が終わった次点でローカル変数は消えるらしい。
コンパイルも少し手間取った。
libboost_contextをリンクしなければいけない。
(-Iやら-Lは各自補うように)
$ g++ coroutine.cpp -lboost_context
SRM417: CubeNets
これまた難しい問題だったけど、綺麗な解法を思い浮かんで気持ちよかった。
(問題概要)
立方体の展開図が文字列で与えられる。
立方体の展開図として正しいかどうか判断せよ。
(解法)
サイコロの展開図として考える。
展開図にそってサイコロを転がして、接地面の数字を割り当てていく。
このとき以下の矛盾がなければよい。
- 同じ数字が2箇所ある
- 同じ場所に2通りの数字の振り方がある
私のサイコロライブラリはゴリ押しなので汚いですがコード。
#include <cstdio> #define IN(x,s,g) ((x) >= (s) && (x) < (g)) #define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h))) #define REP(i,n) for(int i=0; i<(int)(n); i++) #include <queue> #include <set> #include <iostream> #include <sstream> using namespace std; class CubeNets { public: string isCubeNet(vector <string> figure); }; class Dice{ public: enum direction{ UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3, RRIGHT= 4, RLEFT = 5 }; /* * 6 * 2 * 3 1 4 * 5 */ private: static int next_top[7][7][6]; static int next_right[7][7][6]; static int front[7][7]; int _top; int _right; static void initDie(){ front[1][3] = 2; front[1][2] = 4; front[1][4] = 5; front[1][5] = 3; front[2][1] = 3; front[2][3] = 6; front[2][4] = 1; front[2][6] = 4; front[3][1] = 5; front[3][2] = 1; front[3][5] = 6; front[3][6] = 2; for(int i = 4; i < 7; i++){ for(int j = 1; j < 7; j++){ if(i == j || i + j == 7) continue; int t = 7 - i; int l = 7 - j; front[i][j] = front[t][l]; } } for(int t = 1; t < 7; t++){ for(int r = 1; r < 7; r++){ if(t == r || t + r == 7) continue; next_top[t][r][UP] = front[t][r]; next_top[t][r][LEFT] = r; next_top[t][r][RIGHT] = 7 - r; next_top[t][r][DOWN] = 7 - front[t][r]; next_top[t][r][RRIGHT] = t; next_top[t][r][RLEFT] = t; next_right[t][r][UP] = r; next_right[t][r][LEFT] = 7 - t; next_right[t][r][RIGHT] = t; next_right[t][r][DOWN] = r; next_right[t][r][RRIGHT] = 7 - front[t][r]; next_right[t][r][RLEFT] = front[t][r]; } } } static void init(){ static bool _init = false; if(!_init){ initDie(); _init = true; } } public: Dice(int t = 1, int r = 3) : _top(t), _right(r) { init(); } int getTop() const{ return _top; } int getRight() const{ return _right; } int getButtom() const{ return 7 - _top; } int getLeft() const{ return 7 - _right; } int getFront() const{ return front[_top][_right]; } int getBack() const{ return 7 - front[_top][_right]; } void next(int dir){ int tmp = _top; _top = next_top[_top][_right][dir]; _right = next_right[tmp][_right][dir]; } void right() { next(RIGHT); } void left() { next(LEFT); } void up() { next(UP); } void down() { next(DOWN); } void rright(){ next(RRIGHT); } void rleft() { next(RLEFT); } static void forceInit(){ init(); } static int nextTop(int t, int r, int d){ return next_top[t][r][d]; } static int nextRight(int t, int r, int d){ return next_right[t][r][d]; } }; int Dice::next_right[7][7][6] = {{{0}}}; int Dice::next_top[7][7][6] = {{{0}}}; int Dice::front[7][7] = {{0}}; bool solve(const vector<string> &f){ const int h = f.size(); const int w = f[0].size(); vector<vector<int> > g(h, vector<int>(w)); int sx, sy; REP(i, h){ REP(j, w){ if(f[i][j] == '#'){ sx = j; sy = i; goto proc; } } } proc:; int cnt = 0; typedef pair<int, pair<int, Dice> > data; vector<int> use(7); queue<data> q; q.push(make_pair(sx, make_pair(sy, Dice()))); while(q.size()){ const data dt = q.front(); q.pop(); const int x = dt.first; const int y = dt.second.first; const Dice d = dt.second.second; if(g[y][x] != 0){ if(d.getButtom() != g[y][x]) return false; else continue; }else{ if(use[d.getButtom()]) return false; g[y][x] = d.getButtom(); use[d.getButtom()] = 1; cnt++; } if(ISIN(x, y - 1, w, h) && f[y - 1][x] == '#'){ Dice dd = d; dd.up(); q.push(data(x, make_pair(y - 1, dd))); } if(ISIN(x, y + 1, w, h) && f[y + 1][x] == '#'){ Dice dd = d; dd.down(); q.push(data(x, make_pair(y + 1, dd))); } if(ISIN(x - 1, y, w, h) && f[y][x - 1] == '#'){ Dice dd = d; dd.left(); q.push(data(x - 1, make_pair(y, dd))); } if(ISIN(x + 1, y, w, h) && f[y][x + 1] == '#'){ Dice dd = d; dd.right(); q.push(data(x + 1, make_pair(y, dd))); } } return cnt == 6; } string CubeNets::isCubeNet(vector <string> figure){ return solve(figure) ? "YES" : "NO"; }
