三井住友信託銀行プログラミングコンテスト2019 C問題の解答。なぜかdpによる解ばかり見るので普通の全探索による方法を書き留めておく。
問題
AtCoder 商店では、以下の 6 種類の品物が 1000000 個ずつ売られています。
1 個 100 円のおにぎり
1 個 101 円のサンドイッチ
1 個 102 円のクッキー
1 個 103 円のケーキ
1 個 104 円の飴
1 個 105 円のパソコン
高橋君は、合計価格がちょうど X 円となるような買い物をしたいです。そのような買い方が存在するか判定してください。ただし、消費税は考えないものとします。
考察
品物の呼び名を価格の安い順にa,b,...,fとする。たとえばaは100円、fは105円。
6種類の品物それぞれの個数(0-10^6)に関して素朴に全探索していては到底間に合わない。全探索の範囲を削れないか考える。
この問題で求められているのは、上手い買い方の存在についてのyes/noであり、解の列挙ではない。したがって、全探索の範囲は解が存在するときにそのうちの1つ検出するのに十分な広さを確保できればよい。
品物をたくさん買ったとして、その合計額Xを大量のaと少量のb-fで再構成することを考える。aで吸収できない端数は、fを使って吸収するとにする。題意の条件下では品物が売り切れになることはないから、いくらでも偏った買い方をしてよい。
b5=505=a4+f
c5=510=a3+2f
d5=515=a2+3f
e5=520=a+4f
f100=10500=a105
これより、aを山のように使うことを許せば、高々4個のb-eと、高々99個のfでどんな買い物の値段も再現できると分かる。b-fの5品の購入個数が定まればaの必要購入数は自動的に定まるので、全探索範囲はb-fだけでよい。すなわち、5555100通りの全探索で済む。かくして余裕で間に合った。
蛇足: 着想
初歩的な線形代数。
a = (100,0),
b = (100,1),
...
f = (100,5)
のような$R^2$内の6つのベクトルと思えば、線形独立なのは高々2つなのだから、少なくとも4つに関しては他2つによる端的な表記が可能で、その際の線形和の係数はたぶん非負整数にとれるだろう(勘)。b,c,d,e を a,f で表したのはまさにそれ。独立成分として(a,f)を選んだのはこの線形和が書きやすそうだったから。
あとは a,f を元の設定通り一次元量として見てやれば、やはり同じ理屈で一方を他方の定数倍で書ける。最初から一次元量として見なして似たような議論をすることもできなくはないが、それだと係数の膨らみ具合がよろしくなさそうだったので避けた。
実装
# define rep(i, a, n) for (int i = a; i < n; ++i)
typedef long long ll;
int main() {
ll x;
cin >> x;
int ans = 0;
rep(b, 0, 5) rep(c, 0, 5) rep(d, 0, 5) rep(e, 0, 5) rep(f, 0, 100) {
ll resd = x - (b * 101 + c * 102 + d * 103 + e * 104 + f * 105);
if (resd >= 0 && resd % 100 == 0) {
ans = 1;
break;
}
}
cout << ans << endl;
}