TopCoder SRM 639 Div1
今回はSRM639の解説です。
問題は
- Easy: 数学っぽい分析
- Medium: 組み合わせ
となっております。
Easy (250点)
問題
AとBのプレイヤーが交互にあるゲームで戦っている。ゲームはターン1からスタートし、ターンiで勝利した方には2i-1点入る。このときAとBが得た点数がそれぞれx, yと与えられる。これを実現するためにはAは最小何回勝たなければいけないか？もし条件を満たすものが存在しないときは-1を返せ。
制約条件
0 <= x, y <= 1,000,000,000,000
解法
まず、得られる点数は各ターンに2i-1なので、この和は常に平方数になります。したがって、2人の点数の和、すなわちx+yは平方数でなければならず、そうでないなら実行不可能ということになります。
上の考察からターン数はT=sqrt(x+y)であることがわかります。すると制約条件からターン数は高々10^6です。なので全探査できないかを考えてみます。
もし、Aがk回勝つとすると、点数の合計は勝利したターンをa[1], …, a[k]として
x = 2 * sum(a[i]) – k
になるはずです。
ということは、x+kが2で割り切れるとき、S=(x+k)/2がk個の相異なる自然数で分割できればいいことになります。ただし、使える数はターン数T以下です。
このとき、Sが満たすべき条件を考えます。Sは少なくとも1からkまでの和であり、多くともT-k+1からTまでの和です。
実はこの条件を満たしさえすれば、その間のSはk個の相異なる自然数に分割できます。なぜなら、最初に1, 2, …, kという風に数をa[1], …, a[k]に割り当てて、足りない分をa[k], a[k-1], …という順番で1ずつ足していってあげれば、良いからです。
このように足すと、a[1], …, a[k]が相異なるという条件を満たしたまま、目的の数を作ることができます。
なのでまとめると、ターン数Tを最初にもとめ、k=1, …, TについてS=(x+k)/2が上記の条件を満たすかどうかを小さい順に調べていってあげればいいです。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <tuple>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(lint i=0; i<n; i++)
#define REPP(i,s,e) for(lint i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
const int MAX_N = 1500000;
class AliceGame {
public:
long long findMinimumValue(long long x, long long y) {
lint sum = x + y;
if(sum == 0) return 0;
bool ok = false;
lint turn = 0;
for(turn=0; turn<=MAX_N; turn++) {
if(turn * turn == sum) {
ok = true;
break;
}
}
if(!ok) return -1;
for(lint k=0; k<=turn; k++) {
if((x + k) % 2 == 0) {
lint A = (x + k) / 2;
lint s = k * (k + 1) / 2;
lint t = (turn + turn - k + 1) * k / 2;
if(s <= A && A <= t) {
return k;
}
}
}
return -1;
}
};
この問題は盛大なChallenge祭りになっておりまして、おそらくChallengeで落ちたのはx=0, y=1のケースだと思います。
ちなみに、上の回答は線形探索でやっていますが、二分探索に書きかえればもう少し大きいケースでも通ると思います。
Medium (500点)
問題
N×Mのグリッドの各セルに0か1の数字が入っている。このグリッドは、ある直線に対して左右あるいは上下が同じになるときに折りたたむことができる。ありうる折りたたみ方をすべて試したときに得られる結果のグリッドの総数を答えよ。
解法
いつも通り、とても単純に考えてみます。
まず折りたたんだ時に得られる結果というのはどういう風に識別できるでしょうか？いちいちパターンが同じかどうかを試していては時間がかかりそうです。
ですが、折りたたんだ結果が必ず最初のグリッドの部分グリッドになることを考えると、グリッドの左端と右端、上端と下端だけを保存しておけば、パターンの識別が可能であることが分かります。
また、横方向の折りたたみと縦方向の折りたたみの順序は独立なので、横方向に折りたたんでできるパターン数と縦方向に折りたたんでできるパターンの積が答えになることもわかります。
このようなパターンをどう列挙するかですが、折りたためるところをどんどん折りたたんで深さ優先探索の要領で探索するのがよさそうです。
問題は計算量です。この探索の計算量はどのくらいなのかを見積もってみます。今、考えなくてはならないのは縦方向か横方向かのどちらかなので、ここでは横方向での折りたたみということで話を進めます。
すると左端と右端のペアの数は高々N^2個なのでメモ化しておけば、深さ優先の探索ノード数がO(N^2)で抑えられることが分かります。
次にある状態から折りたためるところを探す計算量を考えます。今左端lから右端r-1までの区間が折りたためるかをチェックするとします。
このとき、各列が同じかどうかを調べる計算量がO(M), 折りたたんだ時に対応する列が同じになっているかどうかを調べる計算量が最大O(N)なのでO(NM)で1つの状態が調べられます。
新しい状態の数として考えられるのはO(N^2)個なので、深さ優先の関数を1回実行する計算コストがO(MN^3)、トータルの計算量はO(MN^5)になります。
ところが、この問題ではNとMが250なので計算量が微妙に足りません。
ですが、2つの列が同じであるかどうかというのは前計算しておけますし、それを使えば、区間[l,r-1]が折りたためる区間なのかどうかも前計算しておけます。それぞれの計算量はO(MN^2)とO(N^3)です。
なので、この前計算を使うと新しい状態の列挙にはO(N)しかかかりません。従って、全体の計算量は高々250^3くらいで抑えられます。
これで無事答えが求まります。
注意として、同じ状態を重複して列挙しないように、左端と右端のペアがすでに探索ずみであれば0を返すように深さ優先の関数を書いてあります。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <tuple>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
int table[256][256];
int temp[256][256];
int dp[256][256];
bool same[256][256];
bool symm[256][256];
class BoardFolding {
public:
int n, m;
int tonumber(char c) {
if('0' <= c && c <= '9') return c - '0';
if('a' <= c && c <= 'z') return c - 'a' + 10;
if('A' <= c && c <= 'Z') return c - 'A' + 36;
if(c == '#') return 62;
if(c == '@') return 63;
return -1;
}
void transpose() {
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
temp[i][j] = table[j][i];
}
}
swap(n, m);
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
table[i][j] = temp[i][j];
}
}
}
int dfs(int l, int r) {
int& ret = dp[l][r];
if(ret == -1) {
ret = 1;
for(int rr=l+2; rr<=r; rr+=2) {
if(symm[l][rr]) {
ret += dfs((l+rr)/2, r);
}
}
for(int ll=r-2; ll>=l; ll-=2) {
if(symm[ll][r]) {
ret += dfs(l, (ll+r)/2);
}
}
} else {
return 0;
}
return ret;
}
int calc() {
REP(i,n) {
REP(j,n) {
same[i][j] = true;
REP(k,m) {
if(table[i][k] != table[j][k]) {
same[i][j] = false;
break;
}
}
}
}
memset(symm, 0, sizeof(symm));
REP(l,n) {
for(int r=l+2; r<=n; r+=2) {
int ll, rr;
symm[l][r] = true;
for(ll=l, rr=r-1; ll<rr; ll++, rr--) {
if(!same[ll][rr]) {
symm[l][r] = false;
break;
}
}
}
}
memset(dp, -1, sizeof(dp));
int ret = dfs(0, n);
return ret;
}
int howMany(int N, int M, vector <string> paper) {
this->n = N;
this->m = M;
REP(i,n) {
REP(j,M) {
table[i][j] = (tonumber(paper[i][j/6]) >> (j % 6)) % 2;
}
}
int a = calc();
transpose();
int b = calc();
return a * b;
}
};
まとめ
EasyのChallenge祭りは予想していませんでした。かなり確信を持ってSubmitしたのですが、見事に撃墜されました(1byte違い)。
Mediumは深さ優先っぽいなぁというところまで思いつくのが限界で、二段構えの前計算を行うというのはコンテスト中には思いつきませんでした。
つらいところですが、これで今回の解説を終わります。
最後までお読みいただきありがとうございました。