The Way

D번치고 아주 까다로운 문제였다. 열심히 고민하다 결국 못 풀었다. 편의를 위해 다음 조건을 만족하는 두 binary string을 s와 t를 $s \approx t$로 표기하자.1) s와 t의 길이는 서로 같다. 2) s와 t의 같은 위치에 있는 substring은 maximum non-decreasing subsequence의 길이가 같아야 한다. s가 주어질 때, $s \approx t$이며 0의 개수가 최대한 많은 t를 만드는 문제이다. 풀이는 굉장히 쉬운데, s에 "10"이 있으면 그 위치는 t에도 동일하게 "10"으로 놔두고, s에서 "10"을 제거한 뒤 같은 과정을 반복하면 된다. 더 이상 s에 "10"이 없다면 나머지는 다 0으로 채워도 무방하다. 왜 이런 풀이가 성립하는지 증명해보자. 1..

그간 2번의 팀연습을 더 거쳤으나... absolving을 제대로 하지 못했다. 1주일 12문제도 생각보다 많이 빡세다는 것을 느끼게 되었다. 아무튼 그동안 많은 일이 있었는데, 7월 27일의 예선을 가볍게 진출한 후, 이제 본선을 앞두고 마지막 팀연습을 하게 되었다. 약간 늦게 만나고 노트북 세팅도 상당히 오래 걸린지라, 5시간짜리 문제셋을 골라 2시간 정도 하다가 그냥 가기로 했다.문제셋은 뭐를 할까 고민하다가, 우리 실력이 어느 정도 되는지도 볼 겸 2018 ACM-ICPC Daejeon Regional을 하기로 했다.codeforces에 GYM 탭에서 virtual round를 진행할 수 있었는데, 놀랍게도 그 때 대회를 진행했던 사람들의 데이터도 그대로 들어있다. 작년 VISSLLE 팀도 잘 보..

저번 주에 이어서 또 도전... 저번보다 문제가 약간 별로인 것 같다.저번보다 못한 6문제를 풀었다. 하나는 풀이를 알았는데 시간이 없었고, 하나는 내가 끝끝내 예외를 못찾아서 틀렸으니 조금 더 실력이 있었으면 8문제는 거뜬했을 듯. 내가 1문제를 푼거로 봐서 내가 못한 것 같다.. 근데 나한테 배정된 A~D가 솔직히 좀 어려워서 털릴 만 했다... E번(637C) - Promocodes with MistakesN군이 후다닥 풀었다.6자리의 n개의 이벤트 코드가 있는데, 코드를 칠 때 k자리를 잘못 칠 수 있다. 이 때 모든 코드를 구별하기 위한 최대 k를 구하는 문제.엄청 쉬운데, 두 코드가 p자리가 서로 다르면, (p - 1) / 2개 이하를 잘못 쳐야 둘을 구별할 수 있다. 모든 쌍에 대해 반복하면..

방학 중에 UCPC를 서울대 D군, N군과 같이 나가게 되면서 한 주에 한번씩 모여서 팀연습을 하기로 했다.어제는 첫 번째 팀연습을 했다. 연습은 Road To Grandmaster라는, hyunuk님이 잘 만들어주신 4시간, 12문제짜리 문제셋을 가지고 진행하기로 했다.문제 난이도는 다 1700~2400점 사이의 문제들이라 다 풀 만 한 문제들이다. 엄청난 꿀문제도 없고, 그렇다고 아예 못 풀 문제는 없는 수준의 문제들이다. 처음이라 약간 방황해서 예상보다 약간 성적이 좋지 않지만, 그래도 기존까지는 팀대회에서 뭔가 나 혼자만 푸는 기분이었는데 이번에는 다 같이 푸는 것 같아서 좋았다. 무엇보다 우리 팀에는 빛나는 오렌지가 있기 때문에.. N군 A~D, D군 E~H, 나 I~L을 읽기로 하고 virtu..

문제 코드 * div1과 div2는 문제를 공유하므로 혹시 없는 문제는 같은 Round의 다른 division을 찾아보시기 바랍니다 총평: 맞왜틀의 향연... 이건 순전히 실력부족이다. A. Polycarp's Pockets최대 횟수로 출현하는 숫자를 찾는 문제. B. Binary String Constructing0 a개, 1 b개로 구성된 string을 만들어야되는데, 숫자가 바뀌는 경우가 정확히 x번인 것.많은 답이 존재할 수 있지만, 이런 문제의 경우 극단적인 케이스를 만드는 것이 경험상 편합니다. 총 x번 바뀔 때, 마지막 바뀌는 것만 빼고 숫자 하나씩 쓰면서 바꿔주다가,맨 마지막 바뀔 때는 남은 숫자를 몽땅 다 사용하는 것도 간단한 답이 될 수 있습니다. 예를 들어서 a = 8, b = 7, ..

문제 코드 * div1과 div2는 문제를 공유하므로 혹시 없는 문제는 같은 Round의 다른 division을 찾아보시기 바랍니다 A. Infinity Gauntlet생략. 저는 map 만들어놓고 하나씩 지웠습니다. B. High School: Become Human예상 외의 킬러 문제였습니다. 저를 포함한 많은 분들이 실수 다루는 데에 익숙하지 않다는 것을 잘 알 수 있었습니다. $x^y$와 $y^x$을 직접 계산하려는 분들은 없을것이고, 보통 생각하는게 "양변에 로그를 씌우자!" 일 것입니다. double x, y; cin >> x >> y; double t1 = y * log(x); double t2 = x * log(y); if (t1 > t2) cout > y; double t1 = y * l..