EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)に参加した

8月11日に開催された，CodeforcesのコンテストEPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)に参加した．ABCの3完で8291位．

過去問を解いたことはあったもののCodeforcesのコンテストに出るのは初めてだったので，AtCoderのシステムとの違いに戸惑いながらの参加だった．

RustでCodeforcesに参加する場合，外部クレートであるproconioが使えないので標準入力からの受け取りを自前で実装する必要があるのだが，その際このブログ記事などが大変参考になった．

A - Distanced Coloring

問題概要

問題文

整数$n, m, k$が与えられる．$n\times m$のグリッドを，同色のどの2マス$(x_1, y_1), (x_2, y_2)$も$\max(|x_1-x_2|,|y_1-y_2|)\geq k$だけ離さなければならないという条件下で彩色するとき，必要な色数の最小値は？

考えたこと

いろいろ迷走してしまった．サンプル（$n=m=3, k=2$）の彩色例を眺めて冷静になる．

ひとまず$n, m$が十分大きい場合を考える．このとき，領域$[0, k)\times [0, k)$はすべて異なる色で塗る必要がある．なぜなら，この領域内の任意のマスの組$(x_1, y_1), (x_2, y_2)$は$|x_1-x_2|<k, |y_1-y_2|<k$を満たすため，これらの（チェビシェフ）距離は必ず$k$未満だからである．

よって少なくとも彩色には$k^2$色必要なのだが，実はこの色数で十分であることが証明できる．具体的には，$[0, k)\times [0, k)$の彩色パターンを平行移動させて領域$[ik, (i+1)k)\times [jk, (j+1)k)\;(i=0, 1,\cdots; j=0,1,\cdots)$を塗れば良い．このとき，どの同色マスの組も$x$座標の差と$y$座標の差がいずれも$k$以上であることが保証されているから条件を満たしている！

$n<k$または$m<k$のときには領域$[0, k)\times [0, k)$がマスからはみ出ることを考慮すると，最終的な答えは$\min(k, n)\times \min(k, m)$になる．

提出：https://codeforces.com/contest/2002/submission/275774039

B - Removals Game

こういうad hocにゲームの最適戦略を考える系はいつまでたってもできるようにならない……

問題概要

問題文

AliceとBobが$1,\cdots, n$の順列$a_n, b_n$をめぐってゲームをする．各ターンではそれぞれが順に以下の行動を行う：

1. Aliceが$a_n$の先頭か末尾の要素いずれか一方を削除する．
2. Bobが$b_n$の先頭か末尾の要素いずれか一方を削除する．

このセットを$n-1$ターン行い，最終的に残った$a$の要素$x$と$b$の要素$y$を比較する．$x\neq y$ならAliceの勝ち，$x=y$ならBobの勝ち．お互いが最適に行動したときどちらが勝つか？

考えたこと

いろいろ試していくうちに，Bobがだいぶ不利っぽいことが分かってきた．Aliceが選ばなかった要素をBobが選んでしまうとその時点で詰む．

ターン$1$でAliceが選んだ要素が$x_1$，Bobが選んだ要素が$y_1$だったとする．このとき$x_1\neq y_1$だった場合，Aliceはそれ以降のターンで「$y_1$でないほうを選び続ける」という戦略でBobに勝つことができる（Alice側は$x=y_1$を最後まで残すことができる一方，Bobはもう$y_1$を削除してしまっているので$y_1$を残せない！）．

これは次以降のターンでも同じで，BobはAliceが選んだ要素を選ぶことを続けないと負ける．そのため，お互いが最適に行動したときにBobが勝つ条件は

• 任意のターンにおいて，数列$a$の先頭・末尾と数列$b$の先頭・末尾が集合として一致する．

という場合である．よって，ゲーム開始時点で$a=b$または$a={\rm rev}(b)$ならBobの勝ち，そうでない場合はAliceの勝ち．

コンテスト中はここの行間が埋められなくて苦しんだが，$a, b$の同じ幅の連続部分列がつねに集合として一致しなければならない→$a$で隣接するなら$b$でも隣接しなければならない→$a$と$b$は並びが同じor逆順，と考えて納得した．

提出：https://codeforces.com/contest/2002/submission/275830562

C - Black Circles

さんざん難しく考えて悩んだ割に結論が拍子抜けで悔しい．

問題概要

問題文

2次元平面上に点${\rm P}_1,\cdots, {\rm P}_n$があり，これらの点を中心とした円$C_1,\cdots, C_n$を考える．時刻$t$における円の半径はすべて$t$である．時刻$t=0$にスタート地点${\rm S}(x_{\rm s}, y_{\rm s})$を出発して速度$1$で移動して，円の内部および周に入ることなしにゴール地点${\rm G}(x_{\rm g}, y_{\rm g})$まで到達できるか？　ただし軌道はどのような曲線を描いてもよい．

考えたこと

直線距離で進まない方が最適なパターンがあるかもしれない，という思考にとらわれすぎて時間を浪費してしまった．

障害物（円）がない場合の最短到達時刻は$t_0\equiv |{\rm SG}|=\sqrt{(x_{\rm s}-x_{\rm g})^2+(y_{\rm s}-y_{\rm g})^2}$なので，この時刻$t=t_0$の時点でいずれかの円の内部（または周）に入ってしまう場合（ある$i$で$|{\rm P}_i{\rm G}|\leq t_0$となる場合）は不可能．

意外なのは，そうでない場合必ず到達可能であるということだ．線分${\rm SG}$上に任意に点${\rm P}$をとると，この点を通過した時刻は$t=t_0-|{\rm PG}|$である．このとき，三角形${\rm P}_i{\rm PG}\;(i=1,\cdots, n)$に対して

が成り立つ．この時点での円の半径は$t_0-|{\rm PG}|$であるから，上の不等式$|{\rm P}_i{\rm P}|>t_0-|{\rm PG}|$は点${\rm P}$を通過した時刻において任意の円の外側にあることを意味する．

したがって，到達可能であるための必要十分条件は任意の$i$に対し$|{\rm P}_i{\rm G}|>|{\rm SG}|$となることである．実装においては不等式の両辺を2乗して整数のまま比較すると正確．

提出：https://codeforces.com/contest/2002/submission/275835959

D1 - DFS Checker (Easy Version)

コンテスト中に解き切ることはできなかったものの，終了後に自力で通したのでこちらについても取り上げる．

問題概要

問題文

$1,\cdots, n$の番号が付いた$n$頂点の完全二分木（頂点$i$の子は$2i$と$2i+1$）と，$1,\cdots, n$の順列$(p_i)$が与えられる．以下の$q$個のクエリを処理せよ．

• x y：$(p_i)$の$x$番目の要素と$y$番目の要素をswapし，$(p_i)$がこの二分木のDFS順として正しいかどうかを出力する．

考えたこと

$(p_i)$が与えられた二分木のDFS順として正しいかどうかを判定する代わりに，DFS順（のひとつ）が$(p_i)$になるような二分木が，与えられた二分木と同型かを判定することにする．

クエリを処理する前に，あらかじめDFS順が$(p_i)$になるような二分木を陽に構築し，隣接リストgraphと親のリストparをもっておく．また，

• ${\rm valid}[v]$：頂点$v$の親${\rm par}[v]$は与えられた二分木と同じか

を前計算しておく．これは，各頂点$v=1,\cdots, n$に対して$\lfloor v/2 \rfloor={\rm par}[v]$かどうか（$v$に親がないなら，$v=1$かどうか）をチェックすることでできる．

あとは，クエリごとにp, graph, par, validを差分更新し，その都度すべての$v$に対し${\rm valid}[v]$がtrueかどうかを判定すればよい．頂点$i, j$のswapで影響を受ける頂点は高々8個（$i, j$およびその親と子）なので，計算量はクエリ数$q$に対して線形である．

提出：https://codeforces.com/contest/2002/submission/275852278

雑感

全体的に問題がARCっぽい！　苦手！！

今までARCを避けてきたので瞬発力の低さが如実に表れてしまったなあ……という3時間だった．悔しいのでまた参加したい．