CodeupCoder's Blog

오늘은 codeforces Div 3 후기겸 풀이를 올려보려고 한다.

사실 코포 대회는 주로 저녁 11시 35분에서 새벽 1시 35분까지 열리기 때문에(러시아에서 열리는 대회라 그렇다) 12시에 칼같이 자는 나에게는 적합한 대회가 아니다. (...)

그래도 재미삼아 A번이라도 풀기 위해 대회에 참가했다.(그리고 목표에 충실하게 A번만 풀고 빤스런했다)

그럼 본격적으로 풀이와 후기를 써본다.

A. Special Permutation

Problem Statement

You are given one integer n (n>1).

Recall that a permutation of length nn is an array consisting of nn distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation of length 5, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Your task is to find a permutation p of length n that there is no index i (1≤i≤n) such that pi=i(so, for all i from 1 to n the condition pi≠i should be satisfied).

You have to answer t independent test cases.

If there are several answers, you can print any. It can be proven that the answer exists for each n>1.

Input

The first line of the input contains one integer t (1≤t≤100) — the number of test cases. Then t test cases follow.

The only line of the test case contains one integer n (2≤n≤100) — the length of the permutation you have to find.

Output

For each test case, print n distinct integers p1,p2,…,pn — a permutation that there is no index i (1≤i≤n) such that pi=i (so, for all i from 1 to n the condition pi≠i should be satisfied).

If there are several answers, you can print any. It can be proven that the answer exists for each n>1.

풀이

쉽게 생각하면 쉽고, 어렵게 생각하면 어려운 문제이다.

문제를 번역하면 이렇다.

'n이 주어질 때 n의 순열 p1,p2,…,pn 중 pi≠i 인 순열을 아무거나 출력하세요'

이를 더 간단하게 바꾸면 다음과 같다.

'n이 주어질 때 n의 교란순열중 하나를 출력하세요'

따라서 n의 순열 중 기본적인 것인 1, 2, ..., n 을 한칸씩 밀려쓴 순열을 출력하면 정답이 된다.

#include <stdio.h>
int main()
{
    int t,i;
    scanf("%d\n",&t);
    while(t--)
    {
        int a;
        scanf("%d",&a);
        for(i=2;i<=a;i++)
        {
            printf("%d ",i);
        }
        printf("1 ");
    }
    return 0;
}

[00:09 Wrong Answer on test 2]

[00:09 Wrong Answer on test 1]

[00:10 Accepted]

a가 홀수일 때와 짝수일 때를 굳이 나눠서 생각하다가 1틀을 하고, 마지막에 띄어쓰기가 없어서 또 1틀을 했다.

이런데서 실수하지 말자... ㅠㅠ

B번은 간단한 구현 문제로 보인다. 업솔빙 예정.

대회 후기를 써볼려고 한다..

사실 이 대회는 끝나기 약 15분 전에 들어와서 2문제 밖에 풀지 못했는데, 지금껏 내가 한 대회 중(몇개 안되지만) 가장 빨리 2개를 푼 셋이라 한번 올려본다.

앞으로는 모든 대회에 대한 후기를 올리도록 하겠다.

A. Determinant(100)

Problem Statement

Given is a 2×2 matrix A=[a b

                                                            c d].
The determinant of A can be found as ad−bc.
Find it.

Constraints

• All values in input are integers.
• −100≤a,b,c,d≤100

말 그대로 a*d - b*c를 출력하면 된다.

[89:39 AC]

#include<stdio.h>
int main()
{
    int a,b,c,d;
    scanf("%d %d\n%d %d",&a,&b,&c,&d);
    printf("%d",a*d-b*c);
}

B. Quizzes(200)

Problem Statement

Takahashi will answer N quiz questions.
Initially, he has X points. Each time he answers a question, he gains 1 point if his answer is correct and loses 1 point if it is incorrect.
However, there is an exception: when he has 0 points, he loses nothing for answering a question incorrectly.

You will be given a string S representing whether Takahashi's answers are correct.
If the i-th character of S from the left is o, it means his answer for the i-th question is correct; if that character is x, it means his answer for the i-th question is incorrect.
How many points will he have in the end?

Constraints

• 1≤N≤2×1051≤N≤2×105
• 0≤X≤2×1050≤X≤2×105
• S is a string of length N consisting of o and x.

역시 간단한 구현 문제이다.

[88:09 AC]

#include <stdio.h>
int main()
{
    int i,a,b;
    char n;
    scanf("%d %d\n",&a,&b);
    for(i=0;i<a;i++)
    {
        char n;
        scanf("%c",&n);
        if(n=='o')
        {
            b++;
        }
        if(n=='x')
        {
            if(b==0)
            {
                b=0;
            }
            else
            {
                b--;
            }
        }
    }
    printf("%d",b);
    return 0;
}

대회 중에는 여기까지 풀었다.

늦게 들어와서 등수가 많이 떨어졌다.

C번은 업솔빙 예정이다.

나는 애초에 KOI같은 대회는 나갈 생각도 없었고, 나가서 잘 할 것이라는 자신이 없었다.

엣코더, 코포 뉴비에 백준 플래 4가 뭘 하겠는가..

그런데 오픈 컨테스트가 있다는 것을 보고 뭔가 해보고 싶어서 신청을 해 놓고, 2시간 정도 시간을 내서 풀기로 했다.

11월 16일 8시 25분경에 시험을 시작했고, 초등부 시험을 쳤다.(현재 초딩이다)

결론부터 말하자면... 심하게 뇌절했다.

1차대회 문제를 백준에서 업솔빙했을 때는 굉장히 쉬웠고, 고등부까지 포함해서 1문제 빼고 다 풀었던 기억이다.

그래서 2차대회도 쉽겠지? 하고 시험을 쳤는데 상당히 어려워서 뇌절했던 것 같다.

또 아는 알고리즘이 많이 없어서 푸는 방법은 알아도 구현을 못하는 (아주 큰)문제점이 있었다.(실제로 그런 이유로 3번을 못 푼 것 같다)

서론은 이쯤 하고... 문제 풀이와 본격적인 후기로 들어가자.

시작하자마자 1번으로 들어가서 문제 파일을 다운받았다.

1번 문제는 어렵지 않았다.

풀이는 다음과 같다.

(풀이)

N개 중 K개의 수를 어떻게 뽑아도 처음에 뽑은 수는 0, 그 다음은 1, 3번째는 2 ... 해서 K번째는 K-1 손해를 보게 되어있다.

그래서 가장 큰 K개의 수를 뽑아야 손해를 보더라도 최대가 됨을 알 수 있다.

이에 근거해 수열의 합 개념을 이용하면 문제의 답은 다음의 식과 같다.

(가장 큰 K개의 수) - (K-1)*K/2

문제도 쉽고, 나는 부분점수를 받을 생각을 안하고 애초에 정풀을 생각하려고 노력했기 떄문인지 바로 100점을 받을 수 있었다.

<코드>

이 코드로 19분만에 AC를 받았다. [2020/11/16/08:44] 100/100점

2번 문제는 보자마자 뇌절을 하기 시작했다.

내가 어려워하던 종이접기 문제일 뿐만 아니라 이걸 어떻게 구현할지 전혀 감이 안왔다.

그래서 아무 생각도 안하고 첫 번째 부분문제만 풀기로 하고 k가 1일 때 나올 수 있는 정답이 몇 개인지를 직접 셌다.

얻어진 결과를 하드코딩한 결과 29점을 긁을 수 있었다.

근데 이 29점을 얻는 과정도 순탄하지가 않았던게, 여기서 구현미스로 뇌절을 거의 30분 가까이 했다.

여담으로 이 문제는 부분문제당 테케가 한 개씩, 전체 3개밖에 없었다. 지금 생각하니 대회에 이렇게 데이터가 약해도 되나 싶다.(1번 문제는 데이터가 200개 이상이다)

이 문제는 하드코딩을 했기 때문에(...) 굳이 코드를 공유하지 않겠다.

2번과 3번 문제를 봤는데...

어려워 보여서 문제만 읽고 걍 버렸다.

초딩이 이걸 어케 푸노,,

4번 역시 문제 읽고 버렸다.

그래서 1번에서 100점을 얻어 총 100점으로 대회를 마무리했다.

백준에 문제들이 올라오면 2번 문제는 업솔빙할 예정이다.