1043 거짓말

1043 거짓말 https://www.acmicpc.net/problem/1043

지민이는 파티에 가서 이야기 하는것을 좋아한다.
지민이는 되도록 파티에가서 과장된 이야기를 하려고하는데 몇명의 사람들이 진실을 알고있다.
진실을 아는 사람이 있는 파티에는 과장된 이야기를 하면안되고 진실을 알지 못하더라도
어떤 파티에서는 과장된이야기를, 어떤 파티에서는 과장되지 않은이야기를 들으면 안된다.
지민이가 과장된 이야기를 할 수 있는 파티의 최댓값을 구하는 문제이다.

문제를 보고 이상하게 유량문제로 접근했다.
모델링을 계속 시도해보았지만 적절치 않아서 플로이드 와샬로 진실을 아는 사람이 있는 파티와 
연관된 파티들을 인접리스트로 연결시켜주는 방식을 이용해서 최대유량을 구했다.

사실 최대유량을 구할 필요도 없이 플로이드 와샬로 위에서  말한방식처럼 연결시킨 후
bfs로 탐색시켜주면 끝난다.

#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; #define INF 987654321 int N, M; int num; bool knowtrue[51]; bool chk[51][51]; bool chkadj[51][51]; vector<int> adj[111]; bool visit[111]; int main() {     scanf("%d%d", &N, &M);     scanf("%d", &num);     for (int n = 0, t;n < num;n++) scanf("%d", &t), knowtrue[t - 1] = true;     for (int m = 0;m < M;m++) {         scanf("%d", &num);         for (int n = 0, t;n < num;n++) scanf("%d", &t), chk[m][t - 1] = true;     }     for (int m = 0;m < M;m++) {         for (int k = 0;k < M;k++) {             for (int n = 0;n < N;n++) {                  if (chk[m][n] && chk[k][n]) {                     chkadj[m][k] = true;                     chkadj[k][m] = true;                     break;                 }             }         }     }     for (int k = 0;k < M;k++) {         for (int n = 0;n < M;n++) {             for (int m = 0;m < M;m++) {                 if (!chkadj[n][m] && chkadj[n][k] && chkadj[k][m]) chkadj[n][m] = true;             }         }     }     for (int n = 0;n < M;n++) {         for (int m = 0;m < M;m++) {             if (chkadj[n][m]) {                 adj[n].push_back(m + M);             }         }     }     queue<int> q;     for (int m = 0;m < M;m++) {         bool flag = false;         for (int n = 0;n < N;n++) if (knowtrue[n] && chk[m][n]) { flag = true; break; }         if (flag) q.push(m), visit[m] = true;     }     while (!q.empty()) {         int here = q.front();         q.pop();         for (int &next : adj[here]) {             if (!visit[next]) {                 visit[next] = true;                 q.push(next);             }         }     }     int ans = 0;     for (int m = 0;m < M;m++) {         if (!visit[m + M]) ans++;     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs

Codeforces #455 (Div.2) C - Python Indentation

Codeforces #455 (Div.2) C - Python Indentation http://codeforces.com/contest/909/problem/C

파이썬에서는 들여쓰기로 문법이 적용된다.
for문과 state문 여부가 주어질 때 나타날 수 있는 경우의 수를 구하는 문제이다.

풀어놓고 한번 제출했는데 "메모리초과가 나네? 어차피 틀릴거 놨둬야지" 라고 생각하고 제출안했다...

$dp[idx][level]$ : $idx$에서 들여쓰기가 $level$일 때 경우의 수
$s[idx][level]$ : $idx$에서 $level$부터 N까지 경우의 수의 합
4가지 경우([이전,현재]) 로 나누어 생각해 보았다.

1. [f,f]인 경우
for문 두 번이 연속으로 되어있는 경우는 바로 다음 줄로 이어가야한다.
따라서 $dp[idx][level] = dp[idx-1][level-1]$

2. [s,f]인 경우
state문 다음에 for문이 오므로 state문에 도달한 level 이전까지로 다음 for문이 나타날 수 있다.
$dp[idx][level] = s[idx - 1][level]$

3. [f,s]인 경우
for문다음에 state문이 오면 다음 줄로 이어가야한다.
1과같은 경우가 될수밖에 없다.

4. [s,s]인 경우
2와 같은 경우가 된다.

여기서 2,4인 경우를 구하기 위해 누적 경우의 수를 구해야한다.
누적 경우의 수를 bottom-up방식으로 하면 누적 경우의 수를 구해놓을 수 있다.

#include <cstdio> #include <iostream> #include <string> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <iomanip> #include <set> #include <map> #include <unordered_set> #include <unordered_map> using namespace std; #define mp(a,b) make_pair(a,b) #define mt(a,b,c) mp(a,mp(b,c)) #define mf(a,b,c,d) mp(mp(a,b),mp(c,d)) #define mod (ll)(1e9+7) typedef long long ll; typedef long double ld; typedef unsigned long long ull; int dy[] = { 0, 0, 1, -1 };     //동, 서, 남, 북         int dx[] = { 1, -1, 0, 0 }; int N; char t[5022]; ll dp[5022][5022]; ll s[5022]; int main() {     scanf("%d", &N);     for (int n = 0;n < N;n++) scanf(" %c", &t[n]);       dp[0][0] = 1;     for (int idx = 1;idx < N;idx++) {         memset(s, 0, sizeof s);         for (int level = N - 1;level >= 0;level--) {             s[level] += s[level + 1] % mod + dp[idx - 1][level] % mod;             s[level] %= mod;         }         for (int level = 0;level < N;level++) {             if (t[idx] == 'f') {                 if (t[idx - 1] == 'f') {                     if (level - 1 >= 0) {                         dp[idx][level] += dp[idx - 1][level - 1];                         dp[idx][level] %= mod;                     }                 }                 else {                     dp[idx][level] += s[level];                     dp[idx][level] %= mod;                 }             }             else {    // 's'                 if (t[idx - 1] == 'f') {                     if (level - 1 >= 0) {                         dp[idx][level] += dp[idx - 1][level - 1];                         dp[idx][level] %= mod;                     }                 }                 else {                     dp[idx][level] += s[level];                     dp[idx][level] %= mod;                 }             }         }     }     ll ans = 0;     for (int level = 0;level < N;level++) {         ans += dp[N - 1][level];         ans %= mod;     }     printf("%lld\n", ans);     return 0; } Colored by Color Scripter

cs

너무 아까운 문제였다 ㅠㅠ
dp도 거의 top-down방식으로 사용하는데 bottom-up방식도 연습해놔야겠다.

Codeforces #432 (Div.2) D - Arpa and a list of numbers

Codeforces #432 (Div.2) D - Arpa and a list of numbers
http://codeforces.com/contest/851/problem/D

수열이 주어진다.
각각의 수열값에 대하여 연산을 시행할 수 있다.
연산은 다음과 같이 두가지가 있다.
1. 해당 숫자를 없앤다. (cost x소모)
2. 숫자를 1 올린다. (cost y소모)
수열의 gcd를 1이 아니도록 만들때 소모되는 최소 cost를 구하는 문제이다.

당연히 대회때는 풀지 못했고 솔루션과 AC코드들을 참고해서 이해하는데도 한참걸렸다.

우선 수열의 값이 최대 $10^6$들어오므로 gcd를 2부터 $10^6$까지 올려보면서
수열들의 gcd를 현재 값으로 맞출때의 최소 cost를 구하면 된다.

최소 cost를 구하는 방법은 다음과 같다.
구간 [index + 1, index + gcd - 1]에 있는 $f$를 기준으로 [index + 1, $f$ - 1]에 포함되는 숫자들은 없애고 
[$f$, index + gcd - 1]에 포함되는 숫자들은 index + gcd로 만드는것이다.

이 $f$를 구하는 방법은 이분탐색으로 구해도 되지만 간단하게 gcd - x/y로 구할 수도 있다.

숫자들을 없애는 연산이나 1씩증가시키는 연산에 대해서는 구간합과 구간개수를 이용하면 된다.

#include <cstdio> #define max(a,b) ((a)<(b)?(b):(a)) #define min(a,b) ((a)>(b)?(b):(a)) #define MAX 1005555 long long N, x, y; long long sum[MAX + 1], cnt[MAX + 1]; long long gcnt(int r, int l) {     if (r < l || l >= MAX) return 0;     r = min(r, MAX - 1);     return cnt[r] -  (l <= 0 ? 0 : cnt[l - 1]); } long long gsum(int r, int l) {     if (r < l || l >= MAX) return 0;     r = min(r, MAX - 1);     return sum[r] - (l <= 0 ? 0 : sum[l - 1]); } int main() {     scanf("%lld%lld%lld", &N, &x, &y);     for (int n = 0, in;n < N;n++) {         scanf("%d", &in);         sum[in] += in;         cnt[in]++;     }     for (int n = 1;n <= MAX;n++) {         sum[n] += sum[n - 1];             cnt[n] += cnt[n - 1];     }     long long ans = N*x;     for (int g = 2;g < MAX;g++) {         int f = max(1, g - x / y);         long long query = 0;         for (int plus = 0; plus < MAX;plus += g) {             // [plus + 1, plus + f - 1] delete             query += gcnt(plus + f - 1, plus + 1) * x;             // [plus + f, plus + g - 1] plus             query += (gcnt(plus + g - 1, plus + f)*((plus + g) * 1LL) - gsum(plus + g - 1, plus + f))*y;         }         ans = min(ans, query);     }     printf("%lld\n", ans);     return 0; } Colored by Color Scripter

cs

14672 윤호는 마법약 도둑

14672 윤호는 마법약 도둑 https://www.acmicpc.net/problem/14672

윤호는 M개의 N보다 작은 숫자가 적혀져있는 마법약들을 가지고 있다.
마법약은 1을 제외한 약수들중 하나로 추출 할 수 있다.
추출에 성공하려면 추출한 제품들 중에서 어떠한 원료도 공유해서는 안된다.
윤호의 추출할 수 있는 최대 마법약의 개수를 구하는 문제이다.

마법약들을 추출했을 때 모든 마법약들의 원료들이 서로소인 최대 마법약 개수를 구하는 것이다.
gcd를 이용하기에는 구할 방법이 마땅히 없어보였다.

사실상 원료들이 서로소가 되려면 마법약에서 추출할 수 원료들을 소수로 추출하면 된다.
문제는 최대 마법약 개수를 구해야하는데 이분매칭을 이용하면 된다.

네트워크를 나타내면 위와같이 될것이다.
N이 100,000,000이므로 최대 10,000까지의 소수만 구해주면 되는데 여기 실수가 있었다.

10,000보다 큰 수가 들어올 때 10,000보다 작은 소수로 소인수 분해를 하더라도 끝나지 않을 수 있다.
예를들어 104,729와 같은 수이다. 

이런 수는 따로 처리를 해서 저장을 해줘야한다.
밑의 코드에서 소인수 분해를 하고 x > 1인경우가 따로 처리한 경우이다.

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <unordered_map> #include <queue> using namespace std; #define MAX 3500 #define PLUS 2300 #define INF 987654321 int N, M; int arr[1001]; int pr[10011]; vector<int> prime; int Size; vector<int> adj[MAX]; int C[MAX][MAX], f[MAX][MAX]; const int src = MAX - 2, sink = MAX - 1; int level[MAX], work[MAX]; unordered_map<int, int> save; int cnt = 0; void init() {     int L = (int)sqrt(N) + 1;     for (int n = 2;n*n <= L;n++) {         for (int m = n*n;m <= L;m += n) pr[m] = true;     }     for (int n = 2;n <= L;n++) if (!pr[n]) prime.push_back(n);     Size = prime.size(); } void add_edge(int u, int v, int c) {     adj[u].push_back(v);     adj[v].push_back(u);     C[u][v] = c; } bool bfs() {     memset(level, -1, sizeof level);     queue<int> q;     q.push(src);     level[src] = 0;     while (!q.empty()) {         int here = q.front();         q.pop();         for (auto &next : adj[here]) {             if (level[next] == -1 && C[here][next] - f[here][next] > 0) {                 level[next] = level[here] + 1;                 q.push(next);             }         }     }     return level[sink] != -1; } int dfs(int here, const int sink, int flow) {     if (here == sink) return flow;     for (int &n = work[here]; n < adj[here].size(); n++) {         int next = adj[here][n];         if (level[next] == level[here] + 1 && C[here][next] - f[here][next] > 0) {             int get = dfs(next, sink, min(flow, C[here][next] - f[here][next]));             if (get) {                 f[here][next] += get;                 f[next][here] -= get;                 return get;             }         }     }     return 0; } int main() {     scanf("%d%d", &N, &M);     init();     for (int m = 0, x;m < M;m++) {         scanf("%d", &x);         for (int n = 0;n < Size;n++) {             if (x % prime[n] == 0) {                 add_edge(n, m + PLUS, 1);                 while (x && x % prime[n] == 0) x /= prime[n];             }         }         if (x > 1) {             if (save[x] == 0) save[x] = ++cnt;             add_edge(Size + save[x], m + PLUS, 1);         }         add_edge(m + PLUS, sink, 1);     }     for (int n = 0;n < Size;n++) add_edge(src, n, 1);     for (int n = 1;n <= cnt;n++) add_edge(src, Size + n, 1);     int ans = 0;     while (bfs()) {         memset(work, 0, sizeof work);         while (1) {             int get = dfs(src, sink, INF);             if (!get) break;             ans += get;         }     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs