Codeforces Round #627(Div.3) 연습

코드포스 레드를 달성하기 위해 이번 달 민트 이상을 달성하는 것을 목표로 세우고 연습하였다.

총 6문제였고, 그 중 A,B,C,D번을 풀었다. 신기록이라 많이 기뻤다.

A번

대충 2*1 블록을 넣어서 직사각형 형태로 만들수 있는지의 여부를 묻는 문제이다.

그냥 쉽게 생각하면 블록 수가 모두 짝수이거나 홀수이면 직사각형이 될수 있음을 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define MEM 50
#define sanic ios_base::sync_with_stdio(0);
using namespace std;
int t,n;
int main()
{
    sanic;
    cin >> t;
    while(t--){
        int c=0;
        cin >> n;
        for(int i=0; i<n; i++){
            int q1;
            cin >> q1;
            c += q1%2;
        }
        if(!c || c==n) cout << "YES\n";
        else cout << "NO\n";
    }
}
Colored by Color Scripter
cs

B번

부분 팰린드롬이 존재하냐를 묻는 문제인데, 아무 인덱스나 골라서 적어도 3자리 이상 팰린드롬을 만드는 것이다.

그냥 2칸 이상 떨어진 것 중에서 같은 숫자 쌍이 존재한다면 “YES”를 출력하면 된다.

왜냐하면 3자리 팰린드롬은 중간과 상관없이 양 끝만 같기 때문이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define MEM 5005
#define sanic ios_base::sync_with_stdio(0);
using namespace std;
int t,n;
int a[MEM];
int main()
{
    sanic;
    cin >> t;
    while(t--){
        int c=0;
        cin >> n;
        for(int i=0; i<n; i++)
            cin >> a[i];
        for(int i=0; i<n; i++)
            for(int j=i+2; j<n; j++)
                if(a[i]==a[j])
                    c=1;
        cout << (c ? "YES" : "NO") << '\n';
        memset(a, 0, sizeof(a));
    }
}
Colored by Color Scripter
cs

C번

개구리가 0번 칸에 있고, n+1번째 칸까지 가려고 한다. 적힌 문자열에 따라 왼쪽, 오른쪽으로 k칸 이하만큼 가는데, 개구리가 최소 k칸을 뛰어야 n+1칸에 갈 수 있는가 즉, 최소의 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
#include <bits/stdc++.h>
#define MEM 200005
#define sanic ios_base::sync_with_stdio(0);
using namespace std;
int t;
string s;
int dp[MEM];
int main()
{
    sanic;
    cin >> t;
    while(t--){
        int c=0;
        cin >> s;
        for(int i=0; i<s.size(); i++)
            if(s[i]=='L')
                dp[i+1] = dp[i] + 1;
        for(int i=0; i<=s.size(); i++)
            c = max(c, dp[i]+1);
        cout << c << '\n';
        memset(dp, 0, sizeof(dp));
    }
}
Colored by Color Scripter
cs

D번

간단하게 말하면 걍 수열 a,b에서 ai+aj>bi+bj를 만족하는 i,j(i<j)에 대해 Σ(j-i)를 구하라는 문제이다.

수열 a,b의 차이를 저장해놓을 자료구조(stl::vector)를 잡아놓고,

이분탐색하면서 만족하는 i,j를 찾는다.

찾는 방법은 간단하다. 걍 차이 수열의 탐색중인 구간의 시작 인덱스, 끝 인덱스를 더해서 양수이면 만족하는 i,j를 찾은 것이나 마찬가지라고 볼 수 있다.

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
#include <bits/stdc++.h>
#define MEM 200005
#define sanic ios_base::sync_with_stdio(0);
using namespace std;
typedef long long ll;
vector<ll> v;
ll n,ans;
ll a[MEM], b[MEM];
int main()
{
    sanic;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    for(int i=0;i<n;i++){
        cin >> b[i];
        v.push_back(a[i]-b[i]);
    }
    sort(v.begin(),v.end());
    int s=0,e=n-1;
    while(s<e){
        if(v[s]+v[e]>0){
            ans += e-s;
            e--;
        }
        else
            s++;
    }
    cout << ans;
}
Colored by Color Scripter
cs

코딩공부 같이하고 싶은 사람은 백준의 "그룹입니다" 그룹에 신청해주세요.
https://www.acmicpc.net/group/6712

_DynamicCube

DynamicCube.exe

Codeforces Round #627(Div.3) 연습