裏紙

ほぼ競プロ、たまに日記

CS Academy #53 - Parallel Rectangles

問題

CS Academy

問題概要

xy平面に点がn個与えられる。4点を選んで、それによって長方形を構成したいが、長方形のそれぞれの辺がx軸とy軸にそれぞれ平行になるようにしなければならない。 そのような4点の選び方は何通りあるか。

  •  1 \le n \le 10^5
  •  1 \le x_i , y_i \le 10^5

イデア

1つ目の方針として、 x_1を固定して、それ以外のx_2に対して、それぞれのx座標でy座標が共通で存在するの点((x_1 , Y)(x_2 , Y)という意味)がcnt(y)個あるなら、 _{cnt(y)} C _2通りの長方形を作れるということになる。これは、x座標の候補が多いと間に合わないのは明らか。

2つ目の方針としては、x座標を1つ固定する(Xとする)。そのx座標がXのものに対して、y座標のペアをmapによって数え上げる(++map[(y1,y2)]みたいに)。すると、その各ペアに対して、 _{map [(y_1 , y_2 ) ]} C _2 通りの長方形を作れるということになる。しかし、これは同じx座標上に点があるとペアの数が大量になってmapが抱えるkeyの数が大きくなってしまう。

この2つの方針を組み合わせることを考える。同じx座標にある点の個数で各x座標を2つのタイプに分ける:

  1. そのx座標に点がS個より多く存在
  2. そのx座標に点がS個以下存在

すると、長方形としてx座標を2つ選んだ時、そのx座標のペアは

  1. 両方がtype1
  2. type1とtype2
  3. 両方がtype2

のパターンに分類できる。パターン1と2は前者、3は後者で処理する。

前者に関しては、固定するx_1はtype1のx座標のみを考える。すると、type1の性質により、この固定するx_1はたかだか\frac{n}{S}個になる。そして、この固定した1つのx_1に対して、方針1はO(n)の時間がかかる。

後者に関しては、最悪の場合を考えると(S個もつx座標が大量にある状況)、mapが抱えることになるのは\frac{n}{S} * _S C _2個のkeyになる。

後者にはmapのlogが乗ることも考えると、S\sqrt{n}よりも小さくするのがバランスを取るためにはよい。今回はS=70を採用した。色々いじってみたけどギリギリすぎる(自分のコードがダメなのかもしれない...)

実装(C++)

続きを読む

CF 782 D - Innokenty and a Football League

問題

Problem - D - Codeforces

問題概要

サッカーチームがn個ある。それぞれのサッカーチームにはチーム名があり、2単語から構成されている。

各チームの省略形を3文字で決定したい。各チームに対して、省略形の候補は2種類ある:

  1. 1単語目のprefix3文字を取る。
  2. 1単語目のprefix2文字と2単語目の頭文字を取る。

ただ、あるチームiが2つめの候補を選ぶためには条件がある。それはチームxが2つめの候補を選んだ場合、他のチームはチームiの1つめの候補を、「1つ目の候補として」選んでいてはいけないということである。もちろん、同じ省略形を複数のチームが使うことも許されない。

チームの省略形の割り当てとして、正当なものがあればその割当て方法を、不可能ならNOと答えよ。

  •  1 \le n \le 1000
  • 各チームの2つの単語はそれぞれ3文字以上20文字以下

イデア

最近2-SATを使う問題(http://codeforces.com/problemset/problem/875/C)にコンテスト中に遭遇した(残念ながら時間内に解けなかった)ので、それもあって2-SATの問題をいくつかやっていた。以前に出会ったこの問題も変な貪欲をやろうしていたが、考慮しきるのは大変だし見落としがちなので、条件を作って2-SATで解いてみる。

リテラルx_iを、1つ目の候補を採用することをtrue、2つ目の候補を採用することをfalseとして表すことにする。

クロージャとして作らなければならないのは、まず大前提として同じになってしまうのは避けなければならない。

あとは、概要のところにも書いたとおり、あるチームiが2つめの候補を取る場合は、他のチームjが、チームjが1つめの候補を、1つめの候補として採用していてはならないということである。これは、ijの1つめの候補が同じ場合に、 \lnot ( lnot x_i \land x_j ) = x_i \lor \lnot x_jというクロージャを追加するということを意味する。これで2-SATの条件を盛り込めるので、後はSCCによりこれを解く。辺の数はO(n^2)なので、十分間に合う。

実装(C++)

続きを読む

CF 871 C - Points, Lines and Ready-made Titles

問題

Problem - C - Codeforces

問題概要

2次元平面上に点がn個ある。i番目の点の座標は(x_i , y_i)である。各点に対して、x軸に平行な線を描く、y軸に平行な線を描く、何も描かないのどれかの操作を選ぶことが出来る。 このn個の点から描かれた線を平面上に描かれた画像と見なすと、画像は何通りの可能性があるか、10^9 + 7で割った余りを答えよ。

  •  1 \le n \le 10^5
  •  -10^9 \le x_i , y_i \le 10^9
  • 全ての点は平面上で異なる位置にある。

イデア

全ての点に対して操作は3通りあるので、全体としては3^n通りあるけど、同じy座標の点がそれぞれ横に線引いたら被るしどうやってその重複する数え上げを排除しよう...とか悩んでいた。

点を基準にするのではなく、出来上がる画像を基準にして考える。線が発生し得るx座標に対して小さい順にX_1 , X_2, \ldots , X_a、同様にy座標に対してもY_1 , Y_2 , \ldots , Y_bとして、これらを頂点とし、このxとyを結ぶ辺として各点を考える。

上のグラフを考えると、今回できる操作は各辺に対してその辺をつなぐ2点のどちらかをonに出来るということに対応する。連結成分ごとに考えてみると(連結成分の頂点数をVとする)、連結成分が木なら、全部の頂点をonにするということ以外は出来るので、2^V - 1通りが出来る。木ではなく、閉路が1つでもできるなら全ての通りを実現できるので2^V通りが出来る。

実装(C++)

続きを読む