kwm_t

kwm_tのメモ

ABC-F略解(190-195)

ここら辺りからFがまた黄diffに戻る。
■191F - GCD or MIN
答えになるのはAの最小値以下かつ、適当に選んでgcdとなるもの全て。
gcdがxになる選び方があるかを考える。
xの倍数全てを拾ってきてgcdを取れば良い
これでxにならないならxの倍数全てが、x*pを因数に持つことになるのでxは作れない。

■192F - Potion
無理じゃない?と思った後に制約を眺めると
Σa<=xなので解けるのがわかる。
選ぶ個数cを固定する
dp[i][j][k]:=i番目まで考慮、j個を合計がmod cでkになるように選んだ場合の最大値とする。
O(n^4)になるが軽いので大丈夫。

■193F - Zebraness
縞々を最大にしたい<=>白白、黒々を最小にしたい
(1 == i+j%2)反転させる
白白、黒々を最大にしたい<=>縞々を最小にしたい
sに属する:白、tに属する:黒
とし最小カットを考えれば良い。
既に白黒が確定しているマスは、s,tに切れない辺で結べばいい

■194F - Digits Paradise in Hexadecimal
https://kyopro-memorial.hatenadiary.jp/entry/2021/03/07/172035
昔詳しめに書いただけあって覚えてる。
当時のコードを見たら一部配列外参照してるけど。

■195F - Coprime Present
制約を見るBとAの差は小さい。
すなわち、73より大きい素因数を共通で持つことはない。
既に選んだ素因数をbitでもちbitdpを行う。