Codeforces Global Round 20

https://codeforces.com/contest/1672/problem

A. Log Chopping

게임 이론 문제처럼 보이지만, 사실은 처음부터 승자가 결정되어 있는 문제.

누가 무엇을 자르든, 자르는 총 횟수는 sum(A) - n번이다.

 

B. I love AAAB

A와 B로만 이루어진 string을 다음 operation을 적용하여 만들 수 있는가?

string에 {A...AB}를 원하는 위치에 추가하는 operation

 

처음엔 B의 양 옆에 B가 없어야 한다고 착각했다. 하지만 "" -> "AB" -> "A AB B"로 B가 인접해서 여러 번 나올 수 있었다. 증명을 제대로 시도하지 않은 탓이다.

 

직관은

1) B가 존재하면 A도 존재해야 한다. 즉, B의 카운트보다 A의 카운트가 많아야 한다.

2) A가 존재하면 B도 존재해야 한다. 즉, B가 마지막으로 끝나야 한다.

이 두 가지 조건이 답에 해당한다.

 

근데 명쾌하지가 않다. 위의 조건이 문제의 조건과 동치임을 어떻게 증명하나?

1) 문제의 조건은 위의 조건을 포함하는가?

가능하다. B가 주어진 자리 앞에 A를 배치하고, 나머지 A는 알아서 추가하면 된다.

2) 위의 조건은 문제의 조건을 포함하는가?

어떤 string s가 위의 조건을 만족한다고 하자. string s에 operation 하나를 적용했을 때, 위의 조건이 성립하는 게 자명하다. 수학적 귀납법으로 성립.

 

 

따라서 둘은 동치다.

from sys import stdin

t = readint()
for _ in range(t):
  s = input()
  cnt_a, cnt_b = 0, 0

  ans = "YES"
  for c in s:
    if c == 'A':
      cnt_a += 1
    else:
      cnt_b += 1
    
    if cnt_b > cnt_a:
      ans = "NO"
  if cnt_b == 0:
    ans = "NO"
  if s[-1] != 'B':
    ans = "NO
    "
  print(ans)

C. Unequal Array

어떤 array에서, 인접한 두 수가 같은 경우를 최대 1개까지만 만드는데 필요한 다음 operation의 수

operation: 인접한 두 수를 골라서 같은 수 x로 바꾼다.

 

1) 접근

이 operation을 사용하면 인접한 같은 수가 또 생긴다. 결국, operation을 연이어서 계속 사용해야 한다. 인접한 같은 수를 한 칸 옆으로 미는 것과 같다. 

그러면, 모든 인접한 수가 있는 index를 구해서, 해당 index + 1 ~ 마지막 인접한 수가 있는 index - 1까지 operation을 계속 쓰면 된다.

 

여기서 한 번 틀렸던 것은 operation을 전혀 사용하지 않아도 되는 경우가 있다는 것. 인접한 수가 없거나 한 개면 쓰지 않아도 된다.

from sys import stdin

def readint():
    return int(stdin.readline())

def readarray(typ):
    return list(map(typ, stdin.readline().split()))

t = readint()
for _ in range(t):
  n = readint()
  A = readarray(int)

  equality_indices = []
  for i, (a, b) in enumerate(zip(A[:-1], A[1:])):
    if a == b:
      equality_indices.append(i)

  if (not equality_indices) or len(equality_indices) == 1:
    print(0)
  else:
    equality_front = equality_indices[0]
    equality_back = equality_indices[-1]
    print(max(1, (equality_back - 1) - (equality_front + 1) + 1))

 

D. Cyclic Rotation

이번 대회에서 가장 많은 삽질을 한 문제

array가 주어졌을 때, 같은 값의 수를 두 개 골라서 해당 범위를 왼 쪽으로 한 칸 밀 수 있다. np.roll과 비슷하다.

이 operation을 제한 없이 사용했을 때 한 array를 다른 array와 동일하게 만들 수 있는지를 묻는 문제.

 

발상하는 데 시간이 꽤 오래 걸렸다.

 

핵심 생각은

1) 앞에서부터 하나씩 매칭

일단, 문제가 그렇게 어렵지 않을 거라 가정하고 앞에서부터 하나씩 매칭하면 될 거라고 생각했다.

이게 가능한 이유는, 만약 앞의 array 값이 맞지 않는다면 무조건 operation을 적용해서 바꿔야 하기 때문이다.

2) 같은 값이 여러개일 때는, operation을 index가 가장 낮은 것 두 개에 대해서 적용한다.

앞에서부터 매칭할 때 operation이 가능한지를 찾고, operation이 여러 인덱스에 대해 가능할 수 있다. 이때 어떤 것을 선택해야 할까?

가장 가까운 index에 대해 적용하는 것이 무조건 이득이다. 왜냐하면, 가장 가까운 index에 대해 operation을 여러번 적용하는 게 가장 먼 index에 대해 operation을 한 번만 적용하는 것과 같기 때문이다.

 

이 두 key idea를 이용해서 풀면

 

array A와 B가 있을 때,

A와 B의 인덱스를 앞에서부터 비교해서 -> 만약 다르다면 A의 해당 인덱스에 operation을 적용할 수 있는지를 찾고, 실제로 적용한 것을 시뮬레이션한다.

만약 A와 B가 다른데 operation을 더이상 적용할 수 없다면 Fail이다.

 

여기서 문제는)

array가 단순 list라면, 이 시뮬레이션에 O(n^2)시간이 소요되어 TLE가 확실하다. 어떤 범위의 값들을 한 칸씩 옆으로 미는게 O(n)이기 때문이다.

그래서 투 포인터 기법 비슷한 방식을 써야 한다. 실제로 밀지 않고 말이다.

 

실제로 푼 방식은 서로 다른 값이 나오면 값을 keep하고, 나중에 그 값이 나왔을 때 keep한 것을 복원하는 방식이었다. 그런데 구현이 좀 번거롭다. 너무 절차지향적인 느낌이라고 해야 하나..

틀린 부분들을 보면 i를 +1하는 타이밍이나, 마지막에 keep한 것이 남아있는지 확인하는 로직을 깜빡한 것,

counter를 글로벌 변수로 둔 것도 삽질이긴 하다.

from sys import stdin

def readint():
    return int(stdin.readline())

def readarray(typ):
    return list(map(typ, stdin.readline().split()))

def f(b_j, A, i, keep):
  while A[i] != b_j:
    keep[A[i]] += 1
    i += 1
    if i >= len(A):
      return None, keep
  # A[i] == b_j

  if keep[A[i]] > 0:
    keep[A[i]] -= 1
    next_i = i
  else:
    next_i = i + 1
  if next_i >= len(A):
    next_i = None
  return next_i, keep
    
t = readint()
for _ in range(t):
  n = readint()
  A = readarray(int)
  B = readarray(int)
  
  from collections import Counter
  keep = Counter()
  i, j = 0, 0

  succeed = True
  for b_j in B:
    if i is None:
      succeed = False
      break
    i, keep = f(b_j, A, i, keep)
    # print("i, keep", i, keep)

  print("YES" if succeed else "NO")

확실한 건 -> 함수를 정의할 때 해당 함수가 어떤 상황에 어떤 값을 리턴해야 할 지 확실히 정의해 놓아야 한다.

위의 구현에서 f는, b_j의 값을 찾으면 다음 i가 될 index를 리턴하고, 못 찾거나 다음 i가 될 index가 배열 범위를 벗어나면 None을 리턴한다.

 

F1. Array Shuffling

array A를 array B로 바꾸려 할 때, 필요한 swap operation의 총 개수가 최대가 되는 array를 만들기

그냥 한 단계 미는 게 최선이 아닐까?라고 생각했는데, 가장 빈도 수가 높은 원소의 빈도 수만큼 미는 게 최선이었다.