AtCoder ABC 174

작성일 | In

결과

다 풀었습니다.

A. Air Conditioner

단순 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    if(n >= 30) cout << "Yes\n";
    else cout << "No\n";
}

B. Distance

단순 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

ll n, d, cnt;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> d; d *= d;
    for(int i=1; i<=n; i++){
        ll a, b; cin >> a >> b;
        if(a*a + b*b <= d) cnt++;
    }
    cout << cnt;
}

C. Repsept

정점 $K$개를 만들고, 각각 현재 수를 $K$로 나눈 나머지가 $0, 1, \ldots , K-1$인 상태라고 생각합시다.
현재 수의 맨 뒤에 7을 추가한다는 것은, 현재 수에 10을 곱하고 7을 더하는 것을 의미합니다. $K$의 배수를 만드는 것에만 관심이 있기 때문에 현재 수를 $K$로 나눈 나머지만 저장하고 있어도 됩니다. 0을 만들면 끝나기 때문입니다.
7에서 출발해서 0으로 가는 최단 거리를 찾으면 됩니다.

그래프를 명시적으로 만들고 BFS를 돌려도 되지만, 이 문제에서는 모든 정점의 out degree가 1이기 때문에 굳이 그래프를 만들 필요는 없습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

ll n, cnt, chk[1010101];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    int now = 0;
    while(1){
        now = now * 10 + 7; now %= n;
        cnt++;
        if(chk[now]) break;
        chk[now] = 1;
        if(!now){ cout << cnt; return 0; }
    }
    cout << -1;
}

D. Alter Altar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n, a[202020], cnt;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        char c; cin >> c; a[i] = c == 'R';
        cnt += a[i];
    }
    int ans = 0;
    for(int i=1; i<=cnt; i++) ans += !a[i];
    cout << ans;
}

E. Logs

간단한 파라메트릭 서치 문제입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n, k, a[202020];

int chk(int x){
    ll cnt = 0;
    for(int i=1; i<=n; i++) cnt += (a[i] - 1) / x;
    return cnt <= k;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k; for(int i=1; i<=n; i++) cin >> a[i];
    int l = 1, r = 1e9;
    while(l < r){
        int m = l + r >> 1;
        if(chk(m)) r = m;
        else l = m + 1;
    }
    cout << r;
}

F. Range Set Query

BOJ 수열과 쿼리 5와 동일한 문제입니다.
이렇게 유명한 문제가 어떻게 통과되었을까요?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

struct Query{
    int s, e, x;
    bool operator < (const Query &t) const {
        return p(s/700, e) < p(t.s/700, t.e);
    }
} qry[505050];

int n, q, a[505050];
int cnt[505050], now, res[505050];

void insert(int x){ if(!cnt[a[x]]++) now++; }
void erase(int x){ if(!--cnt[a[x]]) now--; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=q; i++) cin >> qry[i].s >> qry[i].e, qry[i].x = i;
    sort(qry+1, qry+q+1);
    int s = 1, e = 1; insert(1);
    for(int i=1; i<=q; i++){
        while(qry[i].s < s) insert(--s);
        while(e < qry[i].e) insert(++e);
        while(s < qry[i].s) erase(s++);
        while(qry[i].e < e) erase(e--);
        res[qry[i].x] = now;
    }
    for(int i=1; i<=q; i++) cout << res[i] << "\n";
}