AtCoder ABC 186

작성일 | In

총평

D: Do you know Prefix Sum?
E: Do you know Modular Inverse?
F: 좋은 세그먼트 트리 응용 문제

A. Brick

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int a, b; cin >> a >> b; cout << a/b;
}

B. Blocks on Grid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int N, M, X, S;
int A[111][111];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M; X = 1e9;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            cin >> A[i][j];
            X = min(X, A[i][j]);
        }
    }
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) S += A[i][j] - X;
    cout << S;
}

C. Unlucky 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

bool f10(int x){
    while(x){
        if(x % 10 == 7) return false;
        x /= 10;
    }
    return true;
}
bool f8(int x){
    while(x){
        if(x % 8 == 7) return false;
        x /= 8;
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, R = 0; cin >> N;
    for(int i=1; i<=N; i++) R += f10(i) * f8(i);
    cout << R;
}

D. Sum of difference

Do you know Prefix Sum?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

ll N, S[202020];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> S[i];
    sort(S+1, S+N+1);
    for(int i=1; i<=N; i++) S[i] += S[i-1];

    ll ans = 0;
    for(int i=1; i<=N; i++) ans += (S[i]-S[i-1])*(i-1) - S[i-1];
    cout << ans;
}

E. Throne

Do you know Modular Inverse?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) { //ax + by = gcd(a, b)
  ll g = a; x = 1, y = 0;
  if (b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
  return g;
}
ll inv(ll a, ll m){ //return x when ax mod m = 1, fail -> -1
    ll x, y;
    ll g = ext_gcd(a, m, x, y);
    if(g > 1) return -1;
    return mod(x, m);
}

void Solve(){
    ll N, S, K; cin >> N >> S >> K;
    ll g = __gcd(K, N);
    if((N-S) % g != 0){
        cout << -1 << "\n"; return;
    }
    K /= g; N /= g;
    ll x = inv(K, N);
    x = x * (N - S/g) % N;
    cout << x << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T; while(T--) Solve();
}

F. Rook on Grid

(가로 -> 세로)이동으로 갈 수 있는 칸의 개수와 (세로 -> 가로)이동으로 갈 수 있는 칸의 개수를 구한 뒤, 교집합을 빼는 방식으로 문제를 풀어봅시다.
각 이동으로 갈 수 있는 칸의 개수는 쉽게 구할 수 있습니다. 교집합의 크기는 머지 소트 트리를 이용해 쉽게 구할 수 있습니다. 자세한 구현은 아래 코드를 참고해주세요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int S = 1 << 18;

int N, M, K;
vector<int> GI[202020], GJ[202020];
vector<pii> Vec;
ll Val[202020], R;
vector<int> T[1 << 19];

void Build(){
    for(int i=S-1; i; i--) merge(all(T[i<<1]), all(T[i<<1|1]), back_inserter(T[i]));
}
int Query(int l, int r, int x){
    l |= S; r |= S; int ret = 0;
    while(l <= r){
        if(l & 1) ret += T[l].end() - lower_bound(all(T[l]), x), l++;
        if(~r & 1) ret += T[r].end() - lower_bound(all(T[r]), x), r--;
        l >>= 1; r >>= 1;
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> K;
    for(int i=1; i<=K; i++){
        int a, b; cin >> a >> b;
        GI[a].push_back(b);
        GJ[b].push_back(a);
    }
    for(int i=1; i<=N; i++) sort(all(GI[i]));
    for(int j=1; j<=M; j++) sort(all(GJ[j]));
    for(int i=1; i<=N; i++){
        Val[i] = GI[i].empty() ? M : GI[i][0] - 1;
        if(!Val[i]) break;
        R += Val[i];
        T[i|S].push_back(Val[i]);
    }
    Build();
    for(int j=1; j<=M; j++){
        int val = GJ[j].empty() ? N : GJ[j][0] - 1;
        if(!val) break;
        R += val - Query(1, val, j);
    }
    cout << R;
}