競プロの問題紹介001 ABC164 Multiple of 2019
文字列Sのi~j文字目を10進としてみる場合、その数字が2019で割り切れるi,jの組み合わせを答えよ。
・10進の仕方
文字列の部分文字列を10進数にしないといけませんが、|S|<=200000なので単純にやるとオーバーフローします。
多倍長なら入りますが、O(桁数)かかるため他にかける処理時間が足りなくなり厳しそうです。
☆Sをi文字目から見ていくことを考えます。
ex.1817181712114 i=3
i=3,j=3 1
i=3,j=4 17
i=3,j=5 171
...
jを増やすたびに、*10+S[j]されています。(実際は文字列なのでASCIIコードの変換が必要)
ここで、この問題では2019で割り切れるか=mod 2019が0になるかが重要です。jを増やしたときの演算は+と*のみなので、逐次modを取っても答えは変わりません(/以外は逐次modが取れます)
なので、i,jの値=(i,j-1の値*10+S[j])%2019と更新し、i,jの値が0になればカウントを増やすと考えられそうです。
☆i,jを全パターン調べるとO(|S|^2)でアウトです。
i,jの値はmod 2019する関係上、高々2019通りの値(0~2018)のどれかに収まります。なので、dpで値を管理しながら見ていけばO(|S|)で計算できそうです。
ex.1817181712114
i=1 初めの1を記録 (1)
i=2 初めの8を記録、1*10+8=18を記録 (8,18)
i=3 初めの1を記録、8*10+1=81を記録、18*10+1を記録 (1,81,181)
...
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int dp[2][2019]={{0}};
string S;
cin>>S;
int c=0;
for(int i=0;i<S.size();i++){
int n=S[i]-'0';
for(int j=0;j<2019;j++){
if(j==0||dp[0][j]!=0){
//cout<<j<<","<<j*10+n<<","<<dp[0][j]+(j==0)<<endl;
dp[1][(j*10+n)%2019]+=dp[0][j]+(j==0);
}
}
c+=dp[1][0];
for(int j=0;j<2019;j++){
dp[0][j]=dp[1][j];
dp[1][j]=0;
}
}
cout<<c<<endl;
}
AtcoderProblemによると、水下位diffでした。
中々難しいと思うのですが...。
この記事が気に入ったらサポートをしてみませんか?