AtCoder ARC 035

작성일 | In

결과

다 풀었습니다. D는 수업에서 튜토리얼용으로 쓰기 좋은 문제인 것 같습니다.

A. 高橋くんと回文

주어진 문자열에서 * 을 적절한 문자로 바꿔서 회문으로 만들 수 있는지 판별하는 문제입니다.

단순 구현 문제입니다.

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);
    string a; cin >> a;
    int s = 0, e = a.size()-1, flag = 1;
    while(s <= e){
        if(a[s] != '*' && a[e] != '*' && a[s] != a[e]) flag = 0;
        s++; e--;
    }
    if(flag) cout << "YES";
    else cout << "NO";
    cout << "\n";
}

B. アットコーダー王国のコンテスト事情

$T_1, T_2, \ldots , T_N$이 주어집니다. $T_i$는 $i$번째 문제를 풀 때 걸리는 시간이며, 모든 문제를 풀면서 패널티를 최소화하는 것이 목적입니다. 패널티의 최솟값과 최솟값을 만드는 경우의 수를 출력하는 문제입니다.

시간이 적게 걸리는 문제부터 푸는 것이 최적인 것은 직관적으로 알 수 있습니다.
cnt[t] = 푸는데 t만큼의 시간이 걸리는 문제들의 개수로 정의하면 경우의 수는 모든 $i$에 대해 $cnt_i!$을 곱한 값과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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 ll mod = 1e9+7;

ll n, a[10101], cnt[10101], fac[10101], pan, ti;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    fac[0] = 1; for(int i=1; i<10101; i++) fac[i] = fac[i-1] * i % mod;
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i]; sort(a+1, a+n+1);
    for(int i=1; i<=n; i++){
        ti += a[i]; pan += ti; cnt[a[i]]++;
    }
    ll ans = 1;
    for(int i=0; i<10101; i++) ans = ans * fac[cnt[i]] % mod;
    cout << pan << "\n" << ans << "\n";
}

C. アットコーダー王国の交通事情

그래프가 주어졌을 때, $i < j$인 모든 $i, j$에 대해 $i$와 $j$ 사이의 최단 거리의 합을 구하는 문제입니다.
정점 $u, v$를 잇는 간선을 추가하는 쿼리도 주어지고, 쿼리가 주어질 때마다 합을 계산해서 출력해야 합니다.

모든 정점 쌍 사이의 최단 거리는 Floyd-Warshall을 이용해서 $O(N^3)$에 구할 수 있습니다.
Floyd-Warshall을 이용해 모든 정점 쌍 사이의 거리를 구해놓았을 때, 간선 $(u, v)$가 추가된 상황을 생각해봅시다.

$i$에서 $j$로 가는 최단 경로는

  1. 이미 구해놓은 i -> j 경로 (g[i][j])
  2. i에서 u로 간 다음, 새로 추가된 간선을 따라 v로 간 뒤, v에서 j로 이동 (g[i][u] + cst + g[v][j])
  3. i에서 v로 간 다음, 새로 추가된 간선을 따라 u로 간 뒤, u에서 j로 이동 (g[i][v] + cst + g[u][j])

모든 정점 쌍에 대해 $O(N^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
#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, m, g[444][444];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for(int i=1; i<=n; i++) g[i][i] = 0;
    for(int i=1; i<=m; i++){
        int s, e, x; cin >> s >> e >> x;
        g[s][e] = min(g[s][e], x);
        g[e][s] = min(g[e][s], x);
    }
    for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    }
    int q; cin >> q;
    while(q--){
        int a, b, c; cin >> a >> b >> c;
        ll sum = 0;
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
            g[i][j] = min({g[i][j], g[i][a] + g[b][j] + c, g[i][b] + g[a][j] + c});
            if(i < j) sum += g[i][j];
        }
        cout << sum << "\n";
    }
}

D. 高橋くんとマラソンコース

격자 위에 $N$개의 점 $A_1, A_2, \ldots , A_N$이 있고, 아래 2가지 쿼리가 주어집니다.

  • 1 k r c : $A_k$를 $(r, c)$로 바꾼다.
  • 2 a b c d : ($A_a, A_{a+1}, \ldots , A_b$를 지나는 최단 경로의 경우의 수)와 ($A_c, A_{c+1}, \ldots , A_d$를 지나는 최단 경로의 경우의 수) 중에서 어떤 것이 더 많은지 판별한다. 전자가 더 많다면 FIRST를, 후자가 더 많다면 SECOND를 출력한다.

2번 쿼리에서 (경우의 수가 많은 쪽의 경우의 수) ≥ (경우의 수가 적은 쪽의 경우의 수) × 2

$(x1, y1)$과 $(x2, y2)$를 잇는 최단 경로의 경우의 수는 $dx = \vert x1 - x2 \vert , dy = \vert y1 - y2 \vert$라고 하면, $\frac{(dx+dy)!}{dx! dy!}$으로 나타낼 수 있습니다. 물론 이걸 그냥 저장하기에는 너무 크기 때문에, 로그를 씌워서 저장해줘야 합니다.
$\log((dx+dy)!) - \log(dx!) - \log(dy!)$와 같이 나타낼 수 있다.

2번 쿼리에서 구하게 되는 두 값은 두 배 이상 차이나는 것이 보장됩니다. 우리는 그 값들을 로그를 씌워서 저장할 것이기 때문에, 실수오차를 log(2)까지 허용한다고 이해할 수 있습니다. 실수 오차를 굳이 신경쓰지 않아도 됩니다.

로그를 씌웠기 때문에 2번 쿼리는 구간 합 쿼리로 생각할 수 있고, 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
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
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;

int n, q, x[2020202], y[2020202];
double lg[2020202];

double tree[1 << 19];
const int sz = 1 << 18;
void update(int x, double v){
    x |= sz; tree[x] = v;
    while(x >>= 1) tree[x] = tree[x << 1] + tree[x << 1 | 1];
}
double query(int l, int r){
    l |= sz; r |= sz; double ret = 0;
    while(l <= r){
        if(l & 1) ret += tree[l++];
        if(~r & 1) ret += tree[r--];
        l >>= 1; r >>= 1;
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    lg[1] = 0; for(int i=2; i<2020202; i++) lg[i] = lg[i-1] + log(i);
    cin >> n; for(int i=1; i<=n; i++) cin >> x[i] >> y[i];
    for(int i=1; i<n; i++){
        int dx = x[i+1] - x[i], dy = y[i+1] - y[i];
        update(i, lg[dx+dy] - lg[dx] - lg[dy]);
    }
    cin >> q;
    while(q--){
        int op; cin >> op;
        if(op == 1){
            int idx, a, b; cin >> idx >> a >> b;
            x[idx] = a; y[idx] = b;
            if(idx > 1){
                int dx = x[idx] - x[idx-1], dy = y[idx] - y[idx-1];
                update(idx-1, lg[dx+dy] - lg[dx] - lg[dy]);
            }
            if(idx < n){
                int dx = x[idx+1] - x[idx], dy = y[idx+1] - y[idx];
                update(idx, lg[dx+dy] - lg[dx] - lg[dy]);
            }
        }
        else{
            int a, b, c, d; cin >> a >> b >> c >> d;
            double t1 = query(a, b-1), t2 = query(c, d-1);
            if(t1 > t2) cout << "FIRST\n";
            else cout << "SECOND\n";
        }
    }
}