Codeforms Round#698(Div.2)A~C解答

연속된 원소들의 최대 길이를 구하면 되는 문제

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
int a[101];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        int ans = 1;
        int cnt = 0, cnt2 = 1;
 
        for (int i = 0; i < n; i++) {
            if (a[i] != cnt) {
                ans = max(ans, cnt2);
                cnt = a[i];
                cnt2 = 1;
            } else {
                cnt2 += 1;
            }
        }
        ans = max(ans, cnt2);
        cout << ans << '\n';
    }
}

꽤 애먹은 문제..
1. 만약 d가 1인경우는 전부 가능한 경우니까 YES

2. d가 2 ~ 9인 경우를 살펴보자. 먼저 각 원소가 d로 인해 나눠진다면 YES

3. 그렇지 않다면 d의 자릿수가 포함된 어떤 수를 더한 값들로 구해져야 하는데,,
각 원소를 d로 나눈 나머지를 r이라고 했을 때, d를 포함한 자릿수에서 나머지가
r을 가지는 수를 찾으면 된다.

예를들어, d = 9 인 경우를 살펴보자.
a1 = 76이라고 가정하면 나머지 r = 40 % 9 = 4가 되고, 우리는
나머지가 4를 가지고 자릿수에 9가 포함된 수 중 가장 작은 수를 찾으면 된다. 
위의 답은 49 + 9 + 9 + 9 = 76로 표현할 수 있다.

그러면 어떻게 구할 수 있을까? 구하는 방법은 다 해보는 방법이 있다!
- 나머지가 1을 가지는 최소 수 : 91
그러면 우리는 나머지가 1 ~ 8까지의 가지는 수는 크게 잡아도 1000미만이라는 것을 
알 수 있다. 따라서 1 ~ 1000까지 해당 d를 가지는 자릿수에 대해 각 나머지 값들의
최소 값을 DP 방식으로구해둔 다음, 해당 값이 Ai보다 작으면 YES, 그렇지 않으면 NO

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int c[12][12];
bool go(int x, int k) {
    while (x > 0) {
        int y = x % 10;
        if (y == k) return true;
        x /= 10;
    }
    return false;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;
    memset(c, -1, sizeof(c));
    for (int i = 2; i <= 9; i++) {
        for (int j = i; j <= 1000; j++) {
            if (go(j, i)) {
                int x = j % i;
                if (c[i][x] == -1) c[i][x] = j;
            }
        }
    }

    for (int i = 2; i <= 9; i++) {
        for (int j = 1; j < i; j++) {
            if (c[i][j] != -1) {
                int y = c[i][j];
                int x = j + j;
                while (x < 10) {
                    if (c[i][x] == -1) {
                        c[i][x] = c[i][x - j] + y;
                    } else {
                        c[i][x] = min(c[i][x], c[i][x - j] + y);
                    }
                    x += j;
                }
            }
        }
    }

    while (t--) {
        int n, d;
        cin >> n >> d;

        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if (x % d == 0) {
                cout << "YES" << '\n';
                continue;
            }
            int remain = x % d;
            if (c[d][remain] <= x) {
                cout << "YES" << '\n';
            } else
                cout << "NO" << '\n';
        }
    }
}

종이에 끄적거려 보다가 규칙을 찾아서 해결한 문제이다. di를 구하는 방법을 그대로 쓰면
n = 4일 경우,
d[1] =
abs(a[1] - a[1]) +
abs(a[1] - a[2]) +
abs(a[1] - a[3]) +
abs(a[1] - a[4]) +
abs(a[1] + a[1]) +
abs(a[1] + a[2]) +
abs(a[1] + a[3]) +
abs(a[1] + a[4]) 로 나타낼 수 있다.
만약 a[1]이 가장 큰 원소라면 어떻게될까? 그러면 abs 성질을 무시해도 된다.
따라서 다음과 같이 나타낼 수 있다.
d[1] = 8 * a[1] (소거법을 적용)
그러면 가장 큰 수를 구했으면, 그 다음으로 큰 수에 대해 알아보자.
d[2] =
abs(a[2] - a[1]) +
abs(a[2] - a[2]) +
abs(a[2] - a[3]) +
abs(a[2] - a[4]) +
abs(a[2] + a[1]) +
abs(a[2] + a[2]) +
abs(a[2] + a[3]) +
abs(a[2] + a[4]) 로 나타낼 수 있다.
가장 큰수인 a[1]을 제외하고는 abs 성질을 무시할 수 있기 때문에, 다음과 같이 된다.
d[2] = 7 * a[2] + abs(a[2] - a[1]) + a[1]
     = 7 * a[2] + (a[1] - a[2]) + a[1]
     = 6 * a[2] + 2 * a[1]
d[3] 은 다음과 같다.
d[3] = 4 * a[3] + 2 * (a[1] + a[2])

규칙이 보이지 않는가? 규칙을 찾아서 적용시키면 Accept

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll a[200001];
ll n;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        vector<ll> v;
        for (int i = 0; i < n * 2; i++) {
            cin >> a[i];
            v.push_back(a[i]);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        if ((ll)v.size() != n) {
            cout << "NO" << '\n';
            continue;
        }
        ll x = v[n - 1];

        if (x % ((ll)2 * n) != 0) {
            cout << "NO" << '\n';
            continue;
        }

        x /= ((ll)2 * n);
        vector<ll> ans;

        ans.push_back(x);
        bool f = false;

        ll s = x;
        ll cnt = n * (ll)2 - (ll)2;

        for (int i = n - 2; i >= 0; i--) {
            ll y = v[i] - (ll)2 * s;
            if (y <= (ll)0 || y % cnt != (ll)0) {
                f = true;
                break;
            }
            y /= (ll)cnt;
            ans.push_back(y);
            s += y;
            cnt -= (ll)2;
        }

        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        if (f || (ll)ans.size() != n) {
            cout << "NO" << '\n';
        } else
            cout << "YES" << '\n';
    }
}