はじめに
何となく分かったつもりで回答を暗記していた自分へ、、
頑張ってるな、偉いぞ。まだまだ だけどな(笑)
自分なりに嚙み砕いて自分へ解説してみます。
問題: ABC195-B
O(N)解法
以下、入力例の赤枠で早速 混乱されたのではないだろうか？
確かに 120g * 8個 + 130g * 8個 = 2000g なので答えは 16個。
しかし、他のアプローチとして、
入力例1 のように 125g * 16個 == 2000g とも言える。
プログラムを組み立てる上で、どちらが簡単だろうか。
入力例1の方法でも入力例2 と同等の結果を得られないか
確認しなかったのが敗因かもしれない
打開策
いや、責めているわけではない、次回以降、試せばよいと思う。
他にも改善ポイントがある。
例えば、問題文の以下の赤文字を忘れてしまった場合だ。
ココを忘れると、なんとかピッタリ W となる重さの組み合わせを探そうと、
以下のように複雑に捉えてしまう。
120g * 8個 + 130g * 8個 = 2000g なので答えは 16個
問題文を読み返そう。みかんの重さは小数点でもよいのだ。
だから入力例 1 のように以下のスタンスで OK.
↓みかんの重さは小数点の可能性あり
125g * 16個 == 2000g
じゃあ、さっそく for 文で = W となる値を探そう!!... でもちょっと落ち着こう。
具体的な値を求めて OK と判断する？？でも、どうやって。。。。
例えば、A * n <= W <= B * n だったとしよう。
n 個を for 文で回してあげれば、 (n個) * (みかんの重さ) =W となる
組み合わせが何処かに必ず居るのでは？？？
補足
唐突だったかもしれない。
もう少し補足をさせて欲しい。
引き続き 入力例2 を引用して考えてみよう。
A = 120g , B = 150g の場合、みかんの重さは以下のようなバリエーションが考えられる
↓A ↓B
120g , 121g, 122g, 123g, 124g, 125g.........150g
※話を簡単にするために 1g でインクリメントしている
更に、みかんを、それぞれ n 個準備したとする。
↓A * n ↓B * n
120g * n , 121g * n , 122g * n , 123g * n , 124g * n , 125g * n.........150g * n
では、n 個とは具体的には何個だろうか？
A が 1g なら W max 1000000g なので 1000000 個と言える。
A が 1000g なら、、っと考えられるが、まぁ、みかんは最低 1 個は要るだろう。
つまり min 1 <= n <= max 1000000 と考えては如何だろうか。
例を交えてみる。
↓A*n ↓B*n
120g , 121g, 122g, 123g, 124g, 125g.........150g
↓A*n ↓B*n
1200g , 1210g, 1220g, 1230g, 1240g, 1250g.........1500g
如何だろう。
for 文で n 個を 1 ~ 1000000 と変化させた際に
A * n <= W <= B * n ならば、具体的な重さ(ここでは 125g)を求めなくても、
どこかの重さの みかん が n 個で W になっていると判断できないだろうか？
だって、整数でも、少数でも何でも使って良いんでしょ？？(笑)
実装
#include <iostream>
using namespace std;
int main() {
int A, B, W; cin >> A >> B >> W;
W = W * 1000;
int cmax = 0, cmin = 1000000;
for (int n = 1; n <= 1000000; n++) {
if (A * n <= W && W <= B * n) {
cmax = max(cmax, n);
cmin = min(cmin, n);
}
}
if (cmax==0)// cmax が 0 ってことは上記に該当が無かったと判断できる。
cout << "UNSATISFIABLE";
else
cout << cmin << " " << cmax;
//while (1) {}
return 0;
}
O(1)解法
個数が最大/最小となる、それぞれのケースを考察してみよう。
最大値(cmax: count max)
条件1: W%A == 0 の時、cmax = W/A
最小の A を n 個 用意し、
A * n = W となるならば、みかんは最大となる。
条件2: W%A != 0 の時、cmax = W/A
W%A < A なので、A は最大 (W/A -2) 個となります。
上記に ( A+( (W%A)/2) ) x2 を加算すれば W%A の補填が可能です。
以上から個数で考えると、結果的に W/A は変わりません。
最小値(cmin: count min)
条件3: W%B == 0 の時、cmin = W/B
最小の B を n 個 用意し、
B * n = W となるならば、みかんは最小となる。
条件4: W%B != 0 の時、cmin = W/B+1
W%B < B なので、B は最大 (W/B -1) 個となります。
上記に ( A'+( (W%B)/2) ) x2 を加算すれば W%B の補填が可能です。
以上から個数で考えると、結果的に W/B+1 となります。
A' は A <= A' <= B-1 ⇦ -1 でなくても -0.1 or -0.01 or ...etc.
実装
#include <iostream>
using namespace std;
int main() {
int A, B, W; cin >> A >> B >> W;
W = W * 1000;
//最小値
int cmin;
if (W % B == 0)
cmin = W / B;
else
cmin = W / B + 1;
//最大値
int cmax = W / A;
if (W < A)// <= W < A なら どうあがいても無理
cout << "UNSATISFIABLE";
else
cout << cmin << " " << cmax;
return 0;
}
実は上記だと WA が出てくる。
A = B の時
932 932 156
#result
143 142
cmin > cmax が発生するので WA とのことです。
テストケースは公開されているモノもあるので
納得いかない人は自分で確認できます。
よって、以下のコードで AC
#include <iostream>
using namespace std;
int main() {
int A, B, W; cin >> A >> B >> W;
W = W * 1000;
//最小値
int cmin;
if (W % B == 0)
cmin = W / B;
else
cmin = W / B + 1;
//最大値
int cmax = W / A;
if (W < A || cmax < cmin)// A == B の場合における矛盾を条件追加
cout << "UNSATISFIABLE";
else
cout << cmin << " " << cmax;
return 0;
}
お疲れ様でした。
分かりにくい所があれば
遠慮なく突っ込みお願い致します。