79brue의 PS 블로그

이번 문제들은 Round 1보다 까다로웠던 것 같다. A1, A2, C를 풀어 85등으로 Round 3에 진출하였다. B는 답안을 제출했으나 끝나고 틀린 것으로 밝혀졌다. A1. Cottontail Climb (Part 1)문제의 조건을 만족하는 수의 개수가 매우 적으므로 (45개로 기억하지만 정확하지 않다), 모두 만들어둔 뒤 나이브하게 계산하면 문제를 해결할 수 있다.#include using namespace std;typedef long long ll;int t;ll a, b;ll m;vector vec;void init();int main(){ init(); scanf("%d", &t); for(int tc=1; tc=s; i--) v = v * 10 + i; ..

그동안 해커컵을 잘 못하다가 미국에 오니 시간대가 맞아서 편하게 할 수 있게 되었다. 앞 4문제를 풀어 69등으로 Round 2에 진출하였다.A. Subsonic Subway이 문제는 $N$가지 조건이 있고, 그 중 $i$번째 조건은 $i$번 위치에 도달하는 시간이 $A_i$ 이상 $B_i$ 이하라고 해석할 수 있다. 여기에서 속도에 대한 범위를 얻을 수 있다. 속도는 $\frac{i}{B_i}$ 이상 $\frac{i}{A_i}$ 이하가 된다. 이제 이 $N$개의 구간들의 교집합을 모두 구한 뒤, 해당 교집합이 공집합인지, 공집합이 아니라면 왼쪽 끝점 (가능한 최저 속도)가 얼마인지를 구해 주면 된다. 실수형으로 관리를 해도 통과를 할 수 있을 것 같긴 한데, 나는 안전하게 분수 자료형을 만들어서 해결했..

A. Walk the Line최적의 전략은 다음과 같다.$S_i$가 가장 작은 사람 한 명을 고른다.왼쪽 구간에 사람이 두 명 이하가 될 때까지 다음을 반복한다.$S_i$가 가장 작은 사람, 그리고 왼쪽에 남아 있는 사람 중 아무나 함께 오른쪽으로 이동한다. 이때 $S_i$가 더 큰 사람이 wheelbarrow에 탑승한다.$S_i$가 가장 적은 사람이 wheelbarrow를 타고 돌아온다.남은 사람이 오른쪽으로 이동한다.이때 걸리는 시간은 $\min S_i \times \left( \max(n, 2) - 3 \right)$인데, 이보다 답이 더 작아질 수는 없다. $\times$ 오른쪽의 항은 최소 이동 횟수인데, 한 번의 이동이 $\min S_i$보다 짧을 수 없기 때문이다.#include using ..

문제를 풀면서 정리한 생각 노트이다.D서브태스크가 갑자기 많아졌다. 아무래도 ABC 풀고 D/E 긁기로 본선 컷을 자르겠다는 게 의도 같아 보인다. 한편으로는 제출 횟수가 10회 제한이 걸려 있는데 섭테를 6개 주는 것은 조금 잔인하다는 생각도 들었다.문제 이해 (+Subtask 4)초기에 $a$의 값이 모두 다르다고 가정하자. $a$는 여러 연산을 통해 그 값이 바뀐다. 이때 $b_i$를 (몇 회의 연산 이후) 현재 $a_i$가 초기의 $a_j$와 같은 $j$값으로 정의하자. 이때 어떤 연산을 시행한 이후 $b[l \dots r]$은 $l \le i \le r$인 기존의 $b[i]$ 값 중 하나로 전부 바뀌게 된다. 예를 들어,$a = [1, 4, 2, 3]$이었고, 초기에 정의상 $b=[1, 2, 3..

올해 KAIST에서 열린 런 봄 대회에 검수진으로 참여했다. 처음으로 온사이트 대회를 검수해 보아서 신기한 경험을 많이 해 본 것 같다. 풍선을 달아 주거나 온사이트 대회 안내 등의 경험을 처음으로 해 봐서 재미있었다. 문제 셋은 전체적으로 좋지만, (특히 어려운 문제의 경우) 구현량이 많아서 제한 시간 내에 풀기 힘든 셋이었다고 생각한다. G는 특히 기억에 남는 문제로 최근에 본 문제들 중에서도 매우 좋은 편에 속하는 것 같다.A. RUN 수뺄 수 있는 가장 큰 수를 그리디하게 빼면 된다. 증명이 생각보다 어려운데, 재미있으니 스스로 해 볼 가치가 있다고 생각한다.B. 문자열과 쿼리$f(i, j, k)$의 값을 더하는 것으로 생각하지 말고, 새로운 함수 $g(i, j)$를 정의하자. $f(i, j, k..

2월 3일에 열린 솔브드 아레나 파티 Div.1에 미러로 참가했다. 대회 장소가 집에서 멀기도 하고 아레나 #10~#16에 전혀 참가하지 않아서(Arena #16 운영 제외) 선정될 확률도 없었던 터라 본 대회에 참가 신청을 하진 않았다. 대회 결과 5솔브로 본 대회+미러 합산 8등을 했다. 막판에 H를 풀었다면 등수가 크게 올랐을 것 같아서 아쉽다. A. 정렬된 연속한 부분수열의 개수 (0:02) 문제의 조건을 만족하는 모든 $(i, j)$에 대해, $[i, j]$가 다음 조건을 만족하는 $[l, r]$ 중 정확히 하나의 부분구간임을 보일 수 있다. $A_l A_l$ $r=N$이거나 $A_r > A_{r+1}$ 다르게 말..

역사적인 solved.ac 아레나 첫 대회에서 모든 문제를 풀어 4등을 했다. 한동안 OI style의 문제들만 풀다 ICPC style의 문제들을 접하니 조금 난감했는데, 다행히도 운이 좋아 좋은 성적을 받았다. 대회가 성공적으로 마무리된 점은 한국 PS계에 상당히 고무적일 것으로 보인다. 아레나 시스템에 대한 다양한 생각을 해봤는데, 이런 이야기들은 후기 끝에 짧게 써 보겠다. A. 양말 짝 맞추기 (0:00:31) 다섯 개의 수 중 한 번 등장하는 수를 찾는 문제이다. 다양한 풀이 방법이 있지만, 다섯 개의 수를 XOR하는 것이 가장 코딩하기 빠르다. 더보기 #include using namespace std; typedef long long ll; int a, b, c, d, e; int main..

역시 지난번의 굿바이 한별 팀으로 참가해 종합 9등을 했다. 나는 정말 최악의 대회를 치른 것 같다는 느낌이었다. 다른 팀원들이 그나마 많이 풀어 줘서 이 정도라도 올라온 것 같았다. CD. Colored-Dealt (0:13:25) 나는 처음에 AB, CD, EF, GH, IJ를 맡기로 했는데, 일단 CD를 읽자마자 쉽다는 확신이 들어서 바로 잡았다. 우선 전부 다 빨간색으로 배정하고, 왼쪽부터 한 개씩 푸른 색으로 바꿔나가는 식으로 최대 가중치 구간을 한 칸씩 이동시킬 수 있다. 이때 인접한 두 쿼리의 차이를 이용해 $N-1$개의 꽃 색을 알 수 있고, 마지막의 경우 첫 번재 쿼리 결과를 이용해 알아낼 수 있다. #include #include "colored_dealt.h" #include usin..