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

29 Sep 2019

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

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

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

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

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

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

TCP技術入門読書メモ

25 Sep 2019

#network

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

#atcoder

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$の総和。

$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 #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

#atcoder

いくつか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})$

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

$x^{P-1}= \begin{cases} 0 & (x = 0) \\ 1 & (x \neq 0) \end{cases}$

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は先頭ビットが既に現れたかどうか

ABC135

03 Aug 2019

#atcoder

今回は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`

一発で行ける。

ABC #135 F - Strings of Eternity

ローリングハッシュで文字列の比較をO(1)で行えるようにしておく。他のアルゴリズムでも良いと思う。あらかじめSを充分に大きくしておく。 UnionFindを用意しておき、 Sのi番目とTがマッチして、なおかつ S の i+T.size() 番目とTがマッチしているときは、 iとi+T.size()に対して、Union処理を行う。 UnionFind全体で、グループの要素数の最大値が答えとなる。

Previous Page: 1 of 22 Next

1章 TCP入門

2章 TCP/IPの変遷

3章 TCPとデータ転送

1) X+Yが奇数 かつ Kが偶数

2) X+Y>K

3)X+Y<K

3-1) X+Yが偶数

3-2) X+Yが奇数（ 1) の条件よりKも奇数）

4) X+Y==K

1) X+Yが奇数かつ Kが偶数

2) `X+Y>K`

3)`X+Y<K`

3-1) `X+Y`が偶数

3-2) `X+Y`が奇数（ 1) の条件よりKも奇数）

4) `X+Y==K`