Codeforces Round 868 (Div. 2)
A. A-characteristic (800)
모든 $1, -1$은 붙어있어도 상관없다.
$n$개가 있다면 $1$이 $k$개가 있고 $-1$이 $n-k$개가 있는데, 그럼 총 쌍의 개수는
$\dbinom {k}{2} \cdot \dbinom {n-k}{2}$ 이다.
가능한 $k$를 $k \coloneqq 0 \to n$ 까지 순회해주며 $K$개가 나오는지 확인해주면 된다.
B. Sort with Step (900)
$\lvert i-j \rvert=k$ 인 것만 swap이 가능하다는 것은 수열을 $k$개의 그룹으로 나눌 수 있다는 의미이다.
$i$번 째 있는 그룹엔 $i, i+k, i+2k, \dots$ 의 수들만 있어야 하며 자기가 들어가야 할 그룹에 있지 않은 수들의 개수를 bad count라고 하자.
이것이 $0$개라면 정답은 $0$이고, $2$개라면 정답은 $1$이고 아니라면 $-1$이다.
C. Strongly Composite (1300)
일단 $a$의 모든 수들을 소인수분해하자. $n \le 1,000$ 이라서 괜찮다.
이제 모든 소수들만 모아두자.
최대한 그룹의 크기를 최대로 만들어야 하므로 소수들을 어떻게 묶어야 할지 보자.
소수 $p$가 $k$개 있다고 하자.
$\{p, p\}$ 인 그룹은 가능하다. 왜냐하면 $p^2$ 의 합성수는 $p^2$ 밖에 없고 소수 $1$개, 합성수 $1$개로 소수가 더 적은 Strongly Composite 수이기 때문이다.
이렇게 모든 같은 소수들에서 두 개씩 뽑아내면 각 소수마다 $0 \text{~or~} 1$ 개의 소수들이 남고, 이 것들 개수의 합을 $K$라고 하자.
이제 서로 다른 소수들은 최소 $3$개씩 묶어야 한다. 따라서 정답에 $\left\lfloor \dfrac K3 \right\rfloor$ 을 더해준다.
D. Unique Palindromes (1900)
$p \le 20$ 임을 보자.
이건 시간복잡도와 관련있을 수도 있지만, 알파벳은 최대 $26$개이므로 뭔가 이것과 연관지어 생각하는 것이 문제를 해결할 열쇠이다.
$c_i > n$ 이라면 불가능하다. 왜냐면 하나의 알파벳을 추가할 때 팰린드롬은 최대 $1$개씩 추가되기 때문이다.
같은 이유로 $x_{i+1}-x_i < c_{i+1}-c_i$ 라면 불가능하다. 추가할 수 있는 문자보다 늘어나야할 양이 많다면 불가능하다.
그리고 $c_i < 3$ 이라면 불가능하다. 처음 세 개는 무조건 팰린드롬이 $1$개 씩 늘어나게 추가할 수 밖에 없기 때문이다.
$3 < c_i \le n$ 이라고 하자.
문제를 푸는 핵심은 어떤 같은 문자를 계속 추가하면 항상 팰린드롬을 1 늘릴 수 있다는 것이다.
따라서 이렇게 길이를 늘릴 때 사용할 문자를 $0 \sim p-1$ 마다 $d$ 부터 시작해서 $d,e,f,g,\dots$ 처럼 늘려간다.
이제 $abc$는 어디다 사용할 것이냐면 팰린드롬을 늘리지 않게 하는 용도로 사용한다.
처음에 정답을 $abc$로 두고 만약 그 다음 $x_i=7,~c_i=5$ 라고 하자.
문자 $4$개를 추가해야되는데 팰린드롬은 $2$개만(현재 $3$개 이므로) 늘려야 하는 상황이다.
그럼 $2$개를 팰린드롬이 추가되지 않게 사용해야 하므로 $abc$ 를 계속 돌린다.
이후 $d$ 를 $2$개 추가한다.
$abc \to abcab \to abcabdd$
이제 다음번엔 $abc$에선 $c$를 사용해주고 늘리는 용도론 $e$를 사용해주면 정답을 구성해 나갈 수 있다.
void solve() {
int n, k;
cin >> n >> k;
vector<pi> a(k);
for (int i = 0; i < k; i++) cin >> a[i].fi, a[i].fi--;
for (int i = 0; i < k; i++) cin >> a[i].se;
sort(all(a));
string ans;
char nxt_add_char = 'd';
char nxt_skip_char = 'a';
ans = "abc";
for (int i = 0; i < k; i++) {
int x = a[i].fi, c = a[i].se;
if (x <= 2) {
if (x + 1 != c) {
cout << "NO\n";
return;
}
continue;
}
int diff = x + 1 - sz(ans); // 5 - 3
int add = i == 0 ? (c - 3) : (a[i].se - a[i - 1].se);
if (add > diff) {
cout << "NO\n";
return;
}
int skip = diff - add;
while (skip--) {
ans += nxt_skip_char;
nxt_skip_char = (nxt_skip_char - 'a' + 1) % 3 + 'a';
}
while (add--) {
ans += nxt_add_char;
}
nxt_add_char++;
}
cout << "YES\n" << ans << endl;
}
Comments