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