<div id="readability-page-1" class="page"><div><p>IOI 2023 Day 1 대회가 종료되었다. 올해 대회의 개최지는 헝가리로, 한국 팀은 2019년 이후 처음으로 현지에서 오프라인으로 대회를 진행하고 있다.</p>
<p>한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라.</p>
<ul>
<li>장태환, 100 / 53 / 58, 211점, 27등</li>
<li>반딧불, 53 / 80 / 58, 191점, 37등</li>
<li>조영욱, 67 / 51.5 / 58, 176.5점, 44등</li>
<li>박상훈, 70 / 72 / 27, 169점, 50등</li>
</ul>
<p>모든 학생들의 성적이 금메달 / 은메달의 경계선에서 멀지 않아서 Day 2의 결과가 매우 중요할 것으로 보인다. 한국 학생들은 매년 Day 2 결과가 더 좋은 편이다. Day 2에서 좋은 결과를 내기를 소망한다.</p>
<p>문제는 예년 대비 상당히 어려운 편이다. 만점자 수만 봐서는 2018 Day 2, 2021 Day 1보다도 적은, 거의 전례가 없는 수준이다 (11 / 10 / 3). 쉬운 문제가 없어서 긴장하기 쉬운데, 그럼에도 꿋꿋히 문제를 풀어 준 국가대표 학생들에게 박수를 보낸다. Day 1에는 세 명의 만점자가 있으며 모두 중국 학생들이다. 예년과 같이 중국 학생들의 성적이 아주 우수하며, 그 뒤를 일본의 Yuki Tanaka (277.5), 폴란드의 Antoni Buraczewski 학생 (265.5) 가 따랐다.</p>
<p>구현한 코드는 <a href="https://github.com/koosaga/olympiad/tree/master/IOI">https://github.com/koosaga/olympiad/tree/master/IOI</a> 에 모두 올라와 있다.</p>
<h2>Day 1 Problems PDF</h2>
<figure data-ke-align="alignCenter"><a href="https://blog.kakaocdn.net/dn/bg4n7J/btssxH0Xhpa/2f4DNe8dQKvlfbUOhOQqck/notice-ISC.pdf?attach=1&amp;knm=tfile.pdf">
    
    <div><p><span>notice-ISC.pdf</span></p>
<p>0.11MB</p>
</div>
  </a></figure>
<figure data-ke-align="alignCenter"><a href="https://blog.kakaocdn.net/dn/bKnYlB/btssHEOUceP/ynH6Ly1Fc8pYoUqiQysF00/notice-KOR.pdf?attach=1&amp;knm=tfile.pdf">
    
    <div><p><span>notice-KOR.pdf</span></p>
<p>0.19MB</p>
</div>
  </a></figure>
<figure data-ke-align="alignCenter"><a href="https://blog.kakaocdn.net/dn/sjS62/btssHjjPTz8/WfafnWNoOU3MSK3pHLLkm1/closing-KOR.pdf?attach=1&amp;knm=tfile.pdf">
    
    <div><p><span>closing-KOR.pdf</span></p>
<p>0.30MB</p>
</div>
  </a></figure>
<figure data-ke-align="alignCenter"><a href="https://blog.kakaocdn.net/dn/bG98Pk/btssIokSXdK/RdxLdgw2H5TXglHZyK2aeK/longesttrip-ISC.pdf?attach=1&amp;knm=tfile.pdf">
    
    <div><p><span>longesttrip-ISC.pdf</span></p>
<p>0.18MB</p>
</div>
  </a></figure>
<figure data-ke-align="alignCenter"><a href="https://blog.kakaocdn.net/dn/qZbTs/btssB0rU7Mc/0gBrcRTRZK3pPgkQRc6F1k/soccer-ISC.pdf?attach=1&amp;knm=tfile.pdf">
    
    <div><p><span>soccer-ISC.pdf</span></p>
<p>0.64MB</p>
</div>
  </a></figure>
<figure data-ke-align="alignCenter"><a href="https://blog.kakaocdn.net/dn/kZXaD/btsswgoV9D1/Hq88QCU5HnERcvAyOSF3MK/closing-ISC.pdf?attach=1&amp;knm=tfile.pdf">
    
    <div><p><span>closing-ISC.pdf</span></p>
<p>0.17MB</p>
</div>
  </a></figure>
<figure data-ke-align="alignCenter"><a href="https://blog.kakaocdn.net/dn/cwSrQU/btssHz7SXT3/pS1kuMZtNMaKHdgRzpPIIk/soccer-KOR.pdf?attach=1&amp;knm=tfile.pdf">
    
    <div><p><span>soccer-KOR.pdf</span></p>
<p>0.75MB</p>
</div>
  </a></figure>
<figure data-ke-align="alignCenter"><a href="https://blog.kakaocdn.net/dn/bgtyte/btssAzuzyGY/RT77jSZOwWSoJCDNulQzqK/longesttrip-KOR.pdf?attach=1&amp;knm=tfile.pdf">
    
    <div><p><span>longesttrip-KOR.pdf</span></p>
<p>0.31MB</p>
</div>
  </a></figure>

<p>(풀이는 현재 작성 중입니다)</p>
<h2>Problem 1. 봉쇄 시간</h2>
<h2>서브태스크 1 (8점)</h2>
<p>문제 조건에 따라 어떠한 도시가 $X, Y$ 에서 모두 도달 가능하게 배정하는 것은 불가능하다. 고로 각 도시가 둘 중 가까운 도시에 배정되게 하는 것이 최선이고, 이를 위해 배정해야 하는 봉쇄 시간은 DFS를 사용하여 계산할 수 있다. 필요한 봉쇄 시간이 작은 것부터 차례대로 배정하고, 배정할 수 있었던 도시의 개수를 출력하면 된다. 봉쇄 시간을 정렬해야 하니 시간 복잡도는 $O(n \log n)$ 이다.</p>
<h2>서브태스크 2 (17점)</h2>
<p>$X$ 에서 도달 가능한 정점의 집합과, $Y$ 에서 도달 가능한 정점의 집합은 선 위에서 연속 구간을 이룬다. 고로 시도해 볼 수 있는 집합의 후보가 $O(n^4)$ 개이다. 이 집합을 가능하게 하기 위해서 필요한 봉쇄 시간의 합을 계산한 후, 이것이 $K$ 이하인지 확인하면 된다. 시간 복잡도는 $O(n^5)$ 이다.</p>
<h2>서브태스크 3 (29점)</h2>
<p>$X$ 와 $Y$ 에서 도달 가능한 정점 집합의 교집합을 고정하자.</p>
<p>교집합이 비었다면, $X$ 에서 각 정점으로 가는 거리 집합과 $Y$ 에서 각 정점으로 가는 거리 집합을 모두 모은 후, 합이 $K$ 이하로 유지되는 한 최대한 많은 수를 고르면 된다. 한 정점을 두 번 고를 수도 있는데, 이 경우 해당 정점에 대해 필요보다 많은 비용을 소모한 것일 뿐이고 해가 불가능하지는 않아 상관이 없다.</p>
<p>교집합이 비지 않았다면, 이 교집합은 선 위에서 연속 구간을 이룬다. 일단 교집합 내부에서는 $X, Y$ 모두를 도달할 수 있는 봉쇄 시간이 배정되어야 하고, $X$ 와 $Y$ 에서 교집합을 도달하는 경로에도 충분한 봉쇄 시간이 필요하며, 여전히 비용이 남는다면 이 비용으로 남는 정점들에 대해 가까운 정점으로 가게끔 하면 된다.</p>
<p>교집합의 후보가 $O(n^2)$ 개이고, 교집합 내부 / 교집합을 도달하는 경로 상 비용을 계산하는 데 부분합을 사용하여 $O(1)$ 의 시간, 남는 정점들을 배정하는 데 $O(n)$ 의 시간이 소모된다. 시간 복잡도는 $O(n^3)$ 이다.</p>
<h2>서브태스크 4 (43점)</h2>
<p>서브태스크 4를 해결하는 방법은 다양한데 그 중 정해와 다소 비슷한 것을 설명한다.</p>
<p>교집합이 빈 경우는 당연히 따로 처리한다. 선 상에서 $[X, Y]$ 를 잇는 구간을 고려했을 때, 이 구간에서 $X, Y$ 에서 모두 도달 가능한 정점 집합을 고정하자. 즉, 구간 $[X, Y]$ 에 포함되는 또 다른 구간 $[l, r]$ 을 고르는 것이다. 이 때</p>
<ul>
<li>$[X, l)$ 에 있는 정점들은 $X$ 에서 도달 가능</li>
<li>$[l, r]$ 에 있는 정점들은 $X, Y$ 에서 도달 가능</li>
<li>$(r, Y]$ 에 있는 정점들은 $Y$ 에서 도달 가능</li>
</ul>
<p>하기 때문에 $[X, Y]$ 안에 있는 정점들에 배정하는 봉쇄 시간은 결정되며, 이것이 편의성 기여하는 값 역시 고정된다.</p>
<p>$[X, Y]$ 구간 밖에 있는 정점들은, $X, Y$ 에서 모두 도달 가능하거나 그 중 가까운 것에서만 도달 가능하다. 예를 들어, $[0, X-1]$ 구간에 있는 어떤 suffix들은 $X$ 에서 도달 가능한 정점들이고, 또 어떤 suffix는 $X, Y$ 에서 모두 도달 가능할 것이다. suffix는 물론 비어 있을 수 있다.</p>
<p>이 때 구성한 도달 가능성 집합이 $[X, Y]$ 구간에서 정해준 도달 가능성과 모순일 수도 있다. 다시 말해, 여기서는 $X - 1$ 번 정점이 $X, Y$ 에서 모두 도달 가능한 정점이라고 고정했는데, 정작 $X$ 번 정점은 $Y$ 에서 도달 불가능한 경우가 있을 수 있다. 하지만 이 경우에는 $X-1$ 번 정점의 도달 가능성을 만들어 주기 위해서 쓴 비용을 그냥 $X$ 번 정점에 쓰면, 같은 이득을 더 작은 비용으로 볼 수 있다. 이는 중요한 것을 시사하는데, $[X, Y]$ 에서 구간 $[l, r]$ 을 어떻게 골랐든 그 밖의 선택과 독립이며, 고로 구간 안과 밖의 문제를 따로 해결할 수 있다는 것이다. 이제 다음과 같은 값을 계산하자:</p>
<ul>
<li>$Left[i]$: $[0, X - 1]$ 에서 도달 가능성을 적절히 설정하여 $i$ 만큼의 편의성을 얻을 수 있는 최소 비용</li>
<li>$Mid[i]$: $[X, Y]$ 에서 도달 가능성을 적절히 설정하여 $i$ 만큼의 편의성을 얻을 수 있는 최소 비용</li>
<li>$Right[i]$: $[Y+1, N-1]$ 에서 도달 가능성을 적절히 설정하여 $i$ 만큼의 편의성을 얻을 수 있는 최소 비용</li>
</ul>
<p>위 세 값은 모두 부분합을 사용하여 $O(n^2)$ 시간에 구할 수 있다. DP (max convolution) 으로 이를 $O(n^2)$ 에 합쳐주면 전체 문제 역시 해결된다.</p>
<h2>서브태스크 5 (52점)</h2>
<p>아주 단순한 완전 탐색은 되지 않는다. 모든 교집합을 고정한 후 나머지를 Greedy로 해결하거나, $X$ 에서 도달 가능한 집합을 고정한 후 Tree DP로 $Y$ 에서 도달 가능한 집합을 구하는 식으로 해결 가능하다.</p>
<h2>서브태스크 8 (83점)</h2>
<p>트리 상에서 $X, Y$ 를 잇는 경로와 $X, Y$ 에 모두 도달 가능한 정점의 교집합을 모두 고정하자. 서브태스크 4의 원리로 경로 안에서의 비용은 모두 결정된다.</p>
<p>경로 밖에서는, $X, Y$에 모두 도달하거나 아니면 둘 중 하나에만 도달하게 설정할 수 있다. 위에서 사용한 것과 동일한 논리로, 어떠한 노드가 둘 모두에 도달할 수 있는데 그 부모가 둘 중 하나에만 도달할 수 있다면, 부모에 공을 넘김으로서 더 적은 비용으로 같은 효과를 낼 수 있다. 또한, 경로 밖에 어떠한 노드가 $X$ 에 도달하는 것이 $Y$ 에 도달하는 것보다 쉽다면, 그 부모 역시 그러하다.</p>
<p>이러한 식으로 경로 밖에 있는 노드들에 대해서는, <em>부모 자식 관계</em> 와도 아예 독립적으로, 문제가 해결된다. 각각의 노드에 대해서, 둘 중 하나에만 도달하는 비용 $a_i$ 와 둘 다에 도달하는 비용 $b_i$ 를 계산하자. 첫 번째 비용은 편의성에 1을 기여하고, 두 번째 비용은 편의성에 2를 기여한다. 이제 Knapsack DP 로, $i$ 의 편의성을 얻기 위한 최소 비용을 $O(n^2)$ 에 구할 수 있다.</p>
<p>경로 안과 밖의 편의성을 모두 계산하면, 이제 two pointers 를 사용하여 비용 $K$ 로 얻는 최대 편의성을 구할 수 있다. 시간 복잡도는 $O(n^2)$ 이다.</p>
<h2>Problem 2. 가장 긴 여행</h2>
<h2>서브태스크 1 (5점)</h2>
<p>그래프는 완전 그래프이기 때문에, $[0, 1, \ldots, N - 1]$ 혹은 이것의 아무 순열을 반환하면 된다.</p>
<h2>서브태스크 2 (15점)</h2>
<p>모든 $N(N-1)/2$ 개의 쌍에 대해서 두 쌍을 잇는 간선이 존재하는지를 단순하게 물어보면 그래프의 정보를 알 수 있다. $N = 256$ 일 때 이 값은 $32640$ 이다. 고로 서브태스크 2, 3 에서는 그래프의 정보를 알 수 있다고 가정해도 무방하다. 서브태스크 2에서 그래프에 존재하지 <strong>않는</strong> 간선은 같은 정점을 공유할 수 없다. 달리 말해, 그러한 간선들은 매칭을 이룬다.</p>
<p>초기에, $0$ 번 정점을 포함하는 길이 $1$ 의 경로 ($[0]$) 에서 시작해서, 다음과 같은 방법으로 경로를 확장시키자. 이 글에서는 이러한 경로를 <em>Maximal path</em> 라 부른다.</p>
<ul>
<li>현재 경로의 마지막 점과 인접하며, 경로에 속하지 않은 정점을 고른다.</li>
<li>이를 경로의 마지막 점으로 추가한다.</li>
</ul>
<p>서브태스크 2의 그래프에서는 Maximal path의 길이가 $N-1$ 미만일 수 없다. 이보다 작으면 무조건 속하지 않으며 인접한 정점이 존재하기 때문이다.</p>
<p>고로 Maximal path의 길이는 $N-1$ 이거나 $N$ 이다. $N$ 이면 문제는 이미 풀렸다. $N-1$ 일 경우, 경로에 속하지 않는 정점은 경로의 끝점과 인접하지 않으니, 시작점과 인접하고, 시작점 앞에 붙여주면 된다.</p>
<h2>서브태스크 3 (40점)</h2>
<p>서브태스크 2와 동일하게 Maximal path를 찾아주자. 만약 Maximal path $P = [v, \ldots, w]$ 에 더 이상 정점을 추가할 수 없다면, 현재 경로에 속하지 않은 정점들 ($V \setminus P$) 은 $w$ 와 인접하지 않다. $D = 1$ 이라는 성질을 생각해 보면, 경로에 속하지 않은 정점들의 쌍을 모두 고려했을 때, 이들 간에 간선이 항상 존재하고, 달리 말해 $V \setminus P$ 는 클리크를 이룬다는 것을 알 수 있다. 고로 그래프의 모든 정점은 찾은 Maximal path에 속하거나 아니면 클리크에 속한다. Path의 길이가 길면 Path를 반환하고, 아니면 클리크의 정점들을 아무 순서로 반환하면 된다.</p>
<h2>60점</h2>
<p>서브태스크 3과 동일하게 Maximal path $P$ 를 찾아주고, 이에 따른 클리크 $C = V \setminus P$ 역시 찾아주자. 만약 $C, P$ 사이를 잇는 간선이 없다면 둘 중 큰 쪽을 반환해 주면 된다.</p>
<p>그렇지 않다면 둘을 항상 이어줄 수 있다. 만약 $|P| \le 2$ 이면, 둘을 잇는 간선이 경로의 끝점을 이으니 그대로 이어주면 된다. $|P| \geq 3$ 이라고 하자. $C$ 의 임의의 정점과 $P$ 의 두 양 끝점을 보았을 때, 세 가지 경우 중 하나가 성립한다.</p>
<ul>
<li>$C$ 의 임의의 정점이 양 끝점 중 하나와 인접한다 - 그대로 이어붙이면 된다.</li>
<li>둘 다 아니다 - $P$ 의 양 끝점이 인접하기 때문에 $P$ 를 사이클로 볼 수 있다. $C$ 와 $P$ 사이를 잇는 간선이 있다면, 이 간선을 기준으로 $P$ 를 Cyclic shift하여 붙여주면 된다.</li>
</ul>
<h2>70점</h2>
<p>Maximal path를 찾고, $C$ 와 $P$ 사이를 잇는 간선을 찾을 때 이분 탐색을 사용하여 최적화할 수 있다. 특정 정점과 인접한 정점 <em>단 하나</em> 를 찾는 것이기 때문에, 이 하나가 속하는 집합을 이분 탐색과 같이 찾아주는 것이다.</p>
<h2>85점</h2>
<p>60점 풀이의 요령으로 Maximal path를 찾을 때, 경로의 끝점과 인접하지 않은 정점을 순회하는 과정에서 많은 시간이 소모된다. 다음과 같이 알고리즘을 수정하면 이 부분을 최적화 할 수 있다. Maximal path 하나를 관리하는 것이 아니라, <em>최대 2개</em> 의 Maximal path를 관리하자. 초기 상태는 0번 정점을 포함하는 길이 $1$ 의 경로가 하나 있는 상태이다. 만약 현재 경로가 1개라면:</p>
<ul>
<li>경로의 끝점과 새 정점 $v$ 가 인접하면 이 경로에 추가한다.</li>
<li>그렇지 않다면 두 번째 경로를 길이 1의 경로 $[v]$ 로 initialize한다.</li>
</ul>
<p>현재 경로가 2개라면:</p>
<ul>
<li>둘 중 한 경로에 인접하다면 그 경로에 추가한다.</li>
<li>그렇지 않다면 두 경로의 끝점이 인접하다. 두 경로를 하나로 붙인 후, 두 번째 경로를 길이 1의 경로 $[v]$ 로 initialize한다.</li>
</ul>
<p>여기까지 $2n$ 개의 쿼리를 사용하였다. </p>
<p>이제 전체 그래프를 두 개의 경로 $P_1, P_2$ 로 묶었다. 일반성을 잃지 않고 $|P_1| \geq |P_2|$ 라고 하자. 60점 풀이에서는 클리크라는 성질을 사용해서 두 경로를 묶었지만, 사실 그러한 성질이 없어도 두 경로를 묶을 수 있다.</p>
<ul>
<li>$P_1, P_2$ 를 잇는 간선이 없다 - 큰 쪽을 반환한다.</li>
<li>$P_1$ 의 양 끝 정점이 $P_2$ 의 양 끝점 중 하나와 인접한다 - 그대로 이어붙이면 된다.</li>
<li>$P_2$ 의 양 끝 정점이 $P_1$ 의 양 끝점 중 하나와 인접한다 - 그대로 이어붙이면 된다.</li>
<li>두 경우가 모두 아니라 하자. 만약 $|P_i| \geq 3$ 일 경우 경로를 사이클로 바꿀 수 있다. $2\log n$ 번의 쿼리를 사용하여 이분 탐색을 하면, 두 경로 사이를 잇는 간선 하나를 찾을 수 있다. 사이클이거나 길이 2인 경로들이기 때문에, 이 간선 앞 뒤로 경로가 붙어있게 조정할 수 있다.</li>
</ul>
<p>총 $2n + 3 + 2 \log n$ 개의 쿼리를 사용하며, 85점을 받을 수 있다.</p>
<h2>만점 풀이</h2>
<p>제한을 통해서 만점 풀이가 대략 $3/2n + 2 \log n$ 개 정도의 쿼리를 사용한다고 짐작한다면, 시도해 볼만한 전략은 위 풀이에서 2개의 정점을 3번의 쿼리로 한 번에 넣는 것이 되겠다. Maximal path 최대 두 개를 관리하며, 여기에 <em>Maximal path가 두 개일 경우 둘의 끝점이 인접하지 않다</em> 라는 불변량을 추가로 설정하자. $(0, 1)$ 의 인접 여부에 따라서 초기 상태를 결정할 수 있다. </p>
<p>새로 넣는 정점의 번호를 $v, w$ 라고 하자. 만약 현재 경로가 1개라면, $v, w$ 와 경로의 끝점 $p$ 간 세 쌍에 대해서 쿼리를 하자. 쿼리 결과를 토대로 다음 상태는 아래와 같이 정해 준다.</p>
<ul>
<li>만약 $(v, w)$ 가 인접한데 $(v, p)$ 나 $(w, p)$ 중 하나라도 인접한다면 경로의 뒤에 $v, w$ 나 $w, v$ 를 추가한다.</li>
<li>만약 $(v, w)$ 가 인접한데 $(v, p)$ 나 $(w, p)$ 가 모두 인접하지 않다면 $[v, w]$ 라는 경로를 추가한다.</li>
<li>만약 $(v, w)$ 가 인접하지 않다면 $(v, p)$ 나 $(w, p)$ 중 하나는 인접하다. 인접한 쪽을 $p$ 뒤에 붙이고, 선택되지 않은 쪽을 새 경로로 만든다.</li>
</ul>
<p>현재 경로가 2개라면, $v, w, p_1, p_2$ 중 알아야 할 쌍의 개수가 총 5개이다. 그런데, $p_1, p_2$ 가 인접하지 않음이 보장되기 때문에, $p_1$ 이 $v$ 와 인접하지 않다면 자동으로 $p_2$ 와 인접해 지는 등의 성질이 보장된다. 이 점을 잘 사용하면 2개의 쿼리가 줄어들어 3개의 쿼리로 충분해진다. 먼저 $(v, w)$ 간의 인접성을 하나의 쿼리로 확인하자. 만약 $(v, w)$ 가 인접하다면:</p>
<ul>
<li>$(v, p_1)$ 간에 인접한지 확인하자. 일반성을 잃지 않고 $p_1$ 에 인접한 쪽을 $v$ 라고 하자.</li>
<li>$(w, p_2)$ 간에 인접하다면, $p_1 - v - w - p_2$ 와 같이 경로를 붙여준다.</li>
<li>그렇지 않다면 $p_1$ 에 $v, w$ 를 붙이자.</li>
</ul>
<p>만약 $(v, w)$ 가 인접하지 않다면:</p>
<ul>
<li>$(v, p_1)$ 간에 인접한지 확인하자. 일반성을 잃지 않고 $p_1$ 과 $v$ 가 인접하다고 하자.</li>
<li>$(w, p_2)$ 간에 인접하다면, $p_1$ 에 $v$, $p_2$ 에 $w$ 를 붙여준다.</li>
<li>그렇지 않다면, 우리는 $(w, p_2)$ 및 $(p_1, p_2)$ 가 인접하지 않음을 알고 있으며, 고로 $(w, p_1)$ 이 인접함을 유추할 수 있다. 상술했듯이 $(v, p_2)$ 역시 인접하니, $p_1$ 에 $w$, $p_2$ 에 $v$ 를 붙여준다.</li>
</ul>
<p>이후 이들을 이어주는 것은 85점과 동일한 이분 탐색으로 가능하다. </p>
<p>쿼리 개수가 최악의 개수에도 최대 400번 나오게 신중하게 구현해야 함에 유의하자. 본인은 402번의 쿼리를 사용하여 여러 번 틀렸고, 결국 2번의 쿼리를 줄여서 통과하였다.</p></div></div>

구사과

IOI 2023 Day 1 대회가 종료되었다. 올해 대회의 개최지는 헝가리로, 한국 팀은 2019년 이후 처음으로 현지에서 오프라인으로 대회를 진행하고 있다.
한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라.
장태환, 100 / 53 / 58, 211점, 27등
반딧불, 53 / 80 / 58, 191점, 37등
조영욱, 67 / 51.5 / 58, 176.5점, 44등
박상훈, 70 / 72 / 27, 169점, 50등
모든 학생들의 성적이 금메달 / 은메달의 경계선에서 멀지 않아서 Day 2의 결과가 매우 중요할 것으로 보인다. 한국 학생들은 매년 Day 2 결과가 더 좋은 편이다. Day 2에서 좋은 결과를 내기를 소망한다.
문제는 예년 대비 상당히 어려운 편이다. 만점자 수만 봐서는 2018 Day 2, 2021 Day 1보다도 적은, 거의 전례가 없는 수준이다 (11 / 10 / 3). 쉬운 문제가 없어서 긴장하기 쉬운데, 그럼에도 꿋꿋히 문제를 풀어 준 국가대표 학생들에게 박수를 보낸다. Day 1에는 세 명의 만점자가 있으며 모두 중국 학생들이다. 예년과 같이 중국 학생들의 성적이 아주 우수하며, 그 뒤를 일본의 Yuki Tanaka (277.5), 폴란드의 Antoni Buraczewski 학생 (265.5) 가 따랐다.
구현한 코드는 https://github.com/koosaga/olympiad/tree/master/IOI 에 모두 올라와 있다.
Day 1 Problems PDF
(풀이는 현재 작성 중입니다)
Problem 1. 봉쇄 시간
서브태스크 1 (8점)
문제 조건에 따라 어떠한 도시가 $X, Y$ 에서 모두 도달 가능하게 배정하는 것은 불가능하다. 고로 각 도시가 둘 중 가까운 도시에 배정되게 하는 것이 최선이고, 이를 위해 배정해야 하는 봉쇄 시간은 DFS를 사용하여 계산할 수 있다. 필요한 봉쇄 시간이 작은 것부터 차례대로 배정하고, 배정할 수 있었던 도시의 개수를 출력하면 된다. 봉쇄 시간을 정렬해야 하니 시간 복잡도는 $O(n \log n)$ 이다.
서브태스크 2 (17점)
$X$ 에서 도달 가능한 정점의 집합과, $Y$ 에서 도달 가능한 정점의 집합은 선 위에서 연속 구간을 이룬다. 고로 시도해 볼 수 있는 집합의 후보가 $O(n^4)$ 개이다. 이 집합을 가능하게 하기 위해서 필요한 봉쇄 시간의 합을 계산한 후, 이것이 $K$ 이하인지 확인하면 된다. 시간 복잡도는 $O(n^5)$ 이다.
서브태스크 3 (29점)
$X$ 와 $Y$ 에서 도달 가능한 정점 집합의 교집합을 고정하자.
교집합이 비었다면, $X$ 에서 각 정점으로 가는 거리 집합과 $Y$ 에서 각 정점으로 가는 거리 집합을 모두 모은 후, 합이 $K$ 이하로 유지되는 한 최대한 많은 수를 고르면 된다. 한 정점을 두 번 고를 수도 있는데, 이 경우 해당 정점에 대해 필요보다 많은 비용을 소모한 것일 뿐이고 해가 불가능하지는 않아 상관이 없다.
교집합이 비지 않았다면, 이 교집합은 선 위에서 연속 구간을 이룬다. 일단 교집합 내부에서는 $X, Y$ 모두를 도달할 수 있는 봉쇄 시간이 배정되어야 하고, $X$ 와 $Y$ 에서 교집합을 도달하는 경로에도 충분한 봉쇄 시간이 필요하며, 여전히 비용이 남는다면 이 비용으로 남는 정점들에 대해 가까운 정점으로 가게끔 하면 된다.
교집합의 후보가 $O(n^2)$ 개이고, 교집합 내부 / 교집합을 도달하는 경로 상 비용을 계산하는 데 부분합을 사용하여 $O(1)$ 의 시간, 남는 정점들을 배정하는 데 $O(n)$ 의 시간이 소모된다. 시간 복잡도는 $O(n^3)$ 이다.
서브태스크 4 (43점)
서브태스크 4를 해결하는 방법은 다양한데 그 중 정해와 다소 비슷한 것을 설명한다.
교집합이 빈 경우는 당연히 따로 처리한다. 선 상에서 $[X, Y]$ 를 잇는 구간을 고려했을 때, 이 구간에서 $X, Y$ 에서 모두 도달 가능한 정점 집합을 고정하자. 즉, 구간 $[X, Y]$ 에 포함되는 또 다른 구간 $[l, r]$ 을 고르는 것이다. 이 때
$[X, l)$ 에 있는 정점들은 $X$ 에서 도달 가능
$[l, r]$ 에 있는 정점들은 $X, Y$ 에서 도달 가능
$(r, Y]$ 에 있는 정점들은 $Y$ 에서 도달 가능
하기 때문에 $[X, Y]$ 안에 있는 정점들에 배정하는 봉쇄 시간은 결정되며, 이것이 편의성 기여하는 값 역시 고정된다.
$[X, Y]$ 구간 밖에 있는 정점들은, $X, Y$ 에서 모두 도달 가능하거나 그 중 가까운 것에서만 도달 가능하다. 예를 들어, $[0, X-1]$ 구간에 있는 어떤 suffix들은 $X$ 에서 도달 가능한 정점들이고, 또 어떤 suffix는 $X, Y$ 에서 모두 도달 가능할 것이다. suffix는 물론 비어 있을 수 있다.
이 때 구성한 도달 가능성 집합이 $[X, Y]$ 구간에서 정해준 도달 가능성과 모순일 수도 있다. 다시 말해, 여기서는 $X - 1$ 번 정점이 $X, Y$ 에서 모두 도달 가능한 정점이라고 고정했는데, 정작 $X$ 번 정점은 $Y$ 에서 도달 불가능한 경우가 있을 수 있다. 하지만 이 경우에는 $X-1$ 번 정점의 도달 가능성을 만들어 주기 위해서 쓴 비용을 그냥 $X$ 번 정점에 쓰면, 같은 이득을 더 작은 비용으로 볼 수 있다. 이는 중요한 것을 시사하는데, $[X, Y]$ 에서 구간 $[l, r]$ 을 어떻게 골랐든 그 밖의 선택과 독립이며, 고로 구간 안과 밖의 문제를 따로 해결할 수 있다는 것이다. 이제 다음과 같은 값을 계산하자:
$Left[i]$: $[0, X - 1]$ 에서 도달 가능성을 적절히 설정하여 $i$ 만큼의 편의성을 얻을 수 있는 최소 비용
$Mid[i]$: $[X, Y]$ 에서 도달 가능성을 적절히 설정하여 $i$ 만큼의 편의성을 얻을 수 있는 최소 비용
$Right[i]$: $[Y+1, N-1]$ 에서 도달 가능성을 적절히 설정하여 $i$ 만큼의 편의성을 얻을 수 있는 최소 비용
위 세 값은 모두 부분합을 사용하여 $O(n^2)$ 시간에 구할 수 있다. DP (max convolution) 으로 이를 $O(n^2)$ 에 합쳐주면 전체 문제 역시 해결된다.
서브태스크 5 (52점)
아주 단순한 완전 탐색은 되지 않는다. 모든 교집합을 고정한 후 나머지를 Greedy로 해결하거나, $X$ 에서 도달 가능한 집합을 고정한 후 Tree DP로 $Y$ 에서 도달 가능한 집합을 구하는 식으로 해결 가능하다.
서브태스크 8 (83점)
트리 상에서 $X, Y$ 를 잇는 경로와 $X, Y$ 에 모두 도달 가능한 정점의 교집합을 모두 고정하자. 서브태스크 4의 원리로 경로 안에서의 비용은 모두 결정된다.
경로 밖에서는, $X, Y$에 모두 도달하거나 아니면 둘 중 하나에만 도달하게 설정할 수 있다. 위에서 사용한 것과 동일한 논리로, 어떠한 노드가 둘 모두에 도달할 수 있는데 그 부모가 둘 중 하나에만 도달할 수 있다면, 부모에 공을 넘김으로서 더 적은 비용으로 같은 효과를 낼 수 있다. 또한, 경로 밖에 어떠한 노드가 $X$ 에 도달하는 것이 $Y$ 에 도달하는 것보다 쉽다면, 그 부모 역시 그러하다.
이러한 식으로 경로 밖에 있는 노드들에 대해서는, 부모 자식 관계 와도 아예 독립적으로, 문제가 해결된다. 각각의 노드에 대해서, 둘 중 하나에만 도달하는 비용 $a_i$ 와 둘 다에 도달하는 비용 $b_i$ 를 계산하자. 첫 번째 비용은 편의성에 1을 기여하고, 두 번째 비용은 편의성에 2를 기여한다. 이제 Knapsack DP 로, $i$ 의 편의성을 얻기 위한 최소 비용을 $O(n^2)$ 에 구할 수 있다.
경로 안과 밖의 편의성을 모두 계산하면, 이제 two pointers 를 사용하여 비용 $K$ 로 얻는 최대 편의성을 구할 수 있다. 시간 복잡도는 $O(n^2)$ 이다.
Problem 2. 가장 긴 여행
서브태스크 1 (5점)
그래프는 완전 그래프이기 때문에, $[0, 1, \ldots, N - 1]$ 혹은 이것의 아무 순열을 반환하면 된다.
서브태스크 2 (15점)
모든 $N(N-1)/2$ 개의 쌍에 대해서 두 쌍을 잇는 간선이 존재하는지를 단순하게 물어보면 그래프의 정보를 알 수 있다. $N = 256$ 일 때 이 값은 $32640$ 이다. 고로 서브태스크 2, 3 에서는 그래프의 정보를 알 수 있다고 가정해도 무방하다. 서브태스크 2에서 그래프에 존재하지 않는 간선은 같은 정점을 공유할 수 없다. 달리 말해, 그러한 간선들은 매칭을 이룬다.
초기에, $0$ 번 정점을 포함하는 길이 $1$ 의 경로 ($[0]$) 에서 시작해서, 다음과 같은 방법으로 경로를 확장시키자. 이 글에서는 이러한 경로를 Maximal path 라 부른다.
현재 경로의 마지막 점과 인접하며, 경로에 속하지 않은 정점을 고른다.
이를 경로의 마지막 점으로 추가한다.
서브태스크 2의 그래프에서는 Maximal path의 길이가 $N-1$ 미만일 수 없다. 이보다 작으면 무조건 속하지 않으며 인접한 정점이 존재하기 때문이다.
고로 Maximal path의 길이는 $N-1$ 이거나 $N$ 이다. $N$ 이면 문제는 이미 풀렸다. $N-1$ 일 경우, 경로에 속하지 않는 정점은 경로의 끝점과 인접하지 않으니, 시작점과 인접하고, 시작점 앞에 붙여주면 된다.
서브태스크 3 (40점)
서브태스크 2와 동일하게 Maximal path를 찾아주자. 만약 Maximal path $P = [v, \ldots, w]$ 에 더 이상 정점을 추가할 수 없다면, 현재 경로에 속하지 않은 정점들 ($V \setminus P$) 은 $w$ 와 인접하지 않다. $D = 1$ 이라는 성질을 생각해 보면, 경로에 속하지 않은 정점들의 쌍을 모두 고려했을 때, 이들 간에 간선이 항상 존재하고, 달리 말해 $V \setminus P$ 는 클리크를 이룬다는 것을 알 수 있다. 고로 그래프의 모든 정점은 찾은 Maximal path에 속하거나 아니면 클리크에 속한다. Path의 길이가 길면 Path를 반환하고, 아니면 클리크의 정점들을 아무 순서로 반환하면 된다.
60점
서브태스크 3과 동일하게 Maximal path $P$ 를 찾아주고, 이에 따른 클리크 $C = V \setminus P$ 역시 찾아주자. 만약 $C, P$ 사이를 잇는 간선이 없다면 둘 중 큰 쪽을 반환해 주면 된다.
그렇지 않다면 둘을 항상 이어줄 수 있다. 만약 $|P| \le 2$ 이면, 둘을 잇는 간선이 경로의 끝점을 이으니 그대로 이어주면 된다. $|P| \geq 3$ 이라고 하자. $C$ 의 임의의 정점과 $P$ 의 두 양 끝점을 보았을 때, 세 가지 경우 중 하나가 성립한다.
$C$ 의 임의의 정점이 양 끝점 중 하나와 인접한다 - 그대로 이어붙이면 된다.
둘 다 아니다 - $P$ 의 양 끝점이 인접하기 때문에 $P$ 를 사이클로 볼 수 있다. $C$ 와 $P$ 사이를 잇는 간선이 있다면, 이 간선을 기준으로 $P$ 를 Cyclic shift하여 붙여주면 된다.
70점
Maximal path를 찾고, $C$ 와 $P$ 사이를 잇는 간선을 찾을 때 이분 탐색을 사용하여 최적화할 수 있다. 특정 정점과 인접한 정점 단 하나 를 찾는 것이기 때문에, 이 하나가 속하는 집합을 이분 탐색과 같이 찾아주는 것이다.
85점
60점 풀이의 요령으로 Maximal path를 찾을 때, 경로의 끝점과 인접하지 않은 정점을 순회하는 과정에서 많은 시간이 소모된다. 다음과 같이 알고리즘을 수정하면 이 부분을 최적화 할 수 있다. Maximal path 하나를 관리하는 것이 아니라, 최대 2개 의 Maximal path를 관리하자. 초기 상태는 0번 정점을 포함하는 길이 $1$ 의 경로가 하나 있는 상태이다. 만약 현재 경로가 1개라면:
경로의 끝점과 새 정점 $v$ 가 인접하면 이 경로에 추가한다.
그렇지 않다면 두 번째 경로를 길이 1의 경로 $[v]$ 로 initialize한다.
현재 경로가 2개라면:
둘 중 한 경로에 인접하다면 그 경로에 추가한다.
그렇지 않다면 두 경로의 끝점이 인접하다. 두 경로를 하나로 붙인 후, 두 번째 경로를 길이 1의 경로 $[v]$ 로 initialize한다.
여기까지 $2n$ 개의 쿼리를 사용하였다. 
이제 전체 그래프를 두 개의 경로 $P_1, P_2$ 로 묶었다. 일반성을 잃지 않고 $|P_1| \geq |P_2|$ 라고 하자. 60점 풀이에서는 클리크라는 성질을 사용해서 두 경로를 묶었지만, 사실 그러한 성질이 없어도 두 경로를 묶을 수 있다.
$P_1, P_2$ 를 잇는 간선이 없다 - 큰 쪽을 반환한다.
$P_1$ 의 양 끝 정점이 $P_2$ 의 양 끝점 중 하나와 인접한다 - 그대로 이어붙이면 된다.
$P_2$ 의 양 끝 정점이 $P_1$ 의 양 끝점 중 하나와 인접한다 - 그대로 이어붙이면 된다.
두 경우가 모두 아니라 하자. 만약 $|P_i| \geq 3$ 일 경우 경로를 사이클로 바꿀 수 있다. $2\log n$ 번의 쿼리를 사용하여 이분 탐색을 하면, 두 경로 사이를 잇는 간선 하나를 찾을 수 있다. 사이클이거나 길이 2인 경로들이기 때문에, 이 간선 앞 뒤로 경로가 붙어있게 조정할 수 있다.
총 $2n + 3 + 2 \log n$ 개의 쿼리를 사용하며, 85점을 받을 수 있다.
만점 풀이
제한을 통해서 만점 풀이가 대략 $3/2n + 2 \log n$ 개 정도의 쿼리를 사용한다고 짐작한다면, 시도해 볼만한 전략은 위 풀이에서 2개의 정점을 3번의 쿼리로 한 번에 넣는 것이 되겠다. Maximal path 최대 두 개를 관리하며, 여기에 Maximal path가 두 개일 경우 둘의 끝점이 인접하지 않다 라는 불변량을 추가로 설정하자. $(0, 1)$ 의 인접 여부에 따라서 초기 상태를 결정할 수 있다. 
새로 넣는 정점의 번호를 $v, w$ 라고 하자. 만약 현재 경로가 1개라면, $v, w$ 와 경로의 끝점 $p$ 간 세 쌍에 대해서 쿼리를 하자. 쿼리 결과를 토대로 다음 상태는 아래와 같이 정해 준다.
만약 $(v, w)$ 가 인접한데 $(v, p)$ 나 $(w, p)$ 중 하나라도 인접한다면 경로의 뒤에 $v, w$ 나 $w, v$ 를 추가한다.
만약 $(v, w)$ 가 인접한데 $(v, p)$ 나 $(w, p)$ 가 모두 인접하지 않다면 $[v, w]$ 라는 경로를 추가한다.
만약 $(v, w)$ 가 인접하지 않다면 $(v, p)$ 나 $(w, p)$ 중 하나는 인접하다. 인접한 쪽을 $p$ 뒤에 붙이고, 선택되지 않은 쪽을 새 경로로 만든다.
현재 경로가 2개라면, $v, w, p_1, p_2$ 중 알아야 할 쌍의 개수가 총 5개이다. 그런데, $p_1, p_2$ 가 인접하지 않음이 보장되기 때문에, $p_1$ 이 $v$ 와 인접하지 않다면 자동으로 $p_2$ 와 인접해 지는 등의 성질이 보장된다. 이 점을 잘 사용하면 2개의 쿼리가 줄어들어 3개의 쿼리로 충분해진다. 먼저 $(v, w)$ 간의 인접성을 하나의 쿼리로 확인하자. 만약 $(v, w)$ 가 인접하다면:
$(v, p_1)$ 간에 인접한지 확인하자. 일반성을 잃지 않고 $p_1$ 에 인접한 쪽을 $v$ 라고 하자.
$(w, p_2)$ 간에 인접하다면, $p_1 - v - w - p_2$ 와 같이 경로를 붙여준다.
그렇지 않다면 $p_1$ 에 $v, w$ 를 붙이자.
만약 $(v, w)$ 가 인접하지 않다면:
$(v, p_1)$ 간에 인접한지 확인하자. 일반성을 잃지 않고 $p_1$ 과 $v$ 가 인접하다고 하자.
$(w, p_2)$ 간에 인접하다면, $p_1$ 에 $v$, $p_2$ 에 $w$ 를 붙여준다.
그렇지 않다면, 우리는 $(w, p_2)$ 및 $(p_1, p_2)$ 가 인접하지 않음을 알고 있으며, 고로 $(w, p_1)$ 이 인접함을 유추할 수 있다. 상술했듯이 $(v, p_2)$ 역시 인접하니, $p_1$ 에 $w$, $p_2$ 에 $v$ 를 붙여준다.
이후 이들을 이어주는 것은 85점과 동일한 이분 탐색으로 가능하다. 
쿼리 개수가 최악의 개수에도 최대 400번 나오게 신중하게 구현해야 함에 유의하자. 본인은 402번의 쿼리를 사용하여 여러 번 틀렸고, 결국 2번의 쿼리를 줄여서 통과하였다.

IOI 2023 Day 1

댓글