2019-09-18

Segment tree を書く (1)

競プロ

皆さん segment tree （セグ木）をご存じですか？

完全二分木にモノイドの元を乗せ、ある区間に演算した結果を求めることができるデータ構造です。セグ木を貼ればこれとかこれみたいな問題が解けます。詳細を説明している記事はググるとたくさん見つかるので、ここでは深入りしません。

この記事では一点更新・区間取得の場合における実装例とそれに至る気持ちを書きます。タイトルに「(1)」とあるのは、今後遅延セグ木などについても書きたいという意思表示です。

問題設定

集合 $M$ に $e\in M$ が単位元となる演算 $\circ$ を入れたモノイドを考え、 $x_0, x_1, \cdots, x_{N-1} \in M$ に対して次の操作を行います。

一点更新：update(i, val)
- $x_i$ を val $\in M$ に変更する
区間取得：query(l, r)
- $x_l \circ \cdots \circ x_{r-1} \in M$ を求める

$[l, r)$ が空なら $e$ を返すのが自然だと思います。

この記事での実装の要点

長さは 2 の冪に切り上げ
根の index は 1
一点更新は葉から遡っていく
区間取得は左右から範囲を狭めつつ遡る
再帰は使わない*1

以下、少し詳しく書いていきます。

配列の領域確保と index の持ち方

簡単のため、 $N$ を 2 の冪に切り上げたものを $L$ とし、長さ $2L$ の領域を確保することとします。切り上げると完全二分木との対応（下図参照）が取れて見通しが良くなります。

以下ではこの配列を $A$ と呼び、 $i$ 番目( $i=0, 1, \cdots, 2L-1$ )の要素を A[i] もしくは $A_i$ と表記します。

根の index は 1 とします。このとき、A[k] の親は A[k/2]、子は A[2*k] と A[2*k+1] となります（存在すれば）。 $x_i$ と $A_{L+i}$ が対応するとか、ビットシフトで祖先を辿れるとかの理由で根の index を 0 にするよりも 1 にする方が好みです。

f:id:wisteria0410ss:20190917222627p:plain — 木の各頂点に対応する配列の index （L=8 の場合）

一点更新

$x_i$ に対応する $A_{L+i}$ と、 $x_i$ を含む区間の結果を持つところ（A[L+i] の祖先）を更新します。

これは下からやると素直にできます。更新する場所の添字について、右に 1 つビットシフトしつつ 0 になるまでループすれば良いです。上の図の index を2進数で書き直してみると自然に見えると思います。

区間取得

ここでも葉から遡っていくようにして計算します。

最初は最下段に着目するので、 $l$ と $r$ に $L$ を加えておきます。ここで最下段の値を結果の計算に用いるのはどのような場合かを考えると、l または r が奇数であるときだと分かります。しかも、用いられるのは $A_l$ または $A_{r-1}$ という区間の端に相当する値です。このことは最下段以外でも同様に成り立ちます。

したがって、次のような操作で計算できることが分かります。

l += L;  r += L;

v_l = e;  v_r = e;
while(l < r){
    if(l & 1) v_l = v_l ∘ A[l++];
    l >>= 1;
    if(r & 1) v_r = A[r-1] ∘ v_r;
    r >>= 1;
}
return v_l ∘ v_r;

C/C++ っぽく書いてますが、 $\circ$ は適切に置き換える必要がありますね（ところで私の環境だと $l$ と $1$ の区別が絶望的なフォントで表示されて悲しいです）。

「 $l, r$ が奇数なら結果に反映させつつ区間を狭める」という操作を、上に遡りながら区間が十分狭くなるまで繰り返しています。*2

また、ここでは演算 $\circ$ に可換性を仮定していません。もし可換なら、v_l と v_r を区別する必要がなくなるので若干簡潔になります。

実装例

template <typename T>
class segment_tree{
    T *tree;
    std::size_t len;
    T e;
    T op(T, T);
public:
    segment_tree(std::size_t n, T ident) : e(ident){
        for(len = 1; len < n; len <<= 1);
        tree = new T[2 * len];
        for(std::size_t i = 1; i < 2 * len; ++i){
            tree[i] = ident;
        }
    }
    ~segment_tree(){
        delete[] tree;
    }

    void update(std::size_t pos, T val){
        tree[len + pos] = val;
        for(pos = (len + pos) / 2; pos > 0; pos >>= 1){
            tree[pos] = op(tree[2 * pos], tree[2 * pos + 1]);
        }
    }
    
    T query(std::size_t left, std::size_t right){
        left += len;
        right += len;

        T v_l = e, v_r = e;
        while(left < right){
            if(left  & 1) v_l = op(v_l, tree[left++]);
            if(right & 1) v_r = op(tree[right - 1], v_r);
            left >>= 1;
            right >>= 1;
        }
        return op(v_l, v_r);
    }
};

verify

問題

提出コード

*1:私は再帰でない方が見通しが良いと感じがちな人間なので非再帰でいきます。あと非再帰のほうが速いという噂？も聞くので（未検証）

*2:この気持ちに従えば r から 1 を引く操作も書くべきなのですが、次の行での切り捨てられるので同じ結果になります。

2019-07-16

AtCoderで黄色になってからしたこと

競プロポエム

マイプロフィールで自分の名前を見てニヤニヤした atcoder.jp

ところで

青のときにこんなことを言っていました。

目標（2つ上の色）、最低でも（1つ上の色）、あわよくば（3つ上の色）になりたい

と言い続けて来たけど、だんだんつらくなってきそう
— ﾚﾎﾟ(GR,qft,現代物理×2,計算科学×3,実験)期末(固体,GR)院試 (@wisteria0410ss) October 27, 2018

この気持ちがもうないといえば嘘になりますが、

目標赤、最低でも橙、あわよくば銀になりたい

↑不可能では？？

精進をしろ

はい。

2019-04-13

TikZJaxで図を描きたい

GitHub - kisonecat/tikzjax: TikZJax is TikZ running under WebAssembly in the browser

TikZJaxをこのブログでも使ってみようと思ったのですが、どうもjsとcssを読み込む先がhttpsじゃないんですよね（追記：今は https になっているようです）。手元で確かめると

混在アクティブコンテンツ “http://tikzjax.com/v1/fonts.css” の読み込みをブロックしました

などと怒られています。このままでは動きませんね…どうするのがいいんでしょう

因みに、動く環境（あるんですか？）の場合はこの下に何かが表示されているはずです。

↓↓↓ここと↓↓↓

↑↑↑ここの間↑↑↑

どうですか？私には見えません。

[2019/04/13 02:52 追記]

Firefoxのabout:configからsecurity.mixed_content.block_active_contentをfalseに変更したら見えるようになりました（それはそう）。でも、設定を変更してもらわないといけないのは違うじゃないですか……

[2022/05/25 23:00 追記]

久しぶりにブログを開いたついでに確認したら読み込み先が https になっていました。特に設定をいじらずとも図が表示されるようになっているのではないでしょうか。

2019-03-21

TopCoder SRM 753 ～はじめてのDiv. 1～

2019/3/12 0:00～のSRM 753に参加しました。TopCoderのコンテストは2回目です。

結果はEasy 1完（142.22点）で62位でした。青に落ちないかと怯えていましたが、レーティングは1505→1610となりました。よかった。

以下、感想や方針を書いておきます。

Easy

問題の概要

無向単純グラフ $G=(V, E)$ に対して、 $S\subset V$ のうち $S$ による誘導部分グラフが $G$ の橋を含まないものを考える。最大の $|S|$ を求めよ。

$1\leq |V|\leq 1000, |E| \leq 1500$

解法など

まず橋を列挙する。DFSあたりでやれそうだけど実装に自信がないので愚直にやることを考えた。一本ずつ注目しながらunion findで判定すればよさそう。 $O(|E|^2\alpha(|V|))$ なので余裕。

ここでサンプルを見ると、橋の端点ではない頂点は $S$ に含めて良いこと、その残り（橋）だけをみると森になることが分かる。すると、あとは「森のうち隣接する頂点を選ばないようにしつつできるだけ多くの頂点を選ぶ」という問題を解けば良いということになる。

（ここで二部グラフ的に適当に塗れば良いという嘘を実装して時間を溶かす）

落ち着いて考えると、葉から順に選ぶか否かを決めるという方針が立ったのでやる。unordered_setに既に見た頂点か、既に選ばれた頂点かという情報を詰めながらDFSという形で実装して提出。

今思えばこれは無駄に煩雑な実装をしていて、木dpを思い出してメモ化再帰をすればよかったなあという感じです。

Med

方針がたたないので適当にググるをすると、Binary Trieというのが見つかりました。これを使うことで多分解けるという気がしたんですが、時間内にバグを取りきれなかったので提出出来ませんでした。ざんねん。

感想

Easyをもっとはやく解けるようにする必要がありそう。1完早解きの勝負になりやすそうな上、Medを解くにも十分な時間が要るので。

2019-03-07

はじめてのとっぷこーだー（TopCoder SRM 752参戦記）

競プロ TopCoder SRM

2019/03/06 21:00(JST)から行われたTopCoder SRM 752に参加しました。準備からコンテスト終了までの大まかな流れや感想などを書いていきます。

準備

アカウントの作成

これは前もってやっていたのでよく覚えていないのですが、何かと分かりにくかった記憶があります。画面の指示通りに進めばとりあえずアカウントは作成できると思います。

アプレットの準備

コンテストはWeb ArenaかJAVA アプレットから参加します。Web Arenaはβ版らしいので、アプレットを使うことにしました。このPDFに諸々書いてあります。

Ubuntuの場合、

$ sudo apt install icedtea-netx

でjavawsを使えるようにしたら、http://topcodr.co/javaarenaからContestAppletProd.jnlpをダウンロードして

$ javaws [アプレットへのパス]/ContestAppletProd.jnlp

で起動できます。通信するので色々警告が出ますが、適切なボタンを押して先に進むとログイン画面が出ます。ログインに成功したら準備はほぼ終了です。

コンテストの流れ

大体次のような感じでした。

上の「Active Contests」から参加するコンテストを選び、「Register」。参加登録は開始5分前に一旦締め切られるようです。
5分前になったら「Enter」が選べるようになるので選択してルームへ。
開始まで待機。
Codingの時間。プルダウンから得点を選ぶとそれに対応する問題が別窓で出てくる。複数の問題を同時に見ることはできない。また、最初に開いてからの時間で得点が計算されるらしい？
Codingが終わったら5分間の休憩。
Challenge。同じルームにいる人の解答が見られるようになるので、不正確なものを見つけて撃墜する。撃墜に成功すると得点が入るっぽい。
System Test。採点が行われて結果がわかる。

コンテストの感想など

Coding Phase

問題の解答は標準入出力ではなく、指定されたクラスに問題を解く関数を書くという形式のようです。何も設定しないとJavaの問題文が表示されるので、別の言語を使う場合は右上のラジオボタンで変更します。型の指示などがそれに応じて変わります。過去問をやることでこのあたりは把握できていたので良かったです。

Batch Testを選ぶと一括でテストケースのチェックをしてくれるのは便利ですね（表示される結果を理解するのに少し時間がかかった）。

Submitを選ぶと確認のダイアログが出ますが、フォントの関係かボタンの文字が死んでいます。しかし、「□□(Y)」と「□□□(N)」なので「はい」と「いいえ」であることは容易に推測できます。 ~~競プロに必要とされるエスパー力の訓練ですね。~~

結構時間を余らせて3問提出できたので余った時間は見直しをしていました。システス形式は精神衛生上よろしくない。

問題は下のような方針で解きました。

SRMお疲れ様でした。
Div. 2
Easy: 算数をします。余った時間でシミュレーションと一致することを確かめたので大丈夫なはず。
Med: 片方の手札全特定のうち早い方
Hard: DP。MLEが怖いので/usr/bin/time -f "%M" ./a.outをして確かめた。大丈夫なはず。
— 里旬 (@wisteria0410ss) 2019年3月6日

Intermission

呼吸を整える時間。もしかしてここで撃墜補助ツール的なものを準備すると良いのでしょうか。

Challenge Phase

やることはコドフォのHackと同じという理解をしています。

System Testing Phase

通ってくれ。通った。

結果

3完1366.85点でDiv. 2で9位（Room内2位）でした。Coding終了時はRoom内1位だったのにChallengeの得点で抜かされました。ざんねん。

レートは1505(Yellow)になりました。初めての暖色です。わーい。

その他

Arenaで確認できるCoder Infoのうち、Coder typeの項目がProfressionalになってしまっている。アカウント作成時にそんな選択した記憶ないし、私はStudentなんですが... 調べても変更する方法がわからなくて困っています。わかる方がいたら助けてください
間違って触ってしまったせい？でプロフィールに生えた「Data Scientist」が消せない←[追記]コンテストに参加していてもなるらしいです。また、Skillsの欄も勝手に増えたのが確認できました
プロフィールの名前の色はSRMでの色とは別物なのでしょうか？（執筆時点で薄い灰色）←[追記]反映までに時間がかかるそうです
プロフィール設定、わかりにくくないですか
親切な有識者の方がいらっしゃいましたら@wisteria0410ssに教えてくださると幸いです
感想メインの参戦記と準備についての部分で記事を分けたほうが良かったかも
@IKyoproさん、情報提供ありがとうございます

2019-02-26

Ubuntu 18.04.1 LTSでやる 30日OS本〜22日目〜

30日OS本

Ubuntu 18.04.1 LTSでやる 30日OS本、22日目です。他の章へのリンクはここにあります。

1. OSを守ろう

問題なく動作していることが確認できました。

2. バグ発見を手伝おう

QEMUでもbug1.hrbでは「AB」と表示された後に例外が発生しました。EIPレジスタの値を表示させると「EIP = 00000062」となりました。 bug1.mapを見ると、

（前略）
.text           0x0000000000000030       0x73
 *(.text)
 .text          0x0000000000000030       0x5d obj/bug1.o
                0x0000000000000030                app_main
 *fill*         0x000000000000008d        0x3 
 .text          0x0000000000000090       0x13 obj/a_nasm.o
                0x0000000000000090                api_putchar
                0x000000000000009c                api_end
（後略）

となっており、app_main内で例外が発生したことがわかります。 bug1.lstの生成方法がわからなかったので、詳細はbug1.oをディスアセンブルすることで確認します。 objdump -M intel -D obj/bug1.oの結果の一部を下に示します。

00000000 <app_main>:
   0:   55                      push   ebp
   1:   89 e5                   mov    ebp,esp
(中略)
  2f:   83 c4 10                add    esp,0x10
  32:   c6 45 0f 43             mov    BYTE PTR [ebp+0xf],0x43
  36:   8a 45 0f                mov    al,BYTE PTR [ebp+0xf]

この結果と 0x30 + 0x32 = 0x62 より、mov BYTE PTR [ebp+0xf],0x43で例外が発生していたと特定できました。なお、'C'=0x43です。

ところで割り込みの処理asm_inthndlerXXは大体どれも同じ処理をしています。同じことを繰り返し書いておくのは嫌なので、NASMのマクロを利用してまとめてしまいました。 NASMのマクロは

%macro [マクロ名] [引数の数]
（中身）
%endmacro

という形で宣言でき、

[マクロ名] [引数1],[引数2],...,[引数n]

で呼び出せます。マクロの中身にある%1, %2, ..., %nが対応する番号の引数として展開されます。

3. アプリの強制終了

アプリの実行途中で強制終了できるようになりました。[Shift]+[F1]ではなく[Break]で強制終了するようにしようとも思ったのですが、 [Break]は送られてくるキーコードが長くて面倒だったため、今後の課題とすることにしました。

4.・5. C言語で文字列表示

ここでの説明でリンカスクリプトの中身が解読できます。ESPレジスタの初期値がここでは0x400となっているので.head内を書き換え、下の方にある.dataから始まる部分を.data 0x400: ~~~に変更します。https://vanya.jp.net/os/haribote.html#gcchrbにあるリンカスクリプトのアプリケーション用と同様のものに差し替えても良いかも知れません。

ここからAPIを利用して何かをすることが増えるので、api_***という関数の宣言を書き並べたヘッダファイルapi.hを作っておくことにしました。また、"Hari"が見つからないと実行されないようになったため、アセンブラでアプリを作る場合にも一旦オブジェクトファイルを作ってリンクするという流れにします。 Makefileをこれらに合わせて変更します。

APPS := $(patsubst app/%.c,bin/%.hrb,$(patsubst app/%.asm,bin/%.hrb,$(filter-out app/api.asm app/har.lds app/api.h,$(wildcard app/*.*))))
# あるいは
#APPS := $(patsubst app/%.asm,bin/%.hrb,$(filter-out app/api.asm,$(wildcard app/*.asm))) $(patsubst app/%.c,bin/%.hrb,$(wildcard app/*.c))

bin/%.hrb: app/%.c app/api.h obj/api.o app/har.lds Makefile
    gcc -fno-pie -march=i486 -m32 -masm=intel -nostdlib -c $< -o obj/$(*F).o
    ld -o $@ obj/$(*F).o obj/api.o -e app_main -Map lst/$(*F).map -m elf_i386 -T app/har.lds

bin/%.hrb: app/%.asm obj/api.o app/har.lds Makefile
    nasm -felf $< -o obj/$(*F).o -l lst/$(*F).lst
    ld -o $@ obj/$(*F).o obj/api.o -e app_main -Map lst/$(*F).map -m elf_i386 -T app/har.lds

obj/api.o: app/api.asm Makefile
    nasm -felf app/api.asm -o obj/api.o

として、$(APPS)をイメージファイルの依存関係に書いておけば良いです。なお、エントリポイントは「Harimain」から「app_main」に変更してあります。api.asmは本でのa_nask_nasにあたるファイルです。このようにしておけば、新しいアプリを作るときにもMakefileはいじらなくても良くなるはずです。多分。

6.・7.

ウィンドウが増えました。（書いていないので当然）出てきたウィンドウはまだ動かせません。

2019-02-26

Ubuntu 18.04.1 LTSでやる 30日OS本〜21日目〜

30日OS本

Ubuntu 18.04.1 LTSでやる 30日OS本、21日目です。他の章へのリンクはここにあります。

1. 文字列表示APIを今度こそ

本の通りにやると動くようになりました。

2. アプリケーションをC言語で作ってみたい

リンカスクリプトはbootpack.hrbを作ったものをここでは流用しました。また、先頭6 byteの書き換えはバイナリエディタで編集する以外にもリンカスクリプトを書き換えることでも達成できます。

(前略)
.head 0x0 : {
        LONG(64 * 1024)       /*  0 : stack+.data+heap の大きさ（4KBの倍数） */
        LONG(0x69726148)      /*  4 : シグネチャ "Hari" */
(後略)

↑これをこう↓

(前略)
.head 0x0 : {
        LONG(0x000016E8)
        LONG(0x6972CB00)
(後略)

この節の最後でcmd_appに細工をしたら、これは元に戻します。

また、api_putcharに関数をa_nask.nasにあたるファイルを作成して記述する代わりに、インラインアセンブラで書いてしまうこともできます。

void api_putchar(char c){
    __asm__ volatile(
        "mov edx, 1\n"
        "mov al, %0\n"
        "int 0x40\n"
        :
        :"r"(c)
        :"edx", "eax"
    );
    return;
}

void app_main(){
    api_putchar('A');
    return;
}

intel記法を用いているので、コンパイラオプションに-masm=intelが必要です。また、gccではこれで良いのですが、 clangでは更に__asm__の中に.intel_syntax noprefixを書いてやる必要があるらしいです。

ただ、今後のことを考えると何らかのファイルに分離するべきな気がします。

3. OSを守ろう(1)

確かにcrack1を実行するとファイルが読めなくなる？ようです。

4. OSを守ろう(2)

本では実行しても何もおこらないとなっていますが、手元の環境ではHaribote OSが再起動しました（どこかを間違えている可能性は排除できませんが）。

5. 例外をサポートしよう

本ではQEMUのバグで例外が出ないとありますが、そのバグは修正されているようで例外が出ることを確認できました。

6.・7. OSを守ろう(3)・(4)

(3)で作ったcrack2でも(4)の作業によって例外が出るようになりました。