KVM FORUM 2018 で発表されたTowards a more Scalable KVM Hypervisorについてのメモ。 [PATCH v8 0/4] KVM: X86: Add Paravirt TLB Shootdown ゲストOSはOSレベルの同期機構であるTLB shoot downやRCUの処理において、ホストOSのスケジューラの影響を受ける。ベアメタル環境であればすぐに完了する操作であっても、仮想環境上ではその遅延を無視することができなくなる。 TLB（Translatoin Lookaside buffer）は仮想メモリアドレスと物理メモリアドレスのマッピングをキャッシュするために使われる。あるCPUがそのマッピングを切り替えたとき、その以外のCPUでTLBをflushしなかればならない。これを TLB shoot down と呼ぶ。 モダンなOSでは、TLB shoot down はパフォーマンスクリティカルな箇所として位置づけされ、この処理によって遅延が発生しないようチューニングされている。TLBのflushはすぐさま完了するという前提で、IPI（Inter Processor Interrupt）で実装されている。Remote CPUのTLB flushの完了は busy wait で待っているため、ベアメタル環境とは相性が良い。一方で、仮想環境ではvCPUが別のゲストに横取りされたり、実行がブロックされたり、ということが起きるため、長時間にわたって busy wait が継続することになる。 この問題は、準仮想化TLB shoot down によって解決できる。準仮想化TLB shoot down では、動作していないvCPUに対する操作を遅延させておいて、次回そのvCPUが起動するときに、KVMがTLB flushを担当する。特にオーバコミットされた環境で顕著なパフォーマンス向上が見られる。 ゲストとホストどちらからも参照できるメモリ領域に「あるvCPUが preempt されたかどうか」を示すフラグを用意しておく。pv_mmu_ops.flush_tlb_others関数は、アクティブなvCPUに対してはIPI経由でTLB Flushの通知を送り、そうでないvCPUに対してはKVM_VCPU_FLUSH_TLBフラグを付与しておく。その後、KVMはKVM_VCPU_FLUSH_TLBフラグがついているvCPUを起動する際に、INVVPIDを発行する。VM数が増えるに従ってこのチューニングの効果が顕著に現れる。

一度Civilization VIを友人とやった結果、どうやらこのままだと勝てそうにもないので、ちょっと調べてみる。 このゲームは選択の連続なので、仕組みを知らずになあなあで進めてしまうと勝つのは難しそう。 あくまでも初心者が自分のために書いていくメモなのであしからず。 詳しく知りたい方は CIVILIZATION VI wiki を見てください。 まず、マップオプションから、グリッド、資源アイコン、算出アイコンを表示するよう設定しておく。 都市そのものを強化するリソースが、食料と生産力。食料を増やすことで人口が増え、生産力を増やすことで区域・建造物の生産につながる。生産力は、労働者が鉱山を作ることで得られる。ゴールド・科学力・文化力は、市場（商業ハブ区画）、図書館（キャンパス区画）、円形闘技場（劇場広場区画）から得られる。 序盤の戦闘に有利なアステカ、アメリカ、シュメール、ヌビア、ローマ、クリー、インカが、初心者に向いている。 初期配置に癖のあるヌビア、エジプト、マリ、ロシア、カナダ、イギリス、インドネシア、スペイン、ノルウェー、オランダ、フェニキア、マオリなどは難しい。また、宗教メインな文明や、特殊なプレイングが必要な文明も向いてない。 ドイツが扱いやすいそうに感じる。固有区域ハンザが単純に強い。区域はハンザ＞キャンパス＞商業ハブくらいで立てていく。 序盤は、斥候、労働者、戦士、開拓者で進めていく。 都市が川や湖に隣接していると住宅+3なのでよく吟味する。ユニットの中ではチャリオット（のちの戦車）、弓兵（のちの野戦砲）が強い。 丘陵地帯は生産力が強力なので、そこを狙って都市を作る。 都市を作った後は、市民管理で手動で人をどのタイルに配置するか決めることができるので、定期的に見直すと良い。 労働者はむやみに使わず、必要な時まで眠らせておけばよい。 市民+2の住宅が必要で、それを下回るとペナルティが発生して、都市の成長が妨げられる。 交易商は強力なので、作れるタイミングなら優先して作る。 太古の遺産はピラミッド、アポロン神殿が強い。 それ以降の時代では、ペトラ、コロッセオ、アルハンブラ宮殿、チチェン・イツァ、 グレート・ジンバブエ遺跡、紫禁城、ポタラ宮、アルセナーレ・ディ・ヴェネツィア、ビッグベンが強い。 戦争中は勝つまで兵の増強をやめない。相手も兵の生産に集中しているはずなので。 遠距離攻撃する場合は、移動力が1以上残っていれば攻撃可能なので、ヒットアウェイで戦う。 その他 最初期の探索は重要 都市で役割分担 都市数ペナルティがないので、単純に大量に都市を作ると強い 都市の人口は住宅数に制限されるため、食料よりも1人口あたりの生産力重視 3つの山岳があれば、キャンパス区画を作る 丘陵と鉱山で早期生産 遺産は奪う 高級資源は売りつける

提出したコード 解説を漁ってみると、どうやらアルファベットを適当に$K$回挿入したあとの 長さ$N+K$の文字列の中で、$S$の各文字の位置が固定されていると考えればうまくいくということだった。 そう考えると、あとは長さ$N+K$の文字列で$K$文字をどうやって挿入していくかだけを考えれば良い。 入力例1を使って考える。 S = “oof” N = len(“oof”) = 3 K = 5 例えば、位置1に’o’、位置3に’o’、位置5に’f’をおいてみる。 また、長さ$N+K$の文字列を先頭から見たときに"oof"がはじめて登場するのがこれらの位置ということにする（条件1）。 このとき、位置0には’o’以外の25種のアルファベットを挿入できる。 逆に、位置0に’o’を挿入するのは、条件1を満たさないのでダメ。 同様にして、位置2にも’o’以外の25種のアルファベットを挿入できる。 また、位置4にも’f’以外の25種のアルファベットを挿入できる。 位置6と7に関しては、特に制約がないので、26種のアルファベットを挿入できる。 まとめると、‘f’の位置$j$が$N-1 … N+K-1$まで移動したとき、 2つの’o’が取れる位置の組み合わせは${}_j C _{N-1}$ となる。 また、25種のアルファベットを挿入する位置は$j - (N-1) $個、 26種のアルファベットを挿入する位置は$(N+K-1)$個、となる。 つまり答えは$\sum_{j=N-1}^{N+K-1} {}_j C _{N-1} \cdot 25^{j-(N-1)} \cdot 26^{(N+K-1)-j}$となる。

提出したコード 解いた後の振り返りが大事だと思う。 2次元平面上で、スタート位置からゴール位置までの最短経路を求める。 ただし、平面上にはいくつかブロックがあり、そのセルは通れない。 さらに、一回の移動で、同一方向に$1 … K$の任意の個数のセルを進めることができる。 頂点は$(y, x, dir)$として、グラフを考えて、ダイクストラ法で最短経路を算出すればよい。 頂点$(y, x, dir)$からの遷移は以下の通り。 移動にかかるコストを$K$倍して考えるとよい。 方向を変えるときは、$K$で切り上げ。 $cost(y, x, new dir) \leftarrow ((cost(y, x, dir) + K -1) / K) * K$ 同方向に移動。$dir$は上下左右の4種類。$dx$、$dy$は方向ごとの差分。 $cost(y + dy, x + dx, dir) \leftarrow cost(y, x, dir) + 1$ 計算量は$O(HW log(HW))$かな。

EDPC を全部埋めた。 雑多なメモなので、きれいに解法をまとめたものではない。 W - intervals $dp_i$ を、いくつかのビットに1が立っているとき、最も右側にある1が$i$であるときの最終スコアとする。 ここで、$dp_i$は$ max_{j=0 … i-1} dp_j$ と $i$ 文字目を1にしたときに得られるスコアの和で求められる。 $block_i$を右端$r$が$i$であるブロックの集合として、 $dp_i$を計算する際に、 $i$文字目を1にしたときに得られるスコアとして $block_i$ を足しこむ。 $block_i$ は $i$ 未満の $dp$ にも影響するため、遅延セグメントツリーを使って、 影響する $dp$ に区間加算を行う。 最終的な答えは $max_{i=0 … N} dp_i$ となる。 はじめて、遅延セグメントツリーを使った。復習しておく。 Z - Frog 3 $dp_i$ を足場 $i$ に到達するまでの最小コストする。 初期値は $dp_0 = 0$。 まずは素直にDPの更新式を作ると以下のようになる。 $$ \begin{aligned} dp_i &= min_{j=0 … i-1} (dp_j + (h_j - h_i)^2 + C) \\ &= min_{j=0 … i-1} (dp_j + h_j^2 - 2 h_i h_j + h_i^2 + C) \\ &= min_{j=0 … i-1} (-2 h_i h_j + dp_j + h_j^2) + h_i^2 + C \\ \end{aligned} $$...

Linux Observability with BPFを読んだので、メモしておく。 今月、Brendan Gregg氏のBPF本も出るので、 それも読みたいな。 BPFを使うことで、カーネルのイベントをフックして安全にコードを実行できる そのコードがシステムを破壊したりクラッシュさせたりすることが無いよう、BPF側で検証してくれる カーネルモジュールと異なり、BPFプログラムはカーネル再コンパイルの必要がない BPFコードが検証された後、BPFバイトコードは機械命令にJITされる BPFプログラムは、bpf syscall によってBPF VMへとロードされる 2014年前半にAlexei Starovoitov氏がeBPFを導入した 過去のBPFでは2つの32bit registerのみが使えたが、eBPFでは10個の64bit registerまで使える 2014年6月にはeBPFはユーザスペースにも拡張された BPFプログラムタイプ：トレーシングとネットワーキングに大きく分類できる Socket Filter：カーネルに最初に入ったプログラムタイプ。観測目的のみ Kprobe：kprobe ハンドラとしてBPFプログラムを動かす。関数に入るときと出る時が、それぞれSEC(kprobe/sys_exec)とSEC(kretprobe/sys_exec)に対応する Tracepoint：事前にカーネル側で定義されたtracepointに対してBPFプログラムを動かす。/sys/kernel/debug/tracing/eventsで一覧を確認できる XDP：パケット着信時に、早い段階でBPFプログラムを動かす。 Perf：perf eventに対してBPFプログラムを動かす。perfがデータを吐き出す度にBPFプログラムが実行される Cgroup Socket：そのcgroup内のすべてのプロセスにアタッチされる Socket Option：Facebookはデータセンター内の接続において、RTOs（recovery time objectives）の制御に、これを使っている。 Socket Map：BPFでロードバランサを実装するときに使う。CilliumやFacebook Katranはこれを使っている。 BFP Vefirier CVE-2017-16995 のように、過去BFPをバイパスしてカーネルメモリをバイパスできる脆弱性があった DFSで、そのプログラムが終了すること、危険なコードパスが存在しないことを検証する 無限ループを弾くために、すべてのループを禁止している。ループ許可については、本書を書いている時点では、まだ提案の段階。 命令数は4096に制限されている bpf syscall の log_*を設定すれば、検証結果を確認できる BPFプログラムは tail calls によって、他のBPFプログラムを呼び出すことができる 呼び出し時にすべてのコンテキストは失われるので、何らかの方法で情報を共有する必要がある BPFマップ 直接bpf syscall でBPFマップを作成することができる bpf_map_createヘルパ関数を使うのが簡単 bpf_map_update_elem のシグネチャは、カーネル側bpf/bpf_helpers.hとユーザ側tools/lib/bpf/bpf.hで異なるので注意する エラー番号でsteerror(errno)で文字列にすると便利 bpf_map_get_next_keyはそのほかのヘルパ関数と違って、ユーザ側でのみ使えるので注意する array, hash, cgroup storage maps については、スピンロックがあるので、並行アクセス可能 array map は要素数だけ事前にメモリが確保されて、ゼロで初期化される。グローバルな変数確保のために使う？ LRUハッシュやLRM（Longest Prefix Match）Trie mapもある Linux 4....

Kubernetes完全ガイド を読んだので、メモを残しておく。 普段、意識していなかったコマンドや仕組みをまとめておく。 サイズの小さなイメージを作りたければ scratch や apline をベースにする ENTRYPOINT と CMD が設定されているときは、$ENTRYPOINT $CMD が実行されるようなイメージ マルチステージビルド：ビルド専用のコンテナでだけ処理を行い、成果物を実行専用コンテナにコピーすることが出来る CNCF ではプロジェクトの成熟度を「Graduated」「Incubating」「Sandbox」の3段階に設定している オンプレで構築する場合はAWS や GCP でのインスタンスサイズが目安になる Flannel：ノード間でオーバーレイネットワークを構成する Docker, Inc. が提供するkubernetes のプレイグラウンドがある kubernetes のリソースは大きくわけて5種類 Workloads, Discoverty &LB, Config & Storage, Cluser, Metadata 特に Metadata はクラスタ内で他のリソースを操作するためのリソース（HorizontalPodAutoscaler など） Deployment/CronJob > ReplicationController/ReplicaSet/DaemonSet/StatefulSet/Job > Pod という階層構造がある kubectl get all：ほぼすべてのリソースを一覧取得 Stateful Set：0番目の Pod が最初に作られ、最後に削除される kubeconfig clusters、users、contexts の3種類を設定（どれも複数登録可能） context や namespace の切り替えが冗長であれば、kubectx や kubens を使うと良いかも kube-ps1 を使うと cluster と namespace をプロンプトに出力できる source <(kubectl completion bash)などで zsh/bash の補完機能を使える コンウェイの法則：組織図と、マニフェストの管理方法やマイクロサービスのアーキテクチャが似ている kubectl scale：ReplicaSet, ReplicationController, Deployment, StatefulSet, Job, CronJob でスケーリング kubectl apply --prune：実行時にマニフェストから削除されたリソースを検知して、自動で削除 CI/CDでは、単純にこのコマンドを投げ続けるだけでよい kubectl apply --prune --all：クラスタ内に存在するすべてのマニフェストを読み込ませないと、漏れがあったリソースが消えてしまい危険 kubectl apply --prune -l system=a：基本的にラベルを指定しておく デバッグ kubectl cp：コンテナとローカルマシンの間でファイル転送 kubectl port-forward：コンテナとローカルマシンの間でポート転送 kubectl -v：デバッグ出力 サービスディスカバリ spec....

USB接続の無線LAN子機 TP-Link Archer T3U AC1300 を、Thinkpad X1 Carbon 2015（Fedora release 29 (Twenty Nine)、linux 5.3.6-100.fc29.x86_64）から使えるようにしたので手順を残しておく。 # 公式HPではドライバが配布されていなかったので rtl88x2bu を使った git clone https://github.com/cilynx/rtl88x2bu cd rtl88x2bu/ git rev-parse HEAD # 962cd6b1660d3dae996f0bde545f641372c28e12 VER=$(sed -n 's/\PACKAGE_VERSION="\(.*\)"/\1/p' dkms.conf) sudo rsync -rvhP ./ /usr/src/rtl88x2bu-${VER} # /usr/src/<module_name>_<module_version> に移動させて dkms で管理する sudo dkms add -m rtl88x2bu -v ${VER} sudo dkms build -m rtl88x2bu -v ${VER} sudo dkms install -m rtl88x2bu -v ${VER} sudo dkms status sudo modprobe 88x2bu 2種類の子機（オンボードの子機とTP-Linkの子機）を同一のネットワークにつなぐと、metric によって優先順位が決まる。 metric の値を見ると、オンボードの子機側を優先していた（値が小さい）ので入れ替えた。...

越後湯沢で開催された秋桜ハーフマラソンに参加してきた。 大会自体はすごいよかったけど、コースの半分あたりから胃の調子が悪くなり、 13kmでリタイヤという悔しい結果となった。 色々反省点があったので、記録として残しておく。 まず、そもそも食事のタイミングが悪かった。9時30分スタートで、8時あたりでおにぎりを食べた。 3時間前までに取るようにしたい。直前に口にいれるのであれば、ゼリー状のものにしたい。 6.7kmから15kmまで続く下り坂で飛ばしすぎた事も影響していると思う。 お腹が激しく上下して気持ち悪くなってしまった。 スタートから6.7kmまでの上り坂は走り方に気をつけていたが、それ以降については、なんとかなるだろうと考えていなかった。 加えて、腰にポーチを巻いていたので、お腹を圧迫していたのかもしれない。 塩飴を少量持っていただけなので、ポケットにいれておけば事足りていた。 前半の上下の坂でも貯金を作っておこうと、いつも以上に早めのペースで走っていたので、 バテてしまったんだろうな。 ただ、自分でリタイヤを決断できたのは唯一よかったことだった。 以前膝を故障してしまったときは、脚を引きずりながらも、無理して走っていて、 沿道で応援してくれた方からリタイヤを勧められた。 どうも消化不良な感じなので、どこかでリベンジしたい。

TCP技術入門を読んだので、 気になったところを雑多な感じだがメモしておく。まず前半部分。 ネットワークまわりの話は聞いたことはあるが、使わずに忘れてしまっていることが多い。 1章 TCP入門 伝送効率 Ethernetフレーム 1500 バイト、TCPヘッダが 60 バイト、IPヘッダが20バイトとする アプリケーションが使えるのは 1420 バイト Ethernetヘッダ 14 バイト、FCS（Frame Check Sequence）4バイトを考慮すると、伝送効率は$1420/(1500+18) \times 100=93.5 %$ UDP 実際にUDPがやっていることは、転送先へデータを送ることと、チェックサムの確認だけ TCPはユニキャストだが、UDPはユニキャストに加えて、マルチキャストとブロードキャストにも対応 シーケンス番号とタイムスタンプを追加したRTP（Real-time Transport Protocol）や、それに加えて再送機能も追加したRUDP（Reliable user Datagram Protocol）もある QUIC はUDPベースで、それを使ったHTTP/3（HTTP-over-QUIC）。コネクション確立とTLS確立を同時に実施。 TCP ACKのシーケンス番号は、次に受信したい番号。当該セグメントが届くまで、同じシーケンス番号を返送し続ける。 フロー制御：受信側のバッファ溢れを防ぐために、送信データ量を調整すること。TCPでは一度に送信可能なサイズをウィンドウと呼ぶ。特に、送信側がもつパラメータを swnd （send window）と表記する。対して、受信側はrwnd（recieve wndoe）。 TCP輻輳制御 Loss-based：データの消失から輻輳を判断 Delay-based：RTTから輻輳を判断 特定の用途向けプロトコル RUDP（Reliable User Datagram Protocol）：UDPベースで、シーケンス番号、ACK、再送、フロー制御を加えたもの DCCP（Datagram Congestion Control Protocol）：UDPにおける輻輳緩和が目的 2章 TCP/IPの変遷 ARPNETなどではネットワークが信頼性を担保していたが、TCP/IPは各ノードがその役割を担う Nagleアルゴリズム：TCP/IPの送出パケット数削減の方法。輻輳制御アルゴリズムのはしり Windows95（OSR2以降）にTCP/IPが搭載されたことが普及のきっかけになった IEEE 802.11ではMACレイヤーでCSMA/CAを採用 3章 TCPとデータ転送 MTUは、イーサネットは1500バイト、PPPoEでは1492バイト、ATMは9180バイト。ただ最近は任意に設定できる MSS（Maximum Segment Size）：TCPが区切る最大パケット長さ MTU（1500バイト）= IPヘッダ（20バイト）+ TCPヘッダ（20~60バイト）+ アプリケーションデータ（MSS以下） MSSは、TCPのペイロードのみ MTUは、TCPのペイロードからTCPヘッダやIPヘッダまで。Ethernetヘッダは含まない ACK（Acknoledgement Number）：確認応答番号。次に送ってほしいシーケンス番号 コントロールフラグ RST（Reset the connection）：コネクションを強制切断。使われていないポート番号に送るなど、異常があれば有効になる CWR（Congestion Window Reduced）：輻輳ウィンドウの減少を通知する。ECNとセットで使われる ECE（ECN echo）：輻輳が発生したら通知 ウィンドウ制御：一度に送信可能なウィンドウサイズ $swnd$ を調整 $swnd = min(rwnd, cwnd)$ フロー制御：受信側から送信側に送信量を通知して、調整する。受信側は、送信側へ受信可能なバッファ量$rnwd$を通知 輻輳制御：輻輳ウィンドウ $cwnd$ を調整 スロースタート 通信開始時点で、ACKを受け取るたびに $cwnd$ を1セグメントずつ増やしていく $cwnd = cwnd + mss$ 指数的に $cwnd$ が拡大 輻輳回避 スロースタートを行うと、再び再送が起きやすい 再送が起きた時の $cwnd$ の半分 $cwnd/2$を閾値として、それを越えた時は更新を緩やかにする $cwnd = cwnd + mss/cwnd$ RTTごとに線形に増える 高速リカバリー 輻輳のたびに、スロースタート→輻輳回避という挙動をするのは効率が悪い 重複ACKを契機とする Recoで採用 セグメントの消失 再送タイマーがタイムアウトした場合 重複ACKが一定数届いた場合

ABC #139 D - ModSum $p_1=N, p_2=1, p_3=2, … , p_N=N-1$ とすると、$m_1=0, m_2=1, m_3=2, … , m_N=N-1$ となる。 なので、答えは$1, 2, 3, …, N-1$の総和。 ABC #139 E - League $i$と$j$の試合を頂点$(i,j)$と表す。ただし、$i$と$j$をひっくり返したものは同一視する。 各頂点は、直前にすべき試合数$prev_{(i,j)}$と、その次に実行可能な試合の一覧$next_{(i,j)}$をもつ。 そして、$prev_{(i,j)} = 0$である試合を見つけるたびに、貪欲にその試合をしていくよう、シミュレーションする。 ここで、ある試合をするたびに、その次の頂点の$prev_{(p,q)}$をデクリメントすることに注意する。 ABC #139 F - Engines あらかじめ各ベクトルを偏角ソートしておき、 720度分になるようにそのベクトルをつなげておく（後々、楽になる）。 そうすると、この問題の答えは、連続したベクトルの和であることが分かる。 すべてのベクトルについて、以下の操作を行う。 あるベクトルを始まりとして、連続したベクトルを足していき、長さが最長となるものを見つける。 ABC #140 D - Fce Produces Unhappiness まず、幸福でない人に注目して、それをどれだけ減らせるかに注目する。 たとえば、$RLLLLRRRRRLLRRLLRRR$から幸福でない人を抜きだすと、$RL…….RL..RL…R$となる。 連続する人は同時に操作できるので、$RLRLRLR$と考えてよい。 そして、$RLRLRLR$ -> $RLRLR$ -> $RLR$ -> $RR$ -> （空）のように操作を繰り返せば良い。 ABC #140 E - Second Sum Nから1まで、順番に見ていく。 ある要素$i$について見た時、左右には$i+1, i+2, … , N$の要素が置かれていることになる。 右側に最大値がある場合と、左側に最大値がある場合、それぞれについて、組み合わせを計算して、 合算すればよい。最大値の位置については、setのlower_boundで見つけた。...

いくつかABCの問題を解いたけど、ブログに記録するのを忘れていた。 まとめて書いておく。 ABC #136 D - Gathering Children 一度RLの組に入ると抜け出せない。 偶数距離を移動させて、RLの組にくっ付ける。 ABC #136 E - Max GCD ソートしておいて、小さい値は0に、大きい値は答え$d$に近づける。 前と後の両方向から、累積和を求めておく。 ABC #136 F - Enclosed Points ある点$x$がふくまれるような矩形の数は、その上下左右の4つの領域からそれぞれいくつの点を選ぶかによって計算できる。領域ごとに含まれる点の数を$A, B, C, D$とする。 点$x$を含まない場合は、それぞれの領域から点を取るかどうかで16個に場合分けして考える 点$x$を含む場合は単純に$ABCD$ 領域ごとの点数の算出には、平面走査を使う。また、事前に座標は圧縮しておく必要がある。 ABC #137 D - Summer Vacation アルバイトはどれも一日で終るためコストは変わらず、単純に支払日だけが異なるだけ。 アルバイトを報酬の大きい順に見ていって、できるだけ後ろの日程から埋めていく。 ABC #137 E - Coins Respawn まず、DFSを使って、始点と終点どちらからも到達可能な頂点の集合$S$を求める。 あとはコストに$-1$を掛けて、ベルマンフォード法を適用して、最長経路を求める。 もし、集合$S$内の頂点が、閉路に含まれていたら、$-1$を返す。 単純に、ベルマンフォード法で閉路を見つけるだけでは不十分なことに注意する。 ABC #137 F - Polynomial Construction フェルマーの小定理を使う。頻出テクニックだと思うので、復習しておきたい。 $a = {0,0,…,0}$の$i$番目を1にした$a’ = {0,0,..,1,…,0}$を考える。 そうすると、$a$を使った$f$と、$a’$を使った$f’$は以下のような関係になる。 これをすべての1が立っている$i$について、計算すればよい。 $$ f’(x) = f(x) + (1- (x-i)^{P-1}) $$...

今回はE問題がかなり難しかった。F問題より難しく感じた。 Youtubeの解説放送を聞いて、やっとわかってきた。 自分用のメモなので、日本語が雑になっている。。 ABC #135 D - Digits Parade dp[i][j]をi桁目まで見た時に、あまりがjとなる場合の数として、求めていく。 ABC #135 E - Golf 事前に、X>=0,Y>=0にしておく 1) X+Yが奇数 かつ Kが偶数 -1を返す。 どうやっても奇数番地にはたどり着けない 2) X+Y>K n=ceil(X+Y/K)として、X+Y と nK の偶奇が異ればn++とする。余剰 nK-X-Y のために、冗長な経路を作る。 ここで、X=0 だと、序盤の移動において、マンハッタン距離が正しくないので、swap(X,Y)しておく（もちろん出力時には戻す）。 +(X,Y) | Y (0,0)+ - t | | t = (nK-X-Y)/2 |-----| X 3)X+Y<K 3-1) X+Yが偶数 n=2となる。それ以降の計算は、2) と同じ。 +(X,Y) | Y (0,0)+ - t | | t = (2K-X-Y)/2 |-----| X 3-2) X+Yが奇数（ 1) の条件よりKも奇数） n=3になる。これは思いつかない。この場合のみ、X, Y両方向に冗長な経路を取る必要がある。 p +----+ (X,Y) | Y (0,0)+ - t | | t = K-X |-----|----| X p = (K+X-Y)/2 4) X+Y==K 一発で行ける。...

前回の続き。Atcoder Beginner Contest #130 ~ #133を解いたので、まとめておく。 まだまだ解説なしでは解けない。。 ABC #130 F - Minimum Bounding Box dp[i][j]をi,j番目が部分共通文字列となるときの組み合わせ数とする。 更新式もメモ化しておくと高速に計算できる。 ABC #131 F - Must Be Rectangular! (x,y)座標を2部グラフとみなす。 グラフに置き換えて考えることでスムーズに解ける。 ABC #132 F - Small Products N/xが同じ値になるxを同じグループとみなして、グループごとに計算を進める。 DPを圧縮していくイメージ。 ABC #133 F - Colorful Tree 木構造の頂点間の距離はLCA（最小共通祖先）を使うことで求めることができる。 実装解説は蟻本にまとまっている。 あらかじめクエリを先読みしておき、必要な頂点と色を抽出しておく。 DFSしつつ必要な値を埋めていく。

Atcoder Beginner Contest #116 ~ #129のCD問題をすべて解いた。 また、#126 ~ #129についてはEF問題が追加されているので、すべて解いた。 F問題は、解説PDF、解説Youtube、解説ブログを参考にした。 ABC #126 F - XOR Matching https://atcoder.jp/contests/abc126/submissions/5909511 M=3とすると、長さ2^(M+1)の数列は、{0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7}のような要素をもつ。 このとき、{<0,1,...,7からKを除いた昇順の数列> K <7,6,...,0>からKを除いた降順の数列 K}とすれば良い。 K以外の要素について：間にはKだけが残ることになるので、条件を満す Kについて：間には <7,6,...,0>からKを除いた降順の数列 が残る。XORをとるとKになるので条件を満たす。 ABC #127 F - Absolute Minima https://atcoder.jp/contests/abc127/submissions/5930963 中央値が最小値となる性質を利用する。中央値が２つあるときには、左側を採用する。 中央値は、小さいほうと大きいほうをそれぞれ優先度付きキューで管理すると便利。 解説動画では、同一のaを二度入れてキュー間で交換するテクニックを使っていたが、 ナイーブに一度だけ入れる方法でも問題ない。 キューが片方に偏らないように、整理する必要がある。 更新クエリのとき、aが最小値を取る区間のなかに含まれていれば、最小値の更新はない。 一方、含まれていなければ、最小値を取る区間のなかで、最も近い点との差分を、最小値に追加する。 ABC #128 F - Frog Jump https://atcoder.jp/contests/abc128/submissions/5921198 A、Bをそのまま扱うのではなく、C=A-B と k=何度戻りが発生するか という変数に置き換えて考える。 Cを固定すると、kが増えるにつれて、蓮を多く踏めるようになる。 同一の蓮を二度以上通るかどうかは、単純にsetで管理した。 ABC #129 F - Takahashi’s Basics in Education and Learning https://atcoder.jp/contests/abc129/submissions/5945816 難しかった。まず、等差数列の各要素が何桁なのかによって、分割する。たとえば、A=3、B=4であれば、3,7と11,15,19に分けて考える。分割後は、sum_i=0^(l-1) (A+Bi)*10^k^(l-i-1)を求めることになる。 A sum_i=0^(l-1) 10^k^iとB sum_i=0^(l-1) i*10^k^(l-i-1)にわけて、計算する。 どちらも漸化式に変換して解く（コード中のf,gに対応）。 解説動画を見るのがおすすめ。

O’REILLYの「Go言語による並行処理」を読んので、自分用にメモを残しておく。 また、折角なのでhttps://godoc.org/github.com/bobuhiro11/gostream に、本文のアイデアをもとに並行処理に便利な関数群をまとめた。 競合状態は二つ以上の操作を正しい順番で実行しなければいけない状況で、プログラムがその順番を保証していないときに発生する。 論的な正当性を目指すべきで、Sleep関数を挟むような方法では解決しない。 デッドロックが起きる必要条件は、Coffman条件として知られている。 筆者の意見では、ライブロックはデッドロックよりも発見がむずかしい。プログラムの外部からリソース使用率を観測しても検出できないから。 並行処理に関わる関数には、適切にコメントをつける。誰が並行処理を担っているか、どのような並行処理のプリミティブに対応しているか、誰が同期処理を担っているか、を記述する。関数シグネチャでは不十分。 並行性（concurrent）はコードの性質、並列性（parallel）は実行中のプログラムの性質を指す。 Tony hoare「Communicationg Sequence Process」をもとに、Go言語の並行処理プリミティブは設計された。 CSPのほかにも、伝統的なメモリアクセス同期のコードも書ける。syncパッケージ中にまとめられている。 ただ、Goプログラミングスタイルでは、高水準の技術を使うのが推奨されている。ある瞬間に、ただ一つのゴルーチンのみが特定のデータを扱うようにすべき。 メモリ共有のかわりに、チャネルによる通信を行うべき。 メモリサイズに応じて、生成可能なゴルーチン数を概算できる。本文中の例によると、RAM 8GBで数百万のゴルーチンを生成できる。 sync.WaitGroupのAddの呼び出しはできる限り監視対象のゴルーチンの直前に書くのが良い。 デッドロックを避けるために、Mutexを使う時はUnlockの呼び出しをdeferの中で行う。 RWMutexはMutexよりも高機能。書き込みのロックを取っているものがいなければ、複数の読み込みロックを取得できる。 バッファ付きチャネルは早すぎる最適化になりやすい。デッドロックが見えなくなってしまう。 チャネルの所有権のスコープは小さくする。 Goランタイムはcase文全体に対して疑似乱数による一様選択をしている。 空select文 select {}は永遠にブロックする。 情報をたった一つの並行プロセスからのみ得られることを確実にする考え方に、拘束がある。 // チャネルへの書き込みスコープは、関数内にレキシカルに拘束される。 func owner() <-chan int { c := make(chan int) go runc() { defer close(c) for i:=0; i<10; i++ { c <- i } } return c } システムにキューを導入するのは便利だが、早すぎる最適化になってしまう。キュー導入の利点は、ステージの実行時間が減ることはなく、ステージのブロック状態の時間が減ること。 キューでは、リトルの法則でスループットを予測できる。 contextを関数の第一引数として渡す。よく使われるデータへの参照の保管には使わない。 ハートビートは必ずしも必要ではない。長時間稼働させる場合には有用。

BGP in the Data Centerの前半部分を読んだので、気になったところをメモしておく。CLOSネットワークをどのように設計するか、BGPをどのように運用するかについて、実践的な内容が書かれていた。普段触っていない領域なので、勘違いもあると思う。 1. Introduction to Data Center Networks ローカルネットワーク内のサーバ間通信をEast-Westトラフィック、ローカルネットワークと外部のネットワークの間の通信をNorth-Southトラフィックと呼ぶ。 大量のケーブルを管理する必要があるので、巨大なネットワークの管理者は、それぞれ管理技術を持っている。Prescriptive Topology Manager（PTM）というOSSもある。 同一のスイッチで巨大なネットワークを構成しておくと、故障した場合でも、単純に取り替えるだけで復旧できる。日々の運用コストについて考えておくことが大事。 CLOSネットワークを外部と接続するために、Border PodあるいはBorder Leavesを配置する。データセンタ内で使われているルーティングプロトコルは外部とは分離しておく。もし、Border PodやBordor Leavesを配置できない場合には、すべてのSpinesを外部と接続させる（Spineの対称性を保つため）。 iBGPに比較し、eBGPは理解やデプロイが容易なので、eBGPを採用するのが良い。歴史的な観点から、eBGPのほうが完成度の高い実装が多い。 2. How BGP Has Been Adapted to the Data Center PublicなASNは使わないほうが良い。オペレータを混乱させてしまったり、万が一外部に漏れた時にBGPハイジャックになってしまったりといった危険性がある。 2バイトのASNを4バイトへ拡張すると、およそ95,000,000個のprivate ASNを利用できる。 単純にすべてのBGPスピーカにユニークなASNを割り当てると、Path Huntingに苦しむことになる。 あるPrefixへの到達性をもつノードがダウンしたときに、その情報が収束するまでに時間がかかってしまう。これは、BGPのベストパス選択の性質に起因する。 真に到達不可能なのか、それとも別の経路でもって到達できるのかの区別ができない。 密に接続したCLOSトポロジでは、顕著な問題となる。 Path Hunting問題への対応として、以下のASN割り当てモデルがある。ループを検出できるので、必要以上にメッセージを送らなくて済む。ただし、Route Summarizationができないことに注意する。 すべてのToRはユニークなASN LeafはPodごとにユニークなASN。Pod内では同一のASN Spineは共通のASN OSPFやIS-ISはBest path選択のメトリクスを1つだけ。一方、BGPではそれが8つある。 Wise Lip Lovers Apply oral medication Every Night. Wight, LOCAL PREFERENCE, Locally originated, ASPATH, ORIGIN, MED, eBGP over iBGP, NextHop IGP Cost これら8つが等しければ、Equal Costと考えられ、Multipath Selectionできる。 ASPATHの比較については、長さに加えて要素がすべて等しければ、Equal Costとみなされる。 例えば、同一のPrefixが異なるASから届いた時には、Multi Pathとはならない。 ただし、bestpath -as-path multipath-relaxの設定を行うと、ASPATH長のみで（内容には触れずに）比較するよう設定できる。 タイマ設定を変更することで、CLOSトポロジにおける収束を早くする必要がある。ふつうはプロバイダ向けを想定して、安定性を第一にデフォルトが設定されていることが多いので、適宜設定する。 Advertisement Interval：このInterval内に含まれるメッセージは統合されて、送り出される。eBGPの場合、デフォルト30秒だが、0秒に設定すれば良い。 Keepalive and hold Timers：ある周期でkeepaliveメッセージをピアと交換する。Hold timeの期間内に、keepaliveを受け取らなかった場合は、ノードダウンと判定される。ケーブル障害の検知のために、BFD(Bidirectional forwarding Detectiion)を導入している場合でも、BGPプロセス自体のエラー検出のために、これらのタイマを調整する必要がある。おすすめは、3秒ごとのKeepaliveと9秒間のhold timersである。 Connect Timer：ピアの接続が切れた時、再接続までの待ち時間。 3....

京都マラソンから、2週間が経過し、2019.3.3（日）東京マラソンに参加した。 こちらも初応募で初参加となった。 スタート前からゴール後まで、雨が振り続いていた。 特に、スタート前に30分以上、屋根のない中、待っているのがつらかった。 後半は、半分くらい歩いていて、ペースはぐだぐだだったが、無事完走できてよかった。 これで、今冬のマラソン大会参加は一旦終わりにする。 次の東京マラソン参加がいつになるかわからないが、来年も応募しようかな。

2019.2.17（日）、京都マラソン2019に参加した。 初応募で初参加となった。 各地点での通過時間をメモしておく。ハーフ以降の距離でも、長い距離を歩くことはなかった。 スポーツ羊羹、ゼリー、塩飴など補給できるものを多く持っていったので、スタミナ切れがなかったのだろう。 他のマラソン大会だと7時間制限が多い気がするが、 京都マラソンは6時間制限なのでちょっときびしい。 特に、前半はスタートで出遅れたり坂があったりと遅れがちだが、 関門の制限時間がきびしくため、ギリギリで通過していた。 2週間後に、東京マラソンを控えている。そっちも頑張りたい。

Atcoder Beginner Contest #1 ~ #115 の CD 問題をすべて解いた。 C問題は7割くらい、D問題は半分くらい自分の力で解くことができた。 特殊なアルゴリズムを使うことはあまりなく、ちゃんと考察できれば、解けるんじゃないかなと思う。 役立ちそうなことを残しておく。 Example の最初の1~2個は手で解いてみる。特に、幾何の問題は実際に書いてみる。 複数のパラメータを総当たりするときはどちらか一方のパラメータを固定して考える。 あらかじめソートや累積和を計算しておく。 その他、Youtube の解説動画が充実していて、かなり助けになった。