ABC136-138

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

1. $X = Y$ の場合
- $Y % X = Y \oplus X = 0$ なのでOK
1. $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から始まるため）
1. $X > Y$の場合
- 問題の対象外なので考えなくて良い

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

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