[Codeforces] Codeforces Round #667 (Div. 3) C. Yet Another Array Restoration

2020年9月8日2020年12月13日

問題

方針

数列 \( a_n \) は等差数列なので、初項を \( a \)、公差を \( d \) とすると、\( a_n = a_1 + (n – 1)d\) となります。したがって、\( i < j \) とし、\( i \) 番目の項が \( x \) で \( j \) 番目の項が \( y \) であるとき、

\begin{eqnarray}
x  &=& a + (i – 1)d\\
y &=& a + (j – 1)d
\end{eqnarray}

が成り立ちます。これらを \( d \) について解くと、

\[ d = \dfrac{y- x}{j – i}\]

なります。\( d \) は整数となる必要があるので、\( d \) が整数であるとき、\( a_n \) の最小値を全探索します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(int n, int x, int y) {
    int a = 10000;
    int d = 10000;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if ((y - x) % (j - i) != 0) continue;
            int d0 = (y - x) / (j - i);
            int a0 = x - i * d;
            if (a0 < 1) continue;
            if (a + (n - 1) * d > a0 + (n - 1) * d0) {
                a = a0;
                d = d0;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (i == n- 1) {
            cout << a + i * d << "\n";
        } else {
            cout << a + i * d << " ";
        }
    }
}

int main() {
    int t, n, x, y;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n >> x >> y;
        solve(n, x, y);
    }
    return 0;
}