WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM701 Div1 Easy "PartisanGame"

解法

りんごさんのソースコードを参考にしましたm(_ _)m

石取りゲームにありがちなdpをする。(現在の状態から遷移できる状態の中で、勝てるものがあれば勝ち というやつ)
だが、石の数が半端ないのでもう一工夫必要となる。

現在の状態から遷移できる状態はAlice側とBob側合わせても高々10パターンと少ないことを利用する。10パターンそれぞれ勝てる・勝てないの状態しかもっていないので、状態は2^10のバリエーションがあることになる。つまり、dpの状態は最大でも2^10の周期でループすることになる。よって、2^10までdpして、それ以上はループしていることを利用して算出するようにすればよい。

ソースコード

// dp[0][i]:= Aliceの番で石の数がi個あるとき、Aliceは勝てるか?
// dp[1][i]:= Bobの番で石の数がi個あるとき、Bobは勝てるか?
int dp[2][1234567];

class PartisanGame {
    public:
    string getWinner(int n, vector<int> a, vector<int> b) {
        // 2^10までdp
        for (int i = 0; i < 1234567; i++) {
            // Alice?
            dp[0][i] = false;
            for (int j = 0; j < a.size(); j++) {
                int x = a[j];
                if (x <= i && !dp[1][i - x]) dp[0][i] = true;
            }

            // Bob?
            dp[1][i] = false;
            for (int j = 0; j < b.size(); j++) {
                int x = b[j];
                if (x <= i && !dp[0][i - x]) dp[1][i] = true;
            }
        }

        // 周期を算出
        int q = 1050000; // 2^10以上!
        int p = q - 1;
        for (;; p--) {
            if (check(p, q)) break;
        }
        int cycle = p - q;

        // 答え算出
        if (n > p) n = (n - p) % cycle + p;
        return dp[0][n] ? "Alice" : "Bob";
    }

    // pとqは同じ状態か?
    bool check(int p, int q) {
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j < 5; j++) {
                if (dp[i][p + j] != dp[i][q + j]) return false;
            }
        }
        return true;
    }
};

SRM660 Div1 Easy "Coversta"

解法

コチラを参考にしました。m(_ _)m
kmjp.hatenablog.jp

セル(i, j)に置いた時のスコアを出して、それが大きい順にセルをソートしておく。

1個目の基地を任意の位置に置いた時の、2個目の基地のベストな置き場所を考える。
ベストな置き方は、「セルが重複するような置き方の中でスコアが最大なもの」と「セルが重複しないような置き方の中でスコアが最大なもの」の、これら2つの大きいほうである。
セルが重複するパターンは、x.size()をNとするとN * (N - 1)個しかない。スコアの大きい順にセルを見ていったとき、N * (N - 1) + 1見れば、その中に「セルが重複しないような置き方の中でスコアが最大なもの」が必ず含まれているはず。だから、2個目の基地の置き方を探索するときは、N * (N - 1) + 1回行えば十分である。

ソースコード

class Coversta {
    public:
    int place(vector<string> A, vector<int> Y, vector<int> X) {
        int R = A.size();
        int C = A[0].size();
        int N = X.size();

        // スコアだしてリストに詰める
        vector<pair<int, int> > cells;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                int s = 0;
                for (int k = 0; k < N; k++) {
                    int y = i + Y[k];
                    int x = j + X[k];
                    if (0 <= y && y < R && 0 <= x && x < C) {
                        s += A[y][x] - '0';
                    } 
                }
                cells.push_back(make_pair(s, i * C + j));
            }
        }

        // スコア順にソート
        sort(cells.begin(), cells.end(), greater<pair<int, int> >());

        int best = 0;
        // a
        for (int ay = 0; ay < R; ay++) for (int ax = 0; ax < C; ax++) {
            int scoreA = 0;
            set<pair<int, int> > s;
            for (int i = 0; i < N; i++) {
                int y = ay + Y[i];
                int x = ax + X[i];
                if (0 <= y && y < R && 0 <= x && x < C) {
                    scoreA += A[y][x] - '0';
                    s.insert(make_pair(y, x));
                }
            }

            // b
            int checkN = N * (N - 1) + 1;
            for (int bi = 0; bi < checkN && bi < cells.size(); bi++) {
                int scoreB = 0;
                int by = cells[bi].second / C;
                int bx = cells[bi].second % C;
                for (int i = 0; i < N; i++) {
                    int y = by + Y[i];
                    int x = bx + X[i];
                    if (0 <= y && y < R && 0 <= x && x < C
                        && s.find(make_pair(y, x)) == s.end()) {
                        scoreB += A[y][x] - '0';
                    }
                }
                best = max(best, scoreA + scoreB);
            }
        }

        return best;
    }
};

SRM661 Div1 Easy "MissingLCM"

解法

N + 1 ~ Mの中に、1 ~ Nの素因数を全て持っている必要がある。
例えばN = 10であれば、1 ~ 10に2^3, 3^2, 5^1, 7^1の素因数がある。
それぞれ11(N + 1)以上で、どの数であればその素因数を持つかを見ていくと、
2^3は2^3 * 2 = 16が持つ
3^2は3^2 * 2 = 18が持つ
5^1は5^1 * 3 = 15が持つ
7^1は7^2 * 2 = 14が持つ
となり、11 ~ 18で1 ~ 10の素因数を全て持つこととなる。

ソースコード

bool P[1000010];

class MissingLCM {
    public:
    int getMin(int N) {

        long long ans = 2;
        for (int i = 0; i <= N; i++) {
            P[i] = true;
        }
        P[0] = P[1] = false;
        for (int p = 2; p <= N; p++) {

            if (!P[p]) continue;
            for (int i = p + p; i <= N; i += p) {
                P[i] = false;
            }
            // 素数だ!

            // 1~Nはこの素数をどれだけ持つ?
            long long x = 1;
            while (x * p <= N) {
                x *= p;
            }

            // それはいくつ以上の数字で超える?(ただしNより大きいもので)
            long long y = x;
            while (y <= N) {
                y += x;
            }

            // これの最大値をとってく
            ans = max(ans, y);
        }

        return (int)ans;
    }
};

SRM662 Div1 Easy "FoxesOfTheRoundTable"

解法

以下の通りです。orz
mayokoex.hatenablog.com

事後

D=1~1000まで全探索すればいいや。

実装に手間取る

ふぅ・・・なんとか時間ぎりぎりにコミット

WA

SRM662でググる

Greedyかよ!!

ソースコード

class FoxesOfTheRoundTable {
    public:
    vector<int> minimalDifference(vector<int> _h) {
        int n = _h.size();

        // ソートする
        int h[55];
        int hi[55];
        for (int i = 0; i < n; i++) {
            h[i] = _h[i];
            hi[i] = i;
        }
        while (true) {
            bool update = false;
            for (int i = 0; i < n - 1; i++) {
                if (h[i] > h[i + 1]) {
                    swap(h[i], h[i + 1]);
                    swap(hi[i], hi[i + 1]);
                    update = true;
                }
            }
            if (!update) break;
         }
         
         // 行き
         vector<int> ans;
         for (int i = 0; i < n; i += 2) {
             ans.push_back(hi[i]);
         }

         // 帰り
         int start = n % 2 == 0 ? n - 1 : n - 2;
         for (int i = start; i > 0; i -= 2) {
             ans.push_back(hi[i]);
         }

        return ans;
    }
};

SRM663 Div1 Easy "ABBADiv1"

解法

最終的にinitialが反転しないで終わったのか、反転して終わったのかを決め打つ。

■反転しないで終わった時の条件

target = 左側の文字列 + initial + 右側の文字列 とすると、
・左側と右側の文字列で、含まれる'B'の数が一致する事
・左側の文字列の最初が'A'でないこと

■反転して終わった時の条件

target = 左側の文字列 + initial(反転) + 右側の文字列 とすると、
・左側と右側の文字列で、含まれる'B'の数が左側の方が1つ多い事
・左側の文字列の最初が'A'でないこと

事後

ヒントなしで解けたけど、なんか回りくどい方法・・
反対に考えてtarget->initialにできるか?を考えるとよかったポイ

ソースコード

class ABBADiv1 {
    public:
    string canObtain(string initial, string target) {
        int n = initial.size();
        int m = target.size();

        // 順
        for (int i = 0; i <= m - n; i++) {
            bool match = true;
            for (int j = 0; j < n; j++) {
                if (target[i + j] != initial[j]) match = false;
            }
            if (!match) continue;

            int lb = 0;
            for (int j = 0; j < i; j++) {
                if (target[j] == 'B') lb++;
            }
            int rb = 0;
            for (int j = i + n; j < m; j++) {
                if (target[j] == 'B') rb++;
            }
            if (lb != rb) continue;

            if (i != 0 && target[0] == 'A') continue;

            return "Possible";
        }

        // 逆
        reverse(initial.begin(), initial.end());
        for (int i = 0; i <= m - n; i++) {
            bool match = true;
            for (int j = 0; j < n; j++) {
                if (target[i + j] != initial[j]) match = false;
            }
            if (!match) continue;

            int lb = 0;
            for (int j = 0; j < i; j++) {
                if (target[j] == 'B') lb++;
            }
            int rb = 0;
            for (int j = i + n; j < m; j++) {
                if (target[j] == 'B') rb++;
            }
            if (lb != rb + 1) continue;

            if (target[0] == 'A') continue;

            return "Possible";
        }

        // 無理ぃ
        return "Impossible";
    }
};

SRM665 Div1 Easy "LuckySum"

解法

以下、参考にさせていただきました。m(_ _)m
kmjp.hatenablog.jp

事後

実装がちょっと難しくなると頭が混乱するのなんとかして

ソースコード

const long long INF = 123456789012345LL;
long long dp[20][2][3];
int sums[20];

class LuckySum {
    public:
    long long construct(string note) {
        int n = note.size();

        // sums初期化
        for (int i = 0; i < n; i++)
            sums[n - i - 1] = note[i] == '?' ? -1 : note[i] - '0';

        // dp初期化
        for (int d = 0; d <= n; d++)
            for (int c = 0; c < 2; c++)
                for (int e = 0; e < 3; e++)
                    dp[d][c][e] = INF;

        dp[0][0][0] = 0;

        // dp更新
        int ds[] = {7, 4, 0};
        long long p_10 = 1;
        for (int d = 0; d < n; d++) {
            for (int c = 0; c < 2; c++) for (int e = 0; e < 3; e++) {
                if (dp[d][c][e] == INF) continue;

                for (int i = 0; i < 3; i++)  for (int j = 0; j < 3; j++) {
                    int a = ds[i];
                    int b = ds[j];
                    int s = a + b + c;
                    int dight = s % 10;
                    int carry = s / 10;
                    int end = (a == 0 ? 1 : 0) + (b == 0 ? 1 : 0);

                    // 未完了のlackyNumberの数より使用するLackyNumberの数の方が多ければやらない
                    if (2 - e < 2 - end) continue;

                    // 最初の桁であり、endが1以上であればやらない
                    if (d == 0 && end >= 1) continue;

                    // sumsと合っていなければやらない
                    if (sums[d] != -1 && sums[d] != dight) continue;

                    // endが2であり、最後の桁でない、または繰り上がりがなければやらない
                    if (end == 2 && (d != n - 1 || c == 0)) continue;

                    dp[d + 1][carry][end] 
                        = min(dp[d + 1][carry][end], dp[d][c][e] + dight * p_10);
                }
            }
            p_10 *= 10;
        }

        // dp答え
        long long ans = INF;
        for (int e = 0; e < 3; e++) {
            ans = min(ans, dp[n][0][e]);
        }
        return ans == INF ? -1 : ans;
    }
};

SRM664 Div1 Easy "BearPlays"

解法

例のごとく他人だより。以下、参考にさせていただきました。m(_ _)m
mayokoex.hatenablog.com

事後

あ^~あるはずのない周期性に賭けてしまったんじゃ^~

ソースコード

class BearPlays {
    public:
    int pileSize(int A, int B, int K) {
        long long a = A;
        long long b = B;
        long long s = a + b;

        int m = pow_mod(2, K, s);

        long long mi = min(a, b);

        long long res = mi * m % s;

        long long ans = min(res, s - res);

        return (int)ans;
    }

    // a ^ b % mod 繰り返し2乗法!
    long long pow_mod(long long a, long long b, long long mod) {
        long long r = 1;
        while (b > 0) {
            if ((b & 1) != 0) {
                r *= a;
                r %= mod;
            }
            a *= a;
            a %= mod;
            b >>= 1;
        }
        return r;
    }

};