분명 앳코더는 몰라도 코포는 시간 되면 무조건 참여했던거 같은데 이게 얼마만이노;; 생각해보니까 요즘 친거 다 꼴아박아서 안 쓴것 같기도 하고

1d 10p 도 요즘엔 안하고 좀 열심히 해야겠음. 버츄얼도 열심히 돌리고

사탕 계정도 이제 비기너스 럭 다 빠졌는지 꼬라박고 있는데 그냥 본계로 열심히 달려봐야겠음

A. Balance the Bits

괄호 문자열 2개가 있고 a, b 라고 하면 ai = bi 일때 1, ai != bi 일때 0 이라고 표현한 수열만 주어질때 올바른 괄호문자열 2개를 만들 수 있냐?

순간 div2 a 로 착각하고 좀 말릴뻔했음.

우선 첫 번째는 무조건 ( 여야되니까 같을거고 마지막 것도 무조건 ) 여야 되니까 같을거고.. 생각했는데 별 의미없는거 같아서 패스함. 

3분인가에 스코어 보니까 막 1초만에 생각나는 개쉬운 문제는 아닌 것 같아서 좀 더 생각해보기로 함. 

( 를 +1, )를 -1로 보면 a랑 b랑 차이가 0이 한 번 나올때마다 2씩 벌어짐. 마지막엔 둘 다 0이어야 되니까 0은 짝수개여야 함. 

뭐 비슷한 논리로 1도 짝수개여야함. 근데 0짝수 1짝수라고 항상 답은 아니더라고. 예제에도 있음

그래서 걍 그리디 풀이를 찾아봤음. 어차피 0 짝수개면 +2 n/2 개 -2 n/2개 있어야 되니까 1 짝수개도 ( / ( n/2개, ) / ) n/2개 필요함. 

( / ( 는 걍 먼저 나오면 먼저 나올 수록 이득이니까 1은 무조건 ( / ( 먼저 때려박고 0 은 ( / ) 먼저 때려박는거 제출해봤더니 실패해서 ( / ) or ) / ( 번갈아가면서 했음

증명을 대충한 그리디인데 풀이는 맞더라

제출횟수 씨발

-2 19:35 AC 

B. 3-Coloring

N^2 판을 3가지 색깔로 채울 건데 인접한 게 같은 색깔이면 안 됨. i가 주어질 때 i가 아닌 색깔을 무조건 칠해야하고 어디에 칠해야 가능한지 interactive 하게 하는 문제

그래도 조금 자신 있는 interactive인데 B? 이거 무조건 빨리 컷해야겠다는 생각 했음

딱 봐도 체스칸처럼 배치하는게 떠오르길래 그쪽으로 생각해봤음. interactive 가 아니였으면 그냥 offline 처리로 과반수 센 다음 체스판에 껴 넣기만 하면 되는데 그게 아니라 좀 생각 더 했음.

근데 그냥 단순하게 체스판 흑백에 1이랑 2랑 번갈아가면서 끼면 둘 중 하나 언젠간 포화되는데 그러면 남은 칸에 포화된 새끼 말고 딴거 끼면 됨. 색깔이 3개라 무조건 가능함.

근데 씨발 남은 칸에 포화된 새끼 말고 딴거 끼는 과정에서 6-ans-x 를 칠한다 라고 했음;; 그러면 1이 포화된 상태에서 1입력되면 4를 낀다는 소리인데

그것도 4가 나왔으면 금방 알아채는건데 하필이면 6-2-2=2 여서 디버깅 시간도 날림. 짜즌나

-1 34:56 AC 

C. Travelling Salesman Problem

각 도시에 해당된 ai 랑 ci 가 있을 때 i->j 로 가는 가중치가 max(ci, aj-ai) <- abs 없음 일때 TSP 

TSP입갤 ㅋㅋ N 한 50만 됐어도 걍 rne한거 돌렸을 듯 ㅋㅋ 

그래도 공부한 분야라 변형 TSP에서 N이 10만이다? 무조건 그리디라고 생각했음. 

걍 max(ci, aj-ai)니까 ci는 다 더하고 그 차액? 을 더하는 걸 생각해봤을 때, 제일 큰 새끼에서 밑으로 쭉 꼬라박는건 차액이 무조건 0임

그래서 W 형식으로 그려진다.. 뭐 이런걸 생각하면서 시작점이 최저점이면 존나 쉬운데.. 이지랄하고 있었는데

씨발 생각해보니까 TSP는 시작점이 상관 없다는게 지금 떠오름. TSP로 3년 연구한 새끼 맞노

그래서 일단 정렬하고 최저점에서 최고점까지 차액 최소로 쓰면서 등반하는 걸 짰음. ai + ci 까지는 무료로 등반할 수 있으니까 정렬해서 등반하는 그거 ㅇㅇ

구현 실수 간단한거 한 거 때문에 제출 2회랑 시간 날림

-2 1:30:41 AC

D. Flip the Cards

N개의 카드의 양면에 1~2N까지 써져있을때, 앞면은 오름차순 뒷면은 내림차순이도록 하고 싶을때, 주어진 상황에서 최소로 카드를 뒤집어서 해봐라

이때 딱 40분 정도 남아있었는데.. 뭔가 풀 수 있다는 자신감이 들어서 해봤음

대회때 생각했던건 우선 1. 1 이새끼는 맨 앞에 오거나 맨 뒤에 오거나 둘 중 하나임. 근데 맨 앞에 오거나 맨 뒤에 오거나 뒤집으면 그게 그거더라고

그래서 우선 1, x 를 맨 앞에 박고 시작함. 근데 생각해보니까 저 x가 N보다 작으면 내림차순이 성립 자체를 안 함.  

그걸 생각하다가 뭐 2-sat 같은 것도 떠오르고 했지만 개소리였고 그냥 N보다 작거나 같은거 2개가 같은 카드면 안 된다.. 라는 그리디 생각했음.

걍 거의 자명한데 괜히 증명한답시고 증명하다가 시간 날림;; 

그래서 그냥 그걸로 컷하고, 1 x 박으면 x 보다 큰 x+1 ... 2N 은 내림차순엔 절대 못 낌. 그래서 그것들은 뒤에 박고.. 거기서 3이 나왔으면 3은 또 내림차순에 절대 못 끼니까 앞에 박고.. 이걸 떠올렸는데 별로 같아서 보류하다가 걍 이거라도 짜보기로 함. 

근데 짜는게 생각보다 까다롭더라. 결국 못 짰음. 뭔가 짰으면 됐을까? 싶기도 한데 안 됐을거 같음. 가능한 거 아무거나 출력해라 면 몰라도

일어나서 답지 보니까 핵심은 1 .. N 을 어디에 박느냐 더라. 결국엔 1..N은 1...x (오름차순으로 쓰일 것) 이랑 y...z (내림차순으로 쓰일 것) 2개로 나눠져서 연속되서 붙어있게 됨. 

1 3 4

 5 2

이런식으로.. 그러면 결국 중요한건 1..N 밑에 달린 새끼들이 2개의 내림차순 수열로 이루어져야한다는 거

그걸로 가능 / 불가능 여부는 판단할 수 있음. 최소값은? 

걍 일단은 저게 최솟값인데, 일부를 뒤집을 수 있음. 

예를 들면 

1 2 4  ..... x x

x x x  ..... 3 5 가 있을 때 저 5개를 싹 뒤집어서 재배열해도 가능한 경우가 있음. 

3 5 ..... x x x 

x x ..... 4 2 1  이런식으로

언제 가능하냐 하면 지금까지 나온 모든 x의 최솟값이 저기 남은 모든 x의 최댓값보다 크면 됨. 그러면 내림차순도 유지되고, 오름차순도 유지되는 느낌

그래서 이게 가능할때는 ans 랑 N-ans 랑 작은거 가져가고 이걸 반복하면 최솟값이 나온다.. 뭐 이런 뜻

생각의 발상은 결국에는 1, N을 어디에 꽂지? 부터 시작하는 듯. 친창에 저거 푼 사람 한 명은 세그로 처리한거 같고 한 명은 비슷하게 짠 것 같더라. 

E도 nHr 쓰면서 단순 수학 계산하던데 얘도 도전해볼걸 그랫음 아쉽다

전체 후기 

제출횟수가 너무 아쉽다. 그것만 아니었어도 2300급 퍼포먼스였는데

뭐 그래도 레이팅 오른걸 긍정적으로 생각하는게 좋을 듯. D도 어느정도 감 잡았었고

요즘엔 생각은 나름 빨리 하는데 엄청 쉬운걸 좀 고민하는 느낌이 있다. 좀 더 문제를 많이 풀어봐야 할 듯

이제 학기도 끝나감. icpc 까지 6개월정도밖에 안 남았다. 

보니까 시발 돈도 내야되던데 icpc 까지 레드는 죽어도 못 찍을 것 같음. 찐렌지까지만 찍는걸 목표로 하자 ㅇㅇ

icpc까지 D1~D2에 찐렌지 목표로 하자 그러면 레드 언젠간 달 듯

솔직히 휴학까지하면서 ps했는데 레드 한 번이라도 못 달면 쪽팔리잖아

Rating Change : 1925 -> 2002 ( +77 )