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 の高さを調節する行儀の良い方法が分からない。
自分用環境構築メモ
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 も
C++で競技プログラミングをやるための環境構築
Ubuntu 20.04 がリリースされましたね
これはなに
Ubuntu を入れて VSCode を使って C++ で競プロをやるための手順に関する雑なメモ
手順
詳細は後述
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. 書く
コードを書いて手元でコンパイル・実行ができることを確認して準備完了。
お疲れ様でした。
湯取り法について
湯取り法について解説します。 米を食べられる状態にするもので、一般的な手法より高速だと言われています。
必要なもの
- 鍋 1 つ
- ボウル 適当な容器で代用可
- コンロ
- ざる
- 水 たっぷり
- 米 食べたい分だけ
炊飯器不要
手順
- 米と水をボウルに入れてうるかす。洗米不要。
- 鍋に多めに入れた水を沸かす。電気ポットなどで事前に沸かしておいたお湯を利用すると時間を短縮できる。
- 水を切って米を鍋に投入。ここで、鍋の大きさと水量次第ではざるの上に米を入れてもよい。( 5. が楽になる)
- 米がくっつかないように適当にかき混ぜつつ 7 分程度茹でる。米に若干芯が残る程度。
- 米をざるにあけて水分を切る。捨てるお湯は重湯として利用もできる。
- 米を鍋に戻し、十数秒(パチパチ音がするまで)加熱して水分を飛ばす。
- 火を止めて蓋をし、放置。5 分くらいで良さそう。
補足
パラパラ(パサパサ?)した感じになる。汁気のあるおかずをのせて食べると良い。
茹でる際に塩を入れることもあるらしい。ターメリックなどのスパイスを投入するとターメリックライスが出来ます。
タイ米など長粒種でも同様にできる。(というか本来はそっちがメインらしい?)
浸水時間を無視すると 15 分程度なので、速度的には炊飯器の高速炊飯に十分対抗できそう。 (調理時間短縮を積極的に目指すなら、パックの米か早茹でパスタを使いましょう)
鍋にこびりつくのをなんとかしたい
有限回アラート
はてなブログでの 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);">
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 整数で 個の乱数を前もって生成
- 2 つずつ、計 回演算を呼ぶ。結果は適当な変数に足し上げておく
結果は以下の通り。
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)
を書くのも面倒なので、気が変わるまでは関数ポインタを使うことになりそうです。
Segment tree を書く (2)
前回の続きです。 今回はセグ木で必要になる配列の長さの話をします。
前提
前回の実装では
- 長さは 2 の冪に切り上げ
としていました。完全二分木になるので見通しが良くなりますね。 このとき、最悪で*1長さ の配列が必要になります( の場合)。
しかし、実は が 2 の冪ではない場合でもセグ木で確保する配列の長さは で十分なことが知られています。
どうやるか
- 前回の実装例で
n
を 2 の冪に切り上げた値をlen
に代入している部分を削除する len = n;
を書く- おわり
// 9 行目 - for(len = 1; len < n; len <<= 1); + len = 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: は十分大きいと思っている