AtCoder ABC 183

작성일 | In

총평

노잼
D: Do you know Prefix Sum?
E: 단순 DP + Prefix Sum
F: Do you know Small to Large?

A. ReLU

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 x; cin >> x; cout << max(0, x);
}

B. Billiards

초등학교 수학

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/******************************
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, c, d; cin >> a >> b >> c >> d;
    int dx = a - c, dy = b + d;
    cout << fixed << setprecision(10) << (1.0 * a * dy / dx - b) * dx / dy;
}

C. Travel

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
/******************************
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, K, A[9][9], R;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) cin >> A[i][j];
    vector<int> ord(N);
    iota(all(ord), 1);
    do{
        int now = 0, flag = 1;
        for(int i=1; i<N; i++){
            if(!A[ord[i-1]][ord[i]]) flag = 0;
            now += A[ord[i-1]][ord[i]];
        }
        if(!A[ord.back()][ord[0]]) flag = 0;
        now += A[ord.back()][ord[0]];
        if(flag && now == K) R++;
    }while(next_permutation(ord.begin()+1, ord.end()));
    cout << R;
}

D. Water Heater

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
28
/******************************
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, W;
ll S[202020];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> W;
    for(int i=1; i<=N; i++){
        int s, e, x; cin >> s >> e >> x;
        S[s] += x; S[e] -= x;
    }
    for(int i=1; i<202020; i++) S[i] += S[i-1];
    if(*max_element(S, S+202020) > W) cout << "No";
    else cout << "Yes";
}

E. Queen on Grid

$(i, j)$에 도달하는 방법의 수를 $D(i, j)$라고 합시다.
적당한 $i’$, $j’$, $k’$에 대해 $\displaystyle D(i, j) = \sum_{x=i’+1}^{i-1}D(x, j) + \sum_{y=j’+1}^{j-1}D(i, y) + \sum_{z=1}^{k’}D(i-z, j-z)$입니다.

Naive하게 계산하면 $O(N^3)$이 걸리지만, 누적합을 이용해 상태 전이를 최적화하면 $O(N^2)$에 문제를 해결할 수 있습니다.

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
/******************************
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;
const ll MOD = 1e9+7;
inline void Mod(ll &x){ x %= MOD; if(x < 0) x += MOD; }

int N, M;
char A[2020][2020];
ll D[2020][2020];
ll I[2020][2020], J[2020][2020], S[4040][2020];
int IP[2020], JP[2020], SP[4040];


int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) cin >> A[i][j];
    D[1][1] = I[1][1] = J[1][1] = S[2020][1] = 1;
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) {
        if(i == 1 && j == 1) continue;
        int s = i - j + 2020;
        if(A[i][j] == '#'){
            IP[i] = j; JP[j] = i; SP[s] = i;
            continue;
        }
        D[i][j] += I[i][j-1] - I[i][IP[i]];
        D[i][j] += J[i-1][j] - J[JP[j]][j];
        D[i][j] += S[s][i-1] - S[s][SP[s]];
        Mod(D[i][j]);
        I[i][j] = I[i][j-1] + D[i][j]; Mod(I[i][j]);
        J[i][j] = J[i-1][j] + D[i][j]; Mod(J[i][j]);
        S[s][i] = S[s][i-1] + D[i][j]; Mod(S[s][i]);
    }
    cout << D[N][M];
}

F. Confluence

Do you know Small to Large?

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
/******************************
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, Q, P[202020];
map<int, int> M[202020];
int Find(int v){ return v == P[v] ? v : P[v] = Find(P[v]); }
void Merge(int u, int v){
    u = Find(u); v = Find(v);
    if(u == v) return;
    if(M[u].size() > M[v].size()) swap(u, v);
    for(const auto &i : M[u]) M[v][i.x] += i.y;
    P[u] = v;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=1; i<=N; i++){
        int t; cin >> t;
        M[i][t]++;
    }
    iota(P+1, P+N+1, 1);

    for(int i=1; i<=Q; i++){
        int op, a, b; cin >> op >> a >> b;
        if(op == 1) Merge(a, b);
        else cout << M[Find(a)][b] << "\n";
    }
}