Codeforces Round #751 (Div. 2)-B. Divine Array

falconlee236

2021. 11. 20. 15:13

문제 설명

승현이는 $n (1 \le n \le 2000)$개의 정수로 이루어진 성스러운 배열 $a$ 을 받았다. $a$의 각 위치는 초기값을 가지고 있다. 그런데 갑자기 배열에 저주가 내려졌다!! 배열은 화가났고, 멈추지않는 변환이 시작되었다.

변환은 무한번 이루어지는데, 배열 $a$는 다음 방식으로 $i$번째 단계를 수행한다.

모든 주어진 위치 $j$에 대해서 $a_j$는 이 단계를 수행하기 전에 배열 $a$에 있는 $a_j$의 개수로 바뀐다.

당신이 문제를 잘 이해하기 위해서 예시를 들어보자면.
초기단계 $2, 1, 1, 4, 3, 1, 2$
첫번째 단계 이후 $2, 3, 3, 1, 1, 3, 2$
두번째 단계 이후 $2, 3, 3, 2, 2, 3, 2$
세번째 단계 이후 $4, 3, 3, 4, 4, 3, 4$

초기 배열에 $2$ 2개와 $3$ 1개와 $4$ 1개와 $1$ 3개를 가지고 있다. 따라서 첫번째 단계 이후에는 각 원소는 초기 단계에 있는 원소의 개수로 바뀐다. 모든 $2$는 $2$로 바뀌고, 모든 $1$은 $3$으로 바뀌고, $4$와 $3$은 $1$로 바뀐다.

이 변환 단계는 영원히 계속된다.

우리는 $q$개 질의를 수행해야한다. 각 질의에서 승현이는 $k$번째 변환 단계에서 $a_x$값이 어떤상태인지 알고 싶다.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 배열 $a$의 크기 $n (1 \le n \le 2000)$ 이 주어진다.

각 테스트케이스의 두번째 줄에는 배열 $a$의 초기값인 $n$개의 정수 $a_1, a_2, ..., a_n (1 \le a_i \le n)$ 이 주어진다.

각 테스트케이스의 세번째 줄에는 질의의 수 $q$가 주어진다. $q (1 \le q \le 100000)$ 이 주어진다.

다음 $q$개의 줄에는 질의의 정보가 주어진다. $i$번째 줄은 $x_i$와 $k_i (1 \le x_i \le n, 0 \le k_i \le 10^9)$가 주어진다. $k_i$번째 변환 단계 이후에 $a_{x_i}$의 값을 물어보는 뜻이다. $k_i = 0$은 초기 배열의 값을 물어보는 것이다.

Output
각 테스트케이스마다 $q$개의 답을 출력한다. $k_i$번째 변환 단계 이후에 $a_{x_i}$의 값을 출력한다.

Example
input
2
7
2 1 1 4 3 1 2
4
3 0
1 1
2 2
6 1
2
1 1
2
1 0
2 1000000000

output
1
2
3
3
1
2

문제 접근

사용한 알고리즘: 구현, 구성적 알고리즘
걸린 시간 : 00:06
도대체 왜 나는 쉽게 풀수 있는 문제, 단순하게 생각하면 풀 수 있는 문제를 계속 비비배배 꼬아서 생각을 해 문제를 못푸는 것일까? 제발 단순하게 생각을 하자. 그러면 답이 보일테니..

$k_i$의 제한이 $10^9$라는 것을 보고 무조건 특정한 반복 횟수 이후에는 값이 변하지 않을 것이라는 믿음을 가지고 있었다. 그렇다면 어떻게하면 이 특정한 반복 횟수를 구할 수 있을까? 이것을 못찾아서 나는 못풀었는데, 나는 규칙이 따로 있는줄 알았다. 하지만 문제에 있는 해설은 그냥 해보니까 배열의 길이가 $n$이면 $n$번 반복 이후에는 배열의 원소가 변하지 않는다고 한다. 그냥 몇번 해보니까 그렇다고 한다.

에라이 구성적 알고리즘 문제였다.... 정말 짜증난다. 그냥 문제에 주어진대로 구현을 하되, $n$보다 넘어가는 질의가 나오면 그냥 min()을 이용해서 맨 마지막 값으로 바꿔서 푼다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int arr[n + 1][n + 1];
        for(int i = 1; i <= n; i++) cin >> arr[0][i];

        for(int i = 1; i <= n; i++){
            int cnt[n + 1] = {};
            for(int j = 1; j <= n; j++) cnt[arr[i - 1][j]]++;
            for(int j = 1; j <= n; j++) arr[i][j] = cnt[arr[i - 1][j]];
        }

        int q; cin >> q;
        while(q--){
            int x, k; cin >> x >> k;
            cout << arr[min(k, n)][x] << "\n";
        }
    }
    return 0;
}

To the Expert