こんちかー！どうもゆきのんです.今日サークルで解いてた問題が結構良い問題だと感じたので記事にまとめようと思います.
今日の問題はこれです！
問題文が英語なので頑張って問題概要を説明すると.
数字列\(S\)が与えられるので\(S\)の連続する部分文字列の中で\(11\)の倍数で\(0\)よりも大きく先頭が\(0\)でないものの個数を求めよ.\(S\)は複数与えられ,入力の最後は\(0\)である.
\(1 \leq |S| \leq 80000 \)
以下\(S\)の長さを\(N\)とします.まずは愚直解を考えてみましょう.連続する文字列を作成してそれが\(11\)の倍数であるかを確認するというものが考えられます.連続する部分文字列は先頭と終端を決めれば決まるので\(O(N^{2})\)で解くことができます.しかし,単純に数字を作っていくと作成した数字は最大で\(10^{80000}\)となるのでこれを保持することはできません(少なくとも\(c++\)では).ここで,連続する部分文字列を\(K\)とし\(K\)に文字\(t\)をつなげて\(Kt\)とすることを考えます.\(Kt\)を\(11\)で割った余りというのは,\(((Kを11で割った余り)*10+t)\% 11\)で表すことができます.そのため\(K\)を\(11\)で割った余りのみを考えて文字列を作成していけば良いです.ただし,この問題は\(O(N^{2})\)では\(TLE\)となってしまいます.
ここで,\(A_{l,r}\)を\(S[l]S[l+1]･･･S[r]\)で表される文字列を\(11\)で割った余りとします\(( l \leq r )\).上記の考え方から\(A_{l,r+1}=(A_{l,r}*10+S[r+1])\% 11\)で表されることがわかりました.ここで何かまとめられるものがないか考えます.\(A_{l,r+1}\)というのは\(A_{l,r}\)の値から定まります.よって,\(A_{l,r}\)と\(A_{l’,r}\)の値が同じだとしたら\(r\)以降の値は等しくなります.よって\(r\)以降をまとめることができたので,考えるのは\(r\)番目の文字で終わる連続文字列の余りのみで良いです.余りは\(0〜10\)の高々\(11\)通りであり,状態数は\(11*N\)となるので計算量は,\(O(N)\)です.実装はメモ化再帰する方法と\(dp\)でやる方法があります.注意としては,先頭が\(0\)で始まる様なものは数える必要はありません.
\(dp\)で実装を行う場合\(dp\)テーブルを以下のように定めます.
\(dp[i][j]:=i番目で終わる連続文字列を11で割った余りがjとなるものの個数\)
このように定めると\(dp\)の遷移は以下のようになります.
- \(dp[i+1][(j*10+s[i])\% 11]+=dp[i][j]\)
- \(dp[i+1][S[i]]+=1\) \((S[i]!=0)\)
また,答えは\(dp[i][0]\)の和となります.
以下は実装例となります.
\(DP\)での実装
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
while(cin >> s,s!="0"){
int n=s.size();
int dp[n+1][11];
memset(dp,0,sizeof(dp));
int ans=0;
for (int i = 0; i < n; i++) {
if(s[i]-'0') dp[i+1][s[i]-'0']++;
for (int k = 0; k < 11; k++) {
int nx=(11-k+s[i]-'0')%11;
dp[i+1][nx]+=dp[i][k];
}
ans+=dp[i+1][0];
}
cout << ans << endl;
}
return 0;
}
メモ化再帰での実装
#include<bits/stdc++.h>
using namespace std;
int memo[80001][11];
string s;
int dfs(int k,int x){
if(~memo[k][x]) return memo[k][x];
if(k==s.size()-1) return 0;
int ret=0;
int nx=(11+s[k+1]-'0'-x)%11;
if(!nx) ret++;
ret+=dfs(k+1,(11+s[k+1]-'0'-x)%11);
return memo[k][x]=ret;
}
int main(){
while(cin >> s,s!="0"){
int n=s.size();
memset(memo,-1,sizeof(memo));
int ans=0;
for (int i = 0; i < n; i++) {
if(s[i]-'0') ans+=dfs(i,s[i]-'0');
}
cout << ans << endl;
}
return 0;
}
(別解)余りの性質と累積和を用いた解法があります.
\(10 \equiv -1 (mod 11)\)であるから\(A_{l,r+1} \equiv A_{l,r}*10+S[r+1] \equiv S[r+1]-A_{l,r}\)となります.ここで,これを繰り返し用いることで\(A_{l,r} \equiv S[l]-S[l+1]+･･･S[r]\)となるので,偶数番目をプラス,奇数番目をマイナスとして累積和を取って\(11\)で割って余りを考えます.ここで累積和\(i\)番目の累積和を\(cm[i]\)とすると,\(cm[l]=cm[r]\)となる\(l,r\)を考えると\(A_{l,r}=0\)となります.よって\(cm\)の値が\(p\)になる個数が\(k_{p}\)個であったとすると\(l,r\)の選び方は\(_{k_{p}}C_{2}\)通りある(実質\(Zero-Sum\ Ranges\)).ただし先頭が\(0\)の場合を余分に数えてしまっているのでその分を引く必要があります.この数は,\(S[i]=0\)となる\(i\)でそれ以降\((iも含む)\)に出てくる\(cm[i]\)の個数です.これは逆から個数を数えながら回すことで\(O(N)\)で行うことができます.よって全体の計算量は\(O(N)\)でこの問題は解けました.
以下は実装例です.累積和は先頭を\(0\)とした\(N+1\)個で考えています.そのため,\(cm[i]\)と対応するのは\(S[i-1]\)です.
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
while(cin >> s,s!="0"){
int n=s.size();
vector<int> a(n+1,0);
for (int i = 0; i < n; i++) {
a[i+1]=(a[i]+11+(i&1?-1:1)*(s[i]-'0'))%11;
}
vector<int> ma(11,0),mi(11,0);
int ans=0;
for (int i = 0; i < n+1; i++) {
ans+=ma[a[i]]++;
}
for (int i = n; i > 0; i--) {
mi[a[i]]++;
if(s[i-1]=='0') ans-=mi[a[i]];
}
cout << ans << endl;
}
return 0;
}
最初,意気揚々と\(O(N^{2})\)書いたら普通に\(TLE\)だったよね(悲しい).メモ化再帰で実装したとき引数に\(S\)を持たせたままやったら\(MLE\)がでてキレた.