79brue의 PS 블로그

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

뭔가 백준 솔브 수가 높거나 주변 사람들이 많이 얘기를 하는데 나는 뭔지 잘 모르겠는 문제들이 많았고, 이런 문제들을 좀 모아서 풀어 보기로 했다. 첫 번째 문제는 유명한 세그비츠 문제인 수열과 쿼리 25로 정했다. 세그비츠 문제를 아예 안 풀어 본 건 아닌데, 이 문제는 안 풀어봤었고, 뭔가 나만 모르는 웰노운 같아서 풀어봤다. 링크접근이런 특이한 형태의 세그먼트 트리를 쓰는 문제는 일반적으로 적당한 퍼텐셜 함수를 만들어서 푸는 경우가 많다. 가장 대표적인 예시가 수열과 쿼리 26인데, 이 경우 min 연산이나 max 연산을 할 때 서로 다른 수의 개수가 줄어드는 경우가 많다는 사실을 이용해 퍼텐셜 함수를 정의한다. 이 문제도 비슷한 생각을 할 수 있다. 비트 연산의 성질상,and 1이나 or 0은 원..

JOISC 문제 몇 개를 땅따먹기에서 풀어 보았다. BOJ 24137. 塗り箸 (Chopsticks)옛날 NYPC의 어떤 output only와 상당히 비슷해 보이는 문제이다. 형태를 봤을 때 구간 DP로 진행하는 것이 가장 좋아 보인다. 어떤 구간 $[l, r]$에 대해 최소 비용으로 칠하는 방법을 구한다고 생각해 보자. 먼저 이 구간 전체에 색칠할 색 $c$를 정한다. 다음으로 이 위에 덮어쓸 구간을 정한다. 모든 $c$에 대한 최소 비용을 $[l, r]$에 대한 최소 비용으로 정한다. 이렇게 하면 $O(N^3)$ 풀이가 나온다. 상수가 $52/6$ 정도로 다소 커서 걱정되지만, 짜 보면 문제없이 통과된다.#include using namespace std;typedef long long ll;int..

백준 땅따먹기에서 열린 Hanbyeolforces Global Round 2에 참여해 보았다.링크BOJ 11712. JAG-channel IIBitmask DP를 할 것이다. 그런데 무슨 사람을 썼는지 말고 post가 어떤 순서로 있는지도 저장해야 하는 게 까다롭다.$1 \le N-K \le 3$이라는 특이한 조건 때문에 마지막 사람을 저장하면, 마지막 사람에 포함되지 않은 post의 개수가 최대 $3$개이므로 그 순서들만 따로 저장해도 충분함을 알 수 있다. 이렇게 하고 Bitmask DP를 돌리면 문제를 $O(2^N \times N^2 \times 3!)$ 정도의 시간에 풀 수 있다.#include using namespace std;typedef long long ll;struct State{ ..

BOJ 땅따먹기가 생겼다는 소식을 들어서, 테스트 삼아 몇 개 풀어 보았다. https://blobnom.xyz/room/90BOJ 1626. 두 번째로 작은 스패닝 트리먼저 최소 스패닝 트리를 하나 잡은 뒤, 각 간선에 대해 해당 간선을 자르고 넣을 수 있는 가장 작은 가중치의 간선을 구해 보는 식으로 풀면 될 것 같다. 하지만 단순히 이렇게 하면 같은 가중치의 간선을 고를 수도 있으므로, 최소 가중치를 두 개까지 저장해 주는 식으로 문제를 풀 수 있을 것이다. 처음에 Kruskal 알고리즘 등으로 MST를 찾아 준 후, 사용되지 않은 간선들을 양끝점 사이의 경로에 업데이트해 주고, 세그먼트 트리 등을 이용하는 방식으로 문제를 해결할 수 있다. 여러 가지 사소한 edge case들에 주의해야 할 것 같..

BOJ 13874. Internet Trouble문제수직선 상에 $N$개의 마을이 있고, $K$개의 마을에 인터넷을 설치할 것이다. 하나의 마을에 인터넷을 설치하는 데는 $B$의 비용이 든다.$i$번째 마을에는 $A_i$개의 집이 있으며, 각 집과 인터넷을 연결하는 케이블을 설치해야 한다. 이때 $i$번 마을의 집 하나와 $j$번 마을의 인터넷을 연결하는 비용은 $|i-j|\times C$이다.$1 \le K \le N$인 모든 $K$에 대해, $K$개의 마을에 인터넷을 설치할 때 드는 최소 비용을 구하시오.$1 \le N \le 6000$풀이일단 문제의 생김새를 보아 DP로 푸는 것 같다. 그러나 상태 전이를 어떻게 시켜야 할지가 잘 보이지 않는다. 모든 구간 $[l, r]$을 하나의 인터넷으로 덮는 ..

이번 문제들은 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; ..

랜덤한 ICPC 문제 몇 개를 뽑아 풀어보았다.BOJ 17551. Jumbled Journey문제를 solvable하게 만들기 위해 이상한 제한들이 덕지덕지 붙었는데,$i$에서 $j$로 가는 비용 $c$인 간선이 있다면, 이 간선을 통하지 않는 모든 경로의 길이가 $c$보다 크다.어떤 두 정점 $x$와 $y$를 연결하는 서로 다른 경로는 최대 $1000$개이다.따라서, 일단 $O(1000n^2)$ 짜리 (여기에 아마 로그가 붙을 수도 있는) 풀이를 생각하는 것이 가장 합리적인 것으로 보인다.일단 몇 가지 사실을 관찰하고 가면 편리하다.입력에 주어지는 행렬을 $a_{ij}$라고 하자. 또한 $i$에서 $j$로 가는 간선이 있다면 $c_{ij}$를 그 비용으로, 아니라면 $c_{ij} = -1$이라고 정의하..