AtCoder Beginner Contest 343 후기

작성일 | In

A - Wrong Answer

$0$과 $9$ 사이 양의 정수 $A$와 $B$가 주어지고, $A+B$가 아닌 수를 $0$에서 $9$사이 아무 수나 출력하면 됩니다. $(A+B+1)\%10$을 출력하면 언제나 $A+B$가 아닌 수를 출력할 수 있습니다. 2초만 더 빨리 풀었으면 세계 1등인데 까비..

1
2
3
4
5
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int a, b; cin >> a >> b;
    cout << ((a+b)+1)%10 <<'\n';
}

B - Adjacency Matrix

제목 그대로 Adjacency matrix를 만들고 출력하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    vector<vector<int>> g(n, vector<int>(n));
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> g[i][j];
            if(g[i][j]) {
                cout << j+1 << ' ';
            }
        }
        cout << '\n';
    }
}

C - 343

$N(1 \leq N \leq 10^{18})$이하인 palindrome인 세제곱수를 출력하면 되는 문제입니다. 가능한 세제곱수의 base가 $10^6$개라 전부 해보면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool pal(ll v) {
    vector<ll> a;
    while(v) {
        a.pb(v % 10); v /= 10;
    }
    for(int i=0; i<sz(a); i++) {
        if(a[i] != a[sz(a)-1-i]) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    ll n; cin >> n;
    ll ans = -1;
    for(ll i=1; i*i*i<=n; i++) {
        ll v = i*i*i;
        if(pal(v)) {
            ans = v;
        }
    }
    cout << ans << '\n';
}

D - Diversity of Scores

사람 $N$명이 있고, 모두 0점에서 시작합니다. $T(1\leq T\leq2\times10^5)$개의 쿼리가 $a$ $b$꼴로 주어집니다. 이는 사람 $a$에게 $b$점을 추가해주는 쿼리입니다. 각 쿼리 이후 unique한 점수의 갯수를 출력하면 됩니다.

map<long long,int> 꼴로 특정 점수가 몇개가 있는지 관리를 하고, map key의 갯수를 세어주면 됩니다. map의 value가 0이 될 때 원소를 삭제해 주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, t; cin >> n >> t;
    vector<ll> a(n);
    map<ll, int> mp;
    mp[0] = n;
    for(int i=0; i<t; i++) {
        int u; cin >> u; u--;
        ll x; cin >> x;
        mp[a[u]]--;
        if(mp[a[u]] == 0) mp.erase(mp.find(a[u]));
        a[u] += x;
        mp[a[u]]++;
        cout << sz(mp) << '\n';
    }
}

E - 7x7x7

7x7x7 큐브 세개 중 세 큐브가 겹치는 공간, 두 큐브만 겹치는 공간, 한 큐브에만 속한 공간이 $V_3,V_2, V_1$를 만족하는 큐브의 좌표를 찾는 문제입니다. 우선 한 큐브를 $(0,0,0)$에 고정하고, 다른 두개의 큐브만 위치를 생각하면 됩니다. 다른 큐브들이 유의미하게 있을 수 있는 좌표는 각각 $(-7\sim7, -7\sim7,-7\sim7)$입니다. 그 밖을 벗어나게 되면 어차피 안 겹치므로 $(7,7,7)$에 있는 것과 동일한 효과를 가지기 때문입니다. 3개의 좌표를 정하고 각각 $V_1, V_2, V_3$를 $O(1)$에 구할 수 있으면 $O(14^6)$만에 문제를 풀 수 있습니다.

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
int v1, v2, v3;

bool vol2(int x1, int y1, int z1, int x2, int y2, int z2) {
    int mx1 = max(x1, x2);
    int mx2 = min(x1+7, x2+7);
    int my1 = max(y1, y2);
    int my2 = min(y1+7, y2+7);
    int mz1 = max(z1, z2);
    int mz2 = min(z1+7, z2+7);
    if(mx1<mx2&&my1<my2&&mz1<mz2) {
        return (mx2-mx1) * (my2-my1) * (mz2-mz1);
    } else return 0;
}

int vol(int x1, int y1, int z1, int x2, int y2, int z2, int x3, int y3, int z3) {
    int ans = 7 * 7 * 7 * 3;
    int mx1 = max({x1, x2, x3});
    int mx2 = min({x1+7, x2+7, x3+7});
    int my1 = max({y1, y2, y3});
    int my2 = min({y1+7, y2+7, y3+7});
    int mz1 = max({z1, z2, z3});
    int mz2 = min({z1+7, z2+7, z3+7});
    int rv3 = 0;
    if(mx1<mx2&&my1<my2&&mz1<mz2) {
        rv3 = (mx2-mx1) * (my2-my1) * (mz2-mz1);
    }
    int rv2 = 0;
    rv2 += vol2(x1, y1, z1, x2, y2, z2);
    rv2 += vol2(x2, y2, z2, x3, y3, z3);
    rv2 += vol2(x3, y3, z3, x1, y1, z1);
    rv2 -= rv3 * 3;
    int rv1 = 7 * 7 * 7 * 3 - rv2 * 2 - rv3 * 3;
    if(rv1 == v1 && rv2 == v2 && rv3 == v3) return 1;
    return 0;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> v1 >> v2 >> v3;
    for(int x1=-7; x1<=7; x1++) for(int y1=-7; y1<=7; y1++) for(int z1=-7; z1<=7; z1++) {
        for(int x2=-7; x2<=7; x2++) for(int y2=-7; y2<=7; y2++) for(int z2=-7; z2<=7; z2++) {
            if(vol(0,0,0,x1,y1,z1,x2,y2,z2)) {
                cout << "Yes\n";
                cout << 0 << ' ' << 0 << ' ' << 0 << ' ';
                cout << x1 << ' ' << y1 << ' ' << z1 << ' ';
                cout << x2 << ' ' << y2 << ' ' << z2 << '\n';
                return 0;
            }
        }
    }
    cout << "No\n";
}

F - Second Largest Query

$N(1\leq N \leq 2\times 10^5)$개의 원소가 있는 배열이 주어집니다. 다음과 같은 쿼리를 처리하면 됩니다.
1 p x : $A_p$를 $x$로 바꿉니다.
2 l r : $A_l, A_{l+1},\cdots ,A_r$ 중 두번째로 큰 원소의 등장 횟수를 출력합니다. 만약 두번째로 큰 원소가 없다면 0을 출력합니다.

최댓값, 최댓값의 등장횟수, 2번째로 큰 값, 2번째로 큰 값의 등장 횟수를 관리하는 세그먼트 트리를 이용해서 문제를 풀 수 있습니다.

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
66
67
68
69
70
71
72
73
74
75
76
77
struct Node {
    ll mx, mx2, mxocc, mx2occ;
};

class SegmentTree {
public:
    vector<Node> seg;
    int n;
    SegmentTree(int n) {
        seg.resize(4 * n + 5);
        this->n = n;
    }
    Node op(Node a, Node b) {
        Node ret;
        map<ll, int> mp;
        mp[a.mx] += a.mxocc;
        mp[a.mx2] += a.mx2occ;
        mp[b.mx] += b.mxocc;
        mp[b.mx2] += b.mx2occ;
        vector<pair<ll, int>> c;
        for(auto x : mp) c.pb(x);
        sort(all(c), [](pair<ll, int> x, pair<ll, int> y){
            return x.ff > y.ff; 
        });
        ret.mx = c[0].ff; ret.mxocc = c[0].ss;
        if(sz(c) >= 2) ret.mx2 = c[1].ff, ret.mx2occ = c[1].ss;
        else ret.mx2 = 0, ret.mx2occ = 0;
        return ret;
    }
    Node upd_(int idx, int l, int r, int pos, ll val) {
        if (pos < l || pos > r) return seg[idx];
        if (pos == l && pos == r) {
            seg[idx].mx = val;
            seg[idx].mxocc = 1;
            seg[idx].mx2 = 0;
            seg[idx].mx2occ = 0;   
            return seg[idx]; 
        }
        int mid = (l + r) / 2;
        return seg[idx] = op(upd_(idx * 2, l, mid, pos, val),
                upd_(idx * 2 + 1, mid + 1, r, pos, val));
    }
    Node calc_(int idx, int l, int r, int tl, int tr) {
        if (tl > tr) return {0, 0, 0, 0};
        if (tl == l && tr == r) return seg[idx];
        int mid = (l + r) / 2;
        return op(calc_(idx * 2, l, mid, tl, min(tr, mid)),
            calc_(idx * 2 + 1, mid + 1, r, max(mid + 1, tl), tr));
    }
    void upd(int pos, ll val) {
        upd_(1, 0, n - 1, pos, val);
    }
    Node calc(int l, int r) {
        return calc_(1, 0, n - 1, l, r);
    } 
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q; cin >> n >> q;
    vector<ll> a(n);
    SegmentTree st(n);
    for(int i=0; i<n; i++) {
        cin >> a[i];
        st.upd(i, a[i]);
    }
    for(int i=0; i<q; i++) {
        int op; cin >> op;
        if(op == 1) {
            int p, x; cin >> p >> x; p--;
            st.upd(p, x);
        } else {
            int l, r; cin >> l >> r; l--, r--;
            cout << st.calc(l, r).mx2occ << '\n';
        }
    }
}

G - Compress Strings

$N(1\leq N\leq20)$개의 문자열 $S_1, \cdots, S_N(\sum len(S_i)\leq2\times10^5)$이 주어집니다. $N$개의 문자열을 모두 substring으로 포함하는 하나의 문자열 $T$의 최소 길이를 구하는 문제입니다.

우선 한 문자열이 다른 문자열의 substring이 되는 문자열은 제거를 해줍니다. 이 작업은 후술할 dp가 작동하기 위해 꼭 필요한 과정입니다. 모든 $i$와 $j$ 쌍에 대하여 $f(i,j) = i$번째 문자열의 suffix와 $j$​번째 문자열의 prefix가 최대로 얼마나 겹치는지 구해놓았다면 TSP 문제의 dp를 푸는 것처럼 문제를 풀 수 있습니다. 만약 문자열 제거 과정이 없었다면 마지막으로 사용한 문자열의 끝이 다음 문자열의 끝보다 전에 끝난다는 보장을 할 수 없기 때문에 제거 과정이 필요합니다.

$f(i,j)$는 KMP나 Suffix Array와 같은 문자열 알고리즘으로 효율적으로 구할 수 있습니다. 저는 KMP를 까먹어서 SA를 사용하였습니다.

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
string s = "";
string t = "!@#$%^&*()_+{}:<>,.1234567";
vector<int> pos;
vector<int> start;
vector<vector<int>> pref;
int nn;
vector<int> craig;
vector<int> szzz;

int baeje = 0;

void make_sa(string &s) {
    int n = sz(s), m = max(256, n)+1;
    vector<int> r(n*2), nr(n*2);
    vector<int> sa(n), isa(n), cnt(m), idx(n), lcp(n), poss(n);
    for(int i=0 ; i<n ; i++) sa[i] = i, r[i] = s[i];
    for(int d=1 ; d<n ; d *= 2){
        auto cmp = [&](int i,int j){
            return r[i] < r[j] || (r[i] == r[j] && r[i+d] < r[j+d]); };

        for(int i=0 ; i<m ; i++) cnt[i] = 0;
        for(int i=0 ; i<n ; i++) cnt[r[i+d]]++;
        for(int i=1 ; i<m ; i++) cnt[i] += cnt[i-1];
        for(int i=n-1 ; ~i ; i--) idx[--cnt[r[i+d]]] = i;

        for(int i=0 ; i<m ; ++i) cnt[i] = 0;
        for(int i=0 ; i<n ; ++i) cnt[r[i]]++;
        for(int i=1 ; i<m ; ++i) cnt[i] += cnt[i-1];
        for(int i=n-1 ; ~i ; --i) sa[--cnt[r[idx[i]]]] = idx[i];

        nr[sa[0]] = 1;
        for(int i=1 ; i<n ; ++i) nr[sa[i]] = nr[sa[i-1]] + cmp(sa[i-1], sa[i]);
        for(int i=0 ; i<n ; ++i) r[i] = nr[i];

        if(r[sa[n-1]]==n) break;
    }
    for(int i=0 ; i<n ; i++) {
        isa[sa[i]] = i;
    }
    for(int k=0, i=0 ; i<n ; i++) if(isa[i]) {
        for(int j=sa[isa[i]-1]; s[i+k]==s[j+k]; ++k);
        lcp[isa[i]] = (k ? k-- : 0);
    }
    for(int i=0; i<n; i++) {
        poss[sa[i]] = i;
    }
    // lcp[i] = s[i], s[i-1]의 lcp 길이
    for(int i=0; i<nn; i++) {
        int mx = INF;
        for(int j=poss[start[i]]; j>0; j--) {
            mx = min(mx, lcp[j]);
            if(mx >= craig[start[i]]) {
                baeje |= (1<<i);
            }
            // j-1번째 lcp
            if(mx == 0) break;
            if(craig[sa[j-1]] == mx) {
                pref[i][pos[sa[j-1]]] = max(pref[i][pos[sa[j-1]]], mx);
            }
        } 
        mx = INF;
        for(int j=poss[start[i]]+1; j<sz(sa); j++) {
            mx = min(mx, lcp[j]);
            if(mx >= craig[start[i]]) {
                baeje |= (1<<i);
            }
            if(mx == 0) break;
            if(craig[sa[j]] == mx) {
                pref[i][pos[sa[j]]] = max(pref[i][pos[sa[j]]], mx);
            }
        }
    } 
}

vector<vector<int>> dp;

int dfs(int mask, int id) {
    int& ret = dp[mask][id];
    if(ret != -1) return ret;
    if(mask == (1<<nn)-1) return 0; 
    ret = INF;
    for(int i=0; i<nn; i++) if(!(mask & (1<<i))) {
        ret = min(ret, szzz[i] - pref[i][id] + dfs(mask | (1<<i), i));
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    int shit = 0;
    set<string> st;
    for(int i=0; i<n; i++) {
        string v; cin >> v;
        if(st.count(v)) {
            shit++;
            continue;
        }
        st.insert(v);
        szzz.pb(sz(v));
        s += v; s += t[i];
        start.pb(sz(pos));
        int x = sz(v);
        for(int j=0; j<sz(v)+1; j++) {
            craig.pb(x--);
            pos.push_back(i-shit);
        }
    }
    n -= shit;
    nn = n;
    pref = vector<vector<int>>(n, vector<int>(n));
    int id = 0;
    make_sa(s);
    dp = vector<vector<int>>(1<<n, vector<int>(n, -1));
    ll ans = INF;
    for(int i=0; i<n; i++) {
        ans = min(ans, szzz[i] + (ll)dfs(baeje|(1<<i), i));
    }
    cout << ans << '\n';
}