AtCoder ABC 182

작성일 | In

총평

D: 최근에 본 ABC-D 중 가장 좋은 문제
E: 노잼
F: 어렵다.

A. twiblr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#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 a, b; cin >> a >> b;
    cout << max(0, 2*a+100-b);
}

B. Almost GCD

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
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#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[111];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i];

    int mx = 0, ans = -1;
    for(int i=2; i<1010; i++){
        int now = 0;
        for(int j=1; j<=n; j++) if(a[j] % i == 0) now++;
        if(mx < now) mx = now, ans = i;
    }
    cout << ans;
}

C. To 3

비트마스크

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
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#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;

string s;
int a[22];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> s;
    for(int i=0; i<s.size(); i++) a[i] = (s[i] - '0') % 3;
    int n = s.size();
    int mn = 1e9;
    for(int bit=0; bit<(1<<n)-1; bit++){
        int sum = 0, cnt = 0;
        for(int i=0; i<n; i++){
            if(bit & (1 << i)) cnt++;
            else sum += a[i];
        }
        if(sum % 3 == 0) mn = min(mn, __builtin_popcount(bit));
    }
    if(mn == 1e9) cout << -1;
    else cout << mn;
}

D. Wandering

주어진 수열 $A$의 Prefix Sum의 Prefix Maximum을 알고 있으면 쉽게 정답을 구할 수 있습니다.

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
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#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;

ll n, a[202020];
ll s[202020], prefix[202020];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++){
         s[i] = s[i-1] + a[i];
         prefix[i] = max(prefix[i-1], s[i]);
    }

    ll mx = 0, now = 0;
    for(int i=1; i<=n; i++){
        mx = max(mx, now + prefix[i]);
        now += s[i];
    }
    cout << mx;
}

E. Akari

각 칸을 4개로 쪼개서 BFS

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#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;
const int di[] = {1, -1, 0, 0};
const int dj[] = {0, 0, 1, -1};

struct Info{
    int i, j, d;
    Info() : Info(0, 0, 0) {}
    Info(int i, int j, int d) : i(i), j(j), d(d) {}
};

int n, m, k, b;
int a[1515][1515];
int chk[1515][1515][4];
queue<Info> q;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> k >> b;
    for(int i=1; i<=k; i++){
        int x, y; cin >> x >> y;
        for(int j=0; j<4; j++) q.emplace(x, y, j), chk[x][y][j] = 1;
    }
    for(int i=1; i<=b; i++){
        int x, y; cin >> x >> y; a[x][y] = 1;
    }

    while(q.size()){
        int i = q.front().i, j = q.front().j, d = q.front().d; q.pop();
        int ii = i + di[d], jj = j + dj[d];
        if(ii < 1 || jj < 1 || ii > n || jj > m) continue;
        if(a[ii][jj] || chk[ii][jj][d]) continue;
        q.emplace(ii, jj, d); chk[ii][jj][d] = 1;
    }

    int ans = 0;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        int flag = 0;
        for(int d=0; d<4; d++) flag |= chk[i][j][d];
        ans += flag;
    }
    cout << ans;
}

F. Valid payments

풀이 준비 중…

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
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#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;

ll n, k, a[55], dv[55];
map<ll, ll> dp[55];

ll f(int idx, ll rem){
    if(idx == n) return 1;
    if(rem == 0) return 1;
    auto it = dp[idx].lower_bound(rem);
    if(it != dp[idx].end() && it->x == rem) return it->y;

    ll res = f(idx+1, (rem-1) / dv[idx] + 1);
    if(rem % dv[idx] != 0) res += f(idx+1, rem / dv[idx]);
    dp[idx].insert(it, {rem, res});
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k; for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<n; i++) dv[i] = a[i+1] / a[i];
    cout << f(1, k);
}