ABC 190 간단 후기 올립니다~ (atcoder.jp/contests/abc190)
A - Very Very Primitive Game
간단한 구현 문제입니다. 먼저 시작하는 사람의 캔디가 더 많으면 먼저 시작하는 사람이 이기고, 그렇지 않으면 다른 사람이 이깁니다.
int main() {
int a, b, c; cin >> a >> b >> c;
if (c == 0) {
if (a > b) cout << "Takahashi";
else cout << "Aoki";
}
else {
if (b > a) cout << "Aoki";
else cout << "Takahashi";
}
}
B - Magic 3
간단한 구현 문제입니다. X < S and Y > D인 (X, Y)가 존재하면 Yes, 아니면 No를 출력하면 됩니다.
int main() {
int n, s, d; cin >> n >> s >> d;
int x, y;
while (n--) {
cin >> x >> y;
if (x<s && y>d) {
cout << "Yes"; return 0;
}
}
cout << "No";
}
C - Bowls and Dishes
완전탐색 문제입니다. K명의 사람이 C or D를 선택하는 모든 경우(2^K)에 대하여 가장 많은 조건을 만족하는 경우를 출력하면 됩니다
typedef pair<int, int> p;
int N, M, K, ans, S[100];
p ab[100], cd[100];
void f(int idx) {
if (idx == K) {
int dish[104], i;
for (i = 1; i <= N; i++) dish[i] = 0;
for (i = 0; i < K; i++) {
if (S[i] == 1) dish[cd[i].x] = 1;
else dish[cd[i].y] = 1;
}
int sum = 0;
for (i = 0; i < M; i++) {
if (dish[ab[i].x] && dish[ab[i].y]) sum++;
}
ans = max(ans, sum);
return;
}
S[idx] = 1; f(idx + 1);
S[idx] = 2; f(idx + 1);
}
int main() {
int i;
cin >> N >> M;
for (i = 0; i < M; i++) cin >> ab[i].x >> ab[i].y;
cin >> K;
for (i = 0; i < K; i++) cin >> cd[i].x >> cd[i].y;
f(0);
cout << ans;
}
D - Staircase Sequences
수학 문제입니다. 등차수열의 시작과 끝을 각각 a, b라고 할 경우 a + (a+1) + ... + b = N 인 (a, b) 쌍의 개수를 구하면 됩니다. 좌변은 (1+2+...+b) - (1+2+...+a-1) 이므로, b(b+1) - a(a-1)= 2N --> (b+a)(b-a+1)=2N이 됩니다.
2N을 xy꼴로 나타내서 x=b+a, y=b-a+1 or x=b-a+1, y=b+a가 성립하는지 확인하면 됩니다.
ll N;
inline int f(ll x, ll y) {
if ((x + y - 1) % 2 == 0) return 1;
return 0;
}
int main() {
cin >> N;
N *= 2;
ll ans = 0;
for (ll i = 1; i*i <= N; i++) {
if (N%i) continue;
ll j = N / i;
if (f(i, j)) ans++;
if (f(-i, -j)) ans++;
}
cout << ans;
}
E - Magical Ornament
Graph + bit DP 문제입니다. M개의 이웃한 쌍 (A,B)를 edge, N개의 gem이 node인 graph를 생각하자. K개의 C에 대하여 Ci에서 Cj의 shortest path를 구하자.(BFS 이용) 모든 (Ci, Cj) 쌍의 shortest path를 D[K][K]라고 하자. K개의 C를 node, D를 edge로 갖는 Graph에서 임의의 정점에서 다른 모든 노드를 방문하는 최소 비용 (salesman problem)을 구하면 된다.
int N, M, K, C[20], CC[100004], CI[100004], S[20];
vector<int> adj[100004];
int adj2[20][20];
const int INF = (int)1e9;
int dp[1 << 17][17];
int dfs(int state, int u) {
int &ret = dp[state][u]; if (ret != -1) return ret;
if (state == ((1 << K) - 1)) return ret = 0;
ret = INF;
for (int v = 0; v < K; v++) {
if (state&(1 << v)) continue;
if (adj2[u][v] == -1) continue;
int a = dfs(state | (1 << v), v) + adj2[u][v];
if (a < INF) ret = min(ret, a);
}
return ret;
}
int main() {
int i, j;
cin >> N >> M;
for (i = 0; i < M; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b); adj[b].push_back(a);
}
cin >> K;
for (i = 0; i < K; i++) {
cin >> C[i]; CC[C[i]] = 1; CI[C[i]] = i;
}
for (i = 1; i <= N; i++) {
if (CC[i] == 0) continue;
queue<int> q; q.push(i);
vector<int> dist(N + 1, -1); dist[i] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto v : adj[u]) {
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}
for (j = 1; j <= N; j++) {
if (CC[j] == 0 || i == j) continue;
adj2[CI[i]][CI[j]] = adj2[CI[j]][CI[i]] = dist[j];
}
}
int ans = INF;
for (i = 0; i < (1 << K); i++) for (j = 0; j < K; j++) dp[i][j] = -1;
for (i = 0; i < K; i++) {
int ret = dfs(1 << i, i);
if (ret < INF) ans = min(ans, ret + 1);
}
if (ans == INF) ans = -1;
cout << ans;
}
F - Shift and Inversions
Segment Tree 문제입니다. i ~ i + N -1 구간의 inversion count를 구하면 됩니다. (0<= i <N) i=0일 경우는 segment tree를 이용하면 됩니다. (소스코드 rev_cnt) i=1 ~ N-1일 경우는 A[i]보다 작은 숫자와 큰 숫자는 O(1)에 찾을 수 있습니다. (소스크도 up, dn) 이유는 0 ~ N-1 숫자가 한 번씩 나오기 때문입니다.
struct sg {
int st[1200004];
void upd(int a, int b, int node, int node_st, int node_en) {
if (a < node_st || node_en < a) return;
if (node_st == node_en) {
st[node] = b; return;
}
upd(a, b, node * 2, node_st, (node_st + node_en) / 2);
upd(a, b, node * 2 + 1, (node_st + node_en) / 2 + 1, node_en);
st[node] = st[node * 2] + st[node * 2 + 1];
}
int qry(int a, int b, int node, int node_st, int node_en) {
if (a > node_en || node_st > b) return 0;
if (a <= node_st && node_en <= b) return st[node];
return qry(a, b, node * 2, node_st, (node_st + node_en) / 2) +
qry(a, b, node * 2 + 1, (node_st + node_en) / 2 + 1, node_en);
}
}S;
int main() {
int i, n; cin >> n;
vector<int> A(n + 1);
ll rev_cnt = 0;
for (i = 1; i <= n; i++) {
cin >> A[i]; A[i]++;
S.upd(A[i], 1, 1, 1, n);
rev_cnt += (i - S.qry(1, A[i], 1, 1, n));
}
cout << rev_cnt << '\n';
for (i = 1; i < n; i++) {
int dn, up;
dn = A[i] - 1; up = n - A[i];
rev_cnt = rev_cnt - dn + up;
cout << rev_cnt << '\n';
}
}
