ABC141 E - Who Says a Pun?
May 6, 2020
問題
考えたこと(TLE解法)
制約的にN^2はできる。
全探索だとN^3になるので良い方法を考える。
rep(i, n) rep(j, n)で文字列sの全部分列を取得する(これはO(N^2))- 1で取得した文字列をキーにもつhashmapを用意する, valueにはこの文字列が最初に出現した場所の
iの値を持たせる - 過去に出現した文字列が出たとき(mapにすでにキーが登録されている場合)は
mapの値(最初に出現したi(つまりインデックス)) + 部分文字列の長さが今のiの値より小さい場合は重ならずに作れるということなので、この文字列は作れる) - 3の中で作れる文字列の中で一番長い文字列の長さが解となる
これでO(N^2)で行けるかと思ったけど、部分文字列の取得処理が遅かったり, mapで全ての部分文字列を管理するとメモリ制約も超えてしまうため、この解法はTLEとなる
解説を見て
DPを見て解こうとのこと
2つの処理に分けて考えよう
dp[i][j]= i番目からとj番目から始めたときに一致する最大の文字列の長さdp[i][j]が制約(文字列が被ること)に違反していないかチェック
いったん部分文字列が被ることを無視して、dpテーブルを構築します。
s=abcabを考える, このdpテーブルを埋めていく
| i/j | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | ? | ? | ? | ? | ? |
| 2 | ? | ? | ? | ? | ? |
| 3 | ? | ? | ? | ? | ? |
| 4 | ? | ? | ? | ? | ? |
| 5 | ? | ? | ? | ? | ? |
右下から、左に向かって埋めていきます。
| i/j | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | ? | ? | ? | ? | ? |
| 2 | ? | ? | ? | ? | ? |
| 3 | ? | ? | ? | ? | ? |
| 4 | 2 | 0 | 0 | 2 | 0 |
| 5 | 0 | 1 | 0 | 0 | 1 |
このとき、(i,j) = (1,4)のときに注目で, ここで一致すると, 普通であれば次は(i,j) = (2,5)->(3,6)...とチェックが進みますが、実際は右下の値((i,j) = (2,5))に1を足した値がここの値になります。
つまりdp[i][j]の値はdp[i+1][j+1] + 1です。
これでO(N^2)で最大の文字列の長さがわかりました。
がこれテーブル埋めるとわかるのですが、制約に違反する値も含まれます。
| i/j | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 5 | ? | ? | ? | ? |
| 2 | ? | 4 | ? | ? | ? |
| 3 | ? | ? | 3 | ? | ? |
| 4 | 2 | 0 | 0 | 2 | 0 |
| 5 | 0 | 1 | 0 | 0 | 1 |
ので、dpテーブルを埋めた後に、dpテーブルを全列挙して、制約に違反しない(dp[i][j] < j-i+1)中で最大の値が解となります。
提出したコード
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
void chmax(ll& a, ll b) { a = max(a, b); }
void chmin(ll& a, ll b) { a = min(a, b); }
int main() {
int n; cin >> n;
string s; cin >> s;
vector<vector<int>> dp(n, vector<int>(n,0));
for(int i=n-1; i >= 0; i--) for(int j=n-1; j >= 0; j--) {
if(s[i] == s[j]) {
dp[i][j] += 1;
if(i < n-1 && j < n-1) {
dp[i][j] += dp[i+1][j+1];
}
} else {
dp[i][j] = 0;
}
}
int ans = 0;
rep(i, n) rep(j, n) {
if(dp[i][j] < j-i+1) ans = max(ans, dp[i][j]);
}
cout << ans << endl;
return 0;
}