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방식도 연습해놔야겠다.

9520 NP-hard

9520 NP-hard https://www.acmicpc.net/problem/9520

K번 도시를 방문하기 위해서는 K보다 작은 도시를 모두 방문하고 방문하거나
K번도시를 방문한 후에 K보다 작은도시를 모두 방문하면 된다.
K번도시보다 작은도시를 K번도시 이전에 방문하고 다른하나는 K번도시방문후에 방문하면 안된다.
이때 모든 도시를 방문하기위해 드는 시간의 최솟값을 구하는 문제다.

문제 이해를 계속 못했다.
문제의 핵심은 $v_{1}>v_{2}>...>v_{k}<v_{k+1}<...<v_{n}$의 수열중 최솟값을 구하는 문제가 된다.
(위와같은 수열을 bitonic sequence라 한다.)
즉, 4개의 도시중에 만약 방문순서를 2,1,3을 했다면 4는 왼쪽 또는 오른쪽에 붙일 수 있다.
(4,2,1,3 또는 2,1,3,4)

위의 로직을 catch했다면 경찰차문제 풀듯이 쉽게 dp로 풀 수 있다.

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define INF 987654321 int N; int adj[1501][1501]; int dp[1501][1501]; int solve(int l, int r) {     if (l == N - 1 || r == N - 1) return 0;     int &ret = dp[l][r];     if (ret != -1) return ret;     ret = INF;     int next = max(l, r) + 1;     return ret = min(ret, min(solve(next, r) + adj[next][l], solve(l, next) + adj[r][next])); } int main() {     memset(dp, -1, sizeof dp);     scanf("%d", &N);     for (int n = 0;n < N;n++) for (int m = 0;m < N;m++) scanf("%d", &adj[n][m]);     printf("%d\n", solve(0, 1) + adj[0][1]);     return 0; } Colored by Color Scripter

cs

1038 감소하는 수, 1174 줄어드는 숫자

1038 감소하는 수 https://www.acmicpc.net/problem/1038
1174 줄어드는 숫자 https://www.acmicpc.net/problem/1174

음이아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면 줄어드는 숫자이다.
N번째 줄어드는 숫자(감소하는 수)를 구하는 문제다.

옛날에 풀었을 때는 못풀었던 문제다.

dp로 쉽게 점화식을 구해서 구할 수 있다.
$dp[s][l]$ : 앞자리가 $s$이면서 길이가 $l$인 줄어드는 수의 갯수
$dp[s][l]$ = $dp[s-1][l] + dp[s-1][l-1]$
앞자리가 $s$이면서 길이가 $l$인 가장 첫번째 줄어드는 수의 index 위치를 저장해놓으면
N번째 줄어드는 수를 구할 수 있다.

#include <iostream> #include <string> #include <algorithm> #include <map> using namespace std; int N; int cnt; int dp[10][11]; map<int, string> save; map<pair<int, int>, int> pos; int main() {     ios::sync_with_stdio(false);     cin >> N;     if (N > 1022) { cout << "-1\n"; return 0; }     for (int s = 0;s < 10;s++) save[++cnt] = to_string(s), pos[{s, 1}] = cnt, dp[s][1] = 1;     for (int l = 2;l < 11;l++) {         for (int s = l - 1;s < 10;s++) {             pos[{s, l}] = cnt + 1;             dp[s][l] = dp[s - 1][l] + dp[s - 1][l - 1];             int get = pos[{l -2, l - 1}];             for (int n = 0;n < dp[s][l];n++) {                 save[++cnt] = to_string(s) + save[get + n];             }         }     }     cout << save[N + 1];     return 0; } Colored by Color Scripter

cs

프로그래밍 마에스터 예선대회3번

사칙연산 programmers

• (((1 - 3) + 5) - 8) = -5
• ((1 - (3 + 5)) - 8) = -15
• (1 - ((3 + 5) - 8)) = 1
• (1 - (3 + (5 - 8))) = 1
• ((1 - 3) + (5 - 8)) = -5

사칙연산에서 -는 결합법칙이 성립되지 않는다.

위와같이 -의 연산순서에 의해 값이 달라질 수 있다.

수와 연산자가 주어질때 최대값을 구하는 문제다.

1, 2번을 풀고 남은 2시간50분동안 시도했지만 못풀었다.

 첫 번째로 string입력으로 들어오는데 단순하게 생각해서 숫자 string의 값을 0번 인덱스만 받아서

이 오류를 찾는데 1시간이 지나고서야 알게되었다.

 두 번째로 dp를 떠올려서 dp로 맞는 방법으로 접근하긴 했지만 너무 단순하게 생각했다.

 

풀이는 해설에서 아주 잘 설명하고있으니 그것으로 대체한다.

#include <vector> #include <string> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define INF 987654321 int dp[202][202][2]; int N; vector<int> num; int solve(int l, int r, int flag) {     int &ret = dp[l][r][flag];     if (ret != -1) return ret;     ret = 0;     if (flag) {     //최솟값         for (int next = l;next <= r;next++) {             if (next == l && num[next] < 0) ret += (-num[next]);             else ret += num[next];         }         for (int next = l;next < r;next++) {             if (num[next + 1] < 0) {                 ret = min(ret, solve(l, next, 1) - solve(next + 1, r, 0));             }             else {                 ret = min(ret, solve(l, next, 1) + solve(next + 1, r, 1));             }         }     }     else {          //최댓값         for (int next = l;next <= r;next++) {             if (next == l && num[next] < 0) ret += (-num[next]);             else ret += num[next];         }         for (int next = l;next < r;next++) {             if (num[next + 1] < 0) {                 ret = max(ret, solve(l, next, 0) - solve(next + 1, r, 1));             }             else {                 ret = max(ret, solve(l, next, 0) + solve(next + 1, r, 0));             }         }     }     return ret; } int solution(vector<string> in) {     num.clear();     memset(dp, -1, sizeof dp);     int data = 0;     for (int m = in[0].size() - 1, t = 1;m >= 0;m--, t *= 10) data += (in[0][m] - '0')*t;     num.push_back(data);     for (int n = 1;n < in.size();n++) {         if (!(n & 1)) {             data = 0;             for (int m = in[n].size() - 1, t = 1;m >= 0;m--, t *= 10) data += (in[n][m] - '0')*t;             num.push_back((in[n - 1][0] == '-' ? -data : data));         }     }     N = num.size();     int ans = solve(0, N - 1, 0);     return ans; } Colored by Color Scripter

cs

1582 아티스트 이동호

1582 아티스트 이동호 https://www.acmicpc.net/problem/1582

흑 또는 백으로 칠해져있는 N*M 그림이 주어진다.
동호는 흑 또는 백으로 수평으로 칠할 수 있다.
최대 K번 칠할 때 잘못 칠한 부분의 최솟값을 구하는 문제다.
(못 칠한 부분도 잘못 칠한것으로 침)

dp로 [0, 0]에서 시작해서 한행이 끝나면 다음행으로 넘어가서 [N - 1, M - 1]까지 
돌리면 되겠다고 생각했다.
약간의 데이터를 만들어서 돌리니 잘 돌아가서 바로제출했다.

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define INF 987654321 int N, M, K; int dp[111][111][3002][2]; char map[101][101]; int sum[101][101]; int get(int y, int x, int state) {     if (map[y][x] == 'W') {         if (state) return 1;         else return 0;     }     else {         if (state) return 0;         else return 1;     } } int solve(int y, int x, int cnt, int state) {     if (cnt > K) return INF;     if (x == M) {         if (y == N - 1) return 0;         else return min(solve(y + 1, 0, cnt + 1, 0), solve(y + 1, 0, cnt + 1, 1));     }     int &ret = dp[y][x][cnt][state];     if (ret != -1) return ret;     ret = INF;     ret = min(ret, solve(y, x + 1, cnt, state) + get(y, x, state));     ret = min(ret, solve(y, x + 1, cnt + 1, !state) + get(y, x, state));     return ret; } int main() {     memset(dp, -1, sizeof dp);     scanf("%d%d%d", &N, &M, &K);     for (int n = 0;n < N;n++) {         scanf("%s", &map[n]);         int s = 0;         for (int m = 0;m < M;m++) {             if (map[n][m] == 'W') s++;             sum[n][m] = s;         }     }     printf("%d\n", min(solve(0, 0, 1, 0), solve(0, 0, 1, 1)));     return 0; } Colored by Color Scripter

cs

Run-time Error
이때 굉장히 몽롱한 상태여서 배열 크기조차 확인을 하지 않았었다.
자고 다시풀기로하고 좀 생각해보니 y축 배열을 크기 2로 줄이고 Sliding window 하듯이 
번갈아가면서 bottom up방식으로 바꾸면 메모리 낭비를 줄일 수 있을것 같았다.

이때까지 문제조건을 못본게 있었는데 칠하지 못하는 부분은
잘못칠한것으로 처리한다는 조건이였다.

빠진조건에 맞게 수정하고 몇개의 데이터를 돌려보고 제출했다.
다른분들 코드 보니 y축마다 분할해서 푸신분이 대다수였는데 logic은 똑같았다.

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int N, M, K; int dp[2][101][3001][2];        // y,x,k,state char map[101][101]; int get(int y, int x, int state) { // black : 1, white : 0     if (map[y][x] == 'W') {         if (state) return 1;         else return 0;     }     else {         if (state) return 0;         else return 1;     } } int main() {     int ans = 0x3f3f3f3f, tmp = 0x3f3f3f3f;     memset(dp, 0x3f, sizeof dp);     scanf("%d%d%d", &N, &M, &K);     for (int n = 0;n < N;n++) {         scanf("%s", &map[n]);     }     if (K == 0) { printf("%d\n", N*M); return 0; }     if (N == 1 && M == 1) { printf("%d\n", K == 0 ? 1 : 0); return 0; }     dp[0][0][1][0] = get(0, 0, 0);     dp[0][0][1][1] = get(0, 0, 1);     for (int n = 0;n < N;n++) {         for (int m = 0;m < M;m++) {             for (int k = 1;k <= K;k++) {                 for (int f = 0;f < 2;f++) {                     if (n == 0 && m == 0) {}                     else {                         dp[n % 2][m][k][f] = 0x3f3f3f3f;                         if (m - 1 >= 0) {                             dp[n % 2][m][k][f] =                                  min(dp[n % 2][m][k][f], dp[n % 2][m - 1][k][f] + get(n, m, f));                             dp[n % 2][m][k][f] =                                  min(dp[n % 2][m][k][f], dp[n % 2][m - 1][k - 1][!f] + get(n, m, f));                         }                         else {                             dp[n % 2][m][k][f] =                                  min(dp[n % 2][m][k][f], dp[!(n % 2)][M - 1][k - 1][!f] + get(n, m, f));                             dp[n % 2][m][k][f] =                                  min(dp[n % 2][m][k][f], dp[!(n % 2)][M - 1][k - 1][f] + get(n, m, f));                         }                     }                     if (dp[n % 2][m][k][f] != 0x3f3f3f3f) {                         tmp = min(tmp, dp[n % 2][m][k][f] + M - 1 - m + (N - 1 - n)*M);                     }                     if (n == N - 1 && m == M - 1) ans = min(ans, dp[n % 2][m][k][f]);                 }             }         }     }     if (ans != 0x3f3f3f3f) {         printf("%d\n", ans);     }     else {         printf("%d\n", tmp);     }     return 0; } Colored by Color Scripter

cs