bobuhiro11's diary

TP-Link Archer T3U AC1300をLinuxから使う

09 Nov 2019

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 の値を見ると、オンボードの子機側を優先していた(値が小さい)ので入れ替えた。

ip route
sudo nmcli con mod <connection name> ipv4.route-metric 599
sudo systemctl restart NetworkManager

追記: Fedora 30、31にアップデートしたあとも特に問題なかった。

sudo dkms status
# rtl88x2bu, 5.6.1, 5.3.6-100.fc29.x86_64, x86_64: installed
# rtl88x2bu, 5.6.1, 5.3.8-200.fc30.x86_64, x86_64: installed
# rtl88x2bu, 5.6.1, 5.3.8-300.fc31.x86_64, x86_64: installed

2019 越後湯沢 秋桜ハーフマラソン

29 Sep 2019

越後湯沢で開催された秋桜ハーフマラソンに参加してきた。 大会自体はすごいよかったけど、コースの半分あたりから胃の調子が悪くなり、 13kmでリタイヤという悔しい結果となった。 色々反省点があったので、記録として残しておく。

まず、そもそも食事のタイミングが悪かった。9時30分スタートで、8時あたりでおにぎりを食べた。 3時間前までに取るようにしたい。直前に口にいれるのであれば、ゼリー状のものにしたい。

6.7kmから15kmまで続く下り坂で飛ばしすぎた事も影響していると思う。 お腹が激しく上下して気持ち悪くなってしまった。 スタートから6.7kmまでの上り坂は走り方に気をつけていたが、それ以降については、なんとかなるだろうと考えていなかった。 加えて、腰にポーチを巻いていたので、お腹を圧迫していたのかもしれない。 塩飴を少量持っていただけなので、ポケットにいれておけば事足りていた。

前半の上下の坂でも貯金を作っておこうと、いつも以上に早めのペースで走っていたので、 バテてしまったんだろうな。

ただ、自分でリタイヤを決断できたのは唯一よかったことだった。 以前膝を故障してしまったときは、脚を引きずりながらも、無理して走っていて、 沿道で応援してくれた方からリタイヤを勧められた。

どうも消化不良な感じなので、どこかでリベンジしたい。


TCP技術入門 読書メモ

25 Sep 2019

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が一定数届いた場合

ABC139-141

20 Sep 2019

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$の要素が置かれていることになる。 右側に最大値がある場合と、左側に最大値がある場合、それぞれについて、組み合わせを計算して、 合算すればよい。最大値の位置については、setlower_boundで見つけた。

ABC #140 F - Many Slimes

貪欲な感じで、できるだけ体力が大きなスライムから作っていけばよい。 うーん、今回はE・F問題よりもD問題が難しく感じた。。

ABC #141 D - Powerful Discount Tickets

すべてのアイテムを優先度付きキューqに入れておく。 割引券の枚数だけ順番に取り出して、以下の操作を行う。

  • qから最も値段の高いアイテムを取り出す。
  • そのアイテムの値段を半分(切り捨て)にして、再度qに入れる。

ABC #141 E - Who Says a Pun?

長さlenについて、二分探索する。 ある長さについて、ローリングハッシュですべての部分文字列のハッシュ値を入れておき、mapなどで入れておく。 ハッシュ値が一致して、なおかつ重複がなければ、その長さでは条件を満たすことが分かる。

ABC #141 F - Xor Sum 3

各ビットごとに考える。 まず、$A_1 \oplus A_2 \oplus … \oplus A_N$ を計算しておき、 1が立っているビットについて、どのように色分けしても答えに影響しないので、 取り出しておく。取り出した結果、$A_1 \oplus A_2 \oplus … \oplus A_N = 0$の状態になる。 ここで、青色のXORを$X$、赤色のXORを$Y$とする。 $X \oplus Y = 0$なので、XORの性質から、$X = Y$となる。 なので、$A_i$から幾つか選んで、そのXORを最大化するような、選び方を見つけたい。 吐き出し法(連立1次方程式をといていくような感じ)で、上位のビットから見ていき、 1が立っている要素を pivot 行とみなして、他の要素とXORを取っていく。 結果、$X = Y = A_1 \oplus A_2 \oplus … A_N$となる。


ABC136-138

24 Aug 2019

いくつか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$について、計算すればよい。

$(1-(x-i)^{P-1})$のところは、フェルマーの小定理より、$x=i$のときだけ1となる。 法 P において、以下が成り立つ。

ABC #138 D - Ki

各ノードのカウンタ$x$に足しておき、その後に根から累積和っぽく葉までDFS(BFSでもよい)でカウンタを更新していけばよい。

ABC #138 E - Strings of Impurity

文字列$s$を無限に連携した文字列$s’$を考える。 $t$の各文字を前から見ていき、その文字が$s$のどこに現れていくかをDPの要領で計算していく。

ABC #138 F - Coincidenc

Youtubeの解説動画と同じ解法で解いた。 $L \leq X \leq Y \leq R$ と $Y \% X = Y \oplus X$が条件。 まず場合分けをする。

  • 1) $X = Y$ の場合
    • $Y \% X = Y \oplus X = 0$ なのでOK
  • 2) $X < Y$ の場合
    • 2A) 2進数で$X$と$Y$の桁数が同じ
      • $Y \oplus X = Y+X-2(Y\&X)$
      • $Y\%X = Y-X$ (なぜなら $X<Y<2X$ より $Y/X=1$なので)
      • つまり、$X = X \oplus Y$
      • ある桁において$X=1$で$Y=0$はNG(そのほかの3つの場合でOK)
    • 2B) 2進数で$X$と$Y$の桁数が同じ
      • NG($Y\%X$は1から始まり、MODは0から始まるため)
  • 3) $X > Y$の場合
    • 問題の対象外なので考えなくて良い

その後、桁DP dp[i][j][k][s] を埋めていく。

  • 上からi桁番目まで見た時
  • jはX>=Lが確定しているかどうか
  • kはY<=Rが確定しているかどうか
  • sは先頭ビットが既に現れたかどうか