SRM605 DIV2

Rating 829 -> 777.

反省点

  • Arenaは開始5分前ぐらいに開くとサーバーに繋がらないので,前もって繋ぐ.
  • 先入観をなくす.

[250 AlienAndPassword]

通した.

(問題)

文字列Sが与えられる.1文字を消去したときにできる,
異なる文字列の数を求める.

(方針)

1文字消してできるすべての文字列を作成して,
mapに挿入する.mapの要素数が求める答え.

Editorialにはsetを使っている.確かにこの場合はsetが良いので反省.
あと,O(n)の方法として,隣接している文字が異なる場合をカウントしている.
1文字とって異なる文字列の数をカウントする→1文字取っても異ならない文字列は?,という思考を短時間で行えるようにしたい.

[500 AlienAndGames]

解法が思いつかずに通せなかった.

(問題)

最大で50x50の盤面が与えられる.それぞれの領域は'B'か'W'である.
できる操作は,1つの行を選び,その行のすべての列を反転させることである.
求める答えは,'W'からなる正方形領域の最大の面積.

(方針)

正方形の左上の領域を固定して考える.この時の領域の座標を(x, y)とおく.
緑を求めて,赤色を求める.
f:id:tatanaideyo:20140122010632j:plain

[1000 AlienAndSetDiv2]

問題を見てない.復習する.

(問題)

1<= N <= 50, 1 <= K <= 10が与えられる.集合{1, ..., 2 * N}の要素を次の条件を満たすように集合A, Bに分割する.
1.集合Aと集合Bの要素数はN.
2.集合Aと集合Bの要素を昇順に並べた時に|A[i] - B[i]| <= K.
条件を満たすような集合の分割の場合の数が求める答え.

(方針)

まったく分からなかったので,TopCoder SRM605 - Algorithmer’s noteさんの解法を参考に実装.
bitDPで実装をした.
dp[Aの要素数][Bの要素数][直前のK個の状態] := 場合の数.
要素を1から順に追加する.Aの要素数をn,Bの要素数をmとおくと,次に追加する数はn+m+1である.直前のK個の状態をビットで持つ.最下位ビットからi番目が1ならば,数n+m-iは集合Bの要素であり,0ならば集合Aの要素とする.
例を下の図に示す.
f:id:tatanaideyo:20140122103319j:plain
状態dp[n][m][k]の時,次の3つの場合分けが考えられる.
1.n = m
2.n > m
3.n < m
1の場合は数n+m+1は集合Aにも,集合Bにも追加することができる.
2の場合は数n+m+1を集合Aに追加することができるが,集合Bでは,条件2の|A[m + 1] - B[m + 1]| <= Kを満たす場合のみ追加することができる.
これは,直前のK個の要素で集合Aに追加されている数がn-m以上であるかを判定すればよい.
3の場合は2の場合と同様に行う.

ソースコード

[250 AlienAndPassword]

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class AlienAndPassword {
public:
    int getNumber(string S) {
        map<string, bool> memo;

        for (int i = 0; i < S.size(); ++i) {
            string tmp = S;
            tmp.erase(i, 1);
            cerr << tmp << endl;
            memo.insert(map<string, bool>::value_type(tmp, true));
        }

        return memo.size();
    }
};

[500 AlienAndGames]

#include <iostream>
#include <vector>

using namespace std;

class AlienAndGame {
private:
    vector<string> board;
    int MaxSquare(int y, int x);
    int n, m;
public:
    int getNumber(vector <string> _board) {
        board = _board;
        n = board.size();
        m = board[0].size();
        int ans = 0;

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                ans = max(ans, MaxSquare(i, j));

        return ans * ans;
    }
};

int AlienAndGame::MaxSquare(int y, int x)
{
    int res = 1;
    vector<int> sum(n - y, 1);

    for (int i = 0; i + y < n; ++i) {
        bool turn = (board[i + y][x] == 'W') ? false : true;

        for (int j = 1; j + x < m; ++j) {
            if (board[i + y][j + x] == 'W') {
                if (turn)
                    break;
                sum[i]++;
            }
            else {
                if (!turn)
                    break;
                sum[i]++;
            }
        }
    }

    int len = 100;
    for (int i = 0; i < sum.size(); ++i) {
        len = min(sum[i], len);
        res = max(res, min(len, i + 1));
    }

    return res;
}

[1000 AlienAndSetDiv2]

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef long long ll;

class AlienAndSetDiv2 {
    const ll MOD = 1000000007;
    int N, K;
    // dp[i: Aの要素数][j: Bの要素数][直前のK個の状態, Aに入れたならば0,Bに入れたならば1]
    // := (1, ..., i + j)までの要素を入れたときの取りうる場合の数.
    ll dp[52][52][1 << 11];

    inline void Add(ll &a, ll b);
public:
    int getNumber(int _N, int _K) {
        N = _N;
        K = _K;
        int mask = (1 << K) - 1;
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;

        for (int i = 0; i <= N; ++i) {
            for (int j = 0; j <= N; ++j) {
                for (int k = 0; k < (1 << K); ++k) {
                    if (i == j) {
                        Add(dp[i + 1][j][(k << 1) & mask], dp[i][j][k]);
                        Add(dp[i][j + 1][((k << 1) & mask) | 1], dp[i][j][k]);
                    }
                    else if (i > j) {
                        Add(dp[i + 1][j][(k << 1) & mask], dp[i][j][k]);

                        int cnt = 0;
                        for (int l = 0; l < min(K, i + j); ++l)
                            if (((k >> l) & 1) == 0)
                                ++cnt;
                        if (cnt >= i - j)
                            Add(dp[i][j + 1][((k << 1) & mask) | 1], dp[i][j][k]);
                    }
                    else if (i < j) {
                        Add(dp[i][j + 1][((k << 1) & mask) | 1], dp[i][j][k]);

                        int cnt = 0;
                        for (int l = 0; l < min(K, i + j); ++l)
                            if (((k >> l) & 1) == 1)
                                ++cnt;
                        if (cnt >= j - i)
                            Add(dp[i + 1][j][(k << 1) & mask], dp[i][j][k]);
                    }
                }
            }
        }

        ll res = 0;
        for (int k = 0; k < (1 << K); ++k)
            Add(res, dp[N][N][k]);

        return res;
    }
};

inline void AlienAndSetDiv2::Add(ll &a, ll b)
{
    a = (a + (b % MOD)) % MOD;
}