春休み活動記録 (未来編)

これは何

春休みにやり残したこと。

前編: 

春休み活動記録 (前編) - Z-diary

後編: 

春休み活動記録 (後編) - Z-diary

f:id:zaki_joho:20210328135725j:plain

読書

読みたい本読み切れなかった。

ほしいものリスト (Open)

 

映画

まだ第3話見に行ってない

girls-und-panzer-finale.jp

 

ゲーム

2021年4月22日発売予定。

www.gamecity.ne.jp

2021年8月26日発売予定。

www.typemoon.com

 

アニメ

楽しみ~。

higurashianime.com

楽しみ~。

www.tbs.co.jp

  

ポエム

単位揃えてインターン行って〇活してたらM1終わってた。研究してる院生偉すぎ。

春休み活動記録 (後編)

これは何

前編からの続き。3ヶ月に渡る春休みに何を読んだか。

 前編: 

春休み活動記録 (前編) - Z-diary

 未来編: 

春休み活動記録 (未来編) - Z-diary

f:id:zaki_joho:20210328135232j:plain

 

パソコン

実装目線で書かれている点に独自性がある。

www.morikita.co.jp

Python とかの勉強するよりこれ読んだ方が良い。

gihyo.jp

 昨年の4月に受けようとしたが消滅したので放置していた。次の試験は10月らしい。

gihyo.jp

 

将棋

実践で見逃しがちなので。

book.mynavi.jp

book.mynavi.jp

book.mynavi.jp

これ詰むのか~ってのがしばしばある。

www.asakawashobo.co.jp

www.asakawashobo.

co.jp

三間飛車が最近熱いらしい。

book.mynavi.jp

book.mynavi.jp

振り飛車・対雁木・対矢倉で最強。

book.mynavi.jp

対策のため。

book.mynavi.jp

 

社会

聖書1。

nikkeibook.nikkeibp.co.jp

聖書2。

nikkeibook.nikkeibp.co.jp

予言書。

www.shoeisha.co.jp

史書

www.shinchosha.co.jp

周りでベンチャーに行く人少なくないので。 

www.njg.co.jp

 

その他

計算複雑性理論完全に理解した。アルゴリズムとか量子とかやってる人は読んだ方が良い。

www.morikita.co.jp

WORLD END ECONOMICA に似たやつが読みたくて。

現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変 

TVで見て面白そうな回だったので。

www.nhk-book.co.jp

3級取った。2級も一通り読んだけど取る必要はないかな。

www.kinokuniya.co.jp

税金ヤバすぎ。

nikkeibook.nikkeibp.co.jp

レコメンドされた。

www.kinokuniya.co.jp

なんか読んだ。火攻はよく晴れた風の強い日に行うといいらしい。

www.iwanami.co.jp

春休み活動記録 (前編)

これは何

修士学生であるにも関わらず研究をせず春休みと称して3ヶ月も何をしていたのか。

 後編: 

春休み活動記録 (後編) - Z-diary

未来編: 

春休み活動記録 (未来編) - Z-diary

f:id:zaki_joho:20210328135523j:plain

 

イベント

ICPC に参加した。健闘。

zaki-joho.hatenablog.com

Google Hash Code に参加した。同期と後輩が Final Round 進出しててすごい。

codingcompetitions.withgoogle.com

DeNA TechCon 2021 を観た。アンケートに答えたらアマギフ\3000くれた。

techcon.dena.com

 

将棋

十数年ぶりに将棋を再開した。YouTube 見て、本読んで、将棋ウォーズで実戦して elmo で棋譜検討、みたいな感じで勉強している。環境が充実しててこれは強い新人出てくるなあ。

www.youtube.com

www.youtube.com

www.youtube.com

karyuu.hatenablog.com

自宅の Windows にはすぐ導入できたが、研究室の Mac Mini (Apple Silicon) に入れようとしたら自力でソースコード書き換えてビルドする羽目になった。

mk-takizawa.github.io

 

V

ライブ良かった。

 

バイス

Fitbit Charge 4 を買った。毎日散歩する習慣がついた。

www.fitbit.com

 

英語

実践ビジネス英語のWebラジオを聞くようになった。今年度で番組終了らしいのでこれからどうしよう。代替番組募集中。

www.nhk.or.jp

アプリはもうちょっと頑張って作ってほしいな。

www2.nhk.or.jp

 

紅茶

定期的に三条へ紅茶を買いに行っている。CEYLON KANDY が美味しかった。

www.lupicia.com

 

食事

BASE FOOD には飽きたので最近は普通の食パンを食べている。

basefood.co.jp

nosh、定価は高い。

nosh.jp

 

ゲーム

微妙に積んでいたまほよを終わらせた。月姫楽しみ。

www.typemoon.com

 

読書

長くなったので後編

ICPC 2020 Asia Yokohama Regional 参加記

はじめに

2021/03/17 に行われた ICPC 2020 Asia Yokohama Regional にチーム TigerSone. (etonagisa, nikutto, zaki) で参加しました。

結果は8完で9位でした、前回チーム戦をしたのは 国内予選で3人合わせて競プロブランク12ヶ月という状態で臨みました。

f:id:zaki_joho:20210317193410p:plain

standings

 

コンテスト

A: Aにしては難しくない?添字がバグりまくってるのを nagisa にデバッグしてもらって AC。

B: A 解いて見に行ったら nikutto が +1 してたので応援して AC。

C: nagisa に右手法で解けそう~と言われてグッと睨んだら6行のアセンブリが生える。5行以下を全列挙してシミュレートするプログラムを実装したら一発で通る、天才。

E: nagisa と2分探索と greedy でできそ~とか言ってたけど最後の詰めで怪しくなる。nikutto が助けに来て nagisa が実装して AC。

G: nagisa と nikutto が解いてた。

H: nikutto に投げた。

I: nikutto に投げた。

J: nagisa が 解いた。

K: suffix array 見ながら DP できそうで、コンテスト終了まで解いていたが間に合わず。

 

感想

C 問題が一番好き、Sample Input 4 を入力したら 5行の右手法アセンブリが出てきて感動。

 

大きなミスも無く、チームワークを発揮して実力的にベストな結果を出せたと思います。ICPC は今年で引退です。運営の方々、KMC の人々、そしてチームメイトに感謝しています、ありがとうございました。

 

f:id:zaki_joho:20210318162715j:plain

おまけ

誰も顔写真を送らなかったため、3人ともいらすとやになりました。運営の皆様、ごめんなさい。

f:id:zaki_joho:20210317200425p:plain

team member

 

ICPC 2020 国内予選参加記

はじめに

 2020/11/07 に開催された ICPC 2020 国内予選に etonagisa, nukutto, zaki_ の3人でチーム名 TigerSone. で参加し、学内2位全体6位で予選通過しました。横浜でボドゲするのが楽しみです。

 

f:id:zaki_joho:20201107232359p:plain

 

コンテスト開始(?) 

ログインしようとするも database broken とか何とか表示される。メンバー全員がログインできないので、緊急連絡先に電話するも通話中になっていた。サーバー側が壊れてると判断して待機。F5ポチポチしてたらサイレント復旧してた、えぇ…。

 

コンテスト開始

A: zaki, B: nagisa, C: nikutto で分担して実装開始。

A ってこんなに簡単だったけ、A AC (3:50)

B, C は大丈夫らしいので 後ろの問題を見に行く。Dの構文解析パートは簡単だけど n=16 で解けるんか? E は数を数えないといけなそうなのでこの時点で nikutto に丸投げをキメる。

この辺で nagisa が B AC (11:12)。D を相談するも二人でウンウン言ってた。

C の実行が終わらないらしいので呼ばれて C を見に行く。問題読んで解法を聞いた辺りで実行が終了した。C AC (14:35)。

nikutto に D を説明したらすぐに 2^n 解法が降ってきた、天才か? nagisa に見てもらいながら実装する。nikutto に E を投げる。

D を特に事故もなく実装してサンプルが合う。D AC (51:25)。standings 見たら Heno World に次いで2位だった気がする。

nikutto が E 解けそうらしいので nagisa と頑張ってもらうことにする。

ここでまた後ろの問題を見に行く、H: 問題を見てニッコリ、解かせる気、ある?G は制約と最小流量制約が見えてフローだな~復元付きだしやべ~となる。F が解けそうな気がするので考える。

nikutto が部分集合求めるのどうやるんだっけとか言ってたので伝えたら解けたらしい。E AC (1:30:07)。

この時点で G, H が全く通されていなかったので F を3人で解くことにする。ウンウン言いながら大分嘘言った気がする、ごめんね。

nikutto が頑張って書くらしいので応援してたけどデバッグ間に合わなかった、時間は余裕あったし速い愚直書けばよかったと反省。

 

感想

 Fを通しきって6完したかったが、予選通過したのでまあヨシ。

3人とも最近競プロ引退してたけどきっちり本番でパフォーマンス出してくる nikutto と nagisa に感謝です。

2位以下に2完差付けて優勝した __KING__ やべ~。

Rust で Linked List を実装する(2. 永続スタック編)

はじめに

前回の記事で単方向連結リストを実装しました。
zaki-joho.hatenablog.com

単方向連結リストがあるということは? そうですね、永続スタックを実装することができます!
今回の記事は Introduction - Learning Rust With Entirely Too Many Linked Lists の第4章に相当します。

ソースコードは gist (persistent stack · GitHub) に置いてあるので適宜参照してください。

相変わらず Rust 全然分かってないので間違いがあればコメント欄なりで指摘してください。

永続スタック(persistent stack)

永続スタックについておさらいしておきましょう。
まず [A, B, C, D] という要素を持つスタック1があるとします。スタック1 の先頭を取り除いたもの(=[B, C, D])をスタック2とします。そしてスタック2に要素 [X] を追加したもの(=[X, B, C, D])をスタック3とします。

図にするとこんな感じです。

f:id:zaki_joho:20200620220200p:plain
永続スタック

この3つのスタックを管理したいとき、どうすれば良いでしょうか。全ての要素をコピーして別々のスタックとして扱う方法もありますが、要素数が多くなると無駄が多くなりそうです。図を見ると各操作の後に要素の大半は変化していないことが分かります。
新しくスタックを作るとき、先頭要素だけ新しく作成して残りの要素は元のスタックを参照するといい感じに表せそうですね!

永続スタックでは次の操作が O(1) で可能です。

  • head(): 先頭要素にアクセス
  • append(T x): 要素 x を追加して得られるスタック作成
  • tail(): 先頭要素を削除して得られるスタックを作成

更に知りたい方は先行研究 あなたの庭に永続データ構造を飾りませんか? - noshi91のメモ が詳しいです。

実装

永続スタックを完全に理解したところで実装していきます。

構造体

まずは永続スタックを表す構造体を定めます。

use std::sync::Arc;

struct List<T> {
    head: Link<T>,
}

type Link<T> = Option<Arc<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

いきなり Arc が出てきてしまいました。
永続スタックを実装するにあたって、上の図を見直してみると要素 A は複数のスタックから参照されていることが分かります。
各スタックに好き勝手されては困るので、参照カウンタである Arc で管理します。今回は別にマルチスレッドで動かすわけでもないので Rc でもいいのですが、折角なので Arc を使っておきましょう。

正直理解できてるか怪しいので、Rustの `Arc` を読む(1): Arc/Rcの基本 - Qiita を読んで勉強中です。

それ以外の部分は前回と同じように書けます。

操作

構造体が書けたところで各操作を実装していきます。

impl<T> List<T> {
    fn new() -> Self {
        List { head: None }
    }

    fn append(&self, elem: T) -> List<T> {
        List {
            head: Some(Arc::new(Node {
                elem: elem,
                next: self.head.clone(),
            })),
        }
    }

    fn tail(&self) -> List<T> {
        List {
            head: self.head.as_ref().and_then(|node| node.next.clone()),
        }
    }

    fn head(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.elem)
    }
}

new(), head() は前回と一緒です。
tail() はスタックが既に空のときにも処理できるように map() でなく and_then() を使います。
append() が少し問題で、Arc を使って先頭要素への参照を作成する必要があります。

イテレータ

ついでに今回もイテレータを実装します。
mutable にすると大変なことになる(というかコンパイルできるんですか?)ので今回は immutable なイテレータだけです。

struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

これは前回と同じですね。

impl<T> List<T> {
    fn iter(&self) -> Iter<'_, T> {
        Iter {
            next: self.head.as_ref().map(|node| &**node),
        }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

こっちも丸写しで完成してしまいました、楽ちん。

感想

ほぼ Arc で包むだけで永続スタックが書けてしまいました。これで庭が賑やかになりますね。
Drop trait を実装していないので実際に使うとき(あるか?)は注意してください。

次回は Doubly linked list を実装する予定です。目次に "A Bad but Safe Doubly-Linked Deque" とか書かれているんですがどうなってしまうんでしょうか。

Rust で Linked List を実装する(1. 単方向連結リスト編)

はじめに

Rust を勉強したいので Linked List を実装します。
元ネタは Introduction - Learning Rust With Entirely Too Many Linked Lists
リンク先では スタック \rightarrow 永続スタック \rightarrow 双方向 Linked List \rightarrow ... といった順で解説が書かれていて、読み物としても面白いので目を通すことをおすすめします。

とりあえず(単方向)Linked List を実装したので備忘録的に記事を書きます。
まだ上記リンクの3章までしか実装していないので、Linked List とは言っても機能的にはスタック(C++ の std::stack)と呼んだ方が適切かもしれません。

ソースコードsingle linked list · GitHub に置いてあります
Rust 何も分かってないので間違えていたらコメント欄かどこかで教えてください。

環境

  • OS: Windows 10 Home + WSL
  • rustc: ver. 1.44.0
  • エディタ: VSCode + Rust(extension)

Linked List

こんな感じのデータ構造。

f:id:zaki_joho:20200616235214p:plain
単方向リスト

できる操作は

  • 先頭への要素の挿入
  • 先頭要素へのアクセス
  • 先頭要素の削除
  • 素数の取得

で、いずれも O(1) です。
今回はこれらの操作に加え、先頭からシーケンシャルアクセスが可能なイテレータを実装します。

実装

構造体

まずは Linked List を表す構造体を実装します。

struct Node<T> {
    elem: T,
    next: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct List<T> {
    head: Link<T>,
    size: u32,
}

各ノードは値と次のノードへのリンクを保持します。

Option<Box<Node<T>>>

の形でリンクを表すことで、次のノードが存在しないことを None で表現することができます。
リスト自体には先頭要素へのリンクのみを保持します。

操作

リストが定義できたので各操作を実装していきます。

impl<T> List<T> {
    fn new() -> Self {
        List {
            head: None,
            size: 0,
        }
    }

    fn push(&mut self, elem: T) {
        self.size += 1;
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    fn pop(&mut self) -> Option<T> {
        match self.head.take() {
            None => None,
            Some(node) => {
                self.size -= 1;
                self.head = node.next;
                Some(node.elem)
            }
        }
    }

    fn top(&self) -> Option<&T> {
        match &self.head {
            None => None,
            Some(node) => Some(&node.elem),
        }
    }

    fn top_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| &mut node.elem)
    }

    fn is_empty(&self) -> bool {
        match &self.head {
            None => true,
            Some(_) => false,
        }
    }

    fn len(&self) -> u32 {
        self.size
    }

    fn clear(&mut self) {
        self.size = 0;
        self.head = None;
    }
}

take(), as_mut() がやばいですね、コンパイラに怒られまくった。
ここまでの実装でスタックとしては利用できるはずですが、先頭以外の要素も見たいのでシーケンシャルアクセスのできるイテレータを実装していきます。

イテレータ

ここで出てくる関数名とかは std::collections::LinkedList - Rust に従っているはずです、多分。
まずはイテレータを表す構造体を宣言しましょう。

struct IntoIter<T>(List<T>);

struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

<'a> とかが出てきましたね。ライフタイムは完全に理解していないので言及しません、コンパイラが全てを教えてくれます。
リストからイテレータを取得する関数を実装します。

impl<T> List<T> {
    fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter {
            next: self.head.as_ref().map(|node| &**node),
        }
    }

    fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
        IterMut {
            next: self.head.as_mut().map(|node| &mut **node),
        }
    }
}

(&mut **node) がやばいですね、解説は最初に挙げた元ネタに書かれているので気になる人はそちらを読んでください。
さて、ここで Iterator trait を見てみましょう。

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

要素の型を表す Item と次の要素を指すイテレータを得る関数 next() が必要なようです、これも実装していきましょう。

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}

完成!

感想

ライフタイム全然分からない。コンパイラに言われるとおりに直したら動いたのでヨシ。
as_mut() と as_ref() が良く分かっていない気がするのでちゃんとドキュメント読みたいね。
やる気と時間があれば続きを書く予定です。

ところでこんな記事を書いている場合ではない。論文を、書こうね!