전체 글 썸네일형 리스트형 제3회 청소년 IT경시대회 고등부 (알고리즘 부문) 풀이 대회는 아마 작년(2024) 9월?왜 지금 쓰냐면 까먹고 있었는데 어제 4회 KITPA가 있었다. 이번엔 게임 이벤트랑 겹치고 3회 때 대상을 땄기 때문에 신청 안했지만..암튼 까먹고 있다가 오늘 보니까 KITPA 2회 조회수가 올라가있어서 기억났다. 이 글도 좀 일찍 쓸걸 그랬다.5회 때는 그 전에 4회 풀이를 올릴 수 있게 해야겠다.근데 솔직히 너무 오래되서 기억이 잘 안난다. 일단 기억나는 대로 서술난이도는 2회보다 쉽다. 1번 - 재미있는 파이프 퍼즐 (링크) solved.ac 티어더보기Gold V (20250316 기준) 풀이더보기(1,2)에서 시작하는 경우와 (2,1)에서 시작하는 경우를 따지자. 'I'는 무조건 전진해야하고 'L'은 무조건 아래로 가야 하며 아래도 'L'이어야 한다. 항상 전.. 더보기 abc392 Ac를 max로 두고 확인 B정렬하고 하나하나 확인 Cans[q[i]] = q[p[i]]; D각각마다 cnt 배열 저장하고 하나 고정하고 다른거 보면서 자기 내부만 훑으면 되는데 처음에 map으로 cnt 관리해서 TLE+1 E떨어진 컴포넌트끼리 합쳐주면 되는데 반드시 남는 간선이 있는 컴포넌트가 존재하므로 그 간선이랑 연결 안된 다른 정점 아무거나 이어주면 된다. 이 후보를 잘 관리하면 되는데 small to large 쓰면 끝. 구현 미스로 WA+1 F거꾸로 보면서 위치를 맞춰나간다고 생각하면 세그 + 이분탐색 국밥. O(Nlog^2N)인데 펜윅쓰면 개빠름 여기까지 패널티 2개 먹긴 했지만 30분 안에 풀어서 기분이 좋았다. 그런데 슼보에 G를 너무 많이 풀었길래 봤다. G누가봐도 FFT 기본문제.. 더보기 2월 PS (1) 푼 것들 중 의미있는(?) 것을 정리했다.1. 아니메컵 1쿨딱히 시간을 재고 풀진 않았다. M은 이상한 풀이밖에 생각이 안나서 에디토리얼을 보고 풀었다. A (BOJ 27310. :chino_shock:)23년에 푼 문제다.길이, 콜론 개수, 언더바 개수를 세고 그대로 계산하면 된다. B (BOJ 27311. 치노의 라떼 아트 (Easy))일단 #의 min x, max x, min y, max y를 가지고 정사각형을 이루는지 확인하자. 그리고 그 내부만 본다고 하자. 배열을 90도씩 돌려가면서 확인하면 일반성을 잃지 않고 '.'이 왼쪽 위에 있다고 가정할 수 있다. 이를 기준으로 (1) '.'이 정사각형을 이루는지, (2) 왼쪽 위에 '.'이 있는지를 확인하면 된다. C (BOJ 27312. 운영진에게 .. 더보기 1월 PS (2) (1)에서 많이 써서 쓸게 별로 없다. BOJ Random Defense 돌린거 풀이 정리할 생각도 해봤는데 양이 너무 많다.. 그것과는 별개로 저거 너무 좋아요 꼭 써봐야함 1. 2024 SW-IT Contest 개인 Virtual사정이 있어서 원래 3시간 대회인데 2시간만 잡고 풀었다. A (BOJ 32399. 햄버거 정렬) 0:01가능한 경우의 수가 3! = 6이므로 6가지 경우에 대해서 머리로 풀면 된다. B (BOJ 32400. 다트판) 0:04본문에 주어진대로 구현하면 된다. 실수(real number)는 안 쓸수록 좋으니 60을 곱한 후 비교 C (BOJ 32401. ANA는 회문이야) 0:07문제를 잘못 읽고 부분 문자열이 아니라 부분 수열인 줄 알았다.부분 문자열인 원본 문제의 경우, N.. 더보기 2025 국제정보올림피아드 대표학생 선발고사 1차 후기 1/27 - BOJ에 문제가 올라와서 올린다. 사실 글을 쓰는 지금 기준 safezone은 안올라왔는데 보니까 BIKO엔 있다.글은 22일 쯤에 썼고 마지막만 약간 수정 기록용으로 좀 자세하게 서술한다.내 점수는 12(grid) + 100(particles) + 45.4(roadwork) + 14(safezone) = 171.4로 11등이다.이제 시간대별로 한 일을 서술하겠다. 정확하진 않아서 기억나는 대로 서술한다. 제출 시각은 선발고사 사이트에 적혀있는 대로 썼다. 0:00~0:30문제를 쭉 읽었다. grid는 문제 이해만 10분 걸리는 더러워 보이는 문제였다. particles는 정확힌 모르겠지만 서브태스크를 봐서는 긁는 문제가 아닐까 하고 넘어갔다. roadwork는 일단 내가 싫어하는 경우의 수.. 더보기 Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2) 시스텟 전이다.사실 오늘은 몸 상태가 하면 안되는 상태였는데 억지로 했더니 대회 중간에 건강 이슈가 있었다. 설명하기 좀 그러니까 대충 무언가가 역류했다까지만 설명하겠다.그래서 내 뇌까지 같이 붕괴되었다.. 아니 E1에서 왜 HLD를 쓸 생각을 했을까?마지막에 3분 남기고 E1을 맞았는데 이게 HLD 쓰는 구데기 풀이가 오류가 있었기 때문이다. 그냥 오일러 투어만 때리면 되는데 이걸 어떻게 1시간동안 못찾냐.. 그래도 마지막에 찾기라도 해서 다행이다. A1 개수 세기 B걍 자기에서 시작하는 형태만 확인 C이게 차이 수열로 만들고 나서 -1 곱하고 뒤집으면 전 상태에서 뒤집어서 차이 만들었을 때의 값이 나온다. 그래서 그냥 reverse 안하고 차이배열 만들면서 abs(sum) 최댓값 보면 된다. DE1 .. 더보기 Codeforces Round 985 F. Palindrome Everywhere 문제길이 n의 사이클이 있다. 간선은 i->(i+1) mod n으로 가며 R 또는 B로 색깔이 있다. 이때, 모든 쌍 (i,j) (i 풀이팰린드롬으로 간선을 지나가야 한다는 것이 좀 복잡해 보인다. 생각을 편하게 하기 위해서 i,j에 위치하는 두 사람이 있고 이 두 사람이 만나야 하는데, 두 명이 이동하기 위해서는 항상 같은 색깔의 간선만 타고 가야하는 문제라고 문제 서술을 약간 바꿔보자. 문제를 이렇게 바꾸면 꽤 다루기 편한 형태가 된다. 이제 관찰을 하자.관찰 1) R로 색깔이 같은 인접한 간선과 B로 색깔이 같은 인접한 간선이 같이 존재할 경우, 답은 NO이다. 왜냐하면 그 두 위치에 두 사람을 배치하면 움직일 수 없다.이 관찰 하나로 간선의 형태를 매우 단순화시킬 수 있다. 어떤 한 색깔의 간선은.. 더보기 1월 PS (1) 1/7 ~ 1/17동안 IOI 겨울학교가 있었다. 이번 겨울학교는 여름학교 때보다 뭔가 동기(?) 같은게 더 강해져서 더 열심히 했다. 결과적으로 이번 겨울학교에서 실력도 꽤 늘었고, 얻어간 것도 많았다고 생각한다. 그래서 PS에 대한 동기가 어느 때보다 강해졌다. 올해는 이걸 시작으로 진짜 열심히 해야겠다고 생각이 들었다. 아래는 1월 사이에 한 것들을 대충 정리하였다. 1차 선발고사는 따로 글을 쓸 것 같긴 한데.. 2차 치고 나서 묶어서 쓸수도 있고 모르겠다. 1. IOI 겨울학교 계속반겨울학교 계속반에서는 SCPC, ICPC, OI 기출을 랜덤하게? 줬다. IOI'17의 Nowruz, Ancient Books를 제외하고는 모두 업솔빙했으며, Ancient Books는 아마 나중에 업솔빙하지 않을까.. 더보기 이전 1 2 3 4 ··· 13 다음
