79brue의 PS 블로그

옛날 함수컵에 나온 인터랙티브 문제로, 굉장히 쉬운 문제이지만 흥미로워서 글을 써 본다.링크문제$N$개의 스위치가 일렬로 있고, 스위치 사이에 각각 하나씩 총 $N-1$개의 전구가 있다. $N$은 짝수다.처음에는 모든 전구가 꺼져 있다. A와 B 두 사람이 게임을 한다. 총 $N/2$턴으로 진행되며, 각 턴은 다음과 같이 진행된다.먼저 A가 아직까지 안 눌러진 스위치 하나를 누른다.다음으로 B가 아직까지 안 눌러진 스위치 하나를 누른다.이때 두 스위치 사이의 전구들은 켜짐/꺼짐 순서가 반전된다.B는 마지막에 켜진 전구가 꺼진 전구보다 더 많아야 이긴다. B의 필승 전략을 찾아라.풀이풀이는 굉장히 전형적인 유형이지만, 처음 보는 경우 굉장히 신기한 유형이다.스위치들을 인접한 것끼리 두 개씩 묶자. 이러면 ..

문제 링크 엄청 유명한 수학 루비 문제인데, 난 수학에 자신이 없어서 딱히 건드려 본 적이 없었다. 오늘따라 루비를 풀어보고 싶어서 잡기 시작했다. 엄밀한 증명이나 풀이 위주로 적는다기보다는 생각의 흐름 위주로 기록을 남겨 보려고 한다.예제 분석일단 문제의 풀이에 대한 감이 전혀 잡히지 않아서 예제를 가지고 놀아 봤다. 간단한 랜덤화 시뮬레이션 코드를 짜서 시행의 선택에 따라 어떤 결과가 나오는지를 알아보았다. 다양한 방법으로 시행을 해 본 결과, 다음과 같은 두 가지 추측을 하게 되었다.여러 가능한 시행 중 어떤 것을 선택하더라도, 모든 수를 $0$ 이상으로 만드는 데 필요한 시행 횟수가 같다.어떤 방법으로 시행을 완성하더라도 최종 상태가 동일하다.이 관찰을 통해 어떤 수열 $A$에 대해 이 문제의 답..

문제 링크15685B+alpha를 짜고 풀었다. 지금까지 해본 다양한 문제풀이들 중에서도 기억에 남을 정도로 힘들었던 것 같다. 자력솔한 문제 중에서는 최소 3위 안에 드는 것 같다. 해싱을 쓰는 쉬운 풀이가 있다고 하니 구현할 생각이 있다면 그쪽 풀이를 써 보도록 하자. 문제를 요약하면 다음과 같다.그래프 $G$에서 간선 $k$개를 지워서 이분 그래프로 만들 수 있는 $k$의 최솟값 $k_{min}$이 $2$ 이하인지 판정한다.$k_{min}$이 $2$ 이하라면, 그래프 $G$에서 $k_{min}$개의 간선을 지워 이분 그래프로 만드는 경우의 수를 출력한다.접근 방식이 문제에서는 $k_{min}$이 $0$, $1$, $2$인지 각각에 대해서만 판정하면 된다. 따라서 $k_{min}$의 값이 이들 중에 ..

제목만 들어도 모두가 아는 이 전설의 문제는 ONTAK 2010에 출제된 문제다. ONTAK은 폴란드 국가대표 선발 캠프라고 알고 있는데, 자세한 내용은 찾아도 잘 안 나와서 딱히 깊이 알고 있지는 않다.문제는 단순하다. 10개의 파일이 있고, 정수 하나를 입력받아 $(0 \le N \le 10)$ 그저 대응되는 파일의 내용을 출력하기만 하면 된다. 단 코드의 길이는 10만 바이트를 넘을 수 없고, 출력 파일은 예제 파일 $(N = 0)$을 제외하고 모두 20만 바이트를 가뿐히 넘는다는 게 특징.gen0.out그냥 출력하면 된다.gen1.out파일이 너무 커서 웬만한 프로그램으로 열려고 해도 열기 힘들다. 경험상 Visual Studio Code가 이럴 때 정말 좋은 역할을 해 준다.파일을 열어 보면, ..

https://www.acmicpc.net/problem/18344$G=(V, E)$에서 정점 $1$부터 $N$으로 이동하는 최단거리를 찾아야 한다. 단, 이동 중 시작점과 끝점을 포함해 정확히 여덟 개의 서로 다른 정점을 방문해야 한다.서브태스크 1 (1점)방문하는 정점을 $[v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8]$이라고 하고, 이때 사용하는 7개의 간선 번호를 $[e_1, e_2, e_3, e_4, e_5, e_6, e_7]$이라 하자. (단, $v_1 = 1$, $v_8 = N$)$e_2$를 고정하면 $(v_2, v_3)$ 또는 $(v_3, v_2)$가 고정된다. 마찬가지로 $e_4$와 $e_6$을 고정하면 ${ v_4, v_5 }$와 ${ v_6, v_7 }$이 고..

https://www.acmicpc.net/problem/17697 17697번: Railway TripJOI Railways is a company operating one railway. In the railway of JOI Railways, there are N stations on a straight line numbered from 1 to N. For each i (1 ≤ i ≤ N − 1), the station i and the station i + 1 are connected by a railway track. JOI Railwwww.acmicpc.net$N$개의 역이 일렬로 있으며, $i$번 역의 등급은 $A_i$이다. 모든 $A_i$에 대해 $1 \le A_i \le K$가 성립한다..

https://www.acmicpc.net/problem/7469 7469번: K번째 수현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. 현정www.acmicpc.netStep 1 ($O(M \log^3 N)$)이 단계는 머지 소트 트리를 알고 있다면 누구나 풀 수 있습니다. 머지 소트 트리는 일반적인 세그먼트 트리와 비슷한데, $[l, r]$ 구간을 담당하는 노드에는 $[l, r]$ 구간에 있는 수들을 정렬해서 배열 형태로 저장해 둔 세그먼트 트리를 말합니다. 머지 소트 트리의 구축은 모든 노드에 대해 정렬을 독립적으로 하면 $O(N \log^2 N)$에 가능합니다. 정..