AGC 018 A - Getting Difference (300) - くるのプログラミング記録

300点とは思えない程考えさせられました。

リンク：A - Getting Difference
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

問題文

箱に $N$ 個のボールが入っていて、 $i$ 番目のボールには整数 $A_i$ が書かれています。すぬけ君は、次の操作を好きな回数だけ行うことができます。

箱から二つのボールを取り出し、その二つのボールに書かれている数の差の絶対値を書いた新しいボールと一緒に箱に戻す。
すぬけ君が、整数 $K$ の書かれたボールが箱の中に入っている状態にできるかどうか判定してください。

制約

$1 \leq N \leq 10^{5}$

$1 \leq A_i \leq 10^{9}$

$1 \leq K \leq 10^{9}$

入力はすべて整数である。　

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

とりあえず想定解 $O(N)$ か $O(N\log N)$ かなあ、ソートぐらいしかできることないな、と。

シミュレーションっぽいことすると二数の取り方の組合せがやばいのと、数列の要素数がどんどん大きくなりそうで厳しい。

題意の通り操作した際どんな数が出来るか少し考えてみると、作れそうな数は $A_i$ 同士のgcdの倍数ということに気付く。

$A_i$ 同士のgcdの倍数をいい感じに作って $K$ になるか判定する問題かな……って思うものの出来ることが特にない。

愚直に全通りgcdを作ると $O(N^{2}\log A)$ ぐらい？で大きすぎるので。要素も次々に増えるしね。

とりあえずコーナーケースを省くと、 $K \gt \max \{ A_i \}$ のときどうやっても無理なので"IMPOSSIBLE"。

それとgcdが1になるものを見つけると何でも作れるため"POSSIBLLE"になる。

gcdが1は解く鍵になると思って最初に素数を考えるものの、素数があったところで嬉しい訳でもなく( $N = 2, K = 3, A_1 = 14, A_2 = 7$ とかで自明に無理)、互いに素かどうかが大事だなと。しかも素じゃなくてもいいやと気付き結局gcdかよと(無駄考察)

じゃあgcdがどんな数になれば嬉しいかというと $A_i - K$ (このとき $A_i \gt K$ )の約数になってほしいよねと。すなわち $K$ との差分が数列 $A$ のある二要素のgcdの倍数になれば嬉しい。"POSSIBLE"であると。

なので $A_i - K$ を列挙しておく。( $A_i$ あるいは $A_i$ からなるgcd)からある数 $g$ を決め打ちして列挙した数のいずれかが1つ割り切れるかを確認することで判定が可能だなと。

ここから嘘解法感の漂う証明のない考察。
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

$g$ の決め方ですが、小さい方が良い。 $A_i - K$ の要素が割り切れる、というのは最悪の場合で素数であったとしても、1で割り切ることが出来るため。
数字が小さい方が余りの種類が少ないため当たり判定が大きいイメージ。素因数考えると分かりやすい？

また小さい数 $g$ と $A_i$ のgcdをそれぞれとると必ず $g$ 以下になるためその最小の数 $f$ を次の $g$ として採用できる。

$f = g$ だった場合これ以上gcdを取るという操作では数列の要素は増えず $K$ を作ることは出来ないので"IMPOSSIBLE"

計算量とかを深く考えず実装していく。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
	if (a < b) swap(a, b);
	while (b != 0) {
		a = a%b;
		swap(a, b);
	}
	return a;
}

int main() {
	int N, K; cin >> N >> K;
	vector<int> A(N),v; 
	for (int i = 0; i < N; ++i) cin >> A[i];
	set<int> st;

	for (int i = 0; i < N; ++i) {
		
		//最初にあれば終わり
		if (A[i] == K) {
			cout << "POSSIBLE" << endl;
			return 0;
		}

		//差分列挙
		if (A[i] > K) v.push_back(A[i] - K);

		//ユニークだけを列挙
		st.insert(A[i]);
	}

	//最大値がKより小さい場合
	if (v.size() == 0) {
		cout << "IMPOSSIBLE" << endl;
		return 0;
	}

	int mini = 0, mini2 = *min_element(A.begin(),A.end());

	//最小値が更新される限りループ
	while (mini2 != mini) {
		mini = mini2;

		//割り切れればPOSSIBLE
		for (int i = 0; i < v.size(); ++i) {
			if (v[i] % mini == 0) {
				cout << "POSSIBLE" << endl;
				return 0;
			}
		}

		vector<int> u;
		//gcdを作っていく
		for (auto itr = st.begin(); itr != st.end(); ++itr) {
			int g = gcd(mini, *itr);
			u.push_back(g);
		}
		for (int i = 0; i < u.size(); ++i) st.insert(u[i]);
		mini2 = *min_element(u.begin(), u.end());
	}

	cout << "IMPOSSIBLE" << endl;
	return 0;
}

ACしたもののテストケース厳しいならTLEするような気もする……。
間違いあれば是非教えてください。