AtCoder Beginner Contest 186


##[A - ABC Preparation](https://atcoder.jp/contests/abc185/tasks/abc185_a)

O(1)

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int n, w;
    cin >> n >> w;
    cout << n / w << endl;

    return 0;
}
```

##[B - Blocks on Grid](https://atcoder.jp/contests/abc186/tasks/abc186_b)

計算量はO(h*w)。
O(N)であり最小値を計測し差分を加算する。

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int field[100][100];

int main(int argc, const char * argv[]) {
    int h, w;
    cin >> h >> w;

    int min_v = 100;
    rep(y, h){
        rep(x, w){
            cin >> field[y][x];
            min_v = min(min_v, field[y][x]);
        }
    }

    int res = 0;
    rep(y, h){
        rep(x, w){
            res += field[y][x] - min_v;
        }
    }
    cout << res << endl;

    return 0;
}
```


##[C - Unlucky 7](https://atcoder.jp/contests/abc186/tasks/abc186_c)

計算量はO(N)。
最大のループ数は2*10^5。
一般的にC++は簡単な四則演算なら１０億ループを2sec以内に処理できます。
２０万ループなら文字列の変換処理などを行っても余裕で間に合うと思いました。
~~この問題はむしろC++以外の処理の遅い言語を咎めにきた問題に見えました。~~
(@c-yan さんからアドバイスで打ち消し線)

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    ll res=0;
    for(int i=1; i<=n; i++){
        string s = to_string(i);
        int programmerPos = s.find('7');
        if (programmerPos != string::npos){
            res++;
            continue;
        }

        std::stringstream ss;
        ss << std::oct << i;
        s = ss.str(); 
        programmerPos = s.find('7');
        if (programmerPos != string::npos){
            res++;
        }
    }
    cout << n - res << endl;

    return 0;
}
```

##[D - Sum of difference](https://atcoder.jp/contests/abc186/tasks/abc186_d)

###計算量
シグマ計算をそのまま処理するとO（N^2）、（2*10^5）^2になりTLEになります。
|Ai - Aj|の制約がある為にシグマ計算の分配法則などもできません。

###思考の入り口
まず最初に考えたことは絶対値の制約を外す事です。
値をソートを行うことでAj - Aiになり、絶対値の制約をなくす事ができます。

5, 4, 3, 2, 1の配列の際、
(N)Σ(j=i+1)　(Aj - Ai)の計算は、一番の最初のループ時、5*4 - (4+3+2+1)の計算です。
(4+3+2+1)の部分は累積和です。
各要素の加算処理を事前に計算しておく事で、シグマ計算のループを一つ少なくできます。
O(N)？にできました。

###コード実装時の思考
Aiの要素の最大桁数は２*１０^8です。
（2*10^5）^2ほど加算した合計は１０^１８桁に収まりますね。
つまりlong long型です。
このような問題では途中計算でint型の要素と処理した場合、オーバーフローを起こす事があるのでケアレスミスを防ぐ為に全てlong long型を使用します。

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

void solve(int n, vector<ll> &A){
    vector<ll> dp(n+1, 0);

    rep(i, n){
        dp[i+1] = dp[i] + A[i];
    }
    reverse(A.begin(), A.end());
    reverse(dp.begin(), dp.end());

    ll res =0;
    rep(i, n){
        ll v = n - (i+1);
        ll sum = A[i] * v;
        res += sum - dp[i+1];
    }
    cout << res << endl;
}

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;

    //n = 200000;
    vector<ll> A(n);
    //rep(i, n) A[i] = i+1;
    rep(i, n) cin >> A[i];
    sort(A.begin(), A.end());
    solve(n, A);

    return 0;
}
```

###検算
chokudaiさんの昔のツイートを参考にしました。
有益なツイートを毎日ありがとうございます。

solve(）を使用し、実装部分と入力部分を切り離します。
最大値「n = 200000」を指定し、「A[i] = i+1」、「A[i] = n-i」を使い分けることでリミットチェックを行います。
これから難しい問題はsolve()の構成を使用し検算を行っていきます。

##感想
abc初の４完走です。
この１ヶ月間、やさしい数学１、やさしい数学A、高校の数学I・Aが1冊でしっかりわかる本、白チャート数学１Aを読んできました。
シグマ計算は数２Bの分野っぽいですね。
ただ分からないなりに勉強した数学を役立てようと考え結果が出せて良かったです。