Codeforces Global Round 20 ABCDE

AB에서 너무 절었지만 끝까지 포기하지 않고 했더니 5솔 찍었다.

A. Log Chopping

N개의 통나무가 주어진다. errorgorn와 maomao90은 차례로 통나무를 크기가 1이상인 두 조각으로 쪼갠다. 크기가 1인 통나무는 쪼갤 수 없다. 더이상 쪼갤 통나무가 없다면, 해당 차례의 참가자는 패배한다.

풀이

몇가지 예시를 손으로 풀어보면, 통나무를 어떤 크기로 쪼개든 결과는 바뀌지 않는다. 크기가 $a_i$인 통나무를 모두 쪼개려면 $a_i-1$의 차례가 소모된다. 통나무를 모두 쪼개는 시간은

의 차례가 걸린다. ans가 홀수면 errorgorn의 승리이고 짝수면 maomao90의 승리한다.

코드

for __ in range(int(input())):
  n = int(input())
  ans = sum(map(int, input().split()))-n
  if ans%2:
    print('errorgorn')
  else:
    print('maomao90')

B. I love AAAB

string good은 AB, AAB, AAAB 같이 1개 이상의 A로 시작해서 1개의 B로 끝나는 문자열이다.
문자열 S를 입력 받는데, 빈 문자열에 어떤 자리에 string good을 삽입하는 과정을 충분히 반복해서 S를 만들 수 있을까?

풀이

문자열 S를 만들 수 있다면, 몇 가지 변하지 않는 사실이 있다.

1. 어떤 위치에서든 A의 갯수가 B의 갯수보다 많다. 문자열에서 A는 1개 이상, B는 1개 등장하기 때문이다.
2. 시작 위치에는 반드시 A가, 마지막 위치엔 B가 있다.

이 두 조건을 만족하면 YES, 그렇지 않으면 NO

코드

def solve():
  s = input()
  a, b = 0, 0
  for x in s:
    if x=='A':
      a += 1
    else:
      b += 1
    if a < b:
      return False
  if s[-1]=='A' or s[0]=='B':
    return False
  return True

for __ in range(int(input())):
  print('YES' if solve() else 'NO')

C. Unequal Array

크기가 N인 배열이 주어진다. $a_i = a_{i+1}$인 $i$의 갯수를 equality라고 정의한다. $a_i$와 $a_{i+1}$를 $x$로 치환하는 작업을 할 수 있다.
배열의 equality를 1이하로 만들기 위해 위의 작업을 실행해야 하는 최소한의 갯수는?

풀이

$a_i = a_{i+1}$인 최소 $i$인 $s$부터 최대 $i$인 $e$까지 치환 작업을 계속해야 한다.

코드

for __ in range(int(input())):
  n = int(input())
  arr = list(map(int, input().split()))
  
  s, e = n-1, 0
  for i in range(n-1):
    if arr[i]==arr[i+1]:
      s = i
      break
  for i in range(n-1, 0, -1):
    if arr[i]==arr[i-1]:
      e = i
      break

  diff = e-s+1
  if diff <= 2:
    print(0)
  else:
    print(max(1, diff-3))

D. Cyclic Rotation

크기가 N인 배열 $a$가 주어진다. 우리는 다음과 같은 작업을 무한히 할 수 있다.

위의 작업을 얼마든지 해서 배열 $a$를 배열 $b$로 만들 수 있을까?

풀이

위의 작업을 SWAP이라고 하자.
중요한 점은 ($l+1=r$)일 때를 제외하면, SWAP을 무한히 반복할 수 없다는 점이다.
$i\; (l+1 < r)$ 일 때, SWAP을 실행하면 $a[l]=a[r]$이므로 같은 숫자가 이웃하게 된다. SWAP이 끝나면 같은 두 숫자는 이웃하게 되므로 두 숫자로는 더이상 SWAP을 실행할 수 없게 된다.
배열 $b$의 원소 $b_i$를 하나씩 순차적으로 탐색한다. $a_{now}$가 $b_i$와 일치한다면, $a_{now}$와 $b_i$를 매치시키고 $b_{i+1}$로 넘어가서 다시 시작한다. 다르다면, $a_{now}$의 수를 저장해준다. 만약 $b_{i-1}$와 $b_i$가 일치하고 $b_i$가 이전에 저장된 적이 있다면, 그 수와 매치시킨다. 이 부분이 SWAP을 하는 거다. $b_i$가 $b_{i-1}$와 일치하고 이전에 $b_i$와 동일한 숫자가 나왔다면, SWAP을 통해서 이전에 있던 동일한 숫자를 $b_i$로 가져온다.

코드

def solve():
  n = int(input())
  a = list(map(int, input().split()))
  b = list(map(int, input().split()))
  passed = [0]*(n+1)
  idx = 0
  for i in range(n):
    if i > 0 and b[i]==b[i-1]:
      if passed[b[i]]:
        passed[b[i]] -= 1
        continue
    
    while idx < n and b[i] != a[idx]:
      passed[a[idx]] += 1
      idx += 1

    if idx==n:
      return False

    idx += 1

  if sum(passed)!=0:
    return False
  return True


for __ in range(int(input())):
  print('YES' if solve() else 'NO')

E. notepad.exe

인터랙티브 문제다. $n$개의 단어가 editor에 써있다. 각 단어의 길이는 $l_i$로 정의한다. $l_i$는 알 수 없다. $n$개의 단어는 여러 줄에 걸쳐 써있고, 각 단어는 $1$개 이상의 빈칸으로 구분되어 있다. $n$개의 단어를 모두 작성할 수 있는 editor의 최소 넓이를 구하는 문제이다.
editor의 $width$를 입력하면 그 $width$에 맞춰 $n$개의 단어를 모두 쓸 수 있는 최소한의 $height$가 주어진다. 만약에 $max(l_i) > width$라면, $0$이 주어진다.

풀이

코드

def ask(x):
  if x==0:
    return 0
  print('?', x)
  return int(input())

n = int(input())
s, e = 0, 5_000_000
lsum = 0
while s <= e:
  mid = (s+e)//2
  if ask(mid)==1:
    lsum = mid
    e = mid-1
  else:
    s = mid+1

ans = int(1e9)
for i in range(1, n+1):
  tmp = ask(lsum//i)*(lsum//i)
  if tmp:
    ans = min(ans, tmp)
print('!', ans)

F1. Array Shuffling

길이가 $n$인 배열 $a$가 있다. 배열 $b$를 어떤 작업을 통해 배열 $a$로 바꾸는 문제이다. 작업은 다음과 같다.

배열 $b$를 배열 $a$로 바꿀 때 사용하는 위 작업의 최소한 갯수를 sadness라고 한다. 배열 $a$가 주어졌을 때, sadness가 최대인 배열 $b$를 구해라.

풀이

위 작업을 SWAP이라고 하자. 숫자의 갯수에 따라 SWAP 수를 구해보자.

배열 $a$, $b$를 다음과 같이 정의하자.

a = [1, 2, 3, 4]
b = [2, 3, 4, 1]

2개 묶음으로 SWAP해보자.

b = [1, 3, 4, 2] -> [1, 2, 4, 3] -> [1, 2, 3, 4]
SWAP 3번

3개 묶음으로 해보자.

b = [2, 3, 4, 1] -> [1, 2, 4, 3] -> [1, 2, 3, 4]
SWAP 3번

몇 개를 단위로 SWAP하는지는 SWAP수에 영향을 미치지 않는다. 한 단위의 SWAP을 한 개의 사이클로 볼 수 있다. 만약 한 사이클에 중복되는 수가 있다면 어떻게 될까? 결과는 중복되는 수만큼 SWAP수가 줄어든다. SWAP수는 (중복 없는 한 사이클의 길이)-1의 합이다.

배열 $b$는 배열 $a$의 수를 가지고 사이클을 만들어주면 된다. $cnt$에 각 $a_i$마다의 $index$를 저장해준다.
To be continue...

코드

def solve():
  n = int(input())
  arr = list(map(int, input().split()))
  ans = [0]*n
  cnt = [[] for __ in range(n+1)]
  
  for i in range(n):
    cnt[arr[i]].append(i)

  al = [(i, cnt[i]) for i in range(n+1) if cnt[i]]
  al.sort(key=lambda x: (-len(x[1])))
  
  while len(al) > 1:
    x, y = al[-1][0], al[-1][1][-1]
    tt = len(al)
    al[-1][1].pop()
    for i in range(tt-1):
      a, b = al[i][0], al[i][1][-1]
      al[i][1].pop()
      ans[b] = x
      x = a
    ans[y] = x
    while al and not al[-1][1]:
      al.pop()
  
  while al and al[0][1]:
    x, y = al[0][0], al[0][1][-1]
    al[0][1].pop()
    ans[y] = x
  print(*ans)

for __ in range(int(input())):
  solve()

F2. Checker for Array Shuffling

풀이

코드