[2017-09-30] Tenka1 Programmer Contest

링크 : http://tenka1-2017.contest.atcoder.jp/

C,D 두 문제 풀고 285등. 사실 E,F번 둘 다 내가 풀기엔 좀 어려운 문제들이라 어차피 두 문제밖에 못 풀었을 것 같긴 한데, D번 문제가 그렇게 까다로운 문제가 아님에도 불구하고 코딩을 제대로 못해서 각종 예외케이스들 때문에 7번이나 오답을 낸 끝에 겨우겨우 통과해서 굉장히 짜증이 났었다. 좀 예외를 잘 생각하고 빈틈없이 코딩하는 습관을 들여야하는데 아직도 그게 잘 안 된다. 

 레이팅 반영되면 점수 좀 깎일 것 같아서 슬펐는데 이상하게 아직도 레이팅 반영이 안 됨. 언레이티드인가?? 

C. 4/N

 4/N = 1/h+1/n+1/w가 되는 h,n,w를 찾는 문제다. 그렇게 어려운 문제가 아닌데 이상하게 괜히 어렵게 생각했다가 시간을 좀 많이 낭비했다.

 문제 제약에서 h,n,w가 모두 3500이하인 해가 있다라고 보장을 해주고 있기 때문에, h랑 n이 3500이하인 범위에서 두 값을 정해주면 저 식을 만족하는 w가 있는지는 간단한 수식을 통해서 바로 계산할 수 있기 때문에, 3500 범위의 이중 반복문 하나로 쉽게 해결할 수 있고 당연히 시간 안에 답이 잘 나온다. 

D. IntegerotS

 상품들이 n개 있는데, 각 상품들은 Ai라는 가치를 갖고 있고 Bi라는 유틸리티를 갖고 있다. 타카하시가 상품들 몇 개를 살 건데 제약이 하나 있어서, 자신이 살 상품들의 유틸리티를 모두 or 연산한 결과가 어떤 값 K를 넘어가면 안 된다. 이 때 살 수 있는 최대 가치 합(구매한 상품들의 Ai 합)을 구하는 것이 문제.

 문제를 읽자마자 풀이는 바로 떠올랐는데 구현하면서 삽질을 진짜 너무 많이 했다. 내가 생각했던 풀이는, 전체 유틸리티의 or값이 k이하가 되는 경우들을 일일히 테스트해주는 것이었다. 어떤 값이 k이하가 되는 케이스는 여러가지가 있는데, 그걸 간단하게 생각해보면, 원래 값 k의 비트열에서 1이었던 수치가 0으로 바뀌면 그것보다 더 뒤쪽에 있는 비트는 값이 무엇이 되든(다 1이라도) 무조건 k보다 작다. 따라서 내가 구매한 상품들의 유틸리티가 원래 k 비트열에서 어떤 걸 0으로 만들고 그 이후를 다 1이라고 생각했을 때 값에 포함되면 무조건 구매, 아니면 안 구매하는 식으로 구해주면 특정 비트열이 0일 때 최대 가치 합을 구할 수 있고, 0으로 만들어줄 수 있는 비트열의 위치는 총 30개 가량(K범위가 2^30)이므로 O(NlogK) 시간 내에 답을 구할 수 있다.

 풀이는 그리 어려울 게 없고 구현도 사실 까다로운 문제라고 보기는 힘든데 간단한 몇 가지 예외를 자꾸 생각 못해서 계속 틀렸다. 다음에는 같은 실수 안 하도록 조심해야지..