TopCoder SRM 650 Div1
こんにちはtatsyです。本日もSRMの解説いきます。
Easy (250点)
問題
太郎はAとBからなる長さNの文字列を作ろうとしている。この文字列を作るときにposition[i]にはvalue[i]が来ることが分かっている。このとき、余っている部分にAとBを埋めて、2文字AあるいはBが続いている箇所数が最小になるようにしたい。この最小の文字列は何種類作れるか？1,000,000,007で割った余りを求めよ。
解法
まず、大事なこととして、文字列の連続した部分がpositionsとvaluesで指定されていたとしても、そこの部分はもう変えられないので、文字が連続するペア数は変わりません。
大事なのは文字の決まっていない部分の両端にある数字だけです。例えば、
A _ _ _ _ B (間が偶数個かつ両端が違う文字)
のようになっているときは、
A B A B A B
以外にはなりえません。そうでなければAあるいはBを続けなくてはいけないからです。同様に
A _ _ _ _ _ A (間が奇数かつ両端が同じ文字)
のときも
A B A B A B A
以外にはなりえません。ですので、問題は間が偶数かつ両端が同じ文字の時か、間が奇数かつ両端が違う文字の時です。
さて、このとき、連続する文字が最小になる場合は
A _ _ _ _ A (間が偶数で両端が同じ文字)
なら
A B A B A A
A B A A B A
A A B A B A
A B B A B A
A B A B B A
の5通りが考えられます。同様に間が奇数で両端が違う文字の時も(間の数+1)が場合の数になります。
したがって、文字を出現位置順にソートして、その文字と文字の間について、上記の場合の数を計算し、かけ合わせていけばOKです。
一応、再度補足しておきますが、今回は連続する文字数(AAAなら3文字)ではなく2文字続くペアの数(AAAなら2組)を最小化したいので、空白部分の両端以外は考える必要がありません。
#define Integer int
#define REP(i,n) for(Integer i=0; i<n; i++)
#define ALL(a) (a).begin(), (a).end()
typedef pair<int,char> P;
typedef long long lint;
const lint mod = (lint)1.0e9+7;
class TaroFillingAStringDiv1 {
public:
int getNumber(int N, vector<int> position, string value) {
int m = position.size();
vector<P> v;
for(int i=0; i<m; i++) {
v.push_back(make_pair(position[i], value[i]));
}
sort(v.begin(), v.end());
lint ans = 1;
for (int i = 0; i < m - 1; i++) {
int n1 = v[i].first;
int n2 = v[i+1].first;
int gap = n2 - n1 - 1;
if (gap == 0) continue;
char c1 = v[i].second;
char c2 = v[i+1].second;
if (c1 == c2) {
if (gap % 2 == 0) {
ans = (ans * (gap + 1)) % mod;
}
}
else {
if (gap % 2 == 1) {
ans = (ans * (gap + 1)) % mod;
}
}
}
return (int)ans;
}
};
Medium (550点)
問題
ある国は設立からh年が経過しており、現在の街はノードが2^h-1個の平衡二分木構造を持っている。今、王様がこの街に適当に3本の道を追加した。どの街とどの街の間に道があるかという情報が与えられるので、その道の情報が正しいかどうかを判別せよ。
解法
平たく言うと、適当な道を3個取り除いた構造が平衡二分木になっているかどうかをチェックすればいいです。
が、当然ながら削るべき3本の道の選び方はとてもたくさんあるので、これでは計算が間に合いません。
で、どうするかというと、どこがルートになるかを決めて、そこから順に上から、子となる2つのノードを次々に選んでいきます。
それでうまいこと平衡二分木になったら探索成功で情報は正しいということになります。
探索のやり方ですが、セグメント木みたいな感じで子ノードを2i+1と2i+2に持たせて、1つずつ番号をインクリメントしていきます。
といっても言葉ではだいぶ説明しづらいので詳しくはコードを見てください。
で、この探索方法だけだと一部TLEになる入力があるので、もう少し枝刈りしてあげます。
今回の問題の条件だと、各ノードのdegreeは6以上にはならないので、これを利用して枝刈りをします。
下のコードでは親ノードを除いてdegreeが5以上になったら、探索を中断します。
こうすると一応すべてのテストケースで答えが出ます。
なんですけど、これって、もう少し特殊なケース入れたらTLEになりそうなんじゃないかな、というところです。
そこらへんはまだ考察不足です。
typedef long long lint;
typedef pair<int,int> pii;
typedef pair<lint,lint> pll;
#define Integer int
#define REP(i,n) for(Integer i=0; i<n; i++)
#define REPA(i,s,e) for(Integer i=s; i<=e; i++)
#define REPD(i,s,e) for(Integer i=s; i>=e; i--)
#define SIZ(a) (Integer)(a).size()
#define ALL(a) (a).begin(), (a).end()
vector<int> edges[1200];
int nodes[1200];
bool vis[1200];
int n;
class TheKingsRoadsDiv1 {
public:
bool check(int id, int mask) {
if (id * 2 + 1 == n) return true;
int v = nodes[id];
int cnt = 0;
for (int i = 0; i < edges[v].size(); i++) {
if (!vis[edges[v][i]]) cnt++;
}
if (cnt > 5) return false;
for (int i = 0; i < edges[v].size(); i++) {
int t1 = edges[v][i];
if (vis[t1]) continue;
nodes[id * 2 + 1] = t1;
vis[t1] = true;
for (int j = 0; j < i; j++) {
int t2 = edges[v][j];
if (vis[t2]) continue;
nodes[id * 2 + 2] = t2;
vis[t2] = true;
int nmask = mask | (1 << t1) | (1 << t2);
if (check(id + 1, nmask)) {
return true;
}
vis[t2] = false;
}
vis[t1] = false;
}
return false;
}
string getAnswer(int h, vector<int> a, vector<int> b) {
n = (1 << h) - 1;
for (int i = 0; i<n; i++) edges[i].clear();
int ne = (int)a.size();
for (int i = 0; i < ne; i++) {
if (a[i] == b[i]) continue;
edges[a[i] - 1].push_back(b[i]-1);
edges[b[i] - 1].push_back(a[i]-1);
}
bool ok = false;
memset(vis, 0, sizeof(vis));
for (int v = 0; v < n; v++) {
vis[v] = true;
nodes[0] = v;
if (check(0, 0)) {
ok = true;
break;
}
vis[v] = false;
}
return ok ? "Correct" : "Incorrect";
}
};
まとめ
今回のMediumはそれなりに解は見えかけたのですが、計算量の問題は結構難しそうな印象がありました。
うーん、いつになったらMedium解けるんだ？また、次がんばろう。