bobuhiro11's diary

ABC136-138

24 Aug 2019

いくつか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$とする。

領域ごとの点数の算出には、平面走査を使う。また、事前に座標は圧縮しておく必要がある。

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$が条件。 まず場合分けをする。

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


comments powered by Disqus < ABC135 ABC139-141 >