AtCoder ABC 179

작성일 | In

결과

다 풀었습니다.

A. Plural Form

단순 구현 문제입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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);
    string s; cin >> s;
    if(s.back() == 's') s += "es";
    else s += "s";
    cout << s;
}

B. Go to Jail

단순 구현 문제입니다.

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;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n; int cnt = 0;
    for(int i=1; i<=n; i++){
        int a, b; cin >> a >> b;
        if(a == b){
            if(++cnt == 3){ cout << "Yes"; return 0; }
        }
        else cnt = 0;
    }
    cout << "No";
}

C. A × B + C

tau(1..n)을 빠르게 구하는 방법이 생각이 안 나서 ahgus89의 Linear-sieve를 복붙했습니다.

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<int> prime;
int sp[1010101], e[1010101], tau[1010101];

void sieve(int n){
    tau[1] = 1;
    for(int i=2; i<=n; i++){
        if(!sp[i]){ prime.push_back(i); e[i] = 1; tau[i] = 2; }
        for(auto j : prime){
            if(i*j > n) break;
            sp[i*j] = j;
            if(i%j == 0){
                e[i*j] = e[i] + 1;
                tau[i*j] = tau[i] / e[i*j] * (e[i*j] + 1);
                break;
            }
            e[i*j] = 1; tau[i*j] = tau[i] * tau[j];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    sieve(1010100);
    ll n, ans = 0; cin >> n;
    for(int i=1; i<n; i++) ans += tau[i];
    cout << ans;
}

D. Leaping Tak

간단한 DP입니다. 누적합을 잘 사용합시다.

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
#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;
const ll mod = 998244353;

ll n, k, dp[202020], sum[202020];
p range[11];

ll Mod(ll x){
    x %= mod; x += mod; x %= mod;
    return x;
}

ll query(int s, int e){
    if(e < 0) return 0;
    s = max(s, 0);
    if(!s) return sum[e];
    else return Mod(sum[e] - sum[s-1]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k; for(int i=1; i<=k; i++) cin >> range[i].x >> range[i].y;
    dp[1] = sum[1] = 1;
    for(int i=2; i<=n; i++){
        for(int j=1; j<=k; j++) dp[i] += query(i-range[j].y, i-range[j].x);
        dp[i] %= mod;
        sum[i] = sum[i-1] + dp[i]; sum[i] %= mod;
    }
    cout << dp[n];
}

E. Sequence Sum

$M \leq 10^5$입니다. 비둘기집의 원리에 의해 크기가 10만 이하인 사이클이 만들어집니다.
사이클의 시작점과 길이를 찾고 잘 계산하면 됩니다.

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

vector<ll> v;
map<ll, int> mp;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    ll n, x, m, ret = 0; cin >> n >> x >> m;
    int idx = -1;
    for(int i=1; i<=n; i++){
        if(mp.count(x)){ idx = i; break; }
        mp[x] = i; v.push_back(x);
        ret += x;
        x *= x; x %= m;
    }
    if(mp.size() == n){ cout << ret; return 0; }
    ll sz = idx - mp[x], rem = n - idx + 1;
    ll val = 0;
    for(int i=mp[x]-1; i<v.size(); i++) val += v[i];
    ret += rem / sz * val; rem %= sz;
    for(int i=0; i<rem; i++) ret += v[mp[x]-1+i];
    cout << ret;
}

F. Simplified Reversi

각 행 별로 가장 왼쪽에 있는 흰 돌의 위치, 각 열 별로 가장 위에 있는 흰 돌의 위치를 빠르게 갱신하고 구할 수 있으면 됩니다.
Segment Tree에 Lazy Propagation을 비벼먹으면 됩니다.

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
55
56
57
58
59
60
61
62
63
64
65
#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;

struct Seg{
    int tree[1 << 19], tmp[1 << 19];
    Seg(){ memset(tree, 0x3f, sizeof tree); memset(tmp, 0x3f, sizeof tmp); }
    void push(int node, int s, int e){
        if(tmp[node] >= 1e9) return;
        tree[node] = min(tree[node], tmp[node]);
        if(s != e){
            tmp[node << 1] = min(tmp[node << 1], tmp[node]);
            tmp[node << 1 | 1] = min(tmp[node << 1 | 1], tmp[node]);
        }
        tmp[node] = 1e9+7;
    }
    void update(int node, int s, int e, int l, int r, int v){
        push(node, s, e);
        if(r < s || e < l) return;
        if(l <= s && e <= r){
            tmp[node] = min(tmp[node], v); push(node, s, e); return;
        }
        int m = s + e >> 1;
        update(node << 1, s, m, l, r, v);
        update(node << 1 | 1, m+1, e, l, r, v);
        tree[node] = min(tree[node << 1], tree[node << 1 | 1]);
    }
    int query(int node, int s, int e, int l, int r){
        push(node, s, e);
        if(r < s || e < l) return 1e9+7;
        if(l <= s && e <= r) return tree[node];
        int m = s + e >> 1;
        return min(query(node << 1, s, m, l, r), query(node << 1 | 1, m+1, e, l, r));
    }
    void update(int l, int r, int v){ update(1, 1, 202020, l, r, v); }
    int query(int l, int r){ return query(1, 1, 202020, l, r); }
} seg_i, seg_j;

ll n, q, ans;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q; ans = (n-2) * (n-2);
    seg_i.update(1, n, n); seg_j.update(1, n, n);
    seg_i.update(n, n, 1); seg_j.update(n, n, 1);
    while(q--){
        int op, a; cin >> op >> a;
        if(op == 1){
            int t = seg_i.query(a, a);
            ans -= t-2;
            seg_j.update(1, t, a);
        }
        else{
            int t = seg_j.query(a, a);
            ans -= t-2;
            seg_i.update(1, t, a);
        }
    }
    cout << ans;
}