2020-05-25

LaTeX.css を使ってみる

latex.now.sh 何も考えずに記事の冒頭に以下の二行を貼ったらページレイアウトが壊れた（それはそう）。ブログトップも一緒に壊れてしまうので（この記事を読み込むため）、一旦iframeで閉じ込める形に修正しました。

<link rel="stylesheet" href="https://latex.now.sh/style.css">
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>

ところで iframe の高さを調節する行儀の良い方法が分からない。

2020-04-24

自分用環境構築メモ

Ubuntu を入れてからやることリスト

思い出したらなにか追記するかも

初手

LANG=C xdg-user-dirs-gtk-update
timedatectl set-local-rtc 1

シェル

sudo apt install zsh
chsh

インストール

プログラミングまわり

sudo apt install build-essential git libboost-all-dev vim fonts-hack qemu-kvm
sudo apt install libopenblas-dev libgsl-dev

VS Code も入れておく

ツール

sudo apt install gnuplot
sudo apt install imagemagick
sudo apt install ffmpeg
sudo apt install xsel qrencode pdftk sox 
sudo apt install adobe-flashplugin
sudo snap install scrcpy

あと droidcam, discord, slack, zoom

LaTeX

sudo apt install texlive-lang-cjk texlive-lang-japanese texlive-fonts-recommended texlive-fonts-extra texlive-font-utils texlive-latex-recommended texlive-latex-extra texlive-science
sudo kanji-config-updmap-sys ipaex

ぶつりとか

sudo apt install quantum-espresso

XCrysDen と VESTA も

2020-04-24

C++で競技プログラミングをやるための環境構築

競プロ

Ubuntu 20.04 がリリースされましたね

これはなに

Ubuntu を入れて VSCode を使って C++ で競プロをやるための手順に関する雑なメモ

手順

詳細は後述

Ubuntu をインストール
ちょっと設定
もろもろインストール
VSCode の拡張機能とかを入れる
好みに合わせる
おしまい

1. Ubuntu のインストール

ここから好きなバージョンの iso イメージをダウンロード
iso からブータブル USB を作る
作った USB で PC を起動し、指示に従ってインストール

2. インストール後の設定

フォルダ名変更

（日本語でインストールした場合）次のコマンドでホームディレクトリ内のフォルダ名を英語にしておく。

LANG=C xdg-user-dirs-gtk-update

ドキュメントとかピクチャとかにファイルがいるとフォルダが残ってしまうので、最初にやる。これ以降の起動の際に日本語に戻すか聞かれるが、今後表示しないみたいなオプションを選べばもう聞かれなくなる。

時刻に関する設定

（ Windows とデュアルブートにしている場合）次のコマンドで Windows 側と時刻がずれるのを防ぐ。

timedatectl set-local-rtc 1

3. ソフトウェアのインストール

コンパイラなど

必要なものは以下のコマンドでだいたい揃うはず。

sudo apt install build-essential libboost-all-dev git

Ubuntu 20.04 の場合 gcc 9.3.0 が入りました（ 2020/04/24 現在）。

Visual Studio Code

ここから .deb をダウンロードしてインストールする。インストールは端末を開いてsudo apt install ****.debをすれば良い。

4. VS Code の設定

拡張機能として「 C/C++ 」を入れるだけで良さそう。日本語化したければ「 Japanese Language Pack for Visual Studio Code 」も入れる。

貼りたいライブラリはユーザースニペットに仕込んでおくと便利。

5. その他

シェルの変更・フォントの変更・キーバインドの設定などを適当にやって自分好みの環境にする。

たとえば

gsettings set org.gnome.desktop.interface clock-show-seconds true
gsettings set org.gnome.desktop.interface clock-show-weekday true

をすると上の時計に秒と曜日を表示させられる。おすすめ。

6. 書く

コードを書いて手元でコンパイル・実行ができることを確認して準備完了。

お疲れ様でした。

2020-04-21

湯取り法について

料理

湯取り法について解説します。米を食べられる状態にするもので、一般的な手法より高速だと言われています。

必要なもの

鍋　1 つ
ボウル　適当な容器で代用可
コンロ
ざる
水　たっぷり
米　食べたい分だけ

炊飯器不要

手順

米と水をボウルに入れてうるかす。洗米不要。
鍋に多めに入れた水を沸かす。電気ポットなどで事前に沸かしておいたお湯を利用すると時間を短縮できる。
水を切って米を鍋に投入。ここで、鍋の大きさと水量次第ではざるの上に米を入れてもよい。（ 5. が楽になる）
米がくっつかないように適当にかき混ぜつつ 7 分程度茹でる。米に若干芯が残る程度。
米をざるにあけて水分を切る。捨てるお湯は重湯として利用もできる。
米を鍋に戻し、十数秒（パチパチ音がするまで）加熱して水分を飛ばす。
火を止めて蓋をし、放置。5 分くらいで良さそう。

補足

パラパラ（パサパサ？）した感じになる。汁気のあるおかずをのせて食べると良い。

茹でる際に塩を入れることもあるらしい。ターメリックなどのスパイスを投入するとターメリックライスが出来ます。

タイ米など長粒種でも同様にできる。（というか本来はそっちがメインらしい？）

浸水時間を無視すると 15 分程度なので、速度的には炊飯器の高速炊飯に十分対抗できそう。（調理時間短縮を積極的に目指すなら、パックの米か早茹でパスタを使いましょう）

鍋にこびりつくのをなんとかしたい

2020-01-02

有限回アラート

はてなブログでの javascript を試してみる。そのうち消すかも。

<script type="text/javascript">
// コメントを外すとロード時に出る
//alert("ロード時に表示");

function alert_n(n){
    for(var i=1;i<=n;i++) alert(i + " / " + n + "回目");
}
</script>
<input type="button" value="5回表示" onclick="alert_n(5);">

2019-11-29

Segment tree を書く (3)

前々回ではセグ木に載せる演算を別途書くような形で抽象化しました。具体的には、前々回の実装例だと

template <typename T>
T segment_tree::op(T lhs, T rhs){
    // f は入れたい演算に相当
    return f(lhs, rhs);
}

を別途書く必要があるということです。

しかし、最近これは自分の好みではない気がしてきました。より良さそうな方法としては次のようなものが思い浮かびます。

型の情報を渡すのと同じ気持ちで、モノイドの情報をテンプレートパラメータに書いて渡す
- segment_tree<int, std::plus<int>, 0> st(N); のようにして使いたい
- T がリテラル型でないと使えなさそう
- 演算が $+$ ではない場合は自分で構造体か何か書くことになりそう
- だめそう
単位元や演算の情報も持ったモノイドの構造体を作って渡す
- segment_tree<monoid> st(N); のようにして使うことになりそう
- いちいちモノイドの情報を詰めた構造体を作るの、微妙な気がしませんか
  - 好みではないが、良い方法だとは思う
コンストラクタに演算と単位元の情報を渡す
- segment_tree<int> st([](auto x, auto y){ return x+y; }, 0, N); のようにして使いたい
- どのように渡した情報（特に演算）を保持しておくかは要検討

今の私には 3. が本命に見えます。以下 3. について詳細

持ち方

コンストラクタで渡したからにはメンバ変数として持つことになるのですが、問題はどの型を指定するかです。単位元の方は値と同じ T が迷わず使えますが、演算の方は検討の余地がありそうです。

コンストラクタの引数にラムダ式を直書きできる
遅くならない

あたりは満たして欲しいです。

候補

とりあえず思い浮かんだものだけ

テンプレートパラメータを追加して使う
std::function<T(T, T)>
関数ポインタ

検討

ラムダ式を直書きできるか

は多分出来なくて

auto func = [](T x, T y){ return f(x, y); };
segment_tree<T, decltype(func)> st(func, e, N);

のように書く必要がある。 2. と 3. なら

segment_tree<T> st([](T x, T y){ return f(x, y); }, e, N);

のように書ける。

速度

とりあえず以下の 2 通りで評価しました。

3 通りでセグ木を作って AOJの問題に投げてみる
演算部だけ抜き出したクラスを作って演算処理の所要時間を比較する
- 演算として適当なラムダ式を渡す
- 符号なし 64 bit 整数で $2N=2\times 10^7$ 個の乱数を前もって生成
- 2 つずつ、計 $N$ 回演算を呼ぶ。結果は適当な変数に足し上げておく

結果は以下の通り。

	1. テンプレート	2. std::function	3. 関数ポインタ
A.	0.02 sec	0.02 sec	0.02 sec
B. @手元環境	0.014 msec	0.028 msec	0.022 msec
B. @AtCoder コードテスト	0.014 msec	0.026 msec	0.023 msec
B. @Codeforces Custom Test	0.046 msec	0.102 msec	0.047 msec

実行速度は 1. > 3. > 2. の順に速いっぽい。std::functionのコドフォでの遅さが気になる。

結論

decltype(hoge)を書くのも面倒なので、気が変わるまでは関数ポインタを使うことになりそうです。

2019-11-29

Segment tree を書く (2)

競プロ

前回の続きです。今回はセグ木で必要になる配列の長さの話をします。

前提

前回の実装では

長さは 2 の冪に切り上げ

としていました。完全二分木になるので見通しが良くなりますね。このとき、最悪で*1長さ $4(N-1)$ の配列が必要になります（ $\exists k \in \mathbf{N}\ \mathrm{s.t.}\ N=2^k+1$ の場合）。

しかし、実は $N$ が 2 の冪ではない場合でもセグ木で確保する配列の長さは $2N$ で十分なことが知られています。

どうやるか

前回の実装例で n を 2 の冪に切り上げた値を len に代入している部分を削除する
len = n; を書く
おわり

// 9 行目
-        for(len = 1; len < n; len <<= 1);
+        len = n;

$N$ が 2 冪でなくとも 2 冪を仮定した場合と同じコードでうまく動いてくれます。嬉しいですね。

verify

問題は前回と同じです。

問題

提出コードれたと言える。算術符号の符号化には文字の出現頻度（出現回数）の計算と、その文字までの累積確率が必要である。そのため、区間和を効率的に計算可能なデータ構造の開発が必要であった。

フェニック木を使うことで、部分和を O ( log ⁡ n ) {\displaystyle O(\log n)} {\displaystyle O(\log n)} 回の演算で計算することを可能とした。また、最初の要素からの和である部分和だけでなく、任意の区間の和である区間和も同様に O ( log ⁡ n ) {\displaystyle O(\log n)} {\displaystyle O(\log n)} で計算可能とした。

通ってますね。

どうして

あとで加筆します。ゆるして

方針

添字 N から 2N-1 に 0 番目から N-1 番目を割り当てる。このとき、上の方にどの区間にも対応付かない（＝何を入れても壊れない）やつが出ることに注意して動作を追うと分かる。

*1: $N$ は十分大きいと思っている