社会人エンジニアがatcoderで茶色を目指す#3

前回の続きから考察します。

##D - Multiple of 2019
問題文はatcoderを参照してください。

- とりあえず全探索

```C++
    int count=0, num=0;
    std::string s;
    std::cin >> s;

    for(int i=0;i<s.length()-4;i++){
       for(int j=i+4;j<s.length();j++){
           num=atoi(s.substr(i,j-i+1).c_str());
           if(num%2019==0){
               count++;
           }
       }
    }

    // insert code here...
    std::cout << count;
    return 0;
```

TLEになるのは分かってました。
ここから何をしていいか分からずタイムアップ。

解説によると、累積和と組み合わせを使用するらしい。

A1, A2, A3 ... An とした際に、
0, A1, A1+A2, A1+A2+A3, A1+...Anとするものらしい。

今回は、0, A1×10^0,A2×10^1, A3×10^2, ...
として連続した区間にする。 

0を含めた2019を入力にすると正しい答えは出ない。
テストデータは2019の6乗である12114を使用する。

12114を基準として、A1=4, A2=1×10^1の際、
(A1+A2) - A1はA2になる.

121141を基準として、A1=1, A6=121141の際、
A1％2019とA6％2019は等しい。

121142119を基準として、A4の余りは100, A9の余りは100の際、
A4％2019とA9％2019は等しい。

余りが等しい数を測定し、組み合わせを計算すると答えが出る。
余りの数なので2019の配列を用意する。
N個から２個を選ぶ組み合わせなので、

nC2=N×(N-1)/2

そして余り0の組み合わせを考え、最初に余り0を扱う配列にインクリメントを行う。

```C++
    string a;
    cin >> a;

    long long n = a.length();
    reverse(a.begin(), a.end());
    
    vector<int> var(2019,0);
    int c=0, fac=1;
    var[0]++;
    for(int i=0; i<n; i++){
        long long add = a[i] - '0';
        c = (c + fac * add) % 2019;
        fac = (fac * 10) % 2019;
        var[c]++;
    }
    
    int ans = 0;
    for(int i=0; i<2019; i++){
        if(var[i] > 1){
            ans += var[i] * (var[i]-1) / 2;
        }
        
    }
    
    std::cout << ans << endl;
    
    return 0;
```

同じような問題が出ても絶対に解けないでしょう。
実務などは、2019の部分を変数として扱うはずです。
そして0を含む文字列になるはずなのでもっと難しいはず。
難易度が高い別問題があるらしいのでそちらを勉強したいと思います。

##D - Banned K
問題文はatcoderを参照してください。
問題文を読んだ際、組みわせを使用すると考えました。
しかし、その後は本当に分からない。
そのままタイムアップ。

以下は解説を読みました。

```C++
    int n;
    std::cin >> n;
    
    int d[200000]={0};
    vector<int> a(n,0);
    
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    
    for(int i=0; i<n; i++){
        d[a[i]]++;
    }
    
    int sum = 0;
    for(int i=0; i<n; i++){
        sum += d[i] * (d[i]-1) / 2;
    }
    
    for(int i=0; i<n; i++){
        int ans = sum;
        ans -= d[a[i]] * (d[a[i]]-1) / 2;
        ans += (d[a[i]]-1) * (d[a[i]]-2) / 2;
        std::cout << ans << endl;
    }

    return 0;
```

まず全体の組み合わせを計算。
その後、必要な組み合わせパターンを引く。
解説を読んでようやく理解しました。

##D - Line++
問題文はatcoderを参照してください。
まず考えたこと

- 私にはこの問題は解けない

解説を読みました。

```C++
    int d[10000];
    int n, x, y;
    cin >> n >> x >> y;
    
    for(int i=1;i<n;i++){
        for(int j=i+1;j<n+1;j++){
            int dd=min(j-i,abs(i-x)+1+abs(j-y));
            d[dd]++;
        }
    }

    for(int i=1;i<n;i++) cout<<d[i]<<endl;

    return 0;
```

よく考えると、点iから点jまで（１〜５）の距離を全探索で計測することはできました。
思考停止してたので完全な負け試合です。
点１〜点５の距離と、点１からX、Yから点５までの距離、XからYまでの距離を比較し最小値を計測する。
簡単な問題です、数ⅠAが頭から抜け落ちてます。

##D - RGB Triplets
問題文はatcoderを参照してください。

- とりあえず全探索！

TLEでタイムアップ！

解説を読みました。

```C++
    int m;
    std::string s;
    int total=0;
    std::cin >> m;
    std::cin >> s;
    
    int r=0,g=0,b=0;
    
    for(int i=0; i<m; i++){
        string s1 = s.substr(i, 1);
        if(s1=="R") r++;
        if(s1=="G") g++;
        if(s1=="B") b++;
    }
    
    int max = r * g * b;

    for(int i=0; i<m; i++){
       for(int j=i+1; j<m; j++){
           
           int k=2*j-i;
           if(k>=m) continue;
           
           string s1 = s.substr(i, 1);
           string s2 = s.substr(j, 1);
           string s3 = s.substr(k, 1);
           
           if(s1!=s2 && s1!=s3 && s2!=s3){
               total++;
           }
       }
    }

    std::cout << max - total << endl;

    return 0;
```

RとGとBの数を計測し、RとGとBを１つずつ選んだ際の組み合わせMAXを計算。
j-i!=k-jは、k=2*j-iなので３重ループが２重ループになります。
さらに、Si!=Sj, Sj=Sk, Sk!=Siを満たす数を計測しMAXから引きます。
Banned Kと考え方は同じです。
復習はとても大事！！

##その他
D - Lunlun Number
D - Sum of Large Numbers
は理解できませんでした。
泣いた。

##D対策
数ⅠAの範囲とそれに合わせたアルゴリズムから出題されている気がします。
長い時間がかかるけど数ⅠAも含めた勉強をしていきます。
あと、先人が残してくれた記事を参考にしたいと思います。
検索すると多くの人が勉強の仕方を記事にしていてくれてました。