bobuhiro11's diary

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

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

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を関数の第一引数として渡す。よく使われるデータへの参照の保管には使わない。
  • ハートビートは必ずしも必要ではない。長時間稼働させる場合には有用。