はじめに The eXpress data path: fast programmable packet processing in the operating system kernel 1 を読んだ。 この文章はほとんどこの論文をもとに書いたが、一部ニュース記事を引用している。 eBPF／XDPが流行っているということは、BCC、bpftrace、Facebook Katran、Cloudflare Gatebot などeBPF／XDPを使うプロジェクトのGithub Star数から感じ取れる。 eBPF／XDPには、特殊なハードウェア・ソフトウェアに依存せず、 カーネルの仕掛けとして高速パケット処理を実現できるという強力なメリットがある。 一方であまり弱点を主張するような記事は見当たらないので、実際のところどうなのか感触を知りたい。 XDPを使うとNICデバイスドライバのコンテキストで、eBPF Verifilerの制約はありつつも、 比較的自由にパケット処理を実現できる。 また、成熟したLinuxのネットワークスタックと共存しつつ、1コアで24Mppsという高速なパケット処理を実現できる。 XDPプログラムは、eBPFの制約のもとC言語で記述することができ、clangでELFバイナリにコンパイルする。 XDPの競合としてカーネルバイパスなDPDKがある。両者の特徴は以下のとおり。 DPDK： カーネルバイパスによってコンテキストスイッチを避け高速化を図る コアを専有する（特定のコアでCPU 100%に張り付かせてポーリング） スループットとレイテンシどちらの観点で見てもDPDKのほうが優れている ネットワークスタックを再実装する必要がある XDP： 専用コアが不要（電力面などで有利） 容易にロード・アンロードできる 名前空間などカーネルの機能に強く依存するコンテナ環境の普及で、XDPの重要度が増しているように感じる やはりカーネルネットワークスタックと共存できるというメリットが強い アーキテクチャ パケット着信のたびに、デバイスドライバのフックポイントでXDPプログラムが実行される。 このフックポイントは、デバイスドライバの処理の中でも初期に位置する（sk_buff の割り当て前）。 XDPプログラムは、ヘッダのパース、eBPFマップの読み書き、ヘルパ関数（FIBのルックアップなど）の呼び出しを経て、 最終的にパケットをどこに送り出すか決定する。 送り先については、XDPプログラムの終了コードで制御することができ、 ドロップさせる、同インターフェイスに送り返す、他インターフェイスに転送する、AF_XDPとしてユーザプログラムに送る、 通常のネットワークスタックに送る、から選択する。 2つ以上のXDPプログラムを同インターフェイスに紐付けたい場合には tail call として処理を引き渡すことができる。 外部のシステムとデータのやり取りをするために、eBPF Mapが用意されている。 eBPF Verifilerが厳しくチェックしているので、必ずeBPF Mapを使うことになりそうだ。 出典：The eXpress data path: fast programmable packet processing in the operating system kernel...

提出コード 2つの要素$a_l$と$a_r$をSwapしたとき、$a_r > a_l$であれば、 ある範囲ではPrefixSumが増加し、それ以外では変化しないということになる。 つまり、単純に固定されていない要素を降順に並べ替えればよい。 $0 \sim l-1$の範囲ではPrefixSumの変化なし $l \sim r-1$の範囲ではPrefixSumが$+(a_r-a_l)$増加する $r \sim n-1$の範囲ではPrefixSumの変化なし

提出コード 縦方向、横方向にそれぞれどれだけ移動する必要があるか。 縦方向 単純に下に行くだけなので$k$回の移動となる。 横方向 $a_x$を、マス$x$まで移動したときに元々どこからきたのかという情報とする。 つまり、1段目の$a_x$からスタートして、$k$段目の$x$まで移動したということになる。 各$k$ごとに、移動できない領域のいずれかのマスからスタートして、$b_i+1$に移動すると考えればよい。 答えは、$\underset{x}{min} (x-a_x) + k$となる。 以下は、入力例1における$a_x$の遷移を図示したもの。

提出コード 解説放送を見て道筋は理解できたが、そこからが長かった。 比較的実装が重い問題だと思う。 答えの回文LRを文字列Lと文字列Rに分けて考える。どちらも空文字列で初期化しておく。 $s_i$を追加するときは、Lの右側に追加するか、あるいはRの左側に追加する。 何度か$s_i$を追加して、L="abcde"、R="cba" となったとする。 このとき部分文字列 abc はすでに回文の条件を満たすのでL="abc"、R=""と見なしてもよいということになる。 なので、LとRの組 (L, R) を頂点として、ダイクストラ法を適用していけばよい。 LやRとして現れるのは$s_i$のPrefixとSuffixのみなので、今回の制約では十分間に合う。 頂点 (L, R) からの遷移については、すべての$s_i$について、$s_i$をLあるいはRに追加したときに部分的に回文の条件を満たすかどうかをチェックする。条件を満たす場合には、次の頂点に遷移できる。

提出コード 赤diffだった。問題文を読むと手を付けれそうな気がしたけど、そんなに簡単じゃなかった。 まず、$O(N^3)$のDPを考えて、それをもとに計算量を削減していくというアプローチを取る。 $i = 2, 5, 8, 11, \dots$ のように3文字おきに見ていく。 dp[i][x][y]を$i$番目まで見たとき、直前の2つの文字が$x$、$y$であるときの最大スコアとする。 a = v[i], b = v[i+1], c = v[i+2] として、パターン分けしていく。 スコア +1となる場合。どの3つでスコアを増やすか考える。 A) $a = b = c$ の場合、すべての$(x, y)$の組について dp[i+3][x][y] <= dp[x][y] となるので、代わりに答えに+1しておく。$O(1)$ B) $a = b = x$の場合、すべての$y$について dp[i+3][c][y] <= max(dp[i][a][*]) + 1 とする。$O(N)$ C) $a = x = y$の場合、dp[i+3][b][c] <= dp[i][a][a] + 1とする。$O(N)$ スコア +1とならない場合。どの2つを残すか考える。 D) $x$、$y$ を残す場合、dp[i+3][x][y] <= dp[i][x][y]なので何もしない。$O(1)$ E) $x$、$a$ を残す場合、すべての$x$について dp[i+3][x][a] <= dp[i][x][*]とする。$O(N)$...

提出コード もしも $n \ge 4$ かつ $m \ge 4$ の場合には、どうやっても条件A（縦横の長さがともに偶数の正方形内に含まれる1の数が奇数）を満たすことができない。 例えば、$2 \times 2$の正方形が条件Aを満たすとき、その正方形を4つ連結すると、 その和は偶数になってしまう。つまり、$4 \times 4$の正方形では条件Aを満たすことができない。 それ以外の場合には、何度か操作することで必ず条件Aを満たすことができる。 最小の操作回数はDPを使って解くことができる。 $dp_{i,bit}$を、$i$番目の行まで見たときに、$i$番目のビット列が$bit$であるときの 最小の操作回数とする。 更新式は以下の通り。ただし、$bit$と$nbit$と間で条件Aを満たすことを確認する。 $$ \begin{aligned} dp_{i+1,nbit} \Leftarrow dp_{i, bit} + \sum_{j=0}^{m-1} ((nbit » j) \& 1) \oplus a_{i+1,j} \end{aligned} $$

十分に枯れていてあまりトラブルになることは無いけれど、今後も使い続けられる技術なので、 その挙動を知っておくことに意味はあると思う。 NICの完全仮想化・準仮想化 おさらい。完全仮想化は、ゲスト自身が仮想環境で動作していることを認識できないような仮想化のこと。 ホストは、ゲストが利用するデバイスの挙動をすべて模倣する必要がある。 デバイスの模倣のために、大量のトラップが発生し、CPUがホスト側の処理に使われてしまう。 また、デバイスのエミュレーションをホスト側ユーザプロセスで行う場合には、 スケジューリング待ちによる遅延も発生してしまう。 一方、準仮想化では、ゲスト自身が仮想環境で動作していることを認識した上で、 ホストと協力してパフォーマンスを向上の図る。 virtio は準仮想化専用のデバイスドライバによって、仮想的なデバイスを操作する。 アーキテクチャ フロントエンドドライバとバックエンドドライバを、vringが繋ぐ構成になっている。 フロントエンドドライバ ゲスト側で動作する。ゲストOSが発行したIOをvringを経由して、バックエンドドライバへ送る。 バックエンドドライバ ホスト側で動作する。vring経由で受け取ったIOを、物理デバイスへ送る。 https://www.cs.cmu.edu/~412/lectures/Virtio_2015-10-14.pdf Virtio 仕様 SAMLやebXMLなどを標準化している団体 OASIS が Virtual I/O Device (VIRTIO) Version 1.1 として仕様をまとめている。 コールバックや各種データ構造の仕様を決めている。 Virtqueue 実際のIOを担当する部分で、ゲスト物理メモリの一部をホスト側と共有することで、 双方向での読み書きを実現できる。 また、双方向に通知を送るための仕組みも持っており、ホスト側へはMMIO経由で、 ゲスト側へは割り込みを使って通知を送る。 disable_cdやenable_cbといった関数で、割り込み抑制をもう一方へ伝えることができる。 例えば、ゲスト側ドライバで一定期間の間は割り込みが不要な場合には、 その旨を disable_cd でホスト側へ伝える。 通知を送る際には kick を呼ぶ。 struct virtqueue_ops { int (*add_buf)(struct virtqueue *vq, struct scatterlist sg[], unsigned int out_num, unsigned int in_num, void *data); void (*kick)(struct virtqueue *vq); void *(*get_buf)(struct virtqueue *vq, unsigned int *len); void (*disable_cb)(struct virtqueue *vq); bool (*enable_cb)(struct virtqueue *vq); }; https://elixir....

Ubiquiti Networks社のルータ EdgeRouter X （ER-X）を数年前に購入したものの放置したままだったので、 今回 L2 スイッチとして使ってみた。 ER-X上ではDebianベースのOSで動いているため、Prometheus用に Node exporter のような監視プログラムを使うことができる。 Prometheus自体はRaspberry Pi上で動かした。 ElastiFlowも動かしたかったが、Raspberry Piのスペックでは厳しそうだった。 Prometheus と Grafana の導入 Raspberry PiにPrometheusとGrafnaをインストールする。 Prometheusはメトリクスを収集するために、GrafanaはPrometheusで収集したメトリクスをウェブUIから確認するために使う。 wget -q -O - https://packages.grafana.com/gpg.key | sudo apt-key add - echo "deb https://packages.grafana.com/oss/deb stable main" | sudo tee /etc/apt/sources.list.d/grafana.list apt install prometheus grafana -y sudo systemctl start prometheus sudo systemctl start grafana-server Node exporter の導入 ER-XにNode exporterをインストールする。 CPU、メモリ、ディスク、ネットワークに関連するメトリクスを自動で収集してくれる。 curl -L https://github.com/prometheus/node_exporter/releases/download/v1.0.1/node_exporter-1.0.1.linux-mipsle.tar.gz -o node_exporter.tar.gz tar xf ./node_exporter.tar.gz sudo mv ....

提出したコード 文字列 $t$ が与えられるので、$t$ の循環左シフト後と循環右シフト後の文字列を等しくしたい。 $t$からいくつか文字を取り除いてこの条件を満たすときに、取り除く最小の文字数は？ $n$ を $t$ の文字列長として、その偶奇で分けて考える。 $n$ が奇数の場合 $t = t_1 t_2 t_3 t_4 t_5$ を例とする。 巡回左シフト $ t_2 t_3 t_4 t_5 t_1$ と巡回右シフト $t_5 t_1 t_2 t_3 t_4$ を等しくしたい。 つまり、すべての文字を等しくする必要がある。 $n$ が偶数の場合 $t = t_1 t_2 t_3 t_4$ を例とする。 巡回左シフト $t_2 t_3 t_4 t_1$ と巡回右シフト $t_4 t_1 t_2 t_3$ を等しくしたい。 つまり、偶数番目はすべて同じ文字であって、かつ奇数番目もすべて同じ文字でないといけない。 解法 いくつかの文字を取り除いた後の文字列の先頭2文字について全探索をする。 先頭2文字が同じ場合、先頭2文字$aa$の後に何文字か$a \dots a$が続けばよい。 違う場合は、先頭2文字$ab$の後に$ababab \dots ab$が続けばよい。

QEMU/KVM上で https://github.com/kelseyhightower/kubernetes-the-hard-wayを試してみたので、ログを残しておく。 元々の文章では、GCPを前提としているが、今回は手元のQEMU/KVM上で構築した。 バージョン一覧 kubernetes-the-hard-way bf2850974e19c118d04fdc0809ce2ae8a0026a27 Kubernetes 1.12.0 containerd Container Runtime 1.2.0-rc.0 gVisor 50c283b9f56bb7200938d9e207355f05f79f0d17 CNI Container Networking 0.6.0 etcd v3.3.9 CoreDNS v1.2.2 1. 事前準備 VMイメージを取得して、起動するまで。 # VMイメージの準備 $ http_dir=http://ftp.jaist.ac.jp/pub/Linux/Fedora/releases/30/Cloud/x86_64/images $ wget $http_dir/Fedora-Cloud-Base-30-1.2.x86_64.qcow2 $ virt-customize -a /var/lib/libvirt/images/Fedora-Cloud-Base-30-1.2.x86_64.qcow2 \ --run-command 'yum remove cloud-init* -y' \ --root-password password:root $ cd /var/lib/libvirt/images/ $ for i in 0 1 2 ; do \ sudo cp ./Fedora-Cloud-Base-30-1.2.x86_64.qcow2 controller-$i.qcow2; \ sudo cp ./Fedora-Cloud-Base-30-1.2.x86_64.qcow2 worker-$i.qcow2; \ done # VM起動 $ for name in controller-0 controller-1 controller-2 worker-0 worker-1 worker-2 do sudo virt-install --name=$name --virt-type kvm --graphics none \ --disk /var/lib/libvirt/images/$name....

提出したコード 整数$a \ge 2$が与えられるので、$gcd(d_1+d_2,a)=1$を満たすような組$(d_1,d_2)$を求めたい。 ただし、$d_1 \ge 2$かつ$d_2 \ge 2$。 これを$n$個回繰り返す。 まず $a = {p_1}^{k_1} \cdot {p_2}^{k_2} \cdots {p_m}^{k_m}$ のように素因数分解を行う。 もし $m = 1$あるいは$a$が素数の場合には、答えは$(-1,-1)$。 $m \ge 2$の場合には、$(p_1, p_2 \cdot p_3 \cdots p_m)$が答えとなる。 なぜこれが答えでよいのか見ていく。 「$d_1 + d_2$がいかなる素因数$p_i$に対しても割り切れないこと」が言えればよい。 まず、「$d1 + d2$ が $p1$ で割り切れない」ことが正しいのか考えてみる。 $d1 \equiv 0, d2 \not \equiv 0 (mod \ p_1) $ より、$d1 + d2 \not \equiv 0 (mod \ p_1)$ となる。 続いて、「$d1 + d2$ は $p_i (2 \le i \le m)$ で割り切れない」ことが正しいのか考えてみる。 $d1 \not \equiv 0, d2 \equiv 0 (mod \ p_i) $ より、$d1 + d2 \not \equiv 0 (mod \ p_i)$ となる。...

提出したコード 木において「連結成分の数 = 頂点数 - 辺の数」で求められることに注目する。 直感的に、頂点が増えると連結成分の数が1増え、辺の数が増えると連結成分の数が1減るという感じで理解できる。 $f(L, R)$もこれで求められる。 $$ \begin{aligned} &f(L, R) \\ &= 区間[L \ R]に含まれる点の数 \\ &- 両端が区間[L \ R]に含まれる辺の数 \\ \end{aligned} $$ これをLとRの全通りで求めて総和をとればよい。 頂点数と辺の数はそれぞれ独立に求めていけばよい。 $$ \begin{aligned} &\sum_{L,R} f(L,R) \\ &= \sum_{L,R} 区間[L \ R]に含まれる頂点の数 \\ &- \sum_{L,R} 両端が区間[L \ R]に含まれる辺の数 \\ &= V - E \end{aligned} $$ 以下のように図示してみると、ある頂点$i$は全体で$(i+1)(N-i)$回現れるので、すべての$i$でこれの総和を取って$V$とすればよい。 同様にある辺$(u, v)$は全体で$(u+1)(N-v)$回現れるので、すべての辺について総和を取って$E$とする。 $V-E$が答えとなる。

提出したコード コンテスト後追加されたテストケース after_contest01.txt でコケた。 それ以外は自力で通ったので考察の詰めが甘かった。 まず、（A）答えが負となる場合と（B）答えが非負となる場合で場合分けをする。 （A）の場合には、絶対値の小さい順に貪欲にとればよい。（B）の場合を考えていく。まず、キューを2つ用意しておく。 非負な値を降順にソートしたもの（例：9 6 5 2 1 0 0） 負な値を昇順にソートしたもの（例：-8 -7 -3 2） 単純に、負数同士の積は正という性質を使う。 $K$が2個以上残っている場合には、2つのキューからそれぞれ2つの値を取り出して、大小比較をする。 例えば、$9 \cdot 6 = 54 < -8 \cdot -7 = 56$ であれば、負数のキューから2つ値を取り出せばよい。 一方で、非負なキューのほうが大きい場合には、非負のキューから1つ値を取り出せばよい。 繰り返しになるが、非負なキューから取り出す場合には、1つの値だけでよいことに注意する。 https://twitter.com/shirakia/status/1279773457413074944で例が言及されている。after_contest01.txtもこのケースに該当しそう。 そのあとは、非負なキューからとる場合は1つずつ、負なキューからとる場合は2つずつのペアとして、取り出していけばよい。 （B）の計算途中で、どうしても答えを正数にすることができない場合には、（A）の結果を答えとする。

提出したコード 前提知識として、Nimというゲームであることを知っておくと良い。Nimには必勝法があり、すべての山の石の数 $A_i$ についてXORをとり、その結果が0以外であれば、その手番の人が最適な動きを取れば必ず勝つ。 必勝状態であるXOR != 0で手番が回ってきたとき、ある山からある数の石をうまく取り除くと、XOR = 0の状態に遷移できる。 逆に、XOR = 0の状態からは、どんな選び方をしても、必ずXOR != 0 の状態（必勝状態）に遷移してしまう。 ターンの経過に伴って石の数の合計は減っていくので、必ずゲームは終わる。 Grundy数というらしい。 これをふまえて、考察を進める。「1番目の山から0個以上$A_1$個未満の石を2番目の山に移すことで …」とあるので、先頭二つの山についてのみ考えればよいことがわかる。なので、これ以降$A=A_1$、$B=A_2$、$X = A_3 \oplus A_4 \oplus \cdots \oplus A_N$とする。また、“移す"という操作を$A$を$a$、$B$を$b$に変更すると言い換える。そうすると、以下の条件を満たしつつ、できるだけ$a$を大きくすればよい（“移す"石の数が最小）ということになる。 $$ a + b = A + B = S \ a \oplus b = X \ 1 \leq a \leq A \ $$ これは桁DPによって解くことができる。$dp_{i,j,k}$を、下から$i$桁目まで見たときの$a$の最大値とする。 ただし、一つ上の桁に対して繰り上がりがある場合は$j=1$、$i$桁目まで見たときに$a$が$A$を上回っていれば$k=1$とする。 50桁くらいまで見れば十分。 提出コードにコメントをつけておく。初期値は以下の通り。 rep(a, 2) { ull b = a ^ (X & 1); // b は a から決まる ull carry = a & b; ull _sum = a ^ b; if (_sum !...

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....