bobuhiro11's diary

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全体で、グループの要素数の最大値が答えとなる。

ABC EF問題を埋めた（続き）

15 Jul 2019
[atcoder]

前回の続き。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しつつ必要な値を埋めていく。

ABC EF問題を埋めた

16 Jun 2019
[atcoder]

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

Atcoder ProblemsのUser Page

Go言語による並行処理 読書メモ

22 Apr 2019
[go]

O’REILLYの「Go言語による並行処理」を読んので、自分用にメモを残しておく。 また、折角なのでhttps://godoc.org/github.com/nmi/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 読書メモ

21 Mar 2019
[network]

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

BGP in the Data Center

  • 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. Bulding an Automatable BGP Configuration

  • bgp router-idはIPアドレスにしておくのが良い。
  • 広報したいprefixをstaticに設定するよりも、connected、kernel、ospf、bgp、ripなどのprotocolからrouteを引き継くとよい。
  • ただし、不正なアドレスをまちがって広報する可能性があるので、routing policyの設定が必要になる。
    • prefix equalよりもprefix belongsのほうが管理が楽。
  • また、routing policyはふつうroute-mapで設定される。
# routing policyの例
ACCEPT_DC_LOCAL(prefix)
{
  if prefix belongs to 10.1.0.0/16 then accept
  else if (10.0.254.0/24 contains prefix and subnet equals 32) then accept
  else reject}
}