A - 3,2,1,GO

값을 입력받은 후 1부터 입력값까지 반복하여 출력합니다.

코드 보기

#include<bits/stdc++.h>

using namespace std;

int n;

int main(){
    cin >> n;
    for(int i = n; i > 1; --i)
        cout << i << ',';
    cout << 1;
    return 0;
}

B - Split Ticketing

a, b, c를 모두 반복하며 조건을 검사합니다. 조건을 만족하면 "Yes"를 출력하고 함수를 종료합니다. 만약 조건을 만족하는 값이 없으면 "No"를 출력합니다.

코드 보기

#include<bits/stdc++.h>

using namespace std;

int n;
int v[105][105];

int main(){
    cin >> n;
    for(int i = 1; i < n; ++i)
        for(int j = i + 1; j <= n; ++j)
            cin >> v[i][j];
    
    for(int a = 1; a <= n; ++a){
        for(int b = a + 1; b <= n; ++b){
            for(int c = b + 1; c <= n; ++c){
                if(v[a][b] + v[b][c] < v[a][c]){
                    cout << "Yes";
                    return 0;
                }
            }
        }
    }
    
    cout << "No";
    return 0;
}

C - Puddles

배경을 기반으로한 연결된 '.' 블록을 검색합니다. 경계면에 접한 블록은 카운트하지 않습니다. BFS를 사용하여 '.' 블록을 탐색하고 '#'로 변환합니다.

코드 보기

#include<bits/stdc++.h>

using namespace std;

int n, m;
char c[1005][1005];

int dx[] = {0, 1, -1, 0, 0};
int dy[] = {0, 0, 0, 1, -1};

void bfs(int x, int y){
    if(c[x][y] != '.') return;
    queue<pair<int, int>> q;
    q.push({x, y});
    c[x][y] = '#';
    while(!q.empty()){
        auto [a, b] = q.front(); q.pop();
        for(int i = 1; i <= 4; ++i){
            int aa = a + dx[i];
            int bb = b + dy[i];
            if(aa >= 1 && aa <= n && bb >= 1 && bb <= m && c[aa][bb] == '.'){
                q.push({aa, bb});
                c[aa][bb] = '#';
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> c[i][j];
    
    for(int i = 1; i <= m; ++i)
        bfs(1, i), bfs(n, i);
    for(int i = 1; i <= n; ++i)
        bfs(i, 1), bfs(i, m);
    
    int ans = 0;
    
    for(int i = 2; i < n; ++i)
        for(int j = 2; j < m; ++j){
            if(c[i][j] == '.'){
                ans++;
                bfs(i, j);
            }
        }
    
    cout << ans;
    return 0;
}

D - Minimize Range

모든 수를 K로 나눈 나머지로 변환한 후 정렬합니다. 최소 범위를 찾기 위해 배열을 슬라이딩 윈도우로 검사합니다.

코드 보기

#include<bits/stdc++.h>

using namespace std;

int n, k;
int a[200005];

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> a[i], a[i] %= k;
    
    sort(a + 1, a + 1 + n);
    
    int ans = a[n] - a[1];
    
    for(int i = 1; i < n; ++i)
        ans = min(ans, a[i] + k - a[i + 1]);
    
    cout << ans;
    return 0;
}

E - Fibonacci String

Fibonacci 문자열의 성질을 활용하여 효율적으로 문자 검색을 수행합니다.

코드 보기

#include<bits/stdc++.h>

#define int long long

using namespace std;

string x, y;
int len[105], n;
int gs[30][105];
int qx[30][10005];
int qy[30][10005];

int get(int k, int a, int c){
    if(k == 1) return qx[c][a - 1];
    if(k == 2) return qy[c][a - 1];
    if(a <= len[k - 1]) return get(k - 1, a, c);
    else return gs[c][k - 1] + get(k - 2, a - len[k - 1], c);
}

int main(){
    cin >> x >> y;
    len[1] = x.length();
    len[2] = y.length();
    
    for(int i = 0; i < len[1]; ++i){
        gs[x[i] - 'a'][1]++;
        for(int j = 0; j < 26; ++j)
            qx[j][i] = qx[j][i - 1];
        qx[x[i] - 'a'][i]++;
    }
    for(int i = 0; i < len[2]; ++i){
        gs[y[i] - 'a'][2]++;
        for(int j = 0; j < 26; ++j)
            qy[j][i] = qy[j][i - 1];
        qy[y[i] - 'a'][i]++;
    }
    for(n = 3; n <= 100; ++n){
        for(int j = 0; j < 26; ++j)
            gs[j][n] = gs[j][n - 1] + gs[j][n - 2];
        len[n] = len[n - 1] + len[n - 2];
        if(len[n] > 1e18) break;
    }
    
    int _; cin >> _;
    while(_--){
        int l, r; char c;
        cin >> l >> r >> c;
        cout << get(n, r, c - 'a') - get(n, l - 1, c - 'a') << '\n';
    }
    
    return 0;
}

F - Strongly Connected 2

점과 간선을 사용하여 최소 커버리지 구간을 찾는 문제를 해결합니다.

코드 보기

#include<bits/stdc++.h>

#define ls lson[x]
#define rs rson[x]
#define int long long
#define mod 998244353

using namespace std;

int n, m;

struct line{
    int x, y;
} a[200005];

bool cmp(line a, line b){
    return a.x < b.x;
}

int lson[800005];
int rson[800005];
int dp[800005];
int tagadd[800005];
int tagmul[800005];

void pushup(int x){
    dp[x] = (dp[ls] + dp[rs]) % mod;
}

void add_tagadd(int x, int v){
    tagadd[x] += v; tagadd[x] %= mod;
    dp[x] += v; dp[x] %= mod;
}

void add_tagmul(int x, int v){
    tagmul[x] *= v; tagmul[x] %= mod;
    tagadd[x] *= v; tagadd[x] %= mod;
    dp[x] *= v; dp[x] %= mod;
}

void pushdown(int x){
    if(tagmul[x] != 1){
        add_tagmul(ls, tagmul[x]);
        add_tagmul(rs, tagmul[x]);
        tagmul[x] = 1;
    }
    if(tagadd[x] != 0){
        add_tagadd(ls, tagadd[x]);
        add_tagadd(rs, tagadd[x]);
        tagadd[x] = 0;
    }
}

void build(int x, int lx, int rx){
    tagadd[x] = 0; tagmul[x] = 1;
    if(lx == rx) return;
    lson[x] = x * 2;
    rson[x] = x * 2 + 1;
    int mx = (lx + rx) >> 1;
    build(ls, lx, mx);
    build(rs, mx + 1, rx);
    pushup(x);
}

int query(int x, int lx, int rx, int l, int r){
    if(l <= lx && rx <= r) return dp[x];
    pushdown(x);
    int mx = (lx + rx) >> 1, res = 0;
    if(l <= mx) res += query(ls, lx, mx, l, r);
    if(r > mx) res += query(rs, mx + 1, rx, l, r);
    res %= mod;
    return res;
}

void change_add(int x, int lx, int rx, int l, int r, int v){
    if(l <= lx && rx <= r){
        add_tagadd(x, v);
        return;
    }
    pushdown(x);
    int mx = (lx + rx) >> 1;
    if(l <= mx) change_add(ls, lx, mx, l, r, v);
    if(r > mx) change_add(rs, mx + 1, rx, l, r, v);
    pushup(x);
}

void change_mul(int x, int lx, int rx, int l, int r, int v){
    if(l <= lx && rx <= r){
        add_tagmul(x, v);
        return;
    }
    pushdown(x);
    int mx = (lx + rx) >> 1;
    if(l <= mx) change_mul(ls, lx, mx, l, r, v);
    if(r > mx) change_mul(rs, mx + 1, rx, l, r, v);
    pushup(x);
}

int main(){
    cin >> n >> m;
    
    for(int i = 1; i <= m; ++i)
        cin >> a[i].x >> a[i].y;
    
    sort(a + 1, a + 1 + m, cmp);
    
    build(1, 1, n); change_add(1, 1, n, 1, 1, 1);
    for(int i = 1; i <= m; ++i){
        int x = a[i].x, y = a[i].y;
        int det = query(1, 1, n, x, y);
        if(x > 1) change_mul(1, 1, n, 1, x - 1, 2);
        change_add(1, 1, n, y, y, det);
        if(y < n) change_mul(1, 1, n, y + 1, n, 2);
    }
    
    cout << query(1, 1, n, n, n);
    return 0;
}