[AtCoder] ABC308

E가 꽤나 어렵게 느껴졌고, 그냥 넘어가서 F를 잡을걸 그랬다. C에서 3WA를 받았는데, double로 연산하면 터져버리는 케이스가 있었던 것 같다.

A - 2:17

단순 구현 문제이다. 8개의 숫자가 들어오고, 모든 숫자가 25의 배수인지 그리고 각 숫자가 100 ~ 675 이내의 차이를 가지고 있는지 확인하면 된다. 하나라도 만족하지 않을 경우 No를 출력하자.

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <cstring>
#define X first
#define Y second
#define NUM 21
using namespace std;
vector<int> v;
bool flag = true;

int main() {
    for (int i=0; i<8; i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }

    for (int i=0; i<8; i++) {
        if (i != 0) {
            if (v[i] < v[i-1]) flag = false;
        }
        if (v[i] < 100 || v[i] > 675) flag = false;
        if (v[i] % 25 != 0) flag = false;
    }

    if (flag) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }

}

 

B - 9:17

내가 궁금한 string이 들어오고, string별 price가 주어진다. 만약 이 price가 주어지지 않은 문자열이 있다면 P0의 값을 더하면 된다. map을 이용하면 아주 간단하게 해결할 수 있는 문제이다. 해석을 대충하고 넘어갔다가 문제를 괜히 2번 읽었다.

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <cstring>
#define X first
#define Y second
#define NUM 21
using namespace std;
int N, M;
vector<string> v, vv;
map<string,int> mp;

int main() {
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        string s;
        cin >> s;
        v.push_back(s);
    }

    for (int i=0; i<M; i++) {
        string ss;
        cin >> ss;
        vv.push_back(ss);
    }

    int cost;
    cin >> cost;

    for (int i=0; i<M; i++) {
        int c;
        cin >> c;
        mp[vv[i]] = c;
    }
    int answer = 0;

    for (int i=0; i<N; i++) {
        string s = v[i];
        if (mp[s] != 0) {
            answer += mp[s];
        } else {
            answer += cost;
        }
    }
    cout << answer << '\n';
}

 

C - 20:27

아주 간단한 정렬 문제이다. Ai, Bi가 N개 주어질때, Ai / (Ai + Bi)를 기준으로 내림차순 정렬을 수행하고 만약 이 값이 같다면 입력받은 순서로 오름차순으로 정렬하면 된다.

double로 풀었는데 자꾸 틀려서 long double을 넣어봤는데 풀렸다.

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <cstring>
#define X first
#define Y second
#define NUM 21
using namespace std;
typedef pair<int, long double> pid;
int N, M;

vector<pid> v;

bool compare(pid a, pid b) {
    if (a.Y == b.Y) {
        return a.X < b.X;
    }
    return a.Y > b.Y;
}

int main() {
    cin >> N;
    for (int i=1; i<=N; i++) {
        long double a, b;
        cin >> a >> b;
        v.push_back({i, a / (a + b)});
    }    

    sort(v.begin(), v.end(), compare);
    for (auto vv : v) {
        cout << vv.X << ' ';
    }
}

D - 33:37

(1, 1)부터 (H, W)로 이동하려고 한다. 이때 각 칸마다 알파벳이 들어있는데, 무조건 s -> n -> u -> k -> e 을 밟으면서 이동을 해야한다. 주어진 알파벳이 5개뿐이므로, 방문 배열을 3차원으로 잡아 BFS를 돌려볼 수 있다. visited[i][j][k]를 i알파벳을 밟고 j, k에 도달할 수 있는지?로 기준을 잡아서 풀었다.

그런데 지금 다시보니 그럴 필요가 없어보인다. 이미 각 칸에 대해 알파벳이 정해져있고 그냥 순서대로 갈 수 있는지만 보면 될 것 같다.

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <cstring>
#define X first
#define Y second
#define NUM 21
using namespace std;
typedef pair<int, long double> pid;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
bool visited[5][510][510] = {false};
vector<char> ch = {'s', 'n', 'u', 'k', 'e'};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int h, w;
vector<string> graph;
bool flag = false;
queue<piii> q;

void bfs() {
    q.push({{0, 0}, 0});
    visited[0][0][0] = true;
    while (!q.empty()) {
        auto curr = q.front();
        int x = curr.X.X, y = curr.X.Y, d = curr.Y;
        q.pop();
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nd = (d + 1) % 5;
            if (nx < 0 || nx >= h || ny < 0 || ny >= w || visited[nd][nx][ny] || graph[nx][ny] != ch[nd]) continue;
            visited[nd][nx][ny] = true;
            q.push({{nx, ny}, nd});
        }
    }
}

int main() {
    cin >> h >> w;
    for (int i=0; i<h; i++) {
        string s;
        cin >> s;
        graph.push_back(s);
    }

    if (graph[0][0] == 's') {
        bfs();
    }
    for (int i=0; i<5; i++) {
        if (visited[i][h-1][w-1]) flag = true;
    }
    if (flag) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }
}