Hatena::ブログ(Diary)

プログラミング関係のメモとか

2014-05-21

SRM621

SRM621の500で閃いたアルゴリズムがちょい面白い気がしたのでメモっておく。
問題自体の解法に直接は触れないので、解説が見たい方は別のところを参照してください。

以下の問題を考えます。

木をDFS的に探索する。
ある頂点を見ている時に、その頂点から下向きに出ているある枝に対してその枝より下に付いている頂点の集合をSとする。
(上下関係は木の根が上、葉が下とする)
任意の頂点pに対してpがSに含まれるかどうかをO(1)で判定する。
というのを時間的なオーバヘッドほぼ無しで行いたい。

要するにイメージは以下(C++っぽい擬似コード)

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したあとに好きな枝に対してクエリが投げられる(と思う)

2014-01-03

あけおめことよろ

レッドコーダーに一瞬なってから負け続けてレーティングだだ下がりのまま年を越してしまいました。

今年はレッドコーダーでしばらく停滞することを目標にします。
最近練習全然できていないので今のままではムリですね。
SRM練習どこかのタイミングで再開したいです。

2013-10-31

いわゆる転職エントリ

本日付けで会社退職しました。
1週間ほどニートした後に次の仕事はじめます。
早くニートになりたい人よりも先にニートになれました。

研修期間を除くと1年と4ヶ月ほどいたことになると思います。
転職の動機はいろいろありますが、開発志望で入ったのに開発をさせてもらえずモチベーションが保てなくなったといったところがメインです。
周りの友人や先輩にはとても恵まれていたと思っていますが、やりたいことを優先して決めました。
おそらく傍からみるともったいない転職なのでしょうが、まあ転職して良かったと思えるように全力で頑張るだけですね。

転職CodeIQ経由で声かけてもらってそのまま決めた感じです。
とてもおもしろそうな会社だと思っているのでいまのところ満足しています。

2013-04-15

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),
    */

とりあえずインストールできるけど、あってるのかは不明。

2013-02-23

レッドコーダー

先日TopCoderのAlgorithmでレーティングが2200を超え、赤コーダーになりました。
あと1,2年はかかると思っていたので、自分でもびっくりしています。

http://community.topcoder.com/tc?module=MemberProfile&cr=22881459

2010年の7月から始めたみたいなので3年半くらいかかったようです。
まあ、競技プログラミング自体はもう3年くらい前からやっていたわけですが。

Code Forcesの方もあと少しで赤ですが、こちらはその少しが大分遠そう。

しかし最近は解く問題数がどんどん減っているのに何でこんなに一気にレーティングが上がったのかよくわかりません。
あえて探すとすると最近は

  • ブログにも書いてるけど一応SRM対策をしていた
  • 難しい問題を時間をかけて解くことが多くなった
  • ソースコードを読む機会が増えた

あたり。そこが効いたとしか…

データ構造とか大分弱いので、これから勉強していきたいですね。
PKUとかがいいのかなぁ…

次の目標はyasuhさんのレーティング超え