sataniC++

C++、競プロ、数学などについて色々考えたりします。

ダブリング

アルゴリズム アルゴリズム-た

概要

「N個次の要素を知りたい」といった状況で頻繁に用いられるテクニックです。


使える状況

「ある要素に対してその次の要素は容易に得られるが、N個分次の要素を得るクエリがO(N)時間じゃ間に合わない」
というときに、ダブリングを使うことによって、全体の大きさMに対して準備O(M\log M)、クエリO(\log N)で求めることが出来ます。


説明

「使える状況」で述べた場面は、具体的には、

  • ある数XのN乗を求めたい
  • 根付き木において、ある頂点vのN個上の親を知りたい

などです。

どちらも、次の要素（X^2や頂点vの親）は容易に求められますね。


しかし、次の次の次の…と初めの要素からN個次の要素を知るには、単純に考えるとO(N)時間がかかってしまいます。

これをO(\log N)時間で行うことが出来るのが、ダブリングと呼ばれる手法です。


ダブリングは、次のような流れで行います。
まずは各要素における「1つ次の要素」を調べておきます。
こうすることで、「「1つ次の要素」の1つ次の要素」、つまり「2つ次の要素」は即座に得ることが出来るようになります。

これを繰り返すと、各要素の「4つ次の要素」,「8つ次の要素」,…,「2^k個次の要素」と調べ上げることが出来ます。


このとき、k=\lfloor \log N \rfloorまで調べれば、あとはNを二進展開した時に立っているビットの数だけ
「...「○個次の要素」の●個次の要素...」と調べればよいため、
1回N個次の要素を調べるのにはO(\log N)時間しかかかりません。
（ちなみに二進展開とは、2進数に変換することをいいます）


疑似(？)コード

ダブリングは適用できる範囲が広いため、大まかな流れを以下にC++風で記しておきます。
（基本的には\mathtt{next[ 0] }の値を計算するところを変えるだけです）

int N; // 全体の要素数
int LOG_N; // = floor(log_2(N))

// next[k][i]で、i番目の要素の「2^k個次の要素」を指す
// (なお、i番目の要素に対して「2^k個次の要素」が存在しないとき、
//  next[k][i]が指し示す要素番号を-1とします)
std::vector<std::vector<int>> next(LOG_N + 1, std::vector<int>(N)); 

// next[0]を計算
for (int i = 0; i < N; ++i){
    next[0][i] = (iの次の要素);
}

// nextを計算
for (int k = 0; k < LOG_N; ++k){
    for (int i = 0; i < N; ++i){
        if (next[k][i] == -1) {
            // 2^k個次に要素が無い時、当然2^(k+1)個次にも要素はありません
            next[k + 1][i] = -1;
        }
        else {
            // 「2^k個次の要素」の2^k個次の要素は、2^(k+1)個次の要素です
            next[k + 1][i] = next[k][next[k][i]];
        }
    }
}

// ----ここまで準備----

// p番目の要素の「Q個次の要素」を求めることを考えます
for (int k = LOG_N - 1; k >= 0; --k){
    if (p == -1) {
        // pがすでに存在しない要素を指していたら、
        // それ以降で存在する要素を指すことはないためループを抜けます
        break;
    }
    if ((Q >> k) & 1) {
        // Qを二進展開した際、k番目のビットが立っていたら、
        // pの位置を2^kだけ次にずらします
        p = next[k][p];
    }
}

コードの説明

上に示したコードは、次のような流れに沿って処理を行っています。

  • 各要素について、すぐ次の要素\mathtt{next[0]}を調べる
  • 各要素について、\mathtt{next[0]}を使って\mathtt{next[1]}を求め、その\mathtt{next[1]}を使って\mathtt{next[2]}を求め、…として\mathtt{next}全体を調べ上げる
  • 上で求めた\mathtt{next}を使って実際に\mathtt{p}番目の要素の\mathtt{Q}個次の要素を求める

具体例

ある根付き木に対して、頂点vからN回親を辿った先の頂点を求める

今回は、解説スライドを用意してみました。
（すべて画像で構成されているため若干見づらいかと思います。後でPowerPoint等で作り直します…）


備考

一般に、\mathtt{next}配列を構成するのに全体の大きさMとしてO(M\log M)時間がかかりますが、
ある数Xの累乗を求める際には、
「どんな要素(数)であってもK個次の要素はX^Kを掛けることに他ならない」
という性質から、\mathtt{next}配列を構成する必要がなく、各クエリごとのO(\log N)時間しかかかりません。


また、「二進展開する」とは言っていますが、上記コードで示している通り、
実際には「\mathtt{k}番目のビットが立っているか？」を調べるだけで構いません。


あとがき

ダブリングは、繰り返し自乗法、LCA(最近共通祖先)を求める際、Suffix Array(接尾辞配列)の構成などなど、多くの場面で使われる考え方です。
これはアルゴリズムの高速化において、「数を二進展開して考える」ことが基本となっているためでしょう。
（他にも「半分に分割して考える」というのも基本的な考えの一つです）


ダブリング自体を意識して問題を解くことは多くはないかもしれませんが、
高速化の手法の一つとして頭に入れておくと良いでしょう。

競技プログラミングを始めて1年が経ちました

競プロその他

2015/11/22に競技プログラミングを始めてから丁度1年が経ったので、競技プログラミングをやるにあたって、何をしていたか等を記事としてまとめておきます。
（ためになる話は多分そこまでないです）


この記事の流れ

この記事は次のような構成になっております。

  • 始まり
  • 競プロを始めて変わったこと
  • この一年での競プロにおける変化
  • （以下「続きを読む」部分、競プロでの様々なこと）
  • 言語
  • 競プロ環境
  • 練習・勉強方法
  • 成績
  • 最後に

始まり

twitter.com
私が"競技プログラミング"というものに触れたのはyukicoderが一番最初でした。
何故yukicoderかはわかりませんが、yukicoder の"ゆるふわ"推しにつられたのでしょう(？)。
このときは、AtCoderやTopCoder、ICPCなどは全く知りませんでした。


競プロを始めて変わったこと

twitter.com
簡単に言うと、競プロ依存になりました。

競プロは、何かキッカケをもって始めた訳ではないため、
「まぁコーディングの練習として適当にやってみよう」
位の感じでした。


しかし、問題を解き、コンテストにも参加するようになると、だんだん次のようなところに惹かれていきました。

  • 問題を見たときに、「どのアルゴリズムを使うのがいいか？」と考えるのが楽しい
  • 実生活でありうるような、複雑な要素が絡み合う問題をプログラムに解かせることが出来るのが面白い
  • 単純に問題を解くのが楽しい
  • Twitterを通して他の人と競プロの話題で盛り上がることが出来るのが楽しい

などなどです。

こうして、競プロを主軸とした生活が始まるのでした…。



twitter.com
また、Twitterの利用法も大きく変わりました。
このツイートは競プロを始めて1週間くらいの時のものですが、当時まだフォロー/フォロワー数が100人前後しかいませんでした。
f:id:satanic0258:20161123215514p:plain
（競プロを始める前は何故かこんなアイコンだったんですが、覚えている人はいるんでしょうか）



twitter.com
f:id:satanic0258:20161123220040p:plain
ところが、競プロを始めて、競プロ/プログラミングをやっている人をフォローしていたら、気づくとフォロー/フォロワー数が400人前後まで増えていました。

Twitterで話す内容も、半分以上が競プロの内容ばかりとなっています。



twitter.com
また、いつの間にかプログラム実装力がついていました。

プログラミングのコンテストでは、問題を見てからそれをすぐにコードに起こすことが重要となってきます。
そのため、コンテストで経験を積んでいった結果、競技とは関係のないところで簡単なプログラムを作成する際に、素早く目標のプログラムを作成することが出来るようになっていました。
（このおかげで試験も難なくこなせたので、まさに競プロありがとう、と言った感じでした）


この一年での競プロにおける変化

ここでは、各コンテストサイトでのレートの変遷を見ていきます。

AtCoder

f:id:satanic0258:20161123225317p:plain
AtCoderのページが新しくなってからのレートはこのようになっています。
未だ何とか単調増加を続けてはいますが、正直結構厳しいですね…。
なるべく増加を続けられるように頑張りたいと思います。


Codeforces

f:id:satanic0258:20161123225558p:plain
Codeforcesのレートはこのようになっています。
正直こどふぉは問題文がの読解が難しい回が何回かあり、それ故のミスもよくしています…。
（最近Google翻訳の性能が向上したこともあってか、レートも少し上がっています）

また、こどふぉではちゃんとコーナーケースを処理しなければ落ちてしまうことも多々あるため、うっかりそれを忘れてレートが下がったりもしています。
素早く、かつ正しく問題を理解することが大切ですね…。


TopCoder SRM

f:id:satanic0258:20161123230126p:plain
SRMのレートはこのようになっています。
SRMは結構レート変動が激しく、参加した回の半分も色が変わってしまっています（苦笑）。

一応青から黄色になったりしてはいますが、まだdiv1の問題を時間内に解いたことがないため、それが今後の課題となっています。
何とか競プロ2周年までには、div1easyを安定して解けるようになりたいですね。


  • （以下「続きを読む」部分、競プロでの様々なこと）

この先は、過去1年分のツイートを適当に抜粋して、あったことなどのコメントを加えただけのものなので、時間に余裕のあるときどうぞ。

(Twitterのツイートを大量に貼り付けているため、記事のロードに時間がかかる可能性があります)

続きを読む