TopCoder SRM 595 Div1
さっき前回のものを解説したばかりですが、595回も解説します。
ちなみに今回は30分でEasyだけ通したけどレート全然あがらず。
やはり連続でEasy通さないとダメなのか。
気を取り直して解説行きます。
Easy (250点)
この問題ではボールが何個か用意されていて、色塗りロボットがこのボールに白か黒かの色をつけます。
色をつける作業はM回行われて、それぞれの回では位置L[i]と位置R[i]の間にあるボールが黒か白かに塗られます。
さてこのときボールの最終的な塗り方は何通りあるか？という問題。
解決の糸口と思われるのはテストケースの答えが2の累乗の数しかないということ。おそらく答えは2の累乗になるのだろうと考える。
ではそれぞれのケースで2を何乗すればいいのかだが、端的にいうと最終状態で各ボールに塗られる色は何回目の作業で塗られた色なのかを考えればいい。
この問題ではロボットが色を塗らないという選択肢はないので、これでOK。
さてこれさえ分かれば、最終状態に表れる作業の数を数えて、それを2の累乗にすればいいです。
以下が正解のコードです。
#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 LittleElephantAndIntervalsDiv1 {
public:
long long getNumber(int M, vector <int> L, vector <int> R) {
int N = L.size();
vector<int> v(M,-1);
REP(i,N) {
for(int j=L[i]; j<=R[i]; j++) {
v[j-1] = i;
}
}
set<int> s;
for(int i=0; i<M; i++) {
if(v[i] >= 0) {
s.insert(v[i]);
}
}
int p = s.size();
return (1ll << p);
}
}
Medium (500点)
MediumもEasyと同じく区間を扱う問題です。
MediumではR,G,Bという文字のみからなる文字列が与えられます。ここから互いに交わらない2つの区間[a,b], [c,d]を選んだ時、部分文字列をつなげて、新たな文字列Tを作ります。
このとき、Tのなかに連続して現れるGの数がminGreen以上になる場合の数を答える問題。
コンテスト中は、割と愚直にやればできるのでは？と思いコードを書きましたが、いずれかの文字列の真ん中にminGreen以上連続するGが現れる場合をうまく扱えずNG。
では、どうすればよいのかというとDPを使ってどうにかします。
基本的な方針としては
- ある位置iまでの文字を使った時に後ろにいくつのGが並ぶかを調べる
- ある位置i以降の文字を使った時に先頭にいくつのGが並ぶかを調べる
ということをして、互いに交わらない区間になり、なおかつminGreen以上のGが間に並ぶ時だけ数を足しあげていきます。
さて、問題の真ん中にminGreen以上のGが並んでしまう場合ですが、これは後ろにminGreen個のGが現れる場合と同等に扱えばいいです。
逆にある位置以降を見たときには先頭にminGreen個以上のGが現れる場合と同等に扱います。
今回はちょっと分かりづらいので先にコードを載せます。
#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;
LL dp[2511][2511];
class LittleElephantAndRGB {
public:
long long getNumber(vector <string> list, int minGreen) {
string S = "";
REP(i,list.size()) S += list[i];
int n = (int)S.size();
memset(dp, 0, sizeof(dp));
for(int i=n-1; i>=0; i--) {
int mid = 0, post = 0, ma = 0, flag = 0;
for(int j=i; j>=0; j--) {
if(S[j] == 'G') {
if(flag == 0) post++;
mid++;
ma = max(ma, mid);
} else {
mid = 0;
flag = 1;
}
if(ma >= minGreen) {
dp[i][0]++;
} else {
dp[i][minGreen-post]++;
}
}
}
for(int i=0; i<n; i++) {
for(int j=0, sum=0; j<=minGreen; j++) {
sum += dp[i][j];
if(i == 0) {
dp[i][j] = sum;
} else {
dp[i][j] = dp[i-1][j] + sum;
}
}
}
LL ans = 0;
for(int i=1; i<n; i++) {
int mid = 0, pre = 0, ma = 0, flag = 0;
for(int j=i; j<n; j++) {
if(S[j] == 'G') {
if(flag == 0) pre++;
mid++;
ma = max(ma, mid);
} else {
mid = 0;
flag = 1;
}
if(ma >= minGreen) {
ans += dp[i-1][minGreen];
} else {
ans += dp[i-1][pre];
}
}
}
return ans;
}
}
さて、このコードで何をしているのかというと、まずi番目の文字まで使った時の
- 真ん中を含めたGの連続数を数えるための一時変数 (mid)
- 後ろに何文字のGが連続して現れるか (post)
- 真ん中を含めたGの最大連続数 (ma)
- 後ろの文字を数えている途中かを表すフラグ
を計算します。
次にdp表を更新していますが、ここでは、
- i番目以降の文字列で足りないGを補うとき、i以下の全ての場合について考慮する必要がある
- i番目までの文字を使った時足りないGの数がk個だったなら、加える文字はk個以上なら何でもいい
という2つのポイントに基づいて表を更新しています。
最後にi番目以降の文字列を使った場合に先頭に何文字のGが連続するかを求めて(pre)、dp表に入れておいたGの不足分以上を補える場合に答えを足しあげるということをします。
これでうまく答えが得られるはずです。
まとめ
最近、Easyを早々にとくも、あとでコーナーケースが見つかってテストに落ちるということが結構あったので、慎重にいったのですが、思ったより点数が出なくて残念です。
連続してEasyをとくことを目標にしながら、チャンスがあればMediumも狙いたいところです。
というわけで、今回の解説はここまでにします。
最後までお読みいただきありがとうございました。