D. Min Cost String | Edu Round 107 Div.2

LONGNEW·2021년 7월 21일
0

CP

목록 보기
53/155

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

input :

  • n k (1 ≤ n ≤ 2⋅105; 1 ≤ k ≤ 26)

output :

  • Print the string s such that it consists of n characters, each its character is one of the k first Latin letters, and it has the minimum possible cost among all these strings. If there are multiple such strings — print any of them.
    n개로 이루어진 문자열을 출력하시오. 각각의 문자는 알파벳의 k번째 까지만 사용해야 하며 가능한 비용을 작게 해서 만들어야 한다. 다양한 문자열이 존재한다면 그 중 하나를 출력하시오.

조건 :

  • Let's define the cost of a string s as the number of index pairs i and j (1 ≤ i < j < |s|) such that si = sj and si + 1 = sj + 1.
    문자열의 비용은 어떤 인덱스 i와 j가 존재할 때 si = sj and si + 1 = sj + 1 과 같은 원소가 존재하는 횟수를 비용으로 생각한다.

위의 조건을 만족시키지 않는 문자열을 만들고 싶으면 어떻게 해야 할까...

모든 단어

조건을 보면 결국에는 2짜리 단어들 중 동일한 단어가 없는 문장을 만들면 된다.

그러면 aa, ab, ac, ad, ae, ...., zz까지 경우가 존재하는데 예외가 발생한다.

동일한 알파벳

aaab와 같은 경우 위의 비용이 발생하기 때문에 그냥 a, ab, ac의 순서대로 만들면 이를 예방할 수 있다.

그러면 이 단어들을 모두 합해 문장을 만들어서 그냥 출력하면 우리가 원하는 문장을 얻을 수 있다.

import sys

n, k = map(int, sys.stdin.readline().split())
ans = []

for i in range(k):
    now = chr(97 + i)
    ans.append(now)

    for j in range(i + 1, k):
        ans.append(now + chr(97 + j))

ans = "".join(ans)

while len(ans) < n:
    ans += ans

print(ans[:n])

0개의 댓글