Croatian Olympiad in Informatics (COI) 2022 - Codeforces
2022年5月30日にCOCIの最終ラウンド (COI) があった。Openコンテストに参加した。非公式解答を書いておく。
COCIについて
COI は IOI のクロアチア大会および代表選考の大会である。COI はクロアチアの中学生高校生のための大会だがオープンコンテストが COCI で開かれており、無関係の人も COI の問題に挑戦することができる。
コンテストまとめ
| ジャンル | 難易度 | |
|---|---|---|
| 問1 | インタラクティブ、基礎よりの知識問題 | 易 |
| 問2 | IOIコミュニケーション | 難 |
| 問3 | グラフ | 難 |
| 問4 | 木グラフ、データ構造 | 普通 |
問1：Mađioničar
問題
インタラクティブの問題である。ジャッジは長さ N の文字列を持っている。あなたは次の質問を最大 2×N 回行うことができる。
- 質問 query(i, j)：文字列の i 番目から j 番目の部分文字列 (連続、両端を含む) が回文ならば 1 を返答する、回文でないならば 0 を返答する
ジャッジが持っている文字列の部分文字列の中で最長の回文の長さは何文字であるか求めよ。
解答
回文を線形時間で求める Manacher アルゴリズムを用いる。ほぼ Manacher そのままで文字列の一致の判定部分を質問に置き換えてやればよい。
そのままだと 2N 回の質問の上限を超えてしまう場合は、長さ1の自明な質問や、同じ質問の繰り返しをしないようにしてやればよい。
問2：Mensza
IOIコミュニケーション形式の問題。アイデア勝負のパズル系の問題なのでネタバレ防止の為に別記事に書き記す。
natsugiri.hatenablog.com
問3：Povjerenstvo
問題
N人の人がいる。「人xは人yが嫌い」というような情報が M 個与えられる。N人のうちの何人かを委員会の委員にしたい。ただし、嫌いな人と一緒に委員会を行いたくないので、全ての人は以下の条件を満たさなければならない。
- 「あいつは委員にしない」：人xが委員であるならば、人xが嫌いな人は一人も委員ではない
- 「あいつが居るから委員をやらない」：人xが委員でないならば、人xが嫌いな人が少なくとも一人は委員である
入力の制約として、「人xは人yが嫌い」を頂点 x から頂点 y への辺として、N 頂点の有向グラフを作ると奇数頂点のサイクルは存在しないことが保証されている。
条件を満たすような委員会の委員の割り当てを求めよ（複数考えられる場合はどれか一つを求めよ）。割り当てが存在しないならばそれを指摘せよ。
1 ≦ N ≦ 500000
0 ≦ M ≦ 500000
解答
強連結成分分解をする。1つの強連結成分は単一の頂点、もしくは奇数サイクルを持たない、という特徴を持つ。
トポロジカルソートの逆順に貪欲に割り当てを決めていく。N 人全ての人について、委員であるかないか不定の状態からスタートする。各頂点について、
- すでに嫌いな人が委員に決まっているならば、委員にしない
- すべての嫌いな人が委員ではないと決まっているならば、委員にする
と、後退解析に次々に連鎖して決めていく。連鎖が止まったら、適当な人を委員にしてまた後退解析を継続する。
これでうまくいくが証明ができてない。
問4：Vinjete
問題
木グラフが与えられる。辺を通るときは M 種類のアイテムのうち幾つかを持っている必要があり、辺 i を通るときにはアイテムの番号が L[i] から R[i] までの全てを持っている必要がある。
頂点 1 から頂点 x まで最短パスで移動するときに、いくつのアイテムを持っている必要があるか、全ての x (2 ≦ x ≦ N) について求めよ。
1 ≦ N ≦ 100'000
1 ≦ M ≦ 1000'000'000
解答
DFSをしながら、必要なアイテムをセグツリーでアップデートしていく。各辺を通るときに、各アイテムについて「必要になった回数」を +1 すると「必要になった回数が 0 回」のアイテムを数えることができる。
セグツリーのノードは「x番からy番のアイテムの中で必要になった回数の最小値は c 回、そのようなアイテムは k 個ある」という状態を持つ。c が 0 であるか確認したのちに k が必要にならないアイテムの個数になる。最小値の更新は区間に加算する遅延評価のセグツリーでできる。
M が大きい時は座標圧縮することで 2N+2 以下にすることができる。
このように「区間に加算・区間の 0 の個数」という問題は 0 未満にならないことがわかっているならば「区間に加算・区間の最小値の個数」を解くことで求められる。
