Codeforces Round #686 (Div. 3) ABCD

import sys
input = sys.stdin.readline

for TEST in range(int(input())):
    n = int(input())
    for i in range(n-1):
        print(i+2, end=" ")
    print(1)

 

A - Special Permutation

 

한 칸씩 옆으로 밀면 A_i != i가 성립한다.

 

 

import sys
input = sys.stdin.readline

for TEST in range(int(input())):
    n = int(input())
    d = {} # appearance, ind
    s = [*map(int, input().split())]

    for i, c in enumerate(s):
        try:
            d[c] = [d[c][0]+1, d[c][1]]
        except:
            d[c] = [1, i+1]

    m = 2000000000
    w = -1

    for keys in d:
        if d[keys][0] == 1:
            if m>keys:
                m = keys
                w=d[keys][1]

    print(w)

 

B - Unique Bid Auction

 

그냥 구현 문제

 

이런건 안 냈으면 좋겠다.

 

 

import sys
input = sys.stdin.readline

for TEST in range(int(input())):
    n = int(input())
    s = [*map(int, input().split())]

    d = {}
    for i, c in enumerate(s):
        if i==0 or s[i-1]!=c:
            try:
                d[c] += 1
            except:
                d[c] = 1
    if len(d)==1:
        print(0)
    else:
        if d[s[0]]==1 or d[s[-1]]==1:
            print(1)
        else:
            d[s[0]] -= 1
            d[s[-1]] -= 1
            m = min(d.values())
            res = m+1
            print(res)

 

C - Sequence Transformation

 

각 숫자가 몇 번 나오는지 세되, 연속해서 나오면 한 번 나온 걸로 취급한다.

 

수가 한 종류면 0,

 

맨 왼쪽 혹은 맨 오른쪽에 있는 수가 유일하다면 1, (그 수를 선택하면 나머지를 모두 지울 수 있다.)

 

그 외의 경우엔 양 끝에 있는 수를 무시한 최솟값이다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool isPrime[102000];
vector<ll> primes;

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	memset(isPrime, true, sizeof(isPrime));

	isPrime[1] = false;
	for (int i = 2; i <= 101000; ++i) {
		if (!isPrime[i]) continue;
		for (int j = 2 * i; j <= 101000; j += i) isPrime[j] = false;
	}
	for (ll i = 2; i <= 101000; ++i) if (isPrime[i]) primes.push_back((ll)i);

	int TEST; cin >> TEST; while (TEST--) {
		ll n, nn; cin >> n; nn = n;
		vector<ll> res;
		map<ll, int> g;

		for (int i = 0; i < primes.size(); ++i) {
			while (n % primes[i] == 0) {
				g[primes[i]] += 1;
				n /= primes[i];
			}
		}
		ll M = -1, t = -1;
		for (auto& i : g) {
			if (M < i.second) {
				M = i.second;
				t = i.first;
			}
		}

		cout << max(1LL, M) << "\n";
		for (int i = 0; i < M - 1; ++i) {
			cout << t << " ";
			nn /= t;
		}
		cout << nn << "\n";
	}
}

 

D - Number into Sequence

 

소인수분해해서 가장 많이 나온 소수를 (나온 횟수 - 1)번 곱하고 남은 만큼을 더 곱하면 된다.

 

2^2 + 3^3 = 31 같은 경우가 있어 무조건 작은 소수를 택하면 안 된다..