7K12 blog

猫でも分かるアルゴリズム解説

AGC017 B - Moderate Differences

f:id:tkr987:20210805010414p:plain

  • 足し算と引き算は順序関係ないので足し算と引き算の回数に着目して探索できる

f:id:tkr987:20210805054854p:plain
https://atcoder.jp/contests/agc017/submissions/24762083

ABCD が  10^9 なので N の線形処理と予想する。例えば A=10 で C=1, D=5 のとき+すると区間 [11, 15] まで表現できる。更に-すると区間 [6, 14] が表現できる。ここで、足し算や引き算は順序関係ないので±の回数だけに着目して探索する方針とし、±の回数で探索するために文字式で表現する。
k回プラスしてN-k回マイナスするとき最終的に表現できる区間 [ \: kC-(N-k)D, \: kD-(N-k)C \: ] となる。
図のように区間内は全て表現できる(遷移できる)ことに留意すると
rep(i, 0, N) if (i * C - (N - 1 - i) * D <= B - A && B - A <= i * D - (N - 1 - i) * C) aout("YES");
で判定できることが分かる。

感想: こういう典型に慣れて自力ACできるようになりたい