[CF] Codeforces Round #814 (Div. 2)

https://codeforces.com/contest/1719

Dashboard - Codeforces Round #814 (Div. 2) - Codeforces

ㄹㅇㅋㅋ

한동안 신촌연합 중급 문제 해결하느라 시간 없다고 핑계대면서, 코포 치면서도 업솔빙 안하고, 글도 안써서 이번 라운드에서 혼쭐난 것 같다. 방학 끝나면, 새로운 알고리즘은 더 필요 없으니, 진짜 코포+실or골랜디에 집중하면서 실력을 키워야겠다.

 

A. Chip Game (00:05)

관찰을 통해, (가로+세로)가 홀수면 선공이 이기고, 짝수면 선공이 짐을 알 수 있다.

대회 중에는 그냥 넘어갔지만, 왜인지 생각해보자.

 

B. Mathematical Circus (00:55)

풀이의 가닥은 바로 나왔었는데, 바로 코딩하려고 해서 망했던 것 같다. 

FRIENDS STANDINGS 에 있던 블루 선생님들 보면, 보통 20분 내외로 해결하셨던데, 나도 이 정도 스피드가 나올 수 있도록 하는걸 목표로 해야겠다.

 

n, k가 주어졌을 때, 1...n의 순열을 ((a+k)*b)%4==0인 (a, b)인 n/2개의 쌍으로 묶는 것이 가능한 지를 구하는 문제이다.

 

k = 홀수

(홀수+k)*(짝수) = (4의 배수)이고, 1...n에는 홀수 n/2개, 짝수 n/2개가 있으므로

(1, 2) (3, 4) ... (n/2-1, n/2) 로 가능하다.

 

k가 짝수

(홀수+k)*(4의 배수) = (4의 배수)

(4의 배수가 아닌 짝수+k)*(홀수) = (4의 배수)

이고, 1...n에는 홀수 n/2개, (4의 배수) n/4개, (4의 배수가 아닌 짝수) n/4개가 있으므로 

(1, 4) (3, 8) ... (2, 2i-1) (6, 2i+1) ... 로 가능하다. 

 

k = 홀수일 때를 먼저 생각하고, 그 뒤에 k = 짝수일 때를 생각했었는데, 풀이가 얼추 나온 상태에서 생각을 다 끝마치지 않고 코딩하려 했던 것이 시간 많이 쓴 것의 주범인 것 같다. 풀이가 얼추 나왔을 때엔, (4의 배수가 아닌 짝수+k) 를 직접 손으로 노트에 써놓지 않고, 그냥 머릿속으로 나이브하게 생각만 했어서 구현시에 if(k%4==0) 과 같이 썼어야 했는데, if(k==0) 으로만 해서 5번의 WA를 받으면서 계속 엉뚱한 부분을 고쳤었다. 앞으론, 손으로 직접 다 풀이를 명시적으로 한 후에 직접 코딩해야겠다.

 

C. Fighting Tournament (Upsolved)

사람 수 n, 진행 라운드 수 k, 우승 수가 궁금한 사람 i라 하자.

 

n-1번 라운드 이상 진행되면 맨 앞의 사람은 힘이 n이 사람으로 바뀌지 않는다. 즉, n-1번 라운드 이상 진행되면, 이기는 사람은 힘이 n인 사람 밖에 없다. 

i번 사람은 i-1번 라운드 미만 진행되면 한 번도 싸운 적이 없으므로, 무조건 0번 이긴다.

(단, 첫번째 사람은 1번 라운드 미만)

 

i번 이상 진행되면, 힘이 n이 아닌 사람은, ((자신보다 뒤에 있으면서, 자신보다 힘이 센 사람 인덱스) - (자신 인덱스))번 이긴다.

(단, 첫번째 사람은 ((자신보다 뒤에 있으면서, 자신보다 힘이 센 사람 인덱스) - 2)번 이김)

힘이 n인 사람은, (k - (자신 인덱스-2))번 이긴다.

(단, 첫번째 사람은 k번 이김)

 

위와 같이 구현했는데 왜 틀릴까?

주석 부분의 반례를 생각 안해서 틀렸었다. 

즉, i번 이상 진행될 때, 힘이 n이 아닌 사람의 경우에서 k < (자신보다 뒤에 있으면서, 자신보다 힘이 센 사람 인덱스)-1 를 고려 안해서 틀렸었다.

#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
ll gcd(ll a, ll b) 
{
	if (b == 0) return a;
	return gcd(b, a % b);
}
#define lcm(a, b) a * b / gcd(a, b)
const int INF=987654321;
const int MOD=998244353;
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};

void solve()
{
    ll n, q; cin>>n>>q;
    ll a[n+1];
    ll dp[n+1]; //자신까지의 중의 최대 a값
    ll dp2[n+1]; //(자신보다 뒤에 있으면서, 자신보다 힘이 센 사람 인덱스)
    memset(dp, 0, sizeof(dp));
    memset(dp2, 0, sizeof(dp2));
    ll mxidx=0;
    for(ll i=1;i<=n;i++) 
    {
        cin>>a[i];
        if(a[i]==n) mxidx=i;
        dp[i]=max(dp[i-1], a[i]);
    }
    ll idx=n+1;
    for(ll i=n;i>=1;i--)
    {
        dp2[i]=idx;
        if(dp[i-1]<dp[i]) idx=i;
    }
    
    while(q--)
    {
        ll i, k; cin>>i>>k;
        if(k<max(i-1, 1ll)) cout<<0<<'\n';
        else
        {
            if(a[i]==n) cout<<k-max(i-2, 0ll)<<'\n';
            else
            {
                if(dp[i-1]<dp[i])
                {
                    if(k<dp2[i]-1) cout<<k-max(i-2, 0ll)<<'\n'; //이 경우를 고려 안해서 반례가 있었다.
                    else cout<<dp2[i]-max(i, 2ll)<<'\n';
                }
                else cout<<0<<'\n';
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int tc=1; cin>>tc;
    while(tc--) solve();
    return 0;
}