ABC164-D Multiple of 2019

D - Multiple of 2019

解法

入力が $121147$ の時を考えると

$121147,21147,1147,147,47,7,0$

という配列Aを作る

これらを全部mod2019した

$7,957,1147,147,47,7,0$

という配列Bを作る

答えは $B [ i ] = B [j+1 ]$ となる $(i,j)$ のペアの個数 $(i \leq j)$ 　（上の例だと $(i,j)=(0,4)$ のみ満たすので答えは $1$ ）

証明

$B[i ]=B[j+1 ]$
⇔ $A[i ] \% 2019 = A[j+1 ] \% 2019$
⇔ $(A[i ]-A[j+1 ]) \% 2019 =0$

が成り立ち

$A[i ]-A[j+1 ]$ は"Sのi文字目からj文字目までを10進法の整数としてみた値"に $10^{A.size()-j-2}$ 倍したものになってるので、
$10^{n}$ 倍で $2019$ の倍数が入ったり出たりしない*1ことから

$(A[i ]-A[j+1 ]) \% 2019=0$
⇔"Sのi文字目からj文字目までを10進法の整数としてみた値" $\times 10^{A.size()-j-1} \% 2019=0$
⇔"Sのi文字目からj文字目までを10進法の整数としてみた値" $\%2019=0$

が成り立つので

コード

上記の配列Aはオーバーフローするので当然作れなくて、最初からBを作る
Bは上の例では一番最後に0が来ているけど実際には0から作るのが自然なので0から始まるようにする
答えはBの向きによらないので問題はないよ

vector<int> B;
int keta=1;//10^n倍するやつ
B.push_back(0);
for(int i=s.size()-1;i>=0;i--){
  int a=s[i]-'0';
  B.push_back((B.back()+a*keta)%2019);
  keta*=10;keta%=2019;
}

$B[i]=B[j+1]$ となる $(i,j)$ の個数はBの取りうる値が $[0,2019)$ と小さいので配列などを作って適当にやりましょう

int ans=0;
vector<int> T(2019,0);
for(int p:B)T[p]++;
for(int i=0;i<2019;i++)ans+=T[i]*(T[i]-1)/2;

もしくは

int ans=0;
vector<int> T(2019,0);
for(int p:B){
  ans+=T[p];
  T[p]++;
}

でもいい

最終的なコードは

#include <bits/stdc++.h>
using namespace std;

int main(){
  string s;cin>>s;
  vector<int> B;
  int keta=1;//10^n倍するやつ
  B.push_back(0);
  for(int i=s.size()-1;i>=0;i--){
    int a=s[i]-'0';
    B.push_back((B.back()+a*keta)%2019);
    keta*=10;keta%=2019;
  }
  int ans=0;
  vector<int> T(2019,0);
  for(int p:B)T[p]++;
  for(int i=0;i<2019;i++)ans+=T[i]*(T[i]-1)/2;
  cout<<ans<<endl;
}

Submission #12519531 - AtCoder Beginner Contest 164

なんだけど実際にはBすら作る必要はなくて、いらない部分削っていくと

#include <bits/stdc++.h>
using namespace std;

int T[2019],ans;

int main(){
  string s;cin>>s;
  T[0]++;
  for(int i=s.size()-1,keta=1,pre=0;~i;i--){
    ans+=T[(pre+=(s[i]-'0')*keta)%=2019]++;
    (keta*=10)%=2019;
  }
  cout<<ans<<endl;
}

Submission #12560772 - AtCoder Beginner Contest 164

これくらい簡潔になったりする

考え方

解説記事には考察フローも書けみたいなのを見たので一応書こうと思ったんだけど、これくらいは典型なので似たような問題を解いたことが何度もあると多分こんな感じ〜で解けちゃうと言うのが正直なところ
で、そうじゃない人間がどうすればいいかなんだけど

何か使いまわせる値がないか考える
取り敢えず愚直解（今回だとS.size()の二乗解）を書いてみる
（愚直解での）数式を書いて見ていじくる

あたりかなぁと思う
競プロの問題の多くは「何らかの順序でソートすることで順番に計算できるようにする」か「値を使い回す」のどっちか（二分探索とかUnionFindとか例外はいくらでもあるけど）なので、競プロの問題で詰まったら取り敢えずこの二つを試すのが良さそう
特にこの問題だと（文字列の順番は明らかに大事なので）ソートはあんまり出来なさそうかなみたいなのは分かりやすいと思うし
ただ慣れがやっぱり大切なので雑に1000問くらい解くのが一番効果ありそう（コスパがいいかはともかく）
自分で完全に0から解けたら数学者レベルだよみたいな問題も多いからね
数式を書いていじくるって部分に関しては理想はこの動画の感じじゃないかな

*1:2019の倍数に10ⁿをかけても2019の倍数であり、非2019の倍数に10ⁿをかけても非2019の倍数である