A. Roman and Browser

問題文が難しかった．要するに「$1$と$-1$からなる配列から$b+ik$（$i$はすべての整数）番目の値を消したときの$1$の数と$-1$の数の差」の最大値を求める問題． 解答例

解法としては$b$をすべて試せばよい（コード中では$v$）．さらに$b$は$0$から$(k-1)$まで試せばすべて尽くせる（$c=b+ik$の$i$が負にも動くため）．各$b$に対応する$c$も時間内に全部作れるため，$a[c]=1$または$-1$である$c$の個数をそれぞれ数えることができる．ここから答えの候補が求まるから，すべて試して最大値を取ればよい．

B. Build a Contest

B問題であるにもかかわらずSegment Treeを持ちだした．実戦では初めて．まあいい練習にはなったのではないか． 解答例

まず$O(mn)$解を考え，あとで高速化する．「$b[i]$:=iの出た回数」という配列を用意すると，更新は$a$の各要素$a[i]$を読む度に$b[a[i]]$に$1$加算することで行える．すると「$k$個目のセットが作れる」は「$b$のすべての要素が$k$以上である」と言い換えられる．したがって次のようにすればよい：$k:=1$とする．各$a[i]$を読んで$b$を更新したあと，$b$全体を走査して先の条件を満たすか判定し，満たされていれば$k$に1を加算すればよい．

これを速くしたい．ここで「$b$のすべての要素が$k$以上か」は「$b$の最小値が$k$(以上)^[1]か」と言い換えられる．この判定を$O(n)$より軽いオーダで行いたい．こうするとSegment Treeの利用が見えてくる気がする．配列の区間$[1,n]$の最小値を管理すればよいのでRange Minimum Query問題に帰着される．計算量は$O(n+mlogn)$となり，間に合う．

別解(editorial)

「$cnt[i]:=$complexityが$i$の問題数」「$exist[j]:=$round$j$に含まれる問題数」とすれば，complexity$i$の問題に対して次のように更新可能：$cnt[i]$++; $exist[cnt[i]]$++^[2]．「complexityが同じ問題の$k$(=$cnt[i]$)個目はround$k$に入る」と書くと至極当然の事実をコードに落としただけに見えるのだけど，浮かばなかった．$O(m)$． 解答例

別解2

順位表の上位2人がこの解法だったので気になって．順序付き多重集合(MultiSet)を利用する． 解答例

最初の解法と同様に「$b[i]$:=$i$の出た回数」という配列を用意する．このとき同様に$\min \{b[i]\}$が分かればよろしい．ここでMultiSet $S$を使う：$S$に$b[i]$の値を入れておけば，最小値も$O(logN)$で求められる．complexityが$i$の問題に対する更新としては，$b[i]$も$S$と別に持っておき，$S$から$b[i]$を1つ消して$b[i]+1$を1つ加え，$b[i]$++すればよい．

とは書いたがどういう場合に応用できるのかあまり理解しきれていない．$i$に依るクエリが無く，かつ$b[i]$の最大／最小値など（例えば「大きい順からn番目」も木を探索できれば行ける？^[3]）について知りたい場合に，更新前の値を$b[i]$として記録しておけば実現可能なのだろうか．

MultiSetはコンテスト中に何度かそれっぽいものを書いたもののライブラリにはしていなかったこともあり，とりあえずそのようにしてみた．正しく動くかはまだ余り確かめていない．

C. NN and the Optical Illusion

純粋な高校数学という感じがする． 解答例

大円$C$と1つの小円$c$について図示してみるとよさそう．$C$の中心を$O$，$c$の中心を$O'$とする．$O$から$c$に引いた接線を書き，その接点をTとすると斜辺$R+r$の直角三角形$OTO'$ができる．図を描くのをサボっているから分かり難いのだが，これについて$cos(360^{\circ}/2n)=\frac{\sqrt{(R+r)^2-R^2}}{R+r}$と立式できる．これを$R$について解きたい．というわけでwolframに投げると$R=\frac{rsin(\frac{\pi}{n})}{(cos(\frac{\pi}{2n}) - sin(\frac{\pi}{2n}))^2}$と変形してくれる．あとはこれを実装すればよい．

……と本番中は解いたのだけど，どう考えても$sin(360^{\circ}/2n) = \frac{R}{R+r}$を解くべきだった．wolframも要らないし．本番ではwolframをうまく使えずに時間を浪費したこともあり，これに気付かなかったのが惜しまれる．

D. Dasha and Chess

どこから考えればいいか何も分からなかった． 解答例

解説

公式よりUnofficial Editorialなる記事のほうが詳しい． 解法をざっと説明すると，キングを初期位置によらずとりあえず中央に持っていき，盤面を4象限に分ける．一番ルークが少ない象限を背にして斜めに移動すると，相手はルークを逃がしきれず，こちらの必勝となる．

なぜ逃がしきれないか．こちらの勝利条件はルークと行または列を共有することだった．これは象限で考えると，そのルークを含む象限とそれに隣接する計3象限に当たり判定があるということであり，その何れかに入ればよい． いま最もルークの少ない象限を背に斜めに進むとき，それ以外の3象限のルークを攻めていることになる． 各象限のルーク数は最も均衡な状態でも166,166,167,167であるから，攻撃対象の象限にあるルークは高々500個．キングの移動は最大で499回であるから，相手はルークを逃がしきれない．

どうやって思いつけばいいのかわからないが，ポイントとなりそうな点だけ：

• キングをとりあえず中央に持ってくるとどの初期位置でも戦略を同じにできる
  • 盤面の中央から4象限に分けると対称的になるというのもありそう
• 斜め移動のほうが効率が良い
  • 縦または横移動だと移動前と行または列を共有するため，狙えるルークが少ない
  • 縦または横移動で狙えるルークは斜めでも狙えるため，斜め移動を選んで損することもない

移動中にルークと重なってはならないという制約に注意（縦横移動で衝突することはない．斜め移動の場合は縦または横の何れかにだけ移動すればよい）．中央のマス(500,500)を(499,499)と勘違いして1WA．

E. Andrew and Taxi

コンテスト中はDよりもこちらのほうを読んでいたが何も分からず． 解答例

重み付き有向グラフに対してコスト$c$で重み$c$以下の辺を好きなだけ反転させられるとき，閉路を消すために必要な$c$の最小値を求める問題．有向辺をひっくり返した後にさらに閉路ができてしまう場合にどう対処すればいいのか分からなかった．

解説(editorial)

これもEditorialに加えて先のUnofficial Editorialも参照した．まず単調性から$c$についての二分探索が考えられる．以下では$c$を固定する．

重みが$c$以下の辺の向きを考える前に，それ以外，すなわち$c$を超える辺について考えると，これらは操作によって不変．よってここに閉路が含まれていたらその時点で失敗．含まれていないとき，グラフ全体が閉路を持たないような重み$c$以下の辺の向きを決めたい．

解法としては先のグラフに対してトポロジカルソートなるものをすればよい．トポロジカルソートとはDAGに対しすべての有向辺の始点が終点より前に来るようにノードを順序付けすることらしく，DAGなら必ず可能とのこと．有向グラフにおいて閉路の存在と後退辺（DAG順で）の存在は同値だから，この順序に従わない有向辺があると失敗．逆にこの順序に従って$c$以下の辺の始点終点を決定すると後退辺が作られることはないから閉路もない．これが先の疑問に対する回答．

以上より二分探索に$O(\log \max \{ c \})$，トポロジカルソートに$O(|V|+|E|)$の合計$O((|V|+|E|)\log \max \{ c \})$で求解可能．ところで二分探索の対象はグラフにある辺の重みだけに絞ってよいから$O(\log m)$に落とせるが特に必要ない．

トポロジカルソートの実装はwikipediaの閉路検出機能付き版を参考にしたのだが，途中で検出する必要が無ければ模範解答にもあるように普通にトポロジカルソートした結果のサイズが$|V|$かを見れば済んだらしい．

地味に最後の辺を反転させるか決める部分の実装に若干迷ったが，無向グラフと見て隣接リストを作った上で相手の点がトポロジカルソート順で後か，かつ初期状態と異なるかを見ればよい．トポロジカルソート順で後かどうかは今までの列に表れたかを単に配列に入れておけば済むので大したことない．初期状態との比較を入れ忘れて1WA．

---

1. 今回は最小値がkになった途端にkが加算されるため，最小値が$k$より大きくなることはない． ↩︎

2. 実装においては順番を逆にしている．$exist$を説明では1-indexed, 実装では0-indexedで考えているため． ↩︎

3. OCamlの標準ライブラリのMapで行えるかはわからない（splitでバラしていけば実現可能な気はするが未検証）．そのうち競プロ用に内部実装を露出させたTreapなどを実装したい気持ちはある． ↩︎