Codeforces Round #719 (Div. 3) A~C

A. Do Not Be Distracted!

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        vector<int> a(26, 0);
        auto solve = [&]() -> bool{
            char last = s[0];
            a[s[0]-'A'] = 1;
            for(int i = 1; i < n; i++){
                if(last != s[i]){
                    if(a[s[i]-'A']) return false;
                    a[s[i]-'A']++;
                    last = s[i];
                }
            }
            return true;
        };
        cout << (solve() ? "YES" : "NO") << "\n";
    }
    return 0;
}

이전에 나왔던 알파벳이 다시 등장하면 NO, 등장하지 않으면 YES 를 출력해주면 된다.

B. Ordinary Numbers

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        string n;
        cin >> n;
        int ans = 9*(n.size()-1);
        char d = n[0];
        string s = "";
        for(int i = 0; i < n.size(); i++) s += d;
        if(stoi(n) >= stoi(s)) ans += (int)(d-'0');
        else ans += (int)(d-'0')-1;
        cout << ans << "\n";
    }
    return 0;
}

n 이 ordinary 하려면 모든 자리수의 숫자가 같아야 한다. 문제는 1~n 범위에 ordinary 수가 몇 개 있는지 묻고 있다. 예제를 풀어보면 자리수마다 ordinary 수는 9개 씩 존재하며, 제일 높은 자리수는 n 값이 얼만지에 따라 다르다는 걸 알 수 있다. 제일 높은 자리수의 값으로만 이루어진 ordinary 수를 문자열로 만들고 형변환한 후 비교해주었다.

C. Not Adjacent Matrix

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        if(n == 2){
            cout << -1 << "\n";
            continue;
        }
        vector<vector<int>> ans(n, vector<int>(n));
        int d = 1;
        for(int i = 0; i < n; i++){
            int y = 0;
            int x = i;
            for(int j = 0; j < n-i; j++){
                int ny = y+j;
                int nx = x+j;
                ans[ny][nx] = d;
                d++;
            }
            if(y == 0 && x == 0) continue;
            swap(y, x);
            for(int j = 0; j < n-i; j++){
                int ny = y+j;
                int nx = x+j;
                ans[ny][nx] = d;
                d++;
            }
        }
        for(int y = 0; y < n; y++){
            for(int x = 0; x < n; x++){
                cout << ans[y][x] << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

인접한 두 셀의 값 차이가 1이 되지 않도록 nxn 크기의 행렬을 1 부터 n² 까지 값을 한번씩 이용해 채우려고 한다. 예제를 몇개 풀다보니 대각선 방향으로 값을 채워나가면 연속된 값은 인접하지 않게되고, 가운데 대각선을 기준으로 상, 하 로 번갈아가며 값을 채워나가면 항상 조건을 만족한다는 걸 발견했다. 단, 2x2 크기일 땐 조건을 만족하지 못한다.

---

D. Same Differences (Upsolving)

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(auto& i : a) cin >> i;
        map<int, int> m;
        for(int i = 0; i < n; i++){
            a[i] -= i+1;
            m[a[i]]++;
        }
        ll ans = 0;
        for(auto iter = m.begin(); iter != m.end(); iter++){
            ll cnt = iter->second;
            if(cnt > 1) ans += (cnt-1)*cnt/2;
        }
        cout << ans << "\n";
    }
    return 0;
}

배열 a 에서 aj-ai == j-i 를 만족하는 값이 존재하려면 공차가 1인 등차수열이 존재하여야 한다. 단 특정 위치 이후에 오는 값들이 모두 등차수열을 만족할 필요는 없으며, 공차가 1인 등차수열과 비교했을 때 알맞은 위치에 있는 값이 두 개 이상만 존재하면 된다. 값의 개수를 n 이라고 하면 쌍은 (n-1)*n/2 개 존재한다.

연속된 값들을 찾으려면 배열 a 의 모든 원소 값을 해당 인덱스 값만큼 빼주면 연속되는 수들은 값이 일정하다. 문제 조건을 보면 배열 a 의 원소는 n 이하의 값이기 때문에 존재할 수 값의 차이는 -2·1e5 ~ 2·1e5 으로 4·1e5 개뿐이므로 hash map 을 사용하여 연속된 값의 개수를 저장해 주고 2개 이상인 값들에 대해서만 쌍의 개수를 구해주면 된다.

대회 중에는 존재하는 모든 수열을 어떻게 찾아야 할지 생각해내지 못해 풀지 못했다. 끝나자마자 솔루션이 떠올라서 아쉽다.