DynamicCube.exe

12 object(s)
 

AtCoder Beginner Contest #159

총 6문제에서 A,B,C,D를 풀었다.

A번

쉽게 설명하자면 그냥 (n-1)C2+(m-1)C2를 구하라는 문제였다.

nC2 = n(n+1)/2이므로 이를 이용해 O(1)만에 문제를 풀 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
#define MEM 100001
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
const ll INF = 1e9+9;
ll a,b;
int main() {
    cin >> a >> b;
    a--;
    b--;
    cout << a*(a+1)/2 + b*(b+1)/2;
}
cs

B번

팰린드롬 확인 구현 변형 문제.

그냥 구현만 하면 된다.

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
#include <bits/stdc++.h>
#define MEM 100001
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
const ll INF = 1e9+9;
ll l;
string s;
int main() {
    cin >> s;
    l = s.size();
    ll st=0;
    while(st<=l/2){
        if(s[st]!=s[l-st-1]){
            cout << "No";
            return 0;
        }
        st++;
    }
    st=0;
    ll pe=(l-1)/2;
    while(st<=pe/2){
        if(s[st]!=s[pe-st-1]){
            cout << "No";
            return 0;
        }
        st++;
    }
    st=(l+3)/2;
    while(st<=l/2+pe/2){
        if(s[st]!=s[l-st-1]){
            cout << "No";
            return 0;
        }
        st++;
    }
    cout << "Yes";
}
cs

C번

직육면체의 세 변의 길이의 합이 주어질 때, 직육면체의 최대 부피를 구하라는 문제이다.

최대 부피를 가지는 직육면체는 정육면체임을 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
#define MEM 100001
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
const ll INF = 1e9+9;
long double l;
int main() {
    cin >> l;
    l /= 3.0;
    cout.precision(11);
    cout << fixed << l*l*l;
}
cs

D번

k번째 공을 제외한 번호가 같은 공 2개를 선택하는 경우의 수를 구하라는 문제이다.

저 문제는 O(n^2)으로 풀려고 보면 n이 2*10^5이기 때문에 더 좋은 알고리즘을 써야 한다.

해는 이렇게 정의할 수 있다.

(모든 경우의 수) - (k번째 공의 종류를 골랐을때의 경우의 수) + (k번째 공을 제외한 k번째 공의 종류를 골랐을때의 경우의 수)
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
#include <bits/stdc++.h>
#define MEM 300001
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
const ll INF = 1e9+9;
ll n;
ll ba[MEM];
ll c[MEM];
ll ans[MEM];
ll res[MEM];
int main() {
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> ba[i];
    for(int i=0; i<n; i++)
        c[ba[i]]++;
    ans[2] = 1;
    for(int i=2; i<n; i++)
        ans[i+1] += ans[i]+i;
    for(int j=1; j<=n; j++){
        ll o=c[j];
        res[j+1] += res[j]+ans[o];
    }
    for(int i=1; i<=n; i++){
        ll o=c[ba[i-1]];
        cout << res[n+1]-ans[o]+ans[o-1] << '\n';
    }
}
cs


Created by h01000110 (hi) | Code licensed under MIT License