SRM 613 Div2

反省点

250と500を通して559.35pt (61 place)．
Rating 731 -> 870．

• 1000の解法を考える時間が短かったので，焦って無意味なことをしてしまった．

[250 TaroString]

通した．なんか考え方が汚すぎる．

(問題文)

大文字のアルファベットからなる文字列Sが与えられる．
ある文字'X'を選びSのすべての文字'X'を消すという操作ができる．
そのような操作をして文字列Sを"CAT"に変更できるか．

(方針)

文字列Sを"CAT"に変更できる場合は，文字列Sに文字'C'，'A'，'T'が1文字づつ含まれており，かつ，その並びが'C'，'A'，'T'となっている．

[500 TaroFriends]

通した．初期値を決めるのが遅かった．
coordinatesを短い変数名に変えると楽かも．

(問題文)

1次元の直線上に猫がN匹いて，それぞれがいる座標が与えられる．そして，それぞれの猫が左か右にXだけ移動する．
このとき，移動した後の一番左にいる猫と，一番右にいる猫の距離の最小値を答える．

(方針)

この問題では，すべての猫の移動する距離が一定で，求めるのが移動後の端っこの猫なので，右向きに移動する猫と左向きに移動する猫の境界を決めれば，それぞれの猫の移動する向きは決定される．
境界の決め方はN通りなので，それぞれに対して距離を計算すれば求まる．

[1000 TaroCards]

計算量をおとす方法が思いつかなかったので，
単純に場合分けをしてたらシステムテストで落ちた．

(問題文)

N枚のカードが与えられる．カードiにはfirst[i]とsecond[i]という2つの整数が書かれている．
first[i]は1からNの値で，すべてのfirstの値は異なる．
second[i]は1から10までの値．
カードを何枚か選んだ時に，選んだカードに書かれた異なる数字の数がK以下となるカードの選び方を答える．

(方針)

メモ化の仕方を工夫する．
まず，firstの値でカードを昇順にソートする．カードの値がfirstだけの場合はi番目のカードを入れるときは必ず異なる数字になるので，前のカードの選び方によらずに異なる数字が1つ増える．この場合は，メモ化再帰やDPができ時間内に計算ができる．
次に，secondの値を追加した場合を考える．
secondの値は1増加の昇順になっていないのでi番目のカードを選んだときに，異なる数字が1つ増えるのか分からない．なので，選択したカードのsecondの値を覚えておく必要がある．secondの値は高々10なのでメモ化再帰をすることによって時間内に計算できる．

ソースコード

[250 TaroString]

#include <vector>

using namespace std;

class TaroString {
public:
    string getAnswer(string S) {
        int c, a, t;
        const int n = S.size();

        c = a = t = 0;
        for (int i = 0; i < n; ++i) {
            if (S[i] == 'C')
                ++c;
            else if (S[i] == 'A')
                ++a;
            else if (S[i] == 'T')
                ++t;
        }

        if (c == 1 && a == 1 && t == 1) {
            c = a = t = 0;
            for (int i = 0; i < n; ++i) {
                if (S[i] == 'C') {
                    ++c;
                    if (a > 0 || t > 0)
                        return "Impossible";
                }
                else if (S[i] == 'A') {
                    ++a;
                    if (t > 0)
                        return "Impossible";
                }
                else if (S[i] == 'T') {
                    ++t;
                }
            }
            return "Possible";
        }
        else
            return "Impossible";
    }
};

[500 LCMSetEasy]

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

class TaroFriends {
public:
    int getNumber(vector <int> coordinates, int X) {
        const int n = coordinates.size();

        if (n == 1) {
            return 0;
        }

        sort(coordinates.begin(), coordinates.end());
        ll len = abs(coordinates[n - 1] - coordinates[0]);

        for (int i = 0; i < n - 1; ++i) {
            ll r = -1e10, l = 1e10, x;

            for (int j = 0; j < n; ++j) {
                if (j <= i) {
                    x = coordinates[j] + X;
                }
                else {
                    x = coordinates[j] - X;
                }

                r = max(r, x);
                l = min(l, x);
            }

            len = min(len, abs(r - l));
        }

        return len;
    }
};

[1000 ElephantDrinkingEasy]

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstring>

using namespace std;

typedef long long ll;

class TaroCards {
    int N, K;
    vector<pair<int, int>> fs;
    ll memo[52][110][(1 << 10)];

    ll Rec(int idx, int select, int mask);
public:
    ll getNumber(vector <int> first, vector <int> second, int _K) {
        N = first.size();
        K = _K;

        for (int i = 0; i < N; ++i)
            fs.push_back(pair<int, int>(first[i], second[i]));
        sort(fs.begin(), fs.end());

        for (int i = 0; i <= N; ++i)
            for (int j = 0; j <= 2 * N; ++j)
                for (int k = 0; k < 1 << 10; ++k)
                    memo[i][j][k] = -1;

        return Rec(0, 0, 0);
    }
};

ll TaroCards::Rec(int idx, int select, int mask)
{
    if (select + __builtin_popcount(mask) > K)
        return 0;
    if (idx >= N)
            return 1;

    if (memo[idx][select][mask] != -1)
        return memo[idx][select][mask];

    // カードを選ばない
    ll res = Rec(idx + 1, select, mask);


    // カードを選ぶ
    int f = fs[idx].first - 1, s = fs[idx].second - 1;
    if (f < 10)
        res += Rec(idx + 1, select, mask | (1 << f) | (1 << s));
    else
        res += Rec(idx + 1, select + 1, mask | (1 << s));

    return memo[idx][select][mask] = res;
}