コンテスト中の考察
- We Love ABCっぽい。
- AGCになる文字列はそんなにたくさんなさそうだから$4^N$からAGC文字列を取り除けばいいかな？いや、なんか無理。
- 普通にAGCT文字列を考えよう。なんかDPでできそう。
dp[i][A][G][C]とかかな？（適当）。でもこれ意味わからんな - なんか3文字くらい前まで見れれば良さげ。でもどうやってDP書くかわからん...
- 終了
詰まった原因
- どうやってDPするのかわからなかった。
- これどうすればいいんだ？（普通に精進不足っぽいけど）
解法
- DPを考える。インデックスと、何文字か前までの情報を持ったDP。
- 何文字前までの情報を持てばいいのか考える。これは、ひとつ文字を決めた時にスワップすると何文字前まで影響があるかを考えればわかる。
xが今決める文字とすると、***xがxの影響する範囲なのがわかる。なので、xの3文字前までの情報を持てばいいことになる。 - 3文字前までの情報が欲しいことがわかった。詳しくいうと、3文字前がどの文字か、2文字前がどの文字か、1文字前がどの文字かという情報が必要になる。これをDPで表すと
dp[index][c3][c2][c1]: index文字目まで見て、indexの3文字前がc3、2文字前がc2、1文字前がc1のときのAGC文字列を除く組み合わせの数となる。 - 状態の持ち方がわかったのであとは遷移を考える。これは再帰で書くと直感的にかける。過去の状態が引数で渡され、そこから1文字決める(A, G, C, Tのどれか）状況を考える。それをコードに落とし込むと再帰がかける
- あとはメモ化したり細かい部分を書いて終了
コード（自分なりに書いたやつ）
- 文字を数値にすると頭壊れそうだと思ったのでmapで対応させた。場合によってはTLEしそう
- この問題の場合は再帰の方が書きやすかった。初期化がめんどいので。再帰は最後まで行ったら1返しとけばOKなので楽。
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
int val = ((a % mod) + (b % mod)) % mod;
if (val < 0) { val += mod; }
a = val;
}
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
const int mod = 1e9+7;
int N;
auto dp = vectors(111, 9, 9, 9, -1); // dp[i][x][y][z]: i文字目までみたとき、iの3文字前がx、2文字前がy、1文字前がzのとき、AGC文字列以外の組み合わせの数
vector<int> AGCT = {'A', 'G', 'C', 'T'}; // 使用する文字リスト
// 文字とDPに使うインデックスの対応付け
map<char, int> mp = {
{'A', 1},
{'G', 2},
{'C', 3},
{'T', 4},
{'*', 5}, // 「*」はA, G, C, Tのどれも使っていない状態
};
// 渡されたリストがAGCになるかの判定
bool isAGC(vector<int> C) {
return C[0] == 'A' and C[1] == 'G' and C[2] == 'C';
}
int rec(int idx, int c3, int c2, int c1) {
if (idx >= N) {
return !isAGC({c3, c2, c1});
}
if (dp[idx][mp[c3]][mp[c2]][mp[c1]] != -1) {
return dp[idx][mp[c3]][mp[c2]][mp[c1]];
}
int ret = 0;
for (char now : AGCT) {
vector<int> t = {c3, c2, c1, now};
bool ok = true;
// tがAGC文字列になるかを判定する
if (isAGC({c3, c2, c1}) or isAGC({c2, c1, now})) {
ok = false;
}
// tをスワップしてAGC文字列になるかを判定する
for (int i = 0; i < AGCT.size()-1; i++) {
vector<int> tt = t;
swap(tt[i], tt[i+1]);
if (isAGC({tt[0], tt[1], tt[2]}) or isAGC({tt[1], tt[2], tt[3]})) {
ok = false;
}
}
// tがAGC文字列にならないなら遷移させる
if (ok) {
Add(ret, rec(idx + 1, c2, c1, now));
}
}
return dp[idx][mp[c3]][mp[c2]][mp[c1]] = ret;;
}
signed main() {
cin >> N;
int ans = rec(0, '*', '*', '*');
cout << ans << endl;
return 0;
}
コード（自分やつちょっと直した）
- なんか生の数値で対応させてる人が多かったみたいなのでそれで書いてみた。
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
int val = ((a % mod) + (b % mod)) % mod;
if (val < 0) { val += mod; }
a = val;
}
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
const int mod = 1e9+7;
int N;
auto dp = vectors(111, 9, 9, 9, -1); // dp[i][x][y][z]: i文字目までみたとき、iの3文字前がx、2文字前がy、1文字前がzのとき、AGC文字列以外の組み合わせの数
// 渡されたリストがAGCになるかの判定
bool isAGC(vector<int> C) {
return C[0] == 0 and C[1] == 1 and C[2] == 2;
}
int rec(int idx, int c3, int c2, int c1) {
if (idx >= N) {
return !isAGC({c3, c2, c1});
}
if (dp[idx][c3][c2][c1] != -1) {
return dp[idx][c3][c2][c1];
}
int ret = 0;
for (int now = 0; now < 4; now++) {
vector<int> t = {c3, c2, c1, now};
bool ok = true;
// tがAGC文字列になるかを判定する
if (isAGC({c3, c2, c1}) or isAGC({c2, c1, now})) {
ok = false;
}
// tをスワップしてAGC文字列になるかを判定する
for (int i = 0; i < 3; i++) {
vector<int> tt = t;
swap(tt[i], tt[i+1]);
if (isAGC({tt[0], tt[1], tt[2]}) or isAGC({tt[1], tt[2], tt[3]})) {
ok = false;
}
}
// tがAGC文字列にならないなら遷移させる
if (ok) {
Add(ret, rec(idx + 1, c2, c1, now));
}
}
return dp[idx][c3][c2][c1] = ret;;
}
signed main() {
cin >> N;
int ans = 0;
ans = rec(0, 5, 5, 5); // 0:A, 1:G, 2:C, 3:T, 5: 文字がない状態
cout << ans << endl;
return 0;
}
コード（ループDP)
-
dp[0][3][3][3] = 1で初期化してもうまくいくみたい。でも頭のいい方法なので僕は無理。 - 僕は3文字目までを手動で初期化して、3文字目からDPの遷移を進めるようにした。サンプルによってAGC, ACG, GACを除く長さ3の文字列は全て大丈夫と保証されているので安心。
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
int val = ((a % mod) + (b % mod)) % mod;
if (val < 0) { val += mod; }
a = val;
}
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
const int mod = 1e9+7;
int N;
auto dp = vectors(111, 9, 9, 9, 0);
bool isAGC(vector<int> C) {
return C[0] == 0 and C[1] == 1 and C[2] == 2;
}
signed main() {
cin >> N;
int M = 4;
// 3文字目までを初期化
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
if (i == 0 and j == 1 and k == 2) continue;
if (i == 0 and j == 2 and k == 1) continue;
if (i == 1 and j == 0 and k == 2) continue;
dp[3][i][j][k] = 1;
}
}
}
for (int i = 3; i < N; i++) {
for (int c3 = 0; c3 < M; c3++) { // iの3文字前
for (int c2 = 0; c2 < M; c2++) { // iの2文字前
for (int c1 = 0; c1 < M; c1++) { // iの1文字前
for (int now = 0; now < M; now++) { // 新しく選ぶ文字
// AGC文字列になるかどうかの判定
bool ok = true;
vector<int> t = {c3, c2, c1, now};
if (isAGC({c3, c2, c1}) or isAGC({c2, c1, now})) ok = false;
for (int j = 0; j < t.size()-1; j++) {
vector<int> tt = t;
swap(tt[j], tt[j+1]);
if (isAGC({tt[0], tt[1], tt[2]}) or isAGC({tt[1], tt[2], tt[3]})) ok = false;
}
// AGC文字列にならないなら遷移させる
if (ok) {
Add(dp[i+1][c2][c1][now], dp[i][c3][c2][c1]);
}
}
}
}
}
}
int ans = 0;
for (int c3 = 0; c3 < M; c3++) {
for (int c2 = 0; c2 < M; c2++) {
for (int c1 = 0; c1 < M; c1++) {
Add(ans, 1LL*dp[N][c3][c2][c1]);
}
}
}
cout << ans << endl;
return 0;
}
要点
- 過去の状態がインデックス前M文字の情報、未来の状態がAGCTのどれかの文字とするとDPが浮かんでくる感じ？
感想
- どうやってDPすればいいかわからなかった。お前はいつもそうだ。誰もお前を愛さない。
- ループDP、
dp[3]...みたいな中途半端な状態から始めるのが初めてだった。やりやすいようにやればいいのか。
メモ
- 蟻本P327が類題らしい
- パスタ (Pasta)も類題らしい。おーじが言ってた