するめうめ

これはなに

docs.google.com

をやる

SRM 715 MaximumRange

max(+ の個数, - の個数)

class MaximumRange {
    public:
    int findMax(string s) {
        lint p = 0, m = 0;
        for (char c : s) {
            if (c == '+') {
                p++;
            }
            else {
                m++;
            }
        }

        return max(p, m);
    }
};

SRM 735 PalindromeSubsequence

aのみ、bのみを取り出すとそれは回文なので、答えのサイズは 2 以下。 1になるのは s が回文の時だけなので、その通り実装する。

class PalindromeSubsequence {
    public:
    vector<int> optimalPartition(string s) {
        auto t = s;
        reverse(ALLOF(t));

        if (s == t) {
            return vector<int>(s.length(), 1);
        }

        vector<int> ans;
        for (auto c : s) {
            if (c == 'a') {
                ans.push_back(1);
            }
            else {
                ans.push_back(2);
            }
        }

        return ans;
    }
};

SRM 729 MagicNumberThree

dp[i][j] := i 番目まで見て、余りが j になる場合の数として素直にDP

mint dp[100][3];

class MagicNumberThree {
    public:
    int countSubsequences(string s) {
        rep(i, 100) {
            rep(j, 3) {
                dp[i][j] = 0;
            }
        }

        int len = s.length();
        s = "*" + s;
        dp[0][0] = 1;

        rep(i, len) {
            int si = s[i + 1] - '0';
            si %= 3;
            rep(j, 3) {
                // いれる
                dp[i + 1][(j + si) % 3] += dp[i][j];
                // いれない
                dp[i + 1][j] += dp[i][j];
            }

        }


        return dp[len][0].x - 1;
    }
};

SRM 748 EraseToGCD

dp[i][j] := i 番目まで見て gcd が j である場合の数。 空集合の gcd は 0 である(gcd の単位元は 0 ) とすると都合がよいことに注意する

mint dp[510][1010];
class EraseToGCD {
    public:
    int countWays(vector<int> S, int goal) {
        rep(i, 510) {
            rep(j, 1010) {
                dp[i][j] = 0;
            }
        }

        int N = S.size();

        dp[0][S[0]] = 1;
        dp[0][0] = 1;
        rep(i, N - 1) {
            rep(j, 1010) {
                // 入れる
                dp[i + 1][euclidean_gcd(j, S[i + 1])] += dp[i][j];
                // 入れない
                dp[i + 1][j] += dp[i][j];
            }
        }

        return dp[N-1][goal].x;
    }
};

SRM 755 OneHandSort

• Each element of target will be between 0 and N-1, inclusive.
• All elements of target will be distinct.

なので、 i は i 番目(0-indexed) にくることがわかる。

よって、
i 番目にある値を 空きマスに退避
i を↑で開けたマスに移動

を繰り返せば OK。(idx[i] := i のインデックス の実装で頭を壊してしまったが、N <= 500 なのだから、テーブルを持たずに愚直をやってもよかった……)

class OneHandSort {
    public:
    vector<int> sortShelf(vector<int> target) {
        int N = target.size();

        vector<int> ans;
        vector<int> idx(N);
        rep(i, N) {
            idx[target[i]] = i;
        }

        auto processed = target;
        processed.push_back(-1);
        int blank = N;
        rep(i, N) {

            if (processed[i] != -1) {
                // i えらぶ
                ans.push_back(i);

                // 今入ってる数の場所を更新
                idx[processed[i]] = blank;
                swap(processed[i], processed[blank]);
                blank = i;
            }

            // idx[i] えらぶ
            ans.push_back(idx[i]);

            // 今入ってる数の場所を更新
            swap(processed[idx[i]], processed[blank]);
            blank = idx[i];
            idx[i] = i;

            //cout << processed << "\n";
        }

        return ans;
    }
};