환영합니다!

우선 [PProject]가 무엇인지 모르는 분들을 위해 간단히 설명드리자면, 백준에 있는 Platinum 문제들을 $1\,000$문제 이상 푸는 프로젝트로, 본격적인 실력 증진을 위해 진행하는 프로젝트입니다!

저는 풀고 난 뒤에 성취감을 즐기는 타입이기에, 이렇게 블로그에다가 작성을 하니 많은 관심 부탁드립니다 ;)

구체적인 목표는 다음과 같습니다:

Platinum 5: $200$문제
Platinum 4: $200$문제
Platinum 3: $200$문제
Platinum 2: $200$문제
Platinum 1: $200$문제

순차적으로 진행합니다. (Platinum 5 > 4 > 3 > 2 > 1)
glhf!

BOJ 16572: Pixel Triangles

https://www.acmicpc.net/problem/16572

메인 아이디어

문제를 보자마자 imos 트릭이라는 것을 알 수 있었습니다.
imos 트릭이란? > 누적합의 응용으로, $O(N^2)$이 필요한 구간 업데이트를 $O(N)$만에 끝내주는 그저 갓갓 트릭입니다. 누적합 배열에다가 시작점을 $1$만큼 더하고, 끝점을 $-1$만큼 빼면 됩니다. 그 뒤, 한 번 $O(N)$의 시간을 투자해 스위핑 해주면 간단하게 구간을 구할 수 있습니다.

imos를 이용해 2차원 평면에서 삼각형을 만드는 것은 상당히 웰노운입니다. 다음과 같이 짜고 오른쪽으로 한 번, 아래쪽으로 한 번, 그 다음에 오른쪽 아래 대각선으로 한 번 스위핑을 돌리면 됩니다:

그런데, 이 문제에서는 삼각형의 방향이 다르므로, 살짝 변형을 시켜서,
다음과 같은 형태로 짜도록 하겠습니다 :>
순서대로 왼쪽 아래 대각선, 아래쪽, 그리고 오른쪽입니다.

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

int N;
int plane[2005][2005];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for(int i = 0; i < N; i++) {
        int x, y, s; cin >> x >> y >> s;
        
        plane[x][y]++;
        plane[x][y+s]--;
        plane[x+1][y+s]++;
        plane[x+1][y-1]--;
        plane[x+s+1][y]--;
        plane[x+s+1][y-1]++;
    }

    for(int i = 1; i <= 2002; i++) {
        for(int j = 0; j <= 2002; j++) {
            plane[i][j] += plane[i-1][j+1];
        }
    }

    for(int i = 1; i <= 2002; i++) {
        for(int j = 0; j <= 2002; j++) {
            plane[i][j] += plane[i-1][j];
        }
    }

    for(int i = 0; i <= 2002; i++) {
        for(int j = 1; j <= 2002; j++) {
            plane[i][j] += plane[i][j-1];
        }
    }

    int ans = 0;
    for(int i = 0; i <= 2002; i++) {
        for(int j = 0; j <= 2002; j++) {
            if(plane[i][j]) ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}

여담

의외로 시간이 되게 오래 걸려서 놀랐습니다. 스위핑 할 때 조심해야겠네요...

BOJ 27928: 단조 증가 수

https://www.acmicpc.net/problem/27928

메인 아이디어

처음 봤을 때는 Digit DP인가 싶었습니다. (계단 수 같은 문제들이 여기에 해당되죠) 하지만 $10^{18}$ 이하의 단조 증가 수가 몇 안되는 것 같았습니다. 그래서 직접 프로그램을 돌려서 계산했더니 $4\,686\,825$개가 있다고 합니다. 이 정도는 충분히 나이브하게 돌아가니, 무지성 누적 합을 돌려봅시다.

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

vector <ll> increasing_numbers;
vector <ll> psum;
void bfs() {
    queue <ll> q;
    q.push(0);

    while(!q.empty()) {
        ll cur = q.front();
        q.pop();

        increasing_numbers.push_back(cur);
        if(cur >= ll(1e17l)) continue;

        for(int i = max(1LL, cur%10); i <= 9; i++) {
            q.push(cur*10 + i);
        }
    }
}

ll F(const ll x) {
    if(x < 0) return 0;
    if(x >= increasing_numbers.back()) {
        ll add = ((x - increasing_numbers.back() + 1) % MOD) * (increasing_numbers.back() % MOD) % MOD;
        return (psum.back() + add) % MOD;
    }

    int idx = upper_bound(all(increasing_numbers), x) - increasing_numbers.begin() - 1;
    ll add = ((x - increasing_numbers[idx] + 1) % MOD) * (increasing_numbers[idx] % MOD) % MOD;
    return (psum[idx] + add) % MOD;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    bfs();

    psum.resize(increasing_numbers.size());
    
    psum[0] = increasing_numbers[0];
    for(int i = 1; i < increasing_numbers.size(); i++) {
        ll add = ((increasing_numbers[i-1] % MOD) * ((increasing_numbers[i] - increasing_numbers[i-1]) % MOD)) % MOD;
        psum[i] = (psum[i-1] + add) % MOD;
    }

    int T; cin >> T;
    while(T--) {
        ll N, M; cin >> N >> M;

        ll ret = (F(M) - F(N-1)) % MOD;
        if(ret < 0) ret += MOD;

        cout << ret << "\n";
    }
    return 0;
}

여담

생각보다 실행 속도가 빨랐습니다. (로컬에서는 거의 560ms 정도 나오던데...) 그리고 2번 연속이나 누적 합 문제가 나오네요... 3번째 문제나 봅시다.

BOJ 13560: 축구 게임

https://www.acmicpc.net/problem/13560

메인 아이디어

본 적 있었지만 옛날에는 그냥 던졌던 문제입니다. 한 번 풀어봅시다.

우선 점수들의 합 $S$가 $\binom{N}{2}=\frac{N(N-1)}{2}$이여야합니다. 만약 이 조건을 만족하지 않으면 유효하지 않습니다.

또한 $0$점의 개수는 $1$을 초과할 수 없습니다. $0$점의 의미는 모든 게임을 다 졌다는 뜻인데, 모든 게임을 다 진 팀이 $2$개 이상일 수는 없으니까요.

같은 논리로 $N-1$점의 개수는 $1$을 초과할 수 없습니다. 모든 게임을 다 이긴 팀이 $2$개 이상일 수는 없으니까요.

가설 #1: 같은 점수를 가진 팀이 있으면 안된다; 즉, 팀들의 점수는 $0$부터 $N-1$까지 유일한 정수의 수열이다.
반례 #1: $N=5$를 가정하자. 점수 분배 $2$ $2$ $2$ $2$ $2$가 가능하다.

조금 더 생각해봅시다. 자세히 보면, 팀들의 점수의 순서는 바꿔도 아무 상관 없다는 것을 알 수 있습니다. 계산하기 편하게 오름차순 정렬을 해둡시다.

혹여나, $N$을 더 작은 문제들로 나누어서 생각할 수 있을까요?
$N$을 $N-1$, 아니면 $\frac{N}{2}$으로 치환해서 풀 수 없을까요?
이 문제를 $N-1$로 축소시킨 경우, 각 $N-1$개의 팀에 대해서 $S_{N-1} \geq \binom{N-1}{2}$를 만족해야 할 것입니다. 이를 토대로 새로운 가설을 세워봅시다.

가설 #2: 팀들의 점수를 정렬했을 때, 모든 $1 \leq i \leq N$을 만족하는 $i$에 대해서,

$\begin{cases} S_{i} \geq \binom{i}{2} \\ S_{N} = \binom{N}{2} \end{cases}$

를 만족하면 점수는 유효할 것이다. ($S_{i} = \sum^{i}_{j=1}{v_{j}}$, $v_j$는 $j$번째 팀의 점수)

정답 코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

int N;
vector <int> v;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    v.resize(N);
    for(int i = 0; i < N; i++) cin >> v[i];

    sort(all(v));

    int st = v[0];
    for(int i = 1; i < N-1; i++) {
        st += v[i];
        if(st < i * (i+1) / 2) {
            cout << "-1\n";
            return 0;
        }
    }
    if(st + v[N-1] != N * (N-1) / 2) {
        cout << "-1\n";
        return 0;
    }

    cout << "1\n";
    return 0;
}

여담

Proof by AC 성향이 매우 강해서 이에 관한 증명을 찾아보고자 구글을 뒤져봤더니 "Landau's Theorem"이라고 있다고 하더라고요? 이에 관한 건 나중에 자세히 파보도록 하겠습니다.