https://csacademy.com/contest/ioi-2016-training-round-5/summary/
$N$行$M$列に電球が並んでおり、それぞれの電球のON/OFFの情報が与えられる。この電球に対して以下の操作を行い、すべての電球をOFFにすることが可能であればそのような手順のなかで最小のものを、不可能な場合は-1を出力せよ。
前提として、行に対する反転と列に対する反転は分けて考えてよい。このとき、行および列を1列目/1行目の値で2つのグループに分け、それぞれどちらかのグループのみに操作を行うことを考える。このとき操作の方法は4通り存在し、この4通りの操作ですべての電球をOFFにできない場合にはどうやってもすべての電球をOFFにすることはできない(すべてのOFFの状態から電球を点灯させていくことを考えればすぐにわかる)。
また、行に対する操作と列に対する操作を必ずペアにして行わなくてはならないという制約より、行に対する操作の数と列に対する操作の数の偶奇が一致していなくてはならないことがわかる。よって、上述の4通りの操作をすべて試し、条件に合うもののなかで最小の操作を出力すればよい。
自力AC。典型っぽい。ちゃんと考えれば操作を実際にシミュレートする必要はないはずだが、考えるのが面倒だったのでシミュレートした。
ある文字列$S$に対して、最後の文字の次の文字が1文字目であると考えた場合の部分文字列を循環部分文字列と呼ぶ。たとえば、"ABCD"や"EFAB"は"ABCDEF"の長さ4の循環部分文字列である。
'A', 'B'の2種類の文字からなる長さ$N$の文字列$S$が与えられるので、$S$が以下の条件を満たしているかどうかを出力せよ。
文字列が'A', 'B'のどちらかしか含まないとき、明らかにBalancedである。そうでないとき、与えられた文字列に対して以下のような操作を行うことを考える。
文字列に対して上記の操作を行うことで新たな文字列を作る操作をEncodeと呼ぶことにする。文字列のEncodeを繰り返すことで与えられた文字列がBalancedかどうか判断できる理由(Encodeの前後でBalancedかどうかが変化しない理由)を、以下に示す。
上記について、すべて逆も成り立つ。一度のEncodeで文字列の長さは必ず半分以下になるので、全体でO($|S|\log|S|$)となる。
解説AC。難しくないか……？いわゆる「不変量を探す問題」に近いものを感じるが、どうやったら思いつくのかわからない。証明がきちんとできている自信がないので、抜けがある可能性が高い。
二次元平面上の$K$個の点の座標と、$M$個の三角形が与えられる。三角形の頂点のうち1つは必ず原点にあり、与えられる座標はすべて非負の整数である。各三角形について、内部に$K$個の点のうち1つ以上が含まれているかを出力せよ。なお、三角形の辺上に点が乗ることはない。
はじめに、三角形の一辺が$x$軸上に存在し、もう一辺が$y$軸上に存在する場合を考える(部分点)。点はすべて第一象限に存在し、三角形の一点は必ず原点に乗っているから、ある三角形の内部に$K$個の点のうち1つ以上が入っているとき、$K$個の点の凸包を構成する点のうち1つ以上が三角形の内部に入っていることになる。このことから、$K$個の点の凸包を構成する点以外の点について調べる必要はないことがわかる。
凸包を構成する方法の1つに、点を$x$座標でsortして下側凸包と上側凸包を求める方法がある。この要領で、点を原点からの偏角でsortした場合の下側凸包(左下側凸包と呼ぶ)を考えると、与えられた直角三角形の中に点があるかどうかは左下側凸包の点を調べるだけでわかり、左下側凸包の各点と直角三角形の斜辺との距離は下に凸であるから、もっとも斜辺に近い点を三分探索(傾きの二分探索)で求めることができる。このようにして求めた点が三角形の内部に含まれるかを調べれば良いので、凸包の構成がO($K\log K$)、各クエリがO($\log K$)となり、全体でO($(K+M)\log K$)となる。
次に、三角形の原点以外の2点が第一象限内で自由な場合を考える(満点)。基本的な考え方は部分点解法と同じだが、三角形の原点以外の2点A, Bが原点となす角を$\angle AOB$とすると、偏角がこの角度の範疇にない点は三角形に含まれ得ないという点が異なる。偏角が$\angle AOB$の範疇にある点のみの左下側凸包を考えればよいのだが、毎回凸包を構築し直していては全体でO($KM$)となり間に合わない。
ここで、左下側凸包をノードとした完全二分木を考える。これはいわゆるセグメント木であるが、update関数は必要ない。葉には各点1点のみの左下側凸包(つまりその点自身)をもち、各ノードは自分の2つの子がもつ左下側凸包をマージしたものを持っている。左下側凸包のマージはO($K$)で可能なので、$\log K$段の完全二分木を構築するには時間計算量O($K\log K$)ですむ。
クエリに答える際はセグメント木と同様に完全二分木を下っていき、値を返す代わりにそのノードがもつ左下側凸包で三分探索を行い、三角形のなかに含まれる点があるかどうかのbool値を返すことにすれば、各クエリについてO($\log K$)個の凸包について三分探索を行うことになり、時間計算量はO($\log^2 K$)となる。よって、全体の計算量はO($ (K+M)\log^2 K$)となり、この問題が解けた。
解説AC。難しいが、なるほどと思った。凸包を実装したのははじめてで、更にセグ木に+, min, max以外の演算を乗せたのもはじめてだったので非常に勉強になった。
ある無向グラフ$G$に対して、距離2以内の点対をすべて辺で結んだグラフを$G^2$とよぶ。いま、$G$が木であることが分かっている。$G^2$が与えられるので、$G$としてあり得るグラフを1つ出力せよ。
あるノード$v$と、$G$において$v$と隣接しているすべてのノードは$G^2$においてクリークをなす。ここで、あるノード$v$と、$G^2$において$v$と隣接しているすべてのノードが$G^2$においてクリークをなしているとき、$v$は$G$において葉であってよい。なぜならば、$v$が$G$において葉ではないとき、$G$において$v$と隣接する2頂点($u, w$とする)と、$G$において$w$と隣接する$v$でない頂点($x$とする)について、$G^2$において$(u, v)$, $(v, x)$は隣接するが$(u, x)$は隣接しないためである。$u, w$がともに葉であるとき(つまり、木がstar graphであるとき)にはその限りではないが、その場合には$G^2$全体がクリークをなすので、$v$が葉となるような木のなかで同じ$G^2$を構成するものが存在する。
はじめに、上述の方法で葉になりうるノードを1つ探し、これを$v$とする。$G$において$v$と隣接しているノードは1つしかなく、これを$u$とする。$u$の候補は$G^2$において$v$と隣接するノード全てなので、$O(N)$個存在する。ここで、これらの各候補について$G^2$の元となる木$G$を構築できるかどうかを調べることを考える。
もし$v, u$が正しく定まっているならば、以下の方法で正しい木$G$を構築することができる。
$G^2$において$v, u$の両方に隣接しているすべてのノードは、$G$において$u$と隣接しているはずである。同様に、$G^2$においてノード$a$と$a$の1つ前のノードに隣接するすべてのノードは、$G$において$a$と隣接していることがわかる。このようにして、各ノードについて隣接しているノードを増やしていくと最終的に$G$を構築できる。
これをすべての$u$候補について行い、できた$G$から$G^2$を構築する。ここで問題によって与えられた$G^2$と同じものができればそれが正解である。計算量は、$v$の特定が$O(N^3)$、各$u$候補について$G$の構築が$O(M)$、$G^2$の構築・比較が$O(N^2)$なので全体で$O(N(N^2+M))$となる。
解説AC。データ構造問題だった前問とは異なっていわゆる天才構築っぽい問題だった。考えているときは全く分からなかったが、解説を読むとなるほどなと思う(それはそう)。