[AtCoder] ABC305

음..  C에서 조금 말려가지고 아쉽다. D도 조금 해매고.. E는 조금 신박했는데 왜 안뚫리는지 모르겠다. 
그래도 문제는 전반적으로 재밌었던 것 같다. 

A - 4:32

N이 주어질때, 가장 가까운 5의 배수 숫자를 찾으면 된다.

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define MINF 0x7f7f7f7f
#define INF 300000000000001
#define MOD 10007
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, ll> pil;
typedef pair<pii, int> piii;
typedef pair<piii, int> piiii;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, string> plls;

int psum[4000000];
vector<int>  a, b;
vector<pii> v;


void init(){
    int x;
    cin >> x;
    int answer = 1e9;
    int dist = 1e9;
    for (int i=0; i<=100; i++) {
        if (i == 0 || i % 5 == 0) {
            // cout << i << " " << dist << " " << abs(i-x) << " " << answer << '\n';
            if (abs(i - x) < dist) {
                answer = i;
                dist = abs(i-x);
            }
        }
        
    }
    cout << answer << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
}

 

B - 10:55

A - B, B - C, C - D ... 의 간격간 더해야 하는 숫자가 주어져있다.

우리는 P, Q를 입력받아 이들 사이에 있는 간격을 전부 더하면 된다. 어케 간단하게 구현할까..를 고민하다가 그냥 알파벳을 숫자로 치환해서 범위를 계산하는 코드를 직접 짜서 해결했다. 그냥 무지성 구현을 했으면 더 빨랐을 것 같다.

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <map>
#define MINF 0x7f7f7f7f
#define INF 300000000000001
#define MOD 10007
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, ll> pil;
typedef pair<pii, int> piii;
typedef pair<piii, int> piiii;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, string> plls;

map<char, int> mp;

void init(){
    mp['A'] = 0;
    mp['B'] = 1;
    mp['C'] = 2;
    mp['D'] = 3;
    mp['E'] = 4;
    mp['F'] = 5;
    mp['G'] = 6;
    
    char a, b;
    cin >> a >> b;

    int x = min(mp[a], mp[b]), y = max(mp[a], mp[b]);

    int answer = 0;
    if (x <= 0 && y >= 1) {
        answer += 3;
    }
    if (x <= 1 && y >= 2) {
        answer += 1;
    }
    if (x <= 2 && y >= 3) {
        answer += 4;
    }
    if (x <= 3 && y >= 4) {
        answer += 1;
    }
    if (x <= 4 && y >= 5) {
        answer += 5;
    }
    if (x <= 5 && y >= 6) {
        answer += 9;
    }
    cout << answer << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
}

 

C - 28:48

H, W로 주어진 격자판에 연속으로 색칠 된 어떤 직사각형이 존재한다.

우리가 구해야 하는 것은 이 직사각형 중 어떤 한 칸이 비어있을때, 이 칸의 좌표를 구하는 것이다.
이게 생각보다 좀 귀찮은데.. 나는 '#'을 기준으로 4방향에 전부 +1을 더해줬다. 그리고 2중 for문을 돌면서 2이상의 값인 칸이 있다면 해당 칸은 무조건 직사각형에 속하면서 공백인 칸이 보장이 되므로, 이 칸의 좌표를 출력해주면 된다.

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <map>
#define MINF 0x7f7f7f7f
#define INF 300000000000001
#define MOD 10007
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, ll> pil;
typedef pair<pii, int> piii;
typedef pair<piii, int> piiii;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, string> plls;
int n, m;
vector<string> v;
int psum[510][510];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int ax, ay;

void init(){
    memset(psum, 0, sizeof(psum));

    cin >> n >> m;
    for (int i=0; i<n; i++) {
        string s;
        cin >> s;
        v.push_back(s);
    }

    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (v[i][j] == '.') continue;
            int x = i+1, y = j+1;
            for (int k=0; k<4; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx < 0 || ny < 0 || nx > n || ny > m) continue;
                if (v[nx-1][ny-1] == '#') continue;
                psum[nx][ny]++;
            }
        }
    }

    for (int i=0; i<=n; i++) {
        for (int j=0; j<=m; j++) {
            if (psum[i][j] > 1) ax = i, ay = j;
        }
    }

    cout << ax << " " << ay << '\n';
}   

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
}

D - 55:38

홀수번째 주어지는 칸은 잠을 자기 시작한 시간이고, 짝수번째 주어지는 시간은 잠에서 깬 시간이라고 한다.
이때 Q개의 쿼리가 [left, right] 형태로 주어지는데 left ~ right 사이에 잠을 잔 시간을 구하는 문제이다.

제한이 매우 크기 때문에 단순 배열로는 못풀고, 일단 누적합을 이용해야 한다. 
그래서 입력을 받을때, 짝수번째 숫자에서 누적합을 위한 배열을 채워나가자. 이때 숫자의 범위가 너무 크므로 좌표 압축을 수행하게 된다.

그리고 이분 탐색을 통해 left와 right가 홀수번째 숫자인지를 알아야 한다. 이에 따라 구해야 하는 기준이 달라지기 때문이다. 

그위의 그림에서 left가 약 250인 경우와 230인 경우 두가지를 생각해보자. 만약 240보다 작다면 upper_bound를 사용해서 240의 좌표를 이용한 누적합을 구해야 한다. 
반대로 250인 경우에는 240을 기준으로 잡으면서 250 - 240의 만큼을 해당 누적합에서 빼야한다. 이 규칙을 찾았다면 쉽게 해결이 된다.

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <map>
#define MINF 0x7f7f7f7f
#define INF 300000000000001
#define MOD 10007
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, ll> pil;
typedef pair<pii, int> piii;
typedef pair<piii, int> piiii;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, string> plls;
int n;
vector<ll> v;
int q;
ll psum[200010];

void init(){
    memset(psum, 0, sizeof(psum));
    cin >> n;
    for (int i=0; i<n; i++) {
        ll x;
        cin >> x;
        v.push_back(x);
        if (i % 2 == 0) {
            if (i != 0) {
                psum[i] = x - v[i - 1];
            }
        }
    }

    for (int i=0; i<=n; i++) psum[i] += psum[i-1];
    cin >> q;
    for (int i=0; i<q; i++) {
        ll answer = 0;
        
        ll x, y;
        cin >> x >> y;
        
        int left, right;
        int l = upper_bound(v.begin(), v.end(), x) - v.begin();
        int r = lower_bound(v.begin(), v.end(), y) - v.begin();


        if (l % 2 == 0) {
            answer += v[l] - x;
            left = l;

        } else {
            left = l;
        }

        if (r % 2 == 0) {
            answer += y - v[r-1];
            right = r-1;
        } else {
            right = r;
        }


        answer += psum[right] - psum[left];
        cout << answer << '\n';
    }
}   


int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
}

E - 업솔빙

[Atcoder] ABC305 :: E - Art Gallery on Graph