2021 SUAPC 2021 Winter Open

3시부터 순위가 굳었더니 집중력이 확 떨어졌다.
최대한 내가 풀어본 것들을 열심히 적어보도록 하겠다.
매크로는 다음과 같다.
구현 문제 빼고는 다 for문으로 다시 바꿔놓았다.

#define REPh(i,a,b) for (int i = a; i < b; ++i)
#define hPER(i,a,b) for (int i = b-1; i >= a; --i)

A. 우선순위 계산기

완전히 풀기에는 알고리즘적 한계가 보여서 접근하지 못했고, 파싱하는 코드는 작성했다.

void solve() {
    string s; cin >> s;
    vector<ll> x; vector<char> op;
    for (int i = 0; i < (int)s.size(); ++i) {
        int j = i;
        while (isdigit(s[++j]));
        x.EB(stoll(s.substr(i,j-i)));
        if (j < sz(s)) op.EB(s[j]);
        i = j;
    }
//    for (ll X : x) dbgpr(X);
//    for (char Op : op) dbgpr(Op);
}

B. 떡국

그리디한 문제이다.
각 그릇의 종류별로 몇 개가 있는지를 세고,
그 중 가장 많은 개수를 출력하면 된다.

const int N = 5e5+3;
int cnt[N];

void solve() {
    int n; cin >> n;
    for (int x = 0; x < n; ++x) {int x; cin >> x; ++cnt[x];}
    cout << *max_element(cnt, cnt+n);
}

C. 반짝반짝

한 10명 푼 것 같다.
난 보지 않았다.

D. 달고나

젤 어려운 문제 중 하나인 것 같다.
이 또한 난 보지 않았다.

E. 시철이가 사랑한 수식

이 또한 난 보지 않았다.

F. 성싶당

일단, 내가 보기에 반례는 못 찾았는데
정답에 가까울 수 있는 코드다.
업솔빙하고 수정해보겠다.

void solve() {
    int n; cin >> n;
    string p; cin >> p;
    bool b[n];
    for (int k = n-1; k >= 0; --k) b[k] = p[k]-'0';
    __int128 cnt = 1<<(n-1);
    int x = n-1; int d = -1;
    while (cnt--) {
        for (auto p : b) cout << p;
        cout << '\n';
        for (auto p : b) cout << !p;
        cout << '\n';
        b[x] = !b[x];
        x += d;
        if (x == 1 || x == n-1) d *= -1;
    }
}

G. 신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회

몰라요

H. 카카오톡

기하 문제이다.
TLE를 받고 곰곰히 생각해보니, 같은 식을 전개해서 풀면 $O(n^2)$에서 $O(n)$으로 줄일 수 있음을 알아냈다.
그러면 별 문제없이 AC할 수 있다.

void solve() {
    int n; cin >> n;
    map<ii,ll> m;
    for (int i = 0; i < n; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        int d = gcd(a,b);
        a /= d; b /= d;
        if (a < 0) {a *= -1; b *= -1;}
        if (a == 0 && b < 0) b *= -1;
        ++m[{a,b}];
    }
    ll ans = 0, tmp = 0;
    for (auto x : m) {
        ans += x.S;
        tmp += x.S*x.S;
    }
    ans *= ans;
    cout << (ans-tmp)/2;
}

I. 팰린드롬 척화비

잠깐 생각해보면,
? 설마 이건가?
그거다.

void solve() {
    int n; cin >> n;
    cout << string(n,'a');
}

J. 의자 게임

봤는데 잘 모르겠다.

K. 합성인수분해

소인수 분해해서 2개씩 묶어서 곱해주면 된다.
만약 소인수 리스트의 크기가 홀수라면 마지막 3개를 따로 묶어서 곱하면 된다. (사전순이기 때문.)

void solve() {
    ll n; cin >> n;
    vector<ll> f;
    for (ll x = 2; x*x <= n; ++x) {
        while (n%x == 0) {
            f.EB(x);
            n /= x;
        }
    }
    if (n > 1) f.EB(n);
    if (sz(f) < 2) {cout << -1; return;}
    if (sz(f)&1) {
        for (int i = 0; i < sz(f)-3; i += 2) {
            cout << f[i]*f[i+1] << ' ';
        }
        //sz-3,sz-2,sz-1 남음
        cout << f[sz(f)-3]*f[sz(f)-2]*f[sz(f)-1];
        return;
    } else {
        for (int i = 0; i < sz(f); i += 2) {
            cout << f[i]*f[i+1] << ' ';
        }
    }
}

L. 습격받은 도시

모든 '.'의 위치에서 폭탄 설치 가능한가를 따진다면 $O(n^3)$이 된다.
따라서 TLE를 받게 된다.
그래서 윗면, 아랫면, 양 옆면을 기준으로 $O(n^2)$ 안에 폭탄 설치 가능 여부를 따져야 한다.

void solve() {
    int n; cin >> n;
    char a[n][n];
    REPh(i,0,n) REPh(j,0,n) cin >> a[i][j];
    bool b[n][n], x; fill(b[0],&b[n-1][n-1]+1,1);
    //윗면
    REPh(j,0,n) {
        x = true;
        hPER(i,0,n) {
            if (a[i][j] == 'O') {x = false; b[i][j] = false;}
            else if (a[i][j] == 'X') {x = true; b[i][j] = false;}
            else b[i][j] &= x;
        }
    }
    //아랫면
    REPh(j,0,n) {
        x = true;
        REPh(i,0,n) {
            if (a[i][j] == 'O') {x = false; b[i][j] = false;}
            else if (a[i][j] == 'X') {x = true; b[i][j] = false;}
            else b[i][j] &= x;
        }
    }
    //왼쪽면
    REPh(i,0,n) {
        x = true;
        hPER(j,0,n) {
            if (a[i][j] == 'O') {x = false; b[i][j] = false;}
            else if (a[i][j] == 'X') {x = true; b[i][j] = false;}
            else b[i][j] &= x;
        }
    }
    //오른쪽면
    REPh(i,0,n) {
        x = true;
        REPh(j,0,n) {
            if (a[i][j] == 'O') {x = false; b[i][j] = false;}
            else if (a[i][j] == 'X') {x = true; b[i][j] = false;}
            else b[i][j] &= x;
        }
    }
    REPh(i,0,n) {REPh(j,0,n) cout << (b[i][j] ? 'B' : a[i][j]); cout << '\n';}
}

M. Go와 함께하는 전화망 서비스

보지도 않았다.