AtCoder ABC 184

작성일 | In

총평

체감 난이도: A = B < F < E < C < D
C: Atcoder Beginner Contest C말고 Codeforces Round Div.2 C에 나올 것 같은 문제
D: 좋은 기댓값 DP 연습 문제
E: 빈출 유형
F: Do you know Meet in the Middle?

A. Determinant

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);
    ll a, b, c, d; cin >> a >> b >> c >> d;
    cout << a*d - b*c;
}

B. Quizzes

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
/******************************
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 N, X; cin >> N >> X;
    for(int i=1; i<=N; i++){
        char c; cin >> c;
        if(c == 'o') X++;
        else X--;
        X = max(0, X);
    }
    cout << X;
}

C. Super Ryuma

ABC C답지 않게 생각할 것이 많은 문제입니다.
대각선 방향으로 이동하는 것을 2번만 하면, $(i + j) \mod 2$가 같은 모든 칸(체스판에서 색깔이 동일한 모든 칸)을 방문할 수 있습니다. 그러므로 최대 3번만 이동하면 모든 칸을 방문할 수 있습니다. 정답이 1, 2인 경우를 알아봅시다.

  • $\vert dx \vert = \vert dy \vert$인 경우 대각선 방향으로 1번 이동해서 도달할 수 있습니다.
  • $dx \equiv dy (\mod 2)$인 경우 대각선 방향으로 2번 이동해서 도달할 수 있습니다.
  • $\vert dx + dy \vert \leq 3 \cup \vert dx - dy \vert \leq 3$인 경우 대각선 방향으로 1번 이동하면 1번의 이동을 추가해서 원하는 곳으로 갈 수 있습니다. 갈 수 있는 범위를 그림으로 그려보면 쉽게 알 수 있습니다.
  • $\vert dx \vert + \vert dy \vert \leq 3$인 경우 1번 이동해서 도달할 수 있습니다.
  • $\vert dx \vert + \vert dy \vert \leq 6$인 경우 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
/******************************
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, c, d; cin >> a >> b >> c >> d;
    int dx = c - a, dy = d - b, ans = 3;
    if(dx == 0 && dy == 0){ cout << 0; return 0; }
    // 1 -> 2
    if((dx&1) == (dy&1)) ans = min(ans, 2);
    // 3
    if(abs(dx) + abs(dy) <= 3) ans = min(ans, 1);
    // 3 -> 3
    if(abs(dx) + abs(dy) <= 6) ans = min(ans, 2);
    // 1 or 2
    if(dx == dy || dx == -dy) ans = min(ans, 1);
    // 1 -> 3 or 2 -> 3
    if(abs(dx+dy) <= 3 || abs(dx-dy) <= 3) ans = min(ans, 2);
    cout << ans;
}

D. increment of coins

간단한 기댓값 DP 문제입니다.
$D(a, b, c)$: 동전이 각 색깔 별로 $a$, $b$, $c$개 있을 때 100개를 만들기 위해 취해야 하는 행동 횟수의 기댓값으로 정의합시다.
$D(a, b, c) = \frac{a}{a+b+c}D(a+1, b, c) + \frac{b}{a+b+c}D(a, b+1, c) + \frac{c}{a+b+c}D(a, b, c+1)$으로 계산할 수 있습니다.
단, $\max(a, b, c) = 100$이면 $D(a, b, c) = 0$입니다.

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
/******************************
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;

struct Info{
    int a, b, c;
    Info() = default;
    Info(int a, int b, int c) : a(a), b(b), c(c) {}
};

int A, B, C;
double D[111][111][111];

double f(int i, int j, int k){
    double &res = D[i][j][k];
    if(res >= 0) return res;
    if(i == 100 || j == 100 || k == 100) return 0;
    double base = i + j + k;
    res = 0;
    res += i * (f(i+1, j, k) + 1) / base;
    res += j * (f(i, j+1, k) + 1) / base;
    res += k * (f(i, j, k+1) + 1) / base;
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> A >> B >> C;
    for(int i=0; i<111; i++) for(int j=0; j<111; j++) for(int k=0; k<111; k++) D[i][j][k] = -1;
    cout << fixed << setprecision(10) << f(A, B, C);
}

E. Third Avenue

각 알파벳을 담당하는 정점 $V(c)$를 새로 만들어줍시다.
$a_{i, j} = c$라면 $(i, j)$에서 $V(c)$로 들어가는 가중치 0인 간선, $V(c)$에서 $(i, j)$로 나가는 가중치 0인 간선을 추가하고, $V(c)$를 지나갈 때 가중치 1을 부여합시다.
정점에 가중치가 있는 것을 처리하기 힘들기 때문에, $V(c)$ 정점을 들어가는 정점과 나가는 정점으로 분할한 다음, 두 간선을 가중치가 1인 간선으로 연결하면 쉽게 처리할 수 있습니다.

최단 경로를 구하는 것은 Dijkstra를 쓰면 $O(E \log V)$, 0-1 BFS를 쓰면 $O(V+E)$에 문제를 해결할 수 있습니다. 이때 $V = E = O(HW)$입니다.

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
/******************************
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;
typedef pair<int, int> P;
const int di[] = {1, -1, 0, 0};
const int dj[] = {0, 0, 1, -1};
const int ID(char c){ return c - 'a'; }
const int ID(int i, int j){ return i*2001+j; }

int N, M, S, T;
char A[2020][2020];
vector<P> G[4040404];
int D[4040404];

void Connect(int s, int e, int x){
    G[s].emplace_back(e, x);
}

void RegisterChar(int i, int j, char c){
    Connect(ID(i, j), ID(c) << 1, 0);
    Connect(ID(c) << 1 | 1, ID(i, j), 0);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(char i='a'; i<='z'; i++) Connect(ID(i)<<1, ID(i)<<1|1, 1);
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) {
        cin >> A[i][j];
        if(A[i][j] == '.' || A[i][j] == '#') continue;
        else if(A[i][j] == 'S') S = ID(i, j);
        else if(A[i][j] == 'G') T = ID(i, j);
        else RegisterChar(i, j, A[i][j]);
    }
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) {
        if(A[i][j] == '#') continue;
        for(int k=0; k<4; k++){
            int ii = i + di[k], jj = j + dj[k];
            if(ii < 1 || jj < 1 || ii > N || jj > M || A[ii][jj] == '#') continue;
            Connect(ID(i, j), ID(ii, jj), 1);
        }
    }
    memset(D, 0x3f, sizeof D);
    deque<int> q; q.push_back(S); D[S] = 0;
    while(q.size()){
        int v = q.front(); q.pop_front();
        for(auto i : G[v]){
            if(D[i.x] <= D[v] + i.y) continue;
            D[i.x] = D[v] + i.y;
            if(i.y == 0) q.push_front(i.x);
            else q.push_back(i.x);
        }
    }
    if(D[T] < 1e9) cout << D[T];
    else cout << -1;
}

F. Programming Contest

$N \leq 40$? Do you know Meet in the Middle?
Bitmask를 하면 $O(N \cdot 2^N)$에 문제를 해결할 수 있습니다. 주어지는 데이터를 절반씩 나눠서 각각 Brute Force한 다음 이분 탐색을 통해 결과를 합치면 $O(2^{N/2} \log 2^{N/2}) = O(N \cdot 2^{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
36
37
38
39
40
41
42
43
/******************************
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, T, A[44];

vector<ll> Make(const vector<ll> &V){
    int M = V.size();
    vector<ll> ret;
    for(int bit=0; bit<(1<<M); bit++){
        ll now = 0;
        for(int i=0; i<M; i++) if(bit & (1 << i)) now += V[i];
        ret.push_back(now);
    }
    sort(all(ret));
    return move(ret);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> T; for(int i=0; i<N; i++) cin >> A[i];
    vector<ll> a, b;
    for(int i=0; i<N/2; i++) a.push_back(A[i]);
    for(int i=N/2; i<N; i++) b.push_back(A[i]);
    a = Make(a); b = Make(b);
    ll ans = 0;
    for(auto i : a){
        auto it = upper_bound(all(b), T - i);
        if(it == b.begin() || *--it + i > T) continue;
        ans = max(ans, *it + i);
    }
    cout << ans;
}