본문 바로가기

일기

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는 일단 내가 싫어하는 경우의 수.. 더보기
1월 PS (1) 1/7 ~ 1/17동안 IOI 겨울학교가 있었다. 이번 겨울학교는 여름학교 때보다 뭔가 동기(?) 같은게 더 강해져서 더 열심히 했다. 결과적으로 이번 겨울학교에서 실력도 꽤 늘었고, 얻어간 것도 많았다고 생각한다. 그래서 PS에 대한 동기가 어느 때보다 강해졌다. 올해는 이걸 시작으로 진짜 열심히 해야겠다고 생각이 들었다. 아래는 1월 사이에 한 것들을 대충 정리하였다. 1차 선발고사는 따로 글을 쓸 것 같긴 한데.. 2차 치고 나서 묶어서 쓸수도 있고 모르겠다. 1. IOI 겨울학교 계속반겨울학교 계속반에서는 SCPC, ICPC, OI 기출을 랜덤하게? 줬다. IOI'17의 Nowruz, Ancient Books를 제외하고는 모두 업솔빙했으며, Ancient Books는 아마 나중에 업솔빙하지 않을까.. 더보기
solved.ac Ruby V 뜬금없지만 solved.ac 루비를 찍었다.아마 가장 큰 영향은 겨울학교가 아닐까 싶다.. 여름학교 때랑 다르게 업솔빙을 열심히 했더니 루비 몇 개와 다상위 몇 개를 풀어서 겨울학교 동안 50점이 넘게 올랐다.사실 solved.ac 레이팅이 그렇게 중요한 건 아니지만 루비는 다이아때랑 다르게 성취감이 좀 있는 것 같다.루비 5의 영광을 찾이한 문제는 IOI'23 - Longest Trip이다. 여름학교에서 IOI 2023 Day 1을 풀었을 때 얻은 점수에 되게 충격을 먹었던 기억이 있다. 오늘 각 잡고 이 문제를 업솔빙했는데 70점까지는 그래도 어떻게 되는데 85점부터는 생각 자체를 틀어야 해서 좀 어려웠다. D = 1이라는 조건이 되게 재밌는 것 같다. 쿼리는 최악의 경우 총 3/2N + 2logN .. 더보기
재미있는 문제 Online Judge에 있는지는 모르겠고 겨울학교 모의고사로 나온 문제이다. 인터랙티브 비슷한데 좀 다르다. N = 2025 크기의 배열이 있고 그 중 하나만 1이고 나머지는 0이다. K개의 쿼리를 동시에 보낼 수 있는데 각 쿼리는 확인할 배열의 인덱스를 정해서 그 인덱스 중에 1이 있었으면 1을, 아니면 0을 반환한다. 이때 최대 1개의 쿼리는 답을 거꾸로 할 수도 있다. (즉, 1인데 0이라 할 수도 있고 그 반대일 수도 있다) K  시험 당시에는 문제를 잘못 읽어서(...) 버렸는데, 두번째로 쉬운 문제였다. 끝나고 다시 풀어봤는데 꽤 재밌어서 풀이를 남겨두기 위해 풀이를 작성하겠다. #1. K = 33 (25점)이건 쉽다. (근데 이것도 못긁었음..)일단 답을 거꾸로 하는 이상한 녀석이 없다고 .. 더보기
11월 PS (2) 11월 2주차에 푼 문제들 풀이이다. Zero One Algorithm Contest 2024A (BOJ 32642)더보기티어는 Bronze IV.시키는대로 하면 된다.B (BOJ 32643)더보기티어는 Silver I.잘 생각해보면 조건을 만족하는 수는 소수와 1이므로 구간 내의 소수 개수를 빠르게 셀 수 있으면 되고, sieve + prefix sum으로 해결 가능하다.C (BOJ 32645)더보기티어는 Gold III.간단한 게임 이론 dp 문제이다. 자식들 중 후공이 반드시 패배하는 상태가 있을 경우 선공이 승리하고, 그렇지 않으면 후공이 승리한다.D (BOJ 32644)더보기티어는 Gold I.각 회원의 가장 왼쪽 응모권의 위치를 관리한다고 생각하면, 어떤 회원이 당첨되었을 때 그 뒤에 있는 응.. 더보기
11월 PS (1) 10월 말~11월 1주차에 푼 문제 풀이이다. BOJ 32526 문자열 구성하기풀이더보기티어는 Platinum III.f(S)는 S를 두 부분으로 나눴을 때 각각이 모두 팰린드롬인 경우가 몇 번인지를 의미한다.S = A(prefix) + X이고 이게 f(S)의 조건을 만족하는 최소 i(즉 A 길이가 최소)인 경우라고 하자. 정의상 A와 X는 팰린드롬이고 A는 최소 길이이므로 A의 부분 prefix 혹은 suffix가 팰린드롬인 경우는 없다. 이제 S = C + Y이고 이게 A 다음으로 prefix 길이가 최소인 분할이라고 하자. C = A + B + A꼴일 수밖에 없다. 그런데 S = A + X = C + Y = A + B + A + Y이므로 X = B + A + Y이다. X는 팰린드롬이므로 X = B.. 더보기

티스토리툴바