TopCoder SRM 592 Div1
今回の問題は
- Easy: 貪欲 + ひらめき？
- Medium: 動的計画法
てな感じでした。Easyは思いつけばすぐですが、Mediumはさっぱりですね。
それでは解説行きます。
Easy (300点)
この問題はR,G,Bの三色のボールを決められた順番でテーブルに1列に置いていくゲームに関する問題です。
ボールをテーブルに置いた時に得られる点数には次のような規則があります。
- ボールを既に置いてある列の端に置く場合、得られる点数はすでにある列の中の異なるボールの色の数だけ点数が入る
- ボールを既に置いてある列の端以外に置く場合には、新しく置いたボールの右側と左側で、異なるボールの色の数だけ点数が入る
赤のボールしかないのに5点を取ることができるTest Case #3は個人的に少し分かりづらかったです。
つまり今おこうとしているボールが何色かは、入ってくる点数には関係しません。なので全部同じ色でも点数が取れます。
さて問題はボールを置いた時にどういう場合に何点入るかです。
思いつくべきポイントは入るポイントがR,G,Bの玉の組み合わせには関係なく、Rの数、Gの数、Bの数で独立に計算できるというところです。
つまり、ある色のボールが
- テーブルに既に2個以上あるなら、その色について2点
- テーブルに既に1個あるなら、その色について1点
- 置いていなければ点数は得られない
というルールで点数を取れます。
ですから、ボールを置くたびに、各色のボールが何個あるかを保存しておいて、上のルールで点数を足していってやればいいです。
以下が正解のコードです。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
#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
typedef pair<int,int> P;
typedef long long LL;
class LittleElephantAndBalls {
public:
int getNumber(string S) {
int n = S.size();
vector<int> s;
for(int i=0; i<n; i++) {
if(S[i] == 'R') s.push_back(0);
if(S[i] == 'G') s.push_back(1);
if(S[i] == 'B') s.push_back(2);
}
vector<int> cnt(3, 0);
int res = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<3; j++) {
if(cnt[j] >= 2) {
res += 2;
} else if(cnt[j] == 1) {
res += 1;
}
}
cnt[s[i]]++;
}
return res;
}
}
実装自体はたいして難しくないです。たぶんコーナーケースもそんなにないと思われます。
Medium (500点)
この問題では1からNまでの数からなる数列がA,Bの2つ与えられているときに、次のような関数を定義します。
magic(A,B) = max(a1, b1) + … + max(aN, bN)
このときに、関数の値がKを超えるようなものの場合の数を求めるのが問題の目的になります。
まず1つ目のポイントとして、AとBの両方の並びを全て調べる必要はありません。
なぜなら、Aを1, …, Nで固定しておいて、Bを適当に入れ替えてやれば、数の組み合わせとしては全ての場合が得られるからです。
あとはこの時の場合の数にN!を掛けてやれば、AとBの両方を並べ替えた場合を調べるのと同じです。
問題はNが最大50なのでBの並びを全て調べるわけにはいかないということです。まぁ、当然DPで問題を解くわけです。
とりあえず、あるnまで使ったときにk以上になるようなものの数が分かっていれば、n+1を新しく使ったときに関数の値がn+k+1以上にはなります。
なのでdp[n][k]みたいにしてDP表を作ることを考えてみるのですが、実際にはn+1を新しく使ったときn+k+1よりずっと大きな数を作ることができるので、これだけでは不十分です。
そこで、次はAとBの数をnまで使うときに必ずしも、その時点で組み合わせの相手を決める必要がない、というルールを考えましょう。
まだ組み合わせの相手が決まっていない数字の数をrとして、DP表をdp[n][r][k]のように持ちます。
このとき、
- nは現在、考えている数列中の最大の数。つまり1,…,nをつかっている状態
- rはまだ組み合わせが決まっていない数字の数。AとBで未決定のものの数は同じなので、その数をrとする。
- kは関数の取る値
- dp[n][r][k]は上記の条件を満たす数列の組み合わせの場合の数
とします。
次にDP表の更新のルールです。
(ルール1) (n-1)まで数を使っているとき、新しく加える数nの相手を決定しないとするとrの数が1増えてkの値は変わらない。
(ルール2) 新しく加えるnがk以下の場合には、Aの末尾にnを追加して、Bのnを未決定のものと組み合わせることができる。またA末尾のnにBの未決定を割り当てて、Bのnを未決定のままにすることもできる。いずれの場合も、未決定の物の数は変わらず、関数の値はn増える。
(ルール3) 新しく加えるnがk >= 2nを満たす場合には、未決定のものに対してA側、B側の双方でnを割り当てる。すると関数の値が2n増える。このときrは1しか減らないことに注意。
ルール2の場合には未決定になっているものがA側とB側の双方でr個ずつあり、A側のnに未決定を割り当てるか、B側のnに未決定を割り当てるかで、組み合わせの仕方は(2*r+1)通りあります。
AのnとBのnを組み合わせる場合があるので、(2_r)ではなく(2_r+1)通りです。
ルール3の場合にはAに加わるnの相手の決め方がr通り、Bに加わるnの相手の決め方がr通りあります。
更新の方法をまとめると、次のようになります。
- (ルール1) dp[n][r][k] += dp[n-1][r-1][k]
- (ルール2) dp[n][r][k] += (2*r+1) * dp[n-1][r][k-n]
- (ルール3) dp[n][r][k] += (r+1) * (r+1) * dp[n-1][r+1][k-2*n]
ルール3の場合についている係数はdp[n-1][r+1][k-2_n]の場合に未決定が(r+1)であるため(r+1)_(r+1)になるので注意してください。
上記の方法でDP表を埋めたら、最後に答えを求めます。
答えの場合の数はN個すべての数を使っていて、なおかつ未決定のものが0個の場合ですから、このうち関数の値がK以上のものを足しあげます。
これで組み合わせは決まるので、それにN!を書けたものが答えになります。
長くなりましたが、以下が正解のコードです。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
#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
typedef pair<int,int> P;
typedef long long LL;
const LL MOD = 1000000007;
int dp[55][55][2505];
class LittleElephantAndPermutationDiv1 {
public:
int getNumber(int N, int K) {
int n2 = N * N;
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
for(int n=1; n<=N; n++) {
for(int r=0; r<=n; r++) {
for(int k=0; k<=n2; k++) {
LL val = 0;
if(r >= 1) {
val += dp[n-1][r-1][k];
}
if(k >= n) {
val += (LL)(2*r+1) * dp[n-1][r][k-n];
}
if(k >= 2*n) {
val += (LL)(r+1) * (r+1) * dp[n-1][r+1][k-2*n];
}
dp[n][r][k] = val % MOD;
}
}
}
LL res = 0;
for(int k=K; k<=n2; k++) {
if(dp[N][0][k] >= 0) {
res += dp[N][0][k];
res %= MOD;
}
}
for(int i=1; i<=N; i++) {
res = (res * i) % MOD;
}
return (int)res;
}
}
いくつか実装に関して注意することですが、この問題のDP表は少しサイズが大きいのでlong longで持つとメモリが足りません。
ですのでDP表をintで持つことになります。表の値自体がオーバーフローしないように注意するのはもちろんですが、(r+1)*(r+1)などの係数を書けるときにlong longにキャストしないと表に入れる前にオーバーフローするので注意してください。
それにしても、これを空で思いつく人は、いったいどういう頭脳をしているんだろうか。
まとめ
今回はEasyが300点問題だったので、何事かと思いましたが、思いつきさえすれば、そんなに難しくはないと思います。コーナーケースもないですし。
Mediumは分からなかったので何とも言えないですが、実装に加えて、普通にlong longでやるとメモリ足りないというのは、なかなか罠な気がしました。
それでは、今回はここまでで。お読みいただきありがとうございました。