Code Festival 2014 予選A
精神的にくるものがあったので久しぶりに記事を書く。
予選開始
- A問題開く。通す。
- B問題開く。通す。
- C問題開く。通す。
- D問題開く。貪欲に上から決めていけば解けそう…。
- 少し悩んでも良い実装が思い浮かばない。
- しょうがなく桁DPを書く。
- 提出する。WA...
- 原因がわからないまま終了。
反省
D問題、どうせ通るし30点取りに行かなくてもいいかなと思ってたら嵌って本選に行けない順位になってしまった。戦略ミスだなぁ。死にたさ極まる。
A問題
int main() { string s; cin >> s; s += "2014"; cout << s << endl; }
B問題
int main() { string A; long long B; cin >> A >> B; cout << A[(B - 1) % A.size()] << endl; }
C問題
int f(int x) { return x / 4 - x / 100 + x / 400; } int main() { int A, B; cin >> A >> B; cout << f(B) - f(A - 1) << endl; }
D問題
はまったところは2つあった。
- 10000 1のようなケースを想定できてなかった。
- 全ての状態を考えずにdpの処理部書いてた。
あと、添字ミスもあったしホント辛くなりますよ〜…。
const long long INF = 1e16; const int M = 10; long long dp1[20][4][1 << 12]; long long dp2[20][4][1 << 12]; int main() { string A; long long K, ans = INF; cin >> A >> K; int m = A.size(); for(int i = 0; i < m; i++) { for(int k = 0; k < (1 << M); k++) { for(int b = 0; b < 2; b++) { dp1[i][b][k] = INF; dp2[i][b][k] = INF; } } } for(int i = 0; i < 10; i++) { int n = A[0] - '0'; int S = (i == 0 ? 0 : 1 << i); if(n - i >= 0) dp1[0][(n - i) > 0][S] = n - i; if(i - n >= 0) dp2[0][(i - n) > 0][S] = i - n; } // pos for(int i = 1; i < m; i++) { int n = A[i] - '0'; // carry bit for(int b = 0; b < 2; b++) { // used number for(int k = 0; k < (1 << M); k++) { // next number for(int l = 0; l < 10; l++) { long long borrow = 0; long long add = n - l; bool c = add > 0; int S = (l == 0 && k == 0 ? 0 : k | (1 << l)); int count = __builtin_popcount(S); if(count > K) { continue; } if(add >= 0 && b) { dp1[i][0][S] = min(dp1[i][0][S], (dp1[i-1][b][k] + borrow) * 10LL + add); dp1[i][1][S] = min(dp1[i][1][S], (dp1[i-1][b][k] + borrow) * 10LL + add); } if(add < 0 && !b) continue; if(add < 0) { add += 10; c = add > 0; borrow = -1; } dp1[i][c][S] = min(dp1[i][c][S], (dp1[i-1][b][k] + borrow) * 10LL + add); } for(int l = 0; l < 10; l++) { long long borrow = 0; long long add = l - n; bool c = add > 0; int S = (l == 0 && k == 0 ? 0 : k | (1 << l)); int count = __builtin_popcount(S); if(count > K) { continue; } if(add >= 0 && b) { dp2[i][0][S] = min(dp2[i][0][S], (dp2[i-1][b][k] + borrow) * 10LL + add); dp2[i][1][S] = min(dp2[i][1][S], (dp2[i-1][b][k] + borrow) * 10LL + add); } if(add < 0 && !b) continue; if(add < 0) { add += 10; c = add > 0; borrow = -1; } dp2[i][c][S] = min(dp2[i][c][S], (dp2[i-1][b][k] + borrow) * 10LL + add); } } } } for(int j = 0; j < 2; j++) { for(int k = 0; k < (1 << M); k++) { ans = min(ans, dp1[m-1][j][k]); ans = min(ans, dp2[m-1][j][k]); } } cout << ans << endl; }