解説が潤沢でも理解できなかった自分へ。ABC195-Many Oranges 編。

# はじめに
何となく分かったつもりで回答を暗記していた自分へ、、
頑張ってるな、偉いぞ。まだまだ だけどな(笑)
自分なりに嚙み砕いて自分へ解説してみます。

# [問題: ABC195-B](https://atcoder.jp/contests/abc195/tasks/abc195_b)
# O(N)解法 
以下、入力例の赤枠で早速 混乱されたのではないだろうか？
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/cf1a594c-8cc0-f738-9005-c4b404201db7.png)
確かに _120g * 8個 + 130g * 8個 = 2000g_ なので答えは 16個。

しかし、他のアプローチとして、
入力例1 のように _125g * 16個 == 2000g_ とも言える。
プログラムを組み立てる上で、どちらが簡単だろうか。

**入力例1の方法でも入力例2 と同等の結果を得られないか
確認しなかったのが敗因かもしれない**

## 打開策
いや、責めているわけではない、次回以降、試せばよいと思う。

他にも改善ポイントがある。
例えば、問題文の以下の赤文字を忘れてしまった場合だ。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/dd90f0fe-9401-67d8-c302-429a601feec6.png)
ココを忘れると、なんとかピッタリ 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_ と考えては如何だろうか。
例を交えてみる。

```:n=1のとき
↓A*n                                        ↓B*n
120g , 121g, 122g, 123g, 124g, 125g.........150g
```

```:n=10のとき
↓A*n                                              ↓B*n
1200g , 1210g, 1220g, 1230g, 1240g, 1250g.........1500g
```

如何だろう。
for 文で n 個を 1 ~ 1000000 と変化させた際に
_A * n <= W <= B * n_ ならば、具体的な重さ(ここでは 125g)を求めなくても、
**どこかの重さの みかん が n 個で W になっていると判断できないだろうか？**
だって、整数でも、少数でも何でも使って良いんでしょ？？(笑)

## 実装
```abc157b.cpp
#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)解法
個数が最大/最小となる、それぞれのケースを考察してみよう。
## 最<font color="red">大</font>値(cmax: count max)
**条件1: W%A == 0 の時、cmax = W/A**
&emsp;最小の A を n 個 用意し、
&emsp;A * n = W となるならば、みかんは最大となる。

**条件2: W%A != 0 の時、cmax = W/A**
&emsp;W%A < A なので、A は最大 (W/A **-2**) 個となります。
&emsp;上記に (&ensp;A+(&ensp;(W%A)/2)&ensp;) x2 を加算すれば W%A の補填が可能です。
&emsp;以上から個数で考えると、結果的に W/A は変わりません。

## 最<font color="blue">小</font>値(cmin: count min)
**条件3: W%B == 0 の時、cmin = W/B**
&emsp;最小の B を n 個 用意し、
&emsp;B * n = W となるならば、みかんは最小となる。

**条件4: W%B != 0 の時、cmin = W/B+1**
&emsp;W%B < B なので、B は最大 (W/B **-1**) 個となります。
&emsp;上記に (&ensp;A'+(&ensp;(W%B)/2)&ensp;) x2 を加算すれば W%B の補填が可能です。
&emsp;以上から個数で考えると、結果的に W/B+1 となります。
&emsp;_A' は A <= A' <= B-1　⇦ -1 でなくても -0.1 or -0.01 or ...etc._

## 実装
```abc195.cpp
#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 とのことです。
テストケースは公開されているモノもあるので
納得いかない人は自分で確認できます。

https://atcoder.jp/posts/20

よって、以下のコードで AC

```abc195.cpp
#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;
 
}
```

お疲れ様でした。
分かりにくい所があれば
遠慮なく突っ込みお願い致します。