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..

예전에 참가했던 대회 업솔빙은 언젠가는 해야 하는 일이다. 그리고 2023 IOI 선발고사가 가까워진 지금 해보려고 한다. 이미 모든 문제 풀이를 어렴풋이 들은 적이 있지만 기억이 가물가물하기도 하고, 적어도 IOI APIO 기출을 대학에 가기 전에 최대한 풀어놓으려고 한다. 그 뒤로는 OI 문제들보다는 ICPC 문제들에 집중해야 하기 때문에... 간단한 후기 대회 때 사용했던 전략을 간단히 풀어 보자면, IOI 2022 당시 컨디션이 별로 좋지 않았어서 (대회 직후 코로나 확진), 큰 욕심을 내지 않고 섭테주의 전략으로 모든 문제를 풀었다. 사실 컨디션이 좋았어도 섭테 전략으로 가긴 했겠지만, 그랬다면 코딩 속도가 좀 더 빨랐을 것이다. 나는 비교적 구현 속도가 남들보다 빠른 편이라고 생각하기에 평소에..

이번 IOI에 한국 국가대표로 선발이 되어서, 본 대회를 치르게 되었습니다. 코로나19가 계속되는 바람에 올해도 싱가포르 현지에서 대회를 치르지 못하고 우리나라에서 온라인으로 치르게 된 점이 아쉽습니다. 작년에 이어 2년째 IOI에 참가하게 되었는데, 작년과는 느낌이 확연히 다른 대회였습니다. 작년과 다르게 올해는 주변 누구도 성적에 대한 기대를 가지지 않아서 편한 마음으로 시험을 볼 수 있었습니다. 아마 이러한 점도 성적에 영향을 주지 않았나 싶습니다. Day 0 (Practice Session) 연습 세션 문제는 작년과 거의 똑같았습니다. 차이점이 있다면, 무슨 이상한 전처리를 해야 맞는 문제 하나가 간단한 bfs 문제로 바뀌었습니다. 작년에 끝까지 풀지 못했던 문제(Jelly Flavours)를 이..

APIO 2021은 작년 APIO보다 많이 어려운 셋이었고, 점수도 받기 힘들었습니다. cms 화면 캡처는 깜박하고 못 했지만, 47+100+36=183점을 획득했습니다. 전체 성적은 29등(은메달) / 한국 1등입니다. 인증샷은 APIO 결과 화면으로 대체합니다. 문제의 난이도가 매우 높았고 구현도 힘들었으며, 대회 중에 채점 큐가 터져서 정말 고난의 연속이었습니다. 물론 그 덕에 시간을 1시간 더 받긴 했고, 결과적으로는 이득이었던 것 같습니다. 아래는 문제별로 제가 생각한 최대 풀이입니다. A. 육각형 영역 최종 점수: 47점 총평: 100점 풀이는 바로 나왔지만, 구현이 매우 매우 매우 매우 매우 더러워서 시간 내에 도저히 풀 수 없는 문제였습니다. 구현이 간단한 풀이가 있다면 매우 궁금합니다. ..

PMCC는 수학동아에서 운영하는 수학 사이트인 폴리매스에서 개최하는 코딩 대회로, 2020년 8월에 1회 대회가 열렸고, 2021년 2월에 2회 대회가 열렸습니다. 2회 대회는 1회 대회 때보다 더욱 다양해진 실력의 코더들을 위해 Division 1과 2로 나눠서 운영되었습니다. 준비 과정에서 CMS 서버를 세팅해 주신 whqkrtk04님, 문제 출제를 도와 주신 azberjibiou, blackking26, gunwookim님, 그리고 촉박한 검수 기한에도 불구하고 검수에 힘써 주신 16silver, ainta, gs18115, messi, TAMREF님께 감사의 말씀을 전합니다. 아래는 풀이 ppt 파일입니다. 작성을 도와주신 azberjibiou님과 blackking26님께 다시 감사의 말씀을 전합..