https://codeforces.com/contest/1624/problem/D
시간 2초, 메모리 256MB

input :

• t (1 ≤ t ≤ 104)
• n k (1 ≤ k ≤ n ≤ 2 * 105)
• s (n개의 알파벳으로 이루어진 문자열)

output :

• output a single integer — the maximum length of the shortest palindrome string that can be obtained.
  팰린드롬 문자열의 길이를 최대로 만든 후 그 중 최솟값을 출력하시오.

조건 :

• You can color some letters in colors from 1 to k.
  임의의 문자에 색칠을 할 수 있다.

• But for each color, there must be a letter painted in that color.
  각 색깔에 대해, 모든 색깔이 문자에 칠해져 있어야 한다.

• Then you can swap any two symbols painted in the same color as many times as you want.
  동일한 색으로 칠해진 두 문자를 교체시킬 수 있다.

• k 종류의 팰린드롬 문자열 중 길이의 최솟값을 출력하시오.

---

가장 아쉬운 문제이다. 괜히 초반에 쫄아서 G로 갔다가 자아성찰 한번 더하고.. 그냥 20분을 여기 썼으면 풀 수 있지 않았을까 싶다.

그래도 푼 것에 만족을 하도록 하자.

다음 풀이

1. 임의의 색깔
2. 팰린드롬?

색깔 종류 개수가 중요하다. 팰린드롬을 "만드려고 한다면" 동일한 문자에 대해서는 2개씩 넣으면 언제나 팰린드롬을 만들 수 있다.
그렇다고 해서 계속 2개씩 넣으면 안 된다.
예제의 마지막 테케에서 2개씩 넣으면 [4, 2]가 되어서 답을 만들 수 없다.
여기서 추가적으로 가져오는 조건이 (2개의 개수) >= k인 경우에만 모든 문자열에 2씩 넣어준다.

기본적인 사고 과정이 위에 경우이고 우선적으로 2개씩 있는 것들을 다 넣어준다면 1개짜리 들을 추가할 수 있다. 만약 홀수가 된다면 인제는 팰린드롬을 만들 수 없다.

import sys

t = int(sys.stdin.readline())

for _ in range(t):
    n, k = map(int, sys.stdin.readline().split())
    data = list(sys.stdin.readline().rstrip())
    ans = [0] * k

    alpha = dict()
    temp = "abcdefghijklmnopqrstuvwxyz"
    for item in temp:
        alpha[item] = 0

    cnt, ones = 0, 0
    for item in data:
        alpha[item] += 1

        if alpha[item] == 2:
            alpha[item] = 0
            cnt += 1

    for key in alpha.keys():
        if alpha[key] == 0:
            continue
        ones += 1

    idx = 0
    while cnt >= k:
        for i in range(k):
            ans[idx] += 2

            idx += 1
            if idx >= k:
                idx = 0
            cnt -= 1

    ones += cnt * 2
    while ans[-1] % 2 == 0 and ones > 0:
        if ans[idx] % 2 != 0:
            continue

        ans[idx] += 1

        idx += 1
        if idx >= k:
            idx = 0
        ones -= 1

    print(min(ans))

만약 다음에 이런 문제를 접한다면 이렇게 쪼개서 생각을 하도록 해야겠다.