読者です 読者をやめる 読者になる 読者になる

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通りなので,それぞれに対して距離を計算すれば求まる.
f:id:tatanaideyo:20140322023120p:plain

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