AtCoder ABC 263 풀이

https://atcoder.jp/contests/abc263/tasks

Tasks - LINE Verda Programming Contest（AtCoder Beginner Contest 263）

 

A.

정렬후 케이스를 잘 나눠주면 됩니다.

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int a[5];
    for (int i = 0; i < 5; i++)cin >> a[i];
    sort(a, a + 5);
    int cnt = 0;
    if (a[0] == a[1] && a[1] != a[2] && a[2] == a[4]) {
        cout << "Yes";
    }
    else if (a[0] == a[2] && a[2] !=a[3] && a[3] == a[4]) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
}

 

B.

트리 깊이를 찾아주면 됩니다. dfs로 해도 되고 dp식으로 간단히 풀 수 있습니다. 

 

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    vector<int>p(n+1);
    for (int i = 2; i <= n; i++)cin >> p[i];
    vector<int>dep(n+1, 0);
    for (int i = 2; i <= n; i++) {
        dep[i] = dep[p[i]] + 1;
    }
    cout << dep[n];
}

 

C.

N과 M 시리즈 문제입니다. 그냥 백트래킹 해주면 됩니다. 

 

#include<bits/stdc++.h>
using namespace std;
int n, m, vis[11];

void dfs(int idx, int cnt) {
    if (cnt == n) {
        for (int i = 1; i <= m; i++) {
            if (vis[i]) cout << i << " ";
        }
        cout << '\n';
    }
    for (int i = idx; i <= m; i++) {
        if (vis[i])continue;
        vis[i] = 1;
        dfs(i, cnt + 1);
        vis[i] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    dfs(1, 0);
}

 

 

D. 

왼쪽부터 L로 변경, 오른쪽부터 R로 변경 가능할때 합의 최솟값을 찾는 문제입니다. 

어차피 두 경로가 겹치면 나중에 변경한 값으로 덮이니 겹치지 않는 경우와 같게 볼 수 있습니다. 

왼쪽부터 i칸까지, 오른쪽부터 j개 칸을 덮은 값을 구해보면, 

L*i+R*j+psum[N-j]-psum[i] 입니다. N-j=k라고 놓으면, (단, k>i) 

식은 (psum[k]-kR)-(psum[i]-Li)+NR이 됩니다. 

psum[i]-Pi=rp[i], psum[i]-Li=lp[i]로 정의합시다. 

식은 rp[k]-lp[i]+상수 로 깔끔해졌습니다. 여기서 잘 알려진 테크닉을 사용합니다. 

lp[i]만 최댓값을 갱신하며 현재 인덱스의 rp[i]만 빼주면서 차이도 같이 갱신을 해주면 됩니다. 

O(N)에 해줄 수 있습니다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 200005;
ll n, l, r, a;
ll psum[MAX], lp[MAX], rp[MAX];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++) {
        cin >> a;
        psum[i] = psum[i - 1] + a;
        lp[i] = psum[i] - l * i;
        rp[i] = psum[i] - r * i;
    }
    ll ans = psum[n];
    ll maxi = 0;
    for (int i = 0; i <= n; i++) {
        maxi = max(maxi, lp[i]);
        ans = min(ans, rp[i] - maxi + n * r);
    }
    cout << ans;
}

 

 

E.

기댓값 DP 문제입니다. DP[i]를 i번에서 시작하여 N번에 도달할때까지 이동횟수의 기댓값이라 정의합니다. 

i=N-1부터 순차적으로 구해나갑니다. (i=1부터 하지 않는 이유는 i=N일땐 주사위가 없어서

식이 달라지므로 귀찮습니다.)

DP[i]는 DP[i]부터 DP[i+a[i]]까지에서 왔습니다. 기댓값은 평균값과 같으므로, 

DP[i]=sum(DP[j]+1)/(a[i]+1) 입니다. (DP[j]+1인 이유는 DP[j]에서 1번 이동해서 DP[i]로 오기 때문)

식을 정리해주면, 양변에 모두 DP[i]가 있으므로, DP[i]만 몰아서 정리하면, 식이 나오고 

구현해주면 됩니다. 여기서 sum(DP[j])부분은 누적합으로 관리해서 O(1)에 처리해야 O(N)이 됩니다. 

마지막으로 구하는게 P/Q로 나타낼 시 PQ^-1 (mod p)를 구하라고 하네요. 

p가 소수이므로 페르마 소정리+분할정복으로 P/Q 를 PQ^(p-2)로 바꿔서 계산해주면 됩니다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
ll n, a[200005], dp[200005], psum[200005];

ll pow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++)cin >> a[i];
    for (int i = n - 1; i; i--) {
        int s = (psum[i + 1] - psum[i + a[i] + 1] + mod) % mod;
        dp[i] = (s + a[i] + 1) * pow(a[i], mod - 2);
        dp[i] %= mod;
        psum[i] = dp[i] + psum[i + 1];
        psum[i] %= mod;
    }
    cout << dp[1];
}

 

 

 

F.

풀이 예정

 

 

 

G. 

플로우 냄새가 납니다. 백준 소수쌍 문제(https://www.acmicpc.net/problem/1017)와 너무나 닮았는데

짜증나는게 1의 존재입니다.  1만 없다면 이분그래프로 홀짝을 나누고 최대유량문제가 됩니다. 

1은 자신끼리 2를 만들수 있어서 까다롭습니다. 1을 어떻게 써야할까요?

우선 1 2개로는 무조건 답이 1 증가합니다. 그러나 1을 다른 짝수들과 연결가능하다면

1 1개로도 답이 1이상 증가하게 됩니다. 따라서 우선 1을 다른 짝수들과 연결시켜 최대유량을 구해주고, 

나머지 1들을 2개씩 묶어주는게 최적해임을 알 수 있습니다. 

1과 소수가 되는 짝수들을 연결시키고 최대유량 알고리즘을 1번 더 돌려줍니다.

이 때 나오는건 이미 홀짝 이분그래프로 최대유량을 흘린 뒤 1로 만드는 최대유량이 됩니다.

답은 r1(1아닌것끼리 최대유량)+use(1과 짝수들의 최대유량)+(cnt-use)/2 (나머지 1들을 묶은 개수) 입니다. 

풀면서 느껴지는게 앳코더 문제들이 교육적이고 좋은 문제들이 많은 것 같네요.

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 20000007;
ll n, a[111], b[111];
vector<int>g[111];
ll work[111], lv[111];
ll cap[111][111], flow[111][111];

// prime test
bool prime(int x) {
	for (int i = 2; i <= x / i; i++) {
		if (!(x % i)) return 0;
	}
	return 1;
}

// Dinic 
struct Dinic {
	void add(int u, int v, ll c) {
		g[u].push_back(v);
		g[v].push_back(u);
		cap[u][v] += c;
	}
	bool bfs(int S, int T) {
		memset(lv, -1, sizeof(lv));
		queue<int>q;
		lv[S] = 0;
		q.push(S);
		while (q.size()) {
			int cur = q.front(); q.pop();
			for (int nxt : g[cur]) {
				if (lv[nxt] == -1 && cap[cur][nxt] > flow[cur][nxt]) {
					lv[nxt] = lv[cur] + 1;
					q.push(nxt);
				}
			}
		}
		return ~lv[T];
	}
	ll dfs(int cur, ll w, int T) {
		if (cur == T) return w;
		for (ll& i = work[cur]; i < (ll)(g[cur].size()); i++) {
			int nxt = g[cur][i];
			if (lv[nxt] == lv[cur] + 1 && cap[cur][nxt] > flow[cur][nxt]) {
				ll f = dfs(nxt, min(w, cap[cur][nxt] - flow[cur][nxt]), T);
				if (f) {
					flow[cur][nxt] += f;
					flow[nxt][cur] -= f;
					return f;
				}
			}
		}
		return 0;
	}
	ll max_flow(int S, int T) {
		ll ret = 0;
		while (bfs(S, T)) {
			memset(work, 0, sizeof(work));
			while (1) {
				ll f = dfs(S, 1e18, T);
				if (!f) break;
				ret += f;
			}
		}
		return ret;
	}
}dnc;


int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
	int S = 0, T = n + 1;
	int idx = -1;
	ll cnt = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
		if (a[i] == 1) {
			idx = i;
			cnt = b[i];
		}
		// 1아닌 것들끼리 이분그래프 형성
		// 왼쪽이 홀수, 오른쪽이 짝수 
		else {
			if (a[i] & 1)dnc.add(S, i, b[i]); 
			else dnc.add(i, T, b[i]); 
		}
    }
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (a[i] == 1 || a[j] == 1) continue;
			// 홀 -> 짝 연결 
			if ((a[i] & 1) && prime(a[i] + a[j]) && !(a[j] & 1)) {
				dnc.add(i, j, 1e18);
			}
		}
	}
	ll ret1 = dnc.max_flow(S, T); 
	// 1이 없으면
	if (idx == -1) {
		cout << ret1;
		return 0;
	}
	// 1을 연결시키고 최대유량 1번 더 흘림 
	dnc.add(S, idx, cnt);
	for (int i = 1; i <= n; i++) {
		if (prime(1 + a[i])) {
			dnc.add(idx, i, 1e18);
		}
	}
	ll use = dnc.max_flow(S, T);
	cout << ret1 + use + (cnt - use) / 2;
}