Atcoder Begginer Contest 201

F가 꽤 어려운 라운드였던 거 같다. 그리고 D나 E는 꽤 전형적인 문제인데 모르면 처음에 떠올리기 어려운 문제들이다.

이해가 안되거나 설명이 부족하다 싶거나 잘못된 내용은 댓글로 말해주시면 감사하겠습니다.

A - Tiny Arithmetic Sequence

만약에 세 숫자가 등차수열을 이룬다면 정렬했을 때 그 순서대로 공차가 같을 것이다. 이걸로 해결할 수 있다.

#include<bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v(3);
    for (int i = 0; i < 3; ++i) cin >> v[i];
    sort(v.begin(), v.end());
    if (v[1] - v[0] == v[2] - v[1]) cout << "Yes" << '\n';
    else cout << "No" << '\n';
    return 0;
}

B - Do you know the second highest moutain?

모든 높이가 다르기 때문에 높이가 같을 때에 대해서 고민할 필요도 없고 정렬하고 두번째 원소를 출력하면 된다.

#include<bits/stdc++.h>
using namespace std;

int N;
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    vector<pair<int, string>> v(N);
    for (int i = 0; i < N; ++i) cin >> v[i].second >> v[i].first;
    sort(v.begin(), v.end(), greater<>());
    cout << v[1].second << '\n';
    return 0;
}

C - Secret Number

가능한 경우는 0000~9999가 전부로 만 개밖에 안된다. 전부 시도해보자.

#include<bits/stdc++.h>
using namespace std;
int ans;
bool used[10];

int main() {
    string s; cin >> s;
    for (int i = 0; i < 10000; ++i) {
        string a;
        int t = i;
        memset(used, false, sizeof(used));
        for (int j = 0; j < 4; ++j) {
            used[t % 10] = true;
            t /= 10;
        }
        bool flag = true;
        for (int i = 0; i < 10; ++i) {
            if (s[i] == 'o' && !used[i]) flag = false;
            else if (s[i] == 'x' && used[i]) flag = false;
        }
        ans += flag;
    }
    cout << ans << '\n';
    return 0;
}

D - Game in Momotetsu World

플레이어 둘이서 최선의 전략으로 플레이 했을 때 누가 이길지를 결정해야 한다. 영어 디스크립션이 좀 그렇다고 생각한다. best outcome 말고 그냥 승자를 정하라고 하지..

일단 격자 그래프에서 오른쪽 혹은 아래로만 움직이기 때문에 어떤 셀에 piece가 위치 했을 때 누가 돌을 움직일지가 결정된다. i+j가 짝수일 땐 (i, j)에서 Takahashi가 움직이고 홀수일 땐 Aoki가 움직인다.

승패에 영향을 끼치는 것은 결국 둘 사이의 점수 차이기 때문에 이 차이를 가지고 dp식을 세워볼 수 있다.

$dp(i, j)$를 타카하시의 점수 빼기 아오키의 점수로 놓는데 타카하시가 움직일 턴이라면 $dp(i, j)$는 이 값의 달성 가능한 최댓값이라고 하고, 아오키가 움직일 턴이라면 이 값의 달성 가능한 최댓값 중에서 최솟값이라고 하자.

이러한 min-max DP를 생각할 수 있고 $dp(N, M)=0$으로 놓고 테이블을 채우면 된다. 그리고 $dp(1,1)$의 값에 따라서 승패를 정하면 된다.

상태 전이는 아래와 같다.
$$
\begin{aligned}
dp(i, j) = \min(dp(i+1, j)-a(i+1, j), dp(i, j+1)-a(i, j+1)) \text{ if i+j is odd}\\
dp(i, j) = \max(dp(i+1, j)+a(i+1, j), dp(i, j+1)+(i, j+1)) \text{ if i+j is even}
\end{aligned}
$$

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int N, M;
int dp[2005][2005];
int a[2005][2005];

int solve(int y, int x) {
    int& ret = dp[y][x];
    if (abs(ret) != INF) return ret;
    if (y + 1 <= N) {
        if ((x + y) % 2) ret = min(ret, solve(y + 1, x) - a[y + 1][x]);
        else ret = max(ret, solve(y + 1, x) + a[y + 1][x]);
    }
    if (x + 1 <= M) {
        if ((x + y) % 2) ret = min(ret, solve(y, x + 1) - a[y][x + 1]);
        else ret = max(ret, solve(y, x + 1) + a[y][x + 1]);
    }
    return ret;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        string s; cin >> s;
        for (int j = 1; j <= M; ++j) {
            if (s[j - 1] == '+') a[i][j] = 1;
            else a[i][j] = -1;
        }
    }
    for (int i = 1; i <= N; ++i) for (int j = 1; j <= M; ++j) {
        dp[i][j] = (i+j)%2? INF : -INF;
    }
    dp[N][M] = 0;
    int ans = solve(1, 1);
    if (ans > 0) cout << "Takahashi" << '\n';
    else if (ans < 0) cout << "Aoki" << '\n';
    else cout << "Draw" << '\n';
    return 0;
}

E - Xor Distances

트리가 주어지고 모든 정점 간의 경로들에 대해서 경로의 간선 가중치들을 xor한 것들의 합을 구하라는 것이다.

트리 DP를 통해서 이 값을 구해보자. 방식은 트리의 가중치란 문제와 비슷하다.

$one(i, j)$를 $i$를 루트로 하는 서브트리에서 $i$와의 경로의 xor 값에서 $j$번째 비트가 1인 것의 갯수라고 놓자. 이와 비슷하게 $zero(i, j)$도 정의하자.

어떤 노드 $u$를 루트로 하는 서브트리에서 $u$의 자식노드들 $v$를 루트로 하는 서브트리에 대해서 위 값들을 구해놨다고 치자.

그러면 이제 $u$의 자식서브트리와 자식서브트리 사이의 경로들은 $u$를 지나갈 것이다. 이러한 경로들에 대해서 원하는 값을 빠르게 구할 수 있으면 이제 트리 DP를 돌려서 답을 구할 수 있을 것이다.

이제 $u$의 자식을 각각 $v, v'$라고 하고 간선 $(u, v)$의 가중치를 $w$, 간선 $(u, v')$의 가중치를 $w'$라고 하자.

$w$의 $j$번째 비트가 1이라면 $one(u, j)$에 $zero(v, j)$가 더해지고 $zero(u, j)$에는 $one(v, j)$가 더해진다. 이런식으로 $zero(u, j)$와 $one(u, j)$에서 $v, v'$가 각각 얼마나 영향을 끼치는지는 계산이 가능하다.

그러면 이제 그 영향을 끼치는 것들의 갯수를 $cnt_{one}(v, j)$, $cnt_{zero}(v, j)$라고 하면 답에 대해서 두 서브트리가 공헌하게 되는 값은 $\sum_j cnt_{zero}(v, j) \times cnt_{one}(v', j) + cnt_{one}(v, j) \times cnt_{zero}(v',j)$이 된다. 그리고 이건 누적하면서 계산해도 쉽게 계산이 되기 때문에 DFS한번으로 전부 처리가 가능하다.

시간복잡도는 $O(N\log{X})$이 되겠다. $X=2^{60}$이다.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using mint = atcoder::modint1000000007;
using ll = long long;
mint pw[60];
mint ans;
mint one[200005][60], zero[200005][60];
vector<vector<pair<int, ll>>> G(200005);
int N;

void dfs(int cur, int par) {
    for (int i = 0; i < 60; ++i) zero[cur][i] = 1;
    for (pair<int, ll> p : G[cur]) {
        int nxt = p.first;
        ll w = p.second;
        if (nxt == par) continue;
        dfs(nxt, cur);
        for (int i = 0; i < 60; ++i) {
            if (w & (1ll << i)) {
                ans += pw[i] * zero[nxt][i] * zero[cur][i];
                ans += pw[i] * one[nxt][i] * one[cur][i];
                zero[cur][i] += one[nxt][i];
                one[cur][i] += zero[nxt][i];
            }
            else {
                ans += pw[i] * one[nxt][i] * zero[cur][i];
                ans += pw[i] * zero[nxt][i] * one[cur][i];
                zero[cur][i] += zero[nxt][i];
                one[cur][i] += one[nxt][i];
            }
        }
    }
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    pw[0] = 1;
    for (int i = 1; i < 60; ++i) pw[i] = pw[i - 1] * 2;
    cin >> N;
    for (int i = 1; i < N; ++i) {
        ll u, v, w; cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    dfs(1, 0);
    cout << ans.val() << '\n';
    return 0;
}

F - Insertion Sort

일단 연산의 순서에는 아무 제한이 없기 때문에 한 원소당 최대 한 번의 연산만 하면 충분하다.

최대 한 번이기 때문에 연산이 필요 없는 원소들은 어떤 게 있을지 생각해보자. 원하는 상태는 정렬된 상태이기 때문에 이미 정렬된 상태의 것들은 연산을 할 필요가 없다. 이를 통해서 임의의 증가 부분 수열을 잡았다면 그 부분 수열의 원소들은 연산을 할 필요가 없다는 것을 알 수 있다.

그러면 부분 수열 외의 원소들을 생각해보자. 일단 이 증가 부분수열에서 제일 작은 값을 $a$, 제일 큰 값을 $b$라고 하자.

$a < x < b$인 $x$에 대해서는 $A$ 연산 말고는 사용할 수 있는 것이 없다. $x<a$에 대해서는 $A, B$를 사용가능하고 $x>b$에 대해서는 $A, C$가 사용가능하다.

그러면 어떤 부분 증가 수열을 잡았다면 그 때의 최솟값은 아래처럼 정할 수 있다. 일단 그 수열을 $S$라고 하자.
$$
\sum_{i=1}^{a-1} \min(A_i, B_i) + \sum_{i \notin S, a<i<b} A_i + \sum_{i=b+1}^N \min(A_i, C_i)
$$
이제 LIS를 구하는 방식을 그대로 사용해보자. 어떤 증가수열에서 제일 큰 원소를 $b$라고 했을 때 제일 뒤의 $\min(A_i, C_i)$와 관련된 값은 $b$에 의존하는 누적합이고 앞에 값들은 $S$에서 $b$보다 작으면서 제일 큰(두번째로 큰)원소에 의존한다.

이걸 이용해서 $dp(i)$를 $1$부터 $i$까지 정렬했을 때의 최솟값이라고 하자.
$$
dp(i) = \min(\sum_{j=1}^{i-1} \min(A_i, B_i), \underset{j<i, pos_j < pos_i}{\min}{(dp(j)+\sum_{k=j+1}^{i-1}A_k)}
$$
그리고 전체를 정렬하는 비용은 $dp(i) + \sum_{j=i+1}^N \min(A_i, C_i)$가 될 것이다.

$dp(i)$의 두번째 식 때문에 나이브하게 구하면 $O(N^2)$이 걸리지만 $\min$안의 시그마는 $A_i$의 누적합으로 분해해보면 $\min$안의 값을 오롯이 $j$에 의존하는 값으로 바꿀 수 있기 때문에 구간 최소쿼리를 처리하면 되는 형식으로 바뀐다. 이건 세그트리로 $O(\log N)$만에 된다. 따라서 모든 $dp(i)$를 구하는 데에 $O(N \log{N})$이 걸린다.

이걸로 문제를 해결할 수 있다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int N;
int p[200005], rev[200005];
ll a[200005], b[200005], c[200005];
ll asum[200005], bsum[200005], csum[200005];
ll dp[200005];
ll tree[1 << 19];

void update(int node, int s, int e, int idx, ll val) {
	if (s > idx || idx > e) return;
	if (s == idx && idx == e) {
		tree[node] = val;
		return;
	}
	int mid = s + e >> 1;
	int n1 = node << 1, n2 = node << 1 | 1;
	update(n1, s, mid, idx, val);
	update(n2, mid + 1, e, idx, val);
	tree[node] = min(tree[n1], tree[n2]);
}

ll query(int node, int s, int e, int l, int r) {
	if (e < l || s > r) return INF;
	if (l <= s && e <= r) return tree[node];
	int mid = s + e >> 1;
	int n1 = node << 1, n2 = node << 1 | 1;
	return min(query(n1, s, mid, l, r), query(n2, mid + 1, e, l, r));
}

int main() {
	cin.tie(nullptr); ios::sync_with_stdio(false);
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> p[i];
		rev[p[i]] = i;
	}
	for (int i = 1; i <= N; ++i) cin >> a[i] >> b[i] >> c[i];
	for (int i = 1; i <= N; ++i) {
		asum[i] = asum[i - 1] + a[i];
		bsum[i] = bsum[i - 1] + min(a[i], b[i]);
		csum[i] = csum[i - 1] + min(a[i], c[i]);
	}
	fill(dp, dp + N + 1, INF);
	fill(tree, tree + (1 << 19), INF);
	ll ans = INF;
	for (int i = 1; i <= N; ++i) {
		dp[i] = min(bsum[i - 1], asum[i - 1] + query(1, 1, N, 1, rev[i]));
		ans = min(ans, dp[i] + csum[N] - csum[i]);
		update(1, 1, N, rev[i], dp[i] - asum[i]);
	}
	cout << ans << '\n';
	return 0;
}