メモ

自分に向けて書いたメモを取り扱っています.

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;
}