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

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に対応）。 解説動画を見るのがおすすめ。