과거 청산 챌린지 #1

요즘 백준에서 과거에 틀린 문제를 다시 푸는 챌린지를 하고 있다. 시작했을 때는 약 180개 가량의 문제가 있었다. 이 글을 쓰기 시작하는 시점으로 74개의 문제가 남아 있고, 다이아 5 이하의 문제는 전부 업솔빙을 완료했다. (Unrated 제외) 다이아 4부터는 문제들이 쉽지 않은 관계로 블로그 글을 쓰면서 배운 점들을 정리해 볼 생각이다.

 

현재 수준에서는 글마다 3~6개 내외의 문제들이 올라갈 것 같은데, 나중에 문제들이 어려워진다면 이 수가 조정될 수 있다.

 

당분간의 목표는 아래 d4 문제들을 전부 푸는 것이다.

 

남은 문제: 74 → 69문제

 

문제 리스트만 놓고 봤을 때 최악은 아니었지만 (D5에서는 실수 오차 문제 등 풀기 싫은 문제들이 많았다), 34167의 정해가 잘못되었다는 걸 들은 기억이 있다. 또한 맨 위의 Riddle은 풀이는 쉽지만 TL이 매우 작았던 문제로 기억하는데, 이 문제도 조금 힘들 수 있다는 생각이 들었다.

BOJ 16264. Array Study

문제에 해결 경고가 붙어 있어서 가장 먼저 봤다. 보통 해결 경고가 있는 경우는 완전히 같은 문제가 있거나 문제 오류가 있는 경우인데, 다행히도 문제 오류는 아니었고 완전히 같은 문제가 있었다. 심지어 그 문제가 예전에 풀었던 문제라서 확인해봤는데, 16264에 제출했을 때는 TLE를 받은 기록이 있었다.

 

그래서 새로 짜 보기로 했다. 문제는 다음과 같다. 길이 $N$의 배열 $A$는 $-1$과 $1$로만 이루어져 있다. 구간 $Q$개 ($[l_i, r_i]$)가 주어질 때, 각 구간에 대해, 이 구간 내부의 구간 $[s_i, e_i] \subseteq [l_i, r_i]$ 중 $A$의 합이 $0$인 가장 긴 구간의 길이를 구해야 한다. (그런 구간이 없으면 $0$으로 생각한다.)

 

이 문제는 Mo 알고리즘으로 쉽게 풀린다. 기본적으로는 누적합으로 생각해야 한다. 구간 내에서 같은 값이 최대한 멀리 떨어진 것을 찾는다고 생각하자. 구간을 줄이고 늘릴 때 추가/제거되는 수에 대해 해당 수가 등장하는 왼쪽 끝 / 오른쪽 끝을 포인터 변수 등을 이용해 만들어 주면 해당 수가 최대 얼마나 떨어져서 등장하는지를 알 수 있다. 다만 이 방식으로는 모든 수에 대해 이 값을 빠르게 aggregate하는 게 어렵다. (pq를 이용하면 되겠지만 그러면 시간 복잡도가 루트로그가 될 것이다.)

 

여기서 트릭은 모스를 쓸 때 앞 sqrt(N)개 값만 왼쪽 끝이 줄어들 수 있고, 나머지 값들은 왼쪽 끝이 고정이라는 것이다. 그래서 그 값들은 max dist가 계속 늘어나기만 하고 굳이 pq를 쓸 필요 없다. 나머지 값들은 그때 그때 봐 주면 총 시간 복잡도 $O((N+Q) \sqrt N)$에 문제를 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int G = 318;

struct Query{
    int l, r, idx;
    Query(){}
    Query(int l, int r, int idx): l(l), r(r), idx(idx){}
    bool operator<(const Query &nxt)const{
        if(l/G != nxt.l/G) return l/G < nxt.l/G;
        return r < nxt.r;
    }
};

int t;
int n, q;
int A[100002];
Query queries[100002];

vector<int> occ[200002];
int lidx[200002], ridx[200002], nxt[200002];
bool special[200002];
int maxDist;
ll ans[200002];

void init();

inline void addR(int x){
    ridx[A[x]] = max(ridx[A[x]], x);
    if(lidx[A[x]] == n+1) lidx[A[x]] = x;
    if(!special[A[x]]) maxDist = max(maxDist, ridx[A[x]] - lidx[A[x]]);
}

inline void addL(int x){
    lidx[A[x]] = min(lidx[A[x]], x);
    if(!special[A[x]]) maxDist = max(maxDist, ridx[A[x]] - lidx[A[x]]);
}

inline void delR(int x){
    exit(1);
}

inline void delL(int x){
    assert(lidx[A[x]] == x && special[A[x]]);
    lidx[A[x]] = nxt[x];
}

int main(){
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> t;
    while(t--){
        cin >> n;
        A[0] = n;
        for(int i=1; i<=n; i++){
            cin >> A[i];
            A[i] += A[i-1];
        }
        cin >> q;
        for(int i=1; i<=q; i++){
            cin >> queries[i].l >> queries[i].r, queries[i].idx = i;
            queries[i].l--;
        }

        sort(queries+1, queries+q+1);
        for(int i=0; i<=n*2; i++) occ[i].clear();
        for(int i=0; i<=n; i++) occ[A[i]].push_back(i);

        for(int i=0; i<=n*2; i++){
            for(int j=0; j<(int)occ[i].size()-1; j++){
                nxt[occ[i][j]] = occ[i][j+1];
            }
            if(!occ[i].empty()) nxt[occ[i].back()] = n+1;
        }

        int pnt = 1;
        for(int sg=0; sg*G<=n; sg++){
            int S = pnt, E = pnt-1;
            while(E+1 <= q && queries[E+1].l/G == sg) E++;
            if(S>E) continue;
            pnt = E+1;

            int L = sg*G, R = min(n, (sg+1)*G-1);
            for(int i=0; i<=n*2; i++){
                special[i] = false;
                lidx[i] = n+1, ridx[i] = -1;
            }
            for(int i=L; i<=R; i++) special[A[i]] = true;

            maxDist = 0;
            int s = L, e = L-1;
            for(int i=S; i<=E; i++){
                int ql = queries[i].l, qr = queries[i].r;
                while(e < qr) addR(++e);
                while(s > ql) addL(--s);
                while(e > qr) delR(e--);
                while(s < ql) delL(s++);

                int tAns = maxDist;
                for(int i=L; i<=R; i++) tAns = max(tAns, ridx[A[i]] - lidx[A[i]]);
                ans[queries[i].idx] = tAns;
            }
        }

        ll sum = accumulate(ans+1, ans+q+1, 0LL);
        cout << sum << '\n';
    }
}

BOJ 23197. Ley Lines

전형적인 불도저 트릭 연습문제이다. 그래도 오래 걸렸는데, 내가 std::lower_bound의 동작 과정을 잘못 이해하고 있었고, 질문 게시판에 있던 부정확한 정보에 낚였다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct vector2{
    ll x, y; int idx;

    vector2(){}
    vector2(ll x, ll y): x(x), y(y){}
    vector2(ll x, ll y, int idx): x(x), y(y), idx(idx){}

    bool operator==(const vector2 &r)const{
        return x == r.x && y == r.y;
    }
    bool operator<(const vector2 &r)const{
        return x != r.x ? x < r.x : y < r.y;
    }
    bool operator>(const vector2 &r)const{
        return r < *this;
    }

    vector2 operator+(const vector2 &r)const{
        return vector2(x+r.x, y+r.y);
    }
    vector2 operator-(const vector2 &r)const{
        return vector2(x - r.x, y - r.y);
    }
    vector2 operator*(double r)const{
        return vector2(x*r, y*r);
    }

    double norm() const { return hypot(x, y); }

    ll dot(vector2 r)const{
        return x*r.x + y*r.y;
    }
    ll cross(vector2 r)const{
        return x*r.y - y*r.x;
    }
};

ll ccw(vector2 a, vector2 b){
    return a.cross(b);
}
ll ccw(vector2 a, vector2 b, vector2 c){
    return ccw(b-a, c-a);
}

int n; ll T;
vector2 arr[3002];
int ans;

int idx[3002];

int main(){
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n >> T;
    // T*=2;
    for(int i=1; i<=n; i++){
        cin >> arr[i].x >> arr[i].y;
        arr[i].idx = i;
    }

    vector2 origin (0, 0, -1), criteria (2'000'000'000, -1);
    sort(arr+1, arr+n+1, [&](vector2 &a, vector2 &b){
        return a.dot(criteria) < b.dot(criteria);
    });

    for(int i=1; i<=n; i++) idx[arr[i].idx] = i;

    vector<pair<vector2, vector2> > pairs;
    for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) pairs.push_back({arr[i], arr[j]});

    sort(pairs.begin(), pairs.end(), [&](pair<vector2, vector2> &a, pair<vector2, vector2> &b){
        vector2 ap = a.second - a.first, bp = b.second - b.first;
        if(ap.x > 0 || (ap.x == 0 && ap.y < 0)) ap = ap * -1;
        if(bp.x > 0 || (bp.x == 0 && bp.y < 0)) bp = bp * -1;
        // assert(ccw(ap, origin, bp) != 0);
        return ccw(ap, origin, bp) < 0;
    });

    for(auto &[p1, p2]: pairs){
        int p = p1.idx, q = p2.idx;
        int l = min(idx[p], idx[q]), r = max(idx[p], idx[q]);
        assert(r-l==1);

        {
            int MIN = 1, MAX = l-1, ANS = l;
            while(MIN <= MAX){
                int MID = (MIN + MAX) / 2;
                vector2 p3 = arr[MID];
                double D = (double)abs((p1-p3).cross(p2-p3)) / (p2-p1).norm();
                if(D < T + 1e-5) ANS = MID, MAX = MID - 1;
                else MIN = MID + 1;
            }
            ans = max(ans, r-ANS+1);
        }

        {
            int MIN = r+1, MAX = n, ANS = r;
            while(MIN <= MAX){
                int MID = (MIN + MAX) / 2;
                vector2 p3 = arr[MID];
                double D = (double)abs((p1-p3).cross(p2-p3)) / (p2-p1).norm();
                if(D < T + 1e-5) ANS = MID, MIN = MID + 1;
                else MAX = MID - 1;
            }
            ans = max(ans, ANS-l+1);
        }

        swap(idx[p], idx[q]);
        swap(arr[idx[p]], arr[idx[q]]);
    }

    cout << ans;
}

BOJ 27474. 팬케이크 탑

오랫동안 풀지 못해 에디토리얼을 보고 풀었다.

 

핵심은 $\frac{N+1}{2}$번째 상한 팬케이크를 뽑았을 때, 그다음부터는 뭘 뽑았는가의 결과에 상관 없이 상하지 않은 팬케이크가 나온다고 생각하는 것이다. 이렇게 하면 $p/q = r$이라 할 때 $r$의 확률로 상한 팬케이크가 나오는 횟수가 무조건 $\frac{N+1}{2}$번이고, $1-r$의 확률인 경우가 $\frac{N-1}{2}$번이어야 한다.

 

그래서 결국은 순서에 상관없이 $r$의 확률로 $\frac{N+1}{2}$, $1-r$의 확률로 $\frac{N-1}{2}$번 시행할 때 합이 $\frac{N+1}{2}$ 이상일 확률을 구하면 되고, 이걸 계산하는 것은 누적 합과 조합론 등을 이용하면 어렵지 않다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 998244353;

ll mpow(ll x, ll y){
    if(!y) return 1;
    if(y&1) return x*mpow(x, y-1)%MOD;
    ll tmp = mpow(x, y/2);
    return tmp * tmp % MOD;
}

ll fact[1'000'005], factInv[1'000'005];

ll comb(ll x, ll y){
    if(y<0 || y>x) return 0;
    return fact[x] * factInv[y] % MOD * factInv[x-y] % MOD;
}

int n;
ll p, q, r, s;
ll p1[1'000'005], p2[1'000'005];

int main(){
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    fact[0] = 1;
    for(int i=1; i<=1'000'000; i++) fact[i] = (fact[i-1] * i) % MOD;
    factInv[1'000'000] = mpow(fact[1'000'000], MOD-2);
    for(int i=999'999; i>=0; i--) factInv[i] = (factInv[i+1] * (i+1)) % MOD;

    cin >> n >> p >> q;
    r = p * mpow(q, MOD-2) % MOD;
    s = (1 - r + MOD) % MOD;

    if(r <= 1){
        cout << r;
        return 0;
    }

    ll ans = 0;
    int e = (n+1)/2, f = (n-1)/2;

    for(int i=0; i<=e; i++){
        p1[i] = mpow(r, i) * mpow(s, e-i) % MOD * comb(e, i) % MOD;
    }
    for(int i=0; i<=f; i++){
        p2[i] = mpow(s, i) * mpow(r, f-i) % MOD * comb(f, i) % MOD;
    }

    ll sum = 0;
    for(int i=0; i<=f; i++) sum = (sum + p2[i]) % MOD;
    for(int i=e, j=0; i>=0; i--, j++){
        ans = (ans + p1[i] * sum) % MOD;
        sum = (sum - p2[j] + MOD) % MOD;
    }

    cout << ans << '\n';
}

BOJ 16215. Build a Wall!

기하 문제라 어려울 줄 알았는데 사실 다른 문제들보다 풀이가 금방 떠올랐다.

 

핵심은 답이 $x$라면 삼각형을 잡아 인접한 점 사이에 다각형 위의 선분 $2^{x-1}$개씩을 포함하고 있어야 한다는 것이다. 저게 가능한 최대 $x$를 parametric search로 짜면 되는데, 생각해보면 삼각형 중 한 점에 대해서는 양쪽 끝 변이 모두 최소 길이거나 최대 길이여야 한다. 여기서 최소 길이란 $2^{x-1}$에 의해 생기는 최소 길이를 말하고, 최대 길이란 점이 삼각형 안에 있어야 한다는 조건에 의한 최대 길이를 말한다. 따라서 $O(N)$ 시간에 가능성 판별이 된다.

 

$O(NQ \log \log N)$으로 짰는데도 생각보다 시간이 오래 걸렸다. 실수 연산들이 많아서 그런 것 같다. TL이 2.5초인데 거의 근접한 시간 안에 통과했다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct vector2{
    double x, y;
    explicit vector2(double x_ = 0, double y_ = 0): x(x_), y(y_){}

    bool operator==(const vector2 &r)const{
        return x == r.x && y == r.y;
    }
    bool operator<(const vector2 &r)const{
        return x != r.x ? x < r.x : y < r.y;
    }
    bool operator>(const vector2 &r)const{
        return r < *this;
    }

    vector2 operator+(const vector2 &r)const{
        return vector2(x+r.x, y+r.y);
    }
    vector2 operator-(const vector2 &r)const{
        return vector2(x - r.x, y - r.y);
    }
    vector2 operator*(double r)const{
        return vector2(x*r, y*r);
    }

    double norm() const { return hypot(x, y); }

    double dot(const vector2 &r)const{
        return x*r.x + y*r.y;
    }
    double cross(const vector2 &r)const{
        return x*r.y - y*r.x;
    }
};

double ccw(vector2 a, vector2 b){
    return a.cross(b);
}
double ccw(vector2 a, vector2 b, vector2 c){
    return ccw(b-a, c-a);
}

int n, q;
vector2 arr[5002];
vector2 query;

int mostR[5002];
int mostL[5002];

inline bool able(int r, int l, int V){
    return (l-r+n)%n >= V && ccw(arr[r], arr[l], query) > 0;
}

void solveQuery(){
    int pnt = 0;
    for(int i=0; i<n; i++){
        while(ccw(arr[i], arr[(pnt+1)%n], query) > 0) pnt = (pnt+1)%n;
        mostR[i] = pnt;
    }

    pnt = n-1;
    for(int i=n-1; i>=0; i--){
        while(ccw(arr[i], arr[(pnt-1+n)%n], query) < 0) pnt = (pnt-1+n)%n;
        mostL[i] = pnt;
    }

    int L = 0, R = 10, ans = 0;
    while(L <= R){
        int M = (L+R)/2;
        int V = 1<<M;
        if(3*V > n){
            R = M - 1;
            continue;
        }

        bool a = 0;
        for(int i=0; i<n; i++){
            int l = mostL[i], r = mostR[i];
            int p = (i-V+n)%n, q = (i+V)%n;
            if((i-l+n)%n >= V && (r-i+n)%n >= V &&
               (able(r, l, V) || able(q, l, V) || able(r, p, V) || able(q, p, V))){
                a = true;
                break;
            }
        }
        if(a){
            ans = M;
            L = M + 1;
        }
        else R = M - 1;
    }

    cout << (ans + 1) << '\n';
}

int main(){
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i].x >> arr[i].y;
    cin >> q;
    while(q--){
        cin >> query.x >> query.y;
        solveQuery();
    }
}

BOJ 13729. 1013 피보나치

다른 문제들보다 푼 사람이 압도적으로 많아서 시도해 보기로 했다.

 

$10^{n}$꼴 mod에 대해 피보나치 수의 주기가 피사노 주기로 잘 알려져 있다. $10^{13}$에 대한 주기는 $1.5\times 10^{13}$이다. 이 주기는 여전히 크므로 이것만으로는 문제를 풀기에 불충분하다.

 

한 가지 특징은 최소의 $i$를 찾아야 한다는 것이다. 따라서 사실상 모든 occurence를 관리할 수 있는 방법이 필요해 보인다. 여기서 한 가지 접근법이 생기는데, $10^{k-1}$에 대해 모든 경우를 관리하고 있으면 $10^{k}$에서 확인해볼 후보는 10배밖에 안 된다는 것이다. 따라서 작은 $10^k$부터 시작하여 확장해 나가면서 경우의 수를 관리한다는 생각을 할 수 있다. 행렬을 이용해 피보나치 함수를 빠르게 구하는 함수를 만들어 둔다면 어렵지 않게 해결할 수 있다.

 

풀이가 굉장히 특이한 문제 같다.

#include <bits/stdc++.h>

using namespace std;

typedef __int128 ll;
const ll MOD = 10'000'000'000'000;

istream& operator>>(istream &in, ll &x){
    long long y;
    in>>y;
    x=y;
    return in;
}

struct Matrix{
    ll mat[2][2];

    Matrix(){
        mat[0][0] = mat[1][1] = 1;
        mat[1][0] = mat[0][1] = 0;
    }
    Matrix(ll a, ll b, ll c, ll d){
        mat[0][0] = a;
        mat[0][1] = b;
        mat[1][0] = c;
        mat[1][1] = d;
    }

    Matrix operator*(const Matrix &r)const{
        Matrix ret (0,0,0,0);
        for(int a=0; a<2; a++) for(int b=0; b<2; b++) for(int c=0; c<2; c++){
            ret.mat[a][c] = (ret.mat[a][c] + mat[a][b]*r.mat[b][c]) % MOD;
        }
        return ret;
    }
} base(1,1,1,0);

inline ll fib(ll x){
    Matrix ret, b = base;
    for(int i=0; i<50; i++){
        if((x>>i)&1) ret = ret * b;
        b = b * b;
    }
    return ret.mat[0][1];
}

ll n;

int main(){
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n;

    if(n == 10'000'000'000'000){
        cout << -1;
        return 0;
    }

    ll unit = 1000, cycle = 1500;
    set<ll> cand;
    for(int i=0; i<cycle; i++){
        if(fib(i) % unit == n % unit) cand.insert(i);
    }

    while(unit < MOD){
        unit *= 10;
        set<ll> newCand;
        for(ll x: cand){
            for(int a=0; a<10; a++){
                if(fib(a*cycle+x) % unit == n % unit) newCand.insert(a*cycle+x);
            }
        }
        cycle *= 10;
        cand.swap(newCand);
    }

    if(!cand.empty()) cout << (long long)*cand.begin();
    else cout << -1;
}