TopCoder SRM 607 Div1
こんにちはtatsyです。
最近はというと、少し研究の方に集中しようということでSRMをさぼっておりましたが、最近練習をぼちぼちやっております。
というわけでSRM607の問題を解きましたので軽く解説をしたいと思います。
この回の問題は
- Easy: DP (期待値)
- Medium: 条件整理
という感じの解法になっております。
とはいってもMediumは問題の条件をいかに同値な条件に置き換えるかというところなので、整理とはちょっと違うかもですが。
いずれにしても解説始めます！まずEasyから。
Easy (250点)
この問題はある長い文字列Sが与えられたとき、その中に回文となる部分文字列がいくつあるかを答える問題。
ただし、文字列の中には？という文字が含まれていて、そこにはa-zまでも26文字がランダムに配置されます。
その場合には回文となる部分文字列の数の期待値を答えます。
まず最初に注意ですが、この問題では長い文字列Sを得るためにいくつかの文字列を連結する必要があります。
まぁ、ここまでは記事を読んでいる人には当たり前かもしれないですが一応断っておきます。
さて長い文字列が得られたら次は回文の数を数える段階に入ります。
もっともナイーブな方法は、長さが1のものから順に、回文になりうるか、なりうるなら確率はどのくらいか、を計算してたしあげるという方法です。
この計算量は文字列の長さNに対してO(N^3)です。なぜなら、部分文字列の始まる位置が1からNまで、長さが1からNまで、そしてその部分文字列が回文になるかをチェックするのにO(N)必要だからです。
この問題の想定だとNは最大50×50×2で5000になる可能性がありますので、このやり方ではTLEになってしまいます。
ではどうするかというとDPを使います。
僕はDP表を
dp[部分文字列の開始位置][部分文字列の長さ] = その部分文字列が回文になる確率
という風に持ちました。
dp表の更新は開始位置をp、長さをlとするとき、
dp[p][l] = dp[p+1][l-2] × (S[p]とS[l-p-1]が同じ文字になる確率）
となります。S[p]とS[l-p-1]は部分文字列の中心に対称な位置にある文字です。
あとは上記の要領でDP表を更新していって、最後にDP表の該当部分を足しあげれば完成です。以下が正解のコードです。
#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;
double dp[5010][5010];
class PalindromicSubstringsDiv1 {
public:
double expectedPalindromes(vector <string> S1, vector <string> S2) {
stringstream ss;
REP(i,S1.size()) ss << S1[i];
REP(i,S2.size()) ss << S2[i];
string S;
ss >> S;
memset(dp, 0, sizeof(dp));
int ns = S.size();
for(int p=0; p<ns; p++) {
dp[p][0] = 1.0;
dp[p][1] = 1.0;
}
for(int len=2; len<=ns; len++) {
for(int i=0; i+len<=ns; i++) {
double& val = dp[i][len];
char a = S[i];
char b = S[i+len-1];
if(a != '?' && b != '?') {
if(a != b) {
val = 0.0;
} else {
val = dp[i+1][len-2];
}
} else {
val = dp[i+1][len-2] / 26.0;
}
}
}
double ret = 0.0;
for(int l=1; l<=ns; l++) {
for(int i=0; i<ns; i++) {
ret += dp[i][l];
}
}
return ret;
}
};
Medium (475点)
さて続きましてはMediumです。
この問題は自転車のダイヤル鍵のようなもので、もっとダイヤルの桁数が多いものを考えて、ある状態から別の状態に移すための最小の回転数を求める問題です。
ただし、この問題では連続して隣り合っている桁はいくつでも同時に回転させることができます。
この問題をどのように考えるかですが、当然ながら状態数が多すぎるので、グラフを作って最短距離を求めるとかいうやり方では無理です。
なので、「すべてが目的の数字になる」というのを別の言葉で言い換えます。すなわち、
- 両端の数は目的の数になる、つまり数の差が0になる
- ある隣り合った2つの桁に注目した時、各桁の初期と目的の差のギャップが0になる
という条件を考えます。上の条件が満たされれば当然全ての桁が目的の数字になります。
次にどのように回すかです。この問題ではダイヤルは上にも下にも回せるわけですが、上で述べたギャップは一定方向へのズレということにしておきましょう。
すると、ギャップが1になっている2ケタのいずれかを回すと、回した桁の反対側のダイヤルとのギャップは1広がることになります。
これをうまく利用すると片側とはギャップが1、反対側とはギャップが9のダイヤルを回せば、どちらもが同時にギャップ0になります。
今は1つのダイヤルを回すことを考えましたが、問題の条件から連続したダイヤルは何個でも同時に回せるので、適当に1のギャップがある場所と9のギャップがある場所の間にあるダイヤルを全部回転させればギャップを効率よく減らすことができます。
なので、ギャップができるだけ10に近いものとできるだけ0に近いものをペアにして回す、ということを繰り返せば最短の手数で目的の数字にできます。
これにあとは両端の数字の差が0になる、という条件をうまく組み込めば問題が解けます。コードはいたって単純ですが、なぜこれでいいのかは結構わかりづらいかもしれません。
以下が正解のコードです。
#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 CombinationLockDiv1 {
public:
int minimumMoves(vector <string> P, vector <string> Q) {
string s = "";
string t = "";
REP(i,P.size()) s += P[i];
REP(i,Q.size()) t += Q[i];
int len = s.size();
vector<int> dif;
REP(i,len) {
dif.push_back((s[i] - t[i] + 10) % 10);
}
vector<int> v;
v.push_back(dif[0]);
REPP(i,1,len-1) {
v.push_back((dif[i] - dif[i-1] + 10) % 10);
}
v.push_back(10 - dif[len-1]);
sort(ALL(v));
int l = 0;
int r = len;
int ans = 0;
while(l < r) {
int t = min(v[l], 10 - v[r]);
v[l] -= t;
v[r] += t;
ans += t;
if(v[l] == 0) l++;
if(v[r] == 10) r--;
}
return ans;
}
};
まとめ
結構勘が鈍っていて、Easyも解くのに結構時間かかりました。一回わかってしまえば簡単なんですけどね。
今週金曜の夜にもSRMがありますが、夜遅いのででるかどうか考え中です。
それでは、最後までお読みいただきありがとうございました。