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)とおく.
緑を求めて,赤色を求める.
[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の要素とする.
例を下の図に示す.
状態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; }