AtCoder Beginner Contest 318

## 余談
PCの電源が立ち上がらず21:08から参戦。
unrated。

## [A - Full Moon](https://atcoder.jp/contests/abc318/tasks/abc318_a)

O(1)
N-M>=0であるか
(N-M)/P
で解答を求める事ができます。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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; }

int main() {
    int N, M, P;
    cin >> N >> M >> P;

    int ans = 0;

    if(N-M>=0) ans++;

    N = max(0, N - M);

    cout << max(0, ans + (N / P)) << endl;

    return 0;
} 
```

## [B - Overlapping sheets](https://atcoder.jp/contests/abc318/tasks/abc318_b)

O(NNN)
100×100×100=1000000
なので間に合いますね。
全探索をしましょう。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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; }

bool graph[100][100];

int main() {
    int N;
    cin >> N;

    rep(i, N){
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        for(int y=c; y<d; y++){
            for(int x=a; x<b; x++){
                graph[y][x] = true;
            }
        }
    }

    int ans=0;
    for(int y=0; y<=100; y++){
        for(int x=0; x<100; x++){
            if(graph[y][x]) ans++;
        }
    }
    cout << ans << endl;

    return 0;
} 
```

## [C - Blue Spring](https://atcoder.jp/contests/abc318/tasks/abc318_c)

O(N)
ソートと貪欲法
配列Fを大きい順に並べます。

D=2, P=10としたとき、

```
1145141919 ⇨ 9954411111
を並び替える。
上からD個の要素を取り出して判定する。

1, 54411111
9+9=18なのでPの値を換算する
2, 411111
5+4=9なので9の値を換算する
3, 1111
4+1=5なので5の値を換算する
```
と判定するとできますね。


```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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; }

int main() {
    ll N, D, P;
    cin >> N >> D >> P;
    vector<ll> F(N);
    rep(i, N) cin >> F[i];

    sort(F.begin(), F.end());
    reverse(F.begin(), F.end());

    ll cnt = 0;
    ll ans = 0;
    while(cnt<N){
        ll sum = 0;
        rep(i, D){
            if(cnt+i<N) sum += F[cnt+i];
        }
        if(sum>P)  ans += P;
        else ans += sum;
        cnt += D;
    }
    cout << ans << endl;

    return 0;
} 
```

## [D - General Weighted Max Matching](https://atcoder.jp/contests/abc318/tasks/abc318_d)

2≤N≤16の制約を見てbitDPだと分かりますね。
この時点で離脱しようかなと考えました。
順位表を確認すると、２５分の経過で2500人が正解していました。

bitDPで２５００ACってまずないです。
順位表から別解答が存在する事がわかりました。

```
1 2 3 4
の地点があり、
1,2を組み合わせた後に3,4を組み合わせます。
1,3を組み合わせた後に2,4を組み合わせます。
1,4を組み合わせた後に2,3を組み合わせます。
```

N個の任意の地点に、この動かし方ができる方法はメモ化再帰ですね。
別解答が判明しました。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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; }

ll N;
ll D[17][17];
ll ans=0;
bool used[17];

void dfs(ll p, ll sum){

    if(p>=N){
        ans = max(ans, sum);
        return;
    }

    dfs(p+1, sum);

    if(used[p]) return;

    used[p] = true;

    for(int i=p+1; i<=N; i++){
        if(used[i]) continue;
        used[i] = true;
        dfs(p+1, sum + D[p][i]);
        used[i] = false;
    }

    used[p] = false;
}

int main() {
    cin >> N;

    repx(i, 1, N+1){
        repx(j, i+1, N+1){
            cin >> D[i][j];
        }
    }
    dfs(1, 0);
    cout << ans << endl;

    return 0;
} 
```

## [E - Sandwiches](https://atcoder.jp/contests/abc318/tasks/abc318_e)

制約を見てDPっぽいです。
順位表を確認すると、60分の経過で2600人が正解していました。
複雑なDPで2600ACはないですね。
順位表から別解答が存在する事がわかりました。

```
13
9 7 11 7 3 8 1 13 11 11 11 6 13
```

のACする解答は20です。

```
7,11,7

11,7,11
11,3,11
11,8,11
11,1,11
11,13,11

11,7,11
11,3,11
11,8,11
11,1,11
11,13,11

11,7,11
11,3,11
11,8,11
11,1,11
11,13,11

13,11,13
13,11,13
13,11,13
13,6,13
```

規則性がありますね。
11という同じ数字がある場合は、
```
11の間の数字の数x(11の数-1)
```

の掛け算になっています。
もう少し詳しく見てみましょう。

```
13
9 7 11 7 3 8 1 13 11 6 11 11 13
```

とした時、

```
7,11,7

11,7,11
11,3,11
11,8,11
11,1,11
11,13,11

11,7,11
11,3,11
11,8,11
11,1,11
11,13,11
11,６,11

11,7,11
11,3,11
11,8,11
11,1,11
11,13,11
11,6,11

11,6,11

11,6,11

13,11,13
13,6,13
13,11,13
13,11,13
```

の24の解答になります。
規則性がありますね。

```
11,7,11
11,3,11
11,8,11
11,1,11
11,13,11
```

```
11,6,11
```

を計算式で求める事ができれば良さそうです。

最初の１１の要素のインデックスをi
次の１１の要素のインデックスをj
jが示す11はk個目の11である
配列のサイズをsize
として、

```
(j-i-1) * (size-k) * k
```

となりました。
コーディングをします。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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; }

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    map<ll, vector<ll>> mp;
    rep(i, N){
        mp[A[i]].push_back(i);
    }

    ll sum = 0;
    for(auto m:mp){
        ll size = m.second.size();
        for(ll i = 1; i<size; i++){
            sum += (m.second[i] - m.second[i-1] - 1) * (size-i) * i;
        }
    }
    cout << sum << endl;

    return 0;
} 
```

## 余談
コンテスト中の順位表によって、
使用されるアルゴリズムが予測できるという話でした。