AtCoder Beginner Contest 278

A - Shift

K번째 idx부터 N번째까지 출력 한 후
K > N임을 고려해, min(K, N)의 0을 출력한다.
queue를 써도 된다.

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

const int MAX = 105;
int N, K, A[MAX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> K;
    for (int i=0; i<N; i++) cin >> A[i];
    for (int i=K; i<N; i++) cout << A[i] << ' ';
    for (int i=0; i<min(K,N); i++) cout << 0 << ' ';
}

B - Misjudge the Time

그냥 하자

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

int H, M;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> H >> M;

    for (int m=M; m<60; m++) {
        int ten = (H%24)/10*10 + M/10;
        int one = (H%24)%10*10 + M%10;

        if (ten>=0 && ten<=23 && one>=0 && one<=59) {
            cout << H << ' ' << m;
            return 0;
        }
    }

    for (int h = H+1;; h++) {
        for (int m = 0; m<60; m++) {
            int ten = (h%24)/10*10 + m/10;
            int one = (h%24)%10*10 + m%10;

            if (ten>=0 && ten<=23 && one>=0 && one<=59) {
                cout << h%24 << ' ' << m;
                return 0;
            }
        }
    }
}

시간 입력하면 판별하는 함수 만들면 더 좋았을듯

C - FF

A와 B가 서로를 팔로우하고 B와 A를 팔로우하면 Yes를 출력하고
아니면 No를 출력하는 문제다.

범위를 주의해야한다.

2\le N\le 10^9,\ 1\le Q\le 2\times 10^5

처음에 생각해본 구조는 각 N마다 Set을 만들어서
set[a].contain(b) && set[b].contain(a) 면 Yes를 출력하려고 했으나,
N의 범위가 최대 10억이므로 공간복잡도를 고려하면 O(N)은 메모리 초과다.

그래서 string Set을 생각해보았다. A와 B가 친구라면 "A B"를 저장한다.
그리고 set.contain("A B") && set.contain("B A") 라면 Yes를 출력하는 방식으로 저장한다.
Q의 범위는 이십만이므로 괜찮다고 생각했었고, 그렇게 풀어서 AC가 뜨기는 했는데 생각해보니
N이 1e9이면 string에서는 1e9byte이다. 안전한 풀이가 아님을 알았고
제일 좋은 풀이는 pair set를 써야했다.

int는 4byte고 pair<int, int>는 8byte다.
O(8Q)이므로 pair set를 쓰는 풀이가 가장 안전해보인다.
제출해보니 pair set이 string set보다 메모리가 2배이상 줄어들었다

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

int N, Q;
set<pair<int, int>> f;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> Q;
    for (int i=0; i<Q; i++) {
        int T, A, B; cin>>T>>A>>B;
        if (T==1) f.insert({A, B});
        else if (T==2) f.erase({A, B});
        else cout << (f.find({A, B})!=f.end() && f.find({B, A})!=f.end() ? "Yes\n" : "No\n");
    }
}

D - All Assign Point Add

\ 1\le Q\ \le \ 2\cdot 10^5,\ \ 1\le N\le \ 2\cdot 10^5

1번은 모든 N개의 원소를 xq로 바꾸는 연산인데, O(N)의 시간복잡도를 가진다.
Q 또한 O(N)이다. 즉 최대 O(N^2)의 시간복잡도를 가지므로 1초안에 해결할 수 없다.
이를 위해 map을 사용해야한다. default라는 변수에 1번연산을 할 때마다 xq를 default에 저장해서,
1번연산을 하면 모든 map.clear를 통해 모든 원소를 없애고,
각 2번 3번 연산을 할때마다, 정의되지 않은 숫자가 있다면 default에서 값을 가져와 연산한다.
시간복잡도는 O(N)이 된다.

#include <iostream>
#include <algorithm>
#include <map>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

const int MAX = 2*1e5+5;
ll N, Q, dft = 0;
map<ll, ll> A;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N;
    for (int i=1; i<=N; i++) cin>>A[i];
    cin >> Q;

    for (int i=1; i<=Q; i++) {
        int q; cin >> q;
        if (q == 1) {
            A.clear();
            cin >> dft;
        } else if (q==2) {
            int iq, xq; cin >> iq >> xq;
            if (A.find(iq) != A.end()) A[iq] += xq;
            else A[iq] = dft + xq;
        } else {
            int iq; cin >> iq;
            if (A.find(iq) != A.end()) cout << A[iq];
            else cout << dft;
            cout << '\n';
        }
    }
}

E - Grid Filling

1차원을 대상으로 하던 스위핑을 2차원에서 해야한다.
N, H, W가 300. h, w가 150일때를 고려하면, 스위핑을 하지 않고는
O(HWh*w) 이므로 계산해보면 시간초과다.

즉 스위핑을 통해 O(HWh)로 만들어야한다.
그리고 숫자의 개수는 모든 숫자의 개수를 1차원 배열에 저장해놓고
1 이상인 숫자들을 카운트해놓으면 된다.

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

const int MAX = 305;
int H, W, N, h, w, A[MAX][MAX], C[MAX], ans[MAX][MAX], cnt, oriC[MAX];

void addColor(int x) {
    if (!C[x]) cnt++;
    C[x]++;
}

void eraseColor(int x) {
    C[x]--;
    if (!C[x]) cnt--;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> H >> W >> N >> h >> w;
    for (int i=1; i<=H; i++)
        for (int j=1; j<=W; j++)
            cin >> A[i][j], C[A[i][j]]++, oriC[A[i][j]]++;

    for (int i=1; i<=N; i++) if (C[i]) cnt++;
    int original = cnt;

    for (int i=1; i<=H-h+1; i++) {
        cnt = original;
        for (int j=1; j<=N; j++) C[j] = oriC[j];

        for (int j=i; j<i+h; j++) for (int k=1; k<=w; k++)
            eraseColor(A[j][k]);

        ans[i][1] = cnt;
        for (int j=2; j<=W-w+1; j++) {
            for (int k=i; k<i+h; k++)
                addColor(A[k][j-1]),
                eraseColor(A[k][j+w-1]);
            ans[i][j] = cnt;
        }
    }

    for (int i=1; i<=H-h+1; i++) {
        for (int j=1; j<=W-w+1; j++)
            cout << ans[i][j] << ' ';
        cout << '\n';
    }
}

댓글