Codeforces Round 937 (Div. 4)

오랜만에 Div. 4를 쳐보기로 했다.

 

A

 

문제 읽고 푸는 시간보다 로딩시간이 더 길었다.

/**
 *    author:  pizzaroot
 *    created: 2024-03-28 23:45:00
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        int a, b, c; cin >> a >> b >> c;
        if (a < b && b < c) cout << "STAIR\n";
        else if (a < b && b > c) cout << "PEAK\n";
        else cout << "NONE\n";
    }
    return 0;
}

62초에 AC

 

B

 

\(\displaystyle\left\lfloor\frac{i}{2}\right\rfloor+\left\lfloor\frac{j}{2}\right\rfloor\)가 짝수면 #, 홀수면 .을 출력한다.

/**
 *    author:  pizzaroot
 *    created: 2024-03-28 23:46:24
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        for (int i = 0; i < 2 * n; i++) {
            for (int j = 0; j < 2 * n; j++) {
                if ((i / 2 + j / 2) & 1) cout << '.';
                else cout << '#';
            }
            cout << '\n';
        }
    }
    return 0;
}

191초에 AC

 

C

 

약간의 함정이 있었지만 다행히 예제가 친절하다. 다양한 풀이가 있겠지만 초로 변환해서 풀었다.

/**
 *    author:  pizzaroot
 *    created: 2024-03-28 23:48:40
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        string s; cin >> s;
        int t = (s[0] - '0') * 600 + (s[1] - '0') * 60 + (s[3] - '0') * 10 + s[4] - '0';
        cout.fill('0');
        cout << setw(2) << ((t / 60 + 11) % 12) + 1 << ':' << setw(2) << t % 60 << ' ';
        if (t >= 720) cout << "PM\n";
        else cout << "AM\n";
    }
    return 0;
}

9분에 AC

 

D

 

살짝 고민할 뻔 했지만 \(n\) 제한을 보니 binary decimal을 전처리한 후 각각 나누면 된다.

/**
 *    author:  pizzaroot
 *    created: 2024-03-28 23:54:59
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
vector<int> bd = {100000};
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    for (int i = 1; i < 32; i++) {
        int res = 0, cur = i, rep = 5;
        while (rep--) {
            res *= 10;
            res += cur % 2;
            cur /= 2;
        }
        if (res > 1) bd.push_back(res);
    }
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        for (auto &x: bd) while (n % x == 0) n /= x;
        if (n == 1) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

16분에 AC

 

E

 

처음에 KMP인가 하고 좀 고민했는데, 최대 약수 개수가 충분히 작아서 약수마다 체크하면 된다.

/**
 *    author:  pizzaroot
 *    created: 2024-03-29 00:01:40
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        int n; string s; cin >> n >> s;
        for (int i = 1; i <= n; i++) {
            if (n % i) continue;
            int diff = 0;
            for (int j = 0; j < i; j++) {
                vi cnt(128);
                for (int k = j; k < n; k += i) {
                    cnt[s[k]]++;
                }
                diff += n / i - *max_element(all(cnt));
            }
            if (diff <= 1) {
                cout << i << '\n';
                break;
            }
        }
    }
    return 0;
}

32분에 AC

 

F

 

풀이는 금방 떠올랐는데 처음에 수식 계산이 말려서 고생했다.

/**
 *    author:  pizzaroot
 *    created: 2024-03-29 00:18:28
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        ll a, b, c; cin >> a >> b >> c;
        if (a + 1 != c) {cout << "-1\n"; continue;}
        if (a == 0) {cout << b << '\n'; continue;}
        int d = log2(a + c + 0.5) - 1;
        int down = a + c - (1 << d + 1) + 1;
        int up = (1 << d) - down / 2;
        if (b <= up) cout << d + 1 << '\n';
        else cout << d + 1 + (b - up - 1) / (up + down) + 1 << '\n';
    }
    return 0;
}

80분에 AC

 

G

 

문제를 보니 해밀턴 경로가 존재하는지 찾으면 되고 이쯤되니 잘까 하다가 DP 풀이가 떠올라서 바로 짰다.

/**
 *    author:  pizzaroot
 *    created: 2024-03-29 01:28:00
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
int solve(vector<vi> &adj, int n) {
    vector<vi> dp(n, vi(1 << n));
    for (int i = 0; i < n; i++) dp[i][1 << i] = 1;
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i >> j) % 2 == 0) continue;
            for (int k = 0; k < n; k++) {
                if ((i >> k) % 2 == 0) continue;
                if (!adj[k][j]) continue;
                if (j == k) continue;
                if (dp[k][i ^ (1 << j)]) dp[j][i] = 1;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << n); j++) {
            if (dp[i][j]) ans = max(ans, __builtin_popcount(j));
        }
    }
    return n - ans;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n; vector<pair<string, string>> s(n);
        for (auto &x: s) cin >> x.first >> x.second;
        vector<vi> adj(n, vi(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i].first == s[j].first || s[i].second == s[j].second) adj[i][j] = 1;
            }
        }
        cout << solve(adj, n) << '\n';
    }
    return 0;
}

117분에 AC

 

후기

 

Div. 4지만 올솔을 해서 기분이 매우 좋았고, 실력이 실제로 좋아졌는지는 모르겠지만 성취감을 느꼈다. 게다가 일격필살이라 더욱 편안하다.