ABC 337 - 4sol

A - Scoreboard

n개의 점수가 주어지고, 각 점수의 최종 합이 더 큰 사람을 출력하는 문제

#include <iostream>
using namespace std;
int main() {
    int n, x, y, a=0, b=0; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        a+=x, b+=y;
    }
    if (a > b) cout << "Takahashi";
    else if (a == b) cout << "Draw";
    else cout << "Aoki";
}

---

 

B - Extendead ABC

문자열 s가 주어졌을 때, 이를 A / B / C로만 이루어진 부분 문자열로 만들 수 있는지 묻는 문제

 

앞서 입력했던 문자와 동일하다면 continue, 아니라면 비교하여 A다음 B가, 혹은 A 다음 C가, 혹은 B 다음 C가 나왔는지 검사하면 된다.

다만 A / B / C가 존재하지 않아도 된다는 사실을 간과했다.

B 다음 A, 혹은 C 다음 A처럼 이전 문자로만 이동하지 않으면 된다.

#include <iostream>
using namespace std;
int main() {
    string s; cin >> s;
    vector<char>v;
    for (int i = 0; i < s.length()-1; i++) {
        if (s[i] != s[i + 1]) {
            if (int(s[i + 1]) == int(s[i]) + 1 || (int)s[i + 1] == int(s[i]) + 2) continue;
            else {
                cout << "No";
                return 0;
            }
        }
    }
    cout << "Yes";
}

---

 

C - Lining up 2

내 앞 순서의 번호가 적힌 배열이 있고, 가장 처음 앞에 서는 사람은 -1이 적혀있다.

간단하게 map을 이용하여 계산하면 된다.

#include <iostream>
#include <map>
using namespace std;
int main() {
    int n, x, s; cin >> n;
    map<int, int>m;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        if (x == -1) s = i;
        else m[x] = i;
    }
    while (n--) {
        cout << s << " ";
        s = m[s];
    }
}

---

 

D - Cheating Gomoku Narabe

h X w 배열에서 '.'을 'o'로 바꾸어 연속된 o를 n개 만들 수 있는지 묻는 문제

만들 수 있다면 바꾸어야 할 최소 '.'의 개수를 출력하면 된다.

 

먼저 w * h는 2*10^5이지만,

각각을 [200001][200001]으로 만들기에는 배열의 범위를 초과하므로

벡터안에 벡터를 만들었다.

 

이후 가로방향, 세로방향을 각각 확인했는데,

먼저 x가 나오면 모든 카운트를 초기화시켜주었다.

그리고 .이라면 o 변수와 카운트를 증가시키고,

o라면 그냥 카운트만 증가시켰다.

이러면 카운트가 n이 되었을 때 .의 개수를 따로 구할 수 있고,

한 칸씩 움직이면서 사라질 가장 처음의 원소가 o였다면 o 변수를 감소시키면 된다.

#include <iostream>
#include <vector>
using namespace std;
vector<vector<char>>v;
int main() {
    int cnt = 0, ans = 2147483647;
    string s;
    int n, w, h, o = 0; cin >> h >> w >> n;
    v.resize(h);
    for (int i = 0; i < h; i++) {
        cin >> s;
        for (int j = 0; j < w; j++) {
            v[i].push_back(s[j]);
        }
    }
    for (int i = 0; i < h; i++) {
        cnt = 0, o = 0;
        for (int j = 0; j < w; j++) {
            if (v[i][j] == '.') cnt++;
            else if (v[i][j] == 'x') cnt = 0, o = 0;
            else cnt++, o++;
            if (cnt == n) {
                ans = min(ans, cnt - o);
                cnt--;
            }
            if (j>=cnt && v[i][j - cnt] == 'o') o--;
        }
    }
    for (int j = 0; j < w; j++) {
        cnt = 0, o = 0;
        for (int i = 0; i < h; i++) {
            if (v[i][j] == '.') cnt++;
            else if (v[i][j] == 'x') cnt = 0, o = 0;
            else cnt++, o++;
            if (cnt == n) {
                ans = min(ans, cnt - o);
                cnt--;
            }
            if (i >= cnt && v[i - cnt][j] == 'o') o--;
        }
    }
    if (ans == 2147483647) cout << "-1";
    else cout << ans;
}