[Codeforces] Codeforces Round #669 (Div. 2) B. Big Vova
問題
方針
配列 \( a \) を入れ替えて得られる配列を \( b \) とします。ここで、\( g(a, b) \) を \( a, b \) の最大公約数とします。次に配列 \( c \) の \( i \) 番目の要素を
\[ c_i = g(b_1, b_2, \cdots, b_i)\]
とします。このとき、得られる \( c \) の中で辞書式順序が最大であるときの \( b \) を求めます。
まず初めに、\( b_1 = \max(a_1, a_2, \cdots, a_n) \) であることが分かります。ここで、\( g_1 = b_1 \) とします。次に、\( g(g_1, a_i) \) を最大化する \( i \) を求めます。そして、\( b_2 = a_i \) となります。ただし、\( a_i \) は \( b \) の要素に含まれないものとします。同様にして、\( g_2 = g(g_1, a_i) \) とし、\( g(g_2, a_i) \) を最大化するものを求めます。
\( O(N^2) \) の計算量となります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int a[1000]; ll gcd(ll m, ll n) { if (n == 0) return m; else return gcd(n, m % n); } void solve(int n) { sort(a, a + n, greater<int>()); int ans[n]; ans[0] = a[0]; int g = a[0]; bool f[n]{}; f[0] = true; for (int i = 1; i < n; i++) { int idx = i; int best = 0; for (int j = 1; j < n; j++) { if (f[j]) continue; if (best < gcd(g, a[j])) { best = gcd(g, a[j]); idx = j; } } f[idx] = true; g = gcd(g, a[idx]); ans[i] = a[idx]; } for (int i = 0; i < n; i++) { if (i == n - 1) { cout << ans[i] << "\n"; } else { cout << ans[i] << " "; } } } int main() { int t, n; cin >> t; for (int i = 0; i < t; i++) { cin >> n; for (int j = 0; j < n; j++) { cin >> a[j]; } solve(n); } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません