CF 782 D - Innokenty and a Football League
問題
問題概要
サッカーチームが個ある。それぞれのサッカーチームにはチーム名があり、2単語から構成されている。
各チームの省略形を3文字で決定したい。各チームに対して、省略形の候補は2種類ある：
- 1単語目のprefix3文字を取る。
- 1単語目のprefix2文字と2単語目の頭文字を取る。
ただ、あるチームが2つめの候補を選ぶためには条件がある。それはチーム
が2つめの候補を選んだ場合、他のチームはチーム
の1つめの候補を、「1つ目の候補として」選んでいてはいけないということである。もちろん、同じ省略形を複数のチームが使うことも許されない。
チームの省略形の割り当てとして、正当なものがあればその割当て方法を、不可能ならNOと答えよ。
- 各チームの2つの単語はそれぞれ3文字以上20文字以下
アイデア
最近2-SATを使う問題(http://codeforces.com/problemset/problem/875/C)にコンテスト中に遭遇した(残念ながら時間内に解けなかった)ので、それもあって2-SATの問題をいくつかやっていた。以前に出会ったこの問題も変な貪欲をやろうしていたが、考慮しきるのは大変だし見落としがちなので、条件を作って2-SATで解いてみる。
リテラルを、1つ目の候補を採用することを
true、2つ目の候補を採用することをfalseとして表すことにする。
クロージャとして作らなければならないのは、まず大前提として同じになってしまうのは避けなければならない。
あとは、概要のところにも書いたとおり、あるチームが2つめの候補を取る場合は、他のチーム
が、チーム
が1つめの候補を、1つめの候補として採用していてはならないということである。これは、
と
の1つめの候補が同じ場合に、
というクロージャを追加するということを意味する。これで2-SATの条件を盛り込めるので、後はSCCによりこれを解く。辺の数は
なので、十分間に合う。
実装(C++)
続きを読むCF 871 C - Points, Lines and Ready-made Titles
問題
問題概要
2次元平面上に点が個ある。
番目の点の座標は
である。各点に対して、x軸に平行な線を描く、y軸に平行な線を描く、何も描かないのどれかの操作を選ぶことが出来る。
この
個の点から描かれた線を平面上に描かれた画像と見なすと、画像は何通りの可能性があるか、
で割った余りを答えよ。
- 全ての点は平面上で異なる位置にある。
アイデア
全ての点に対して操作は3通りあるので、全体としては通りあるけど、同じy座標の点がそれぞれ横に線引いたら被るしどうやってその重複する数え上げを排除しよう...とか悩んでいた。
点を基準にするのではなく、出来上がる画像を基準にして考える。線が発生し得るx座標に対して小さい順に、同様にy座標に対しても
として、これらを頂点とし、このxとyを結ぶ辺として各点を考える。
上のグラフを考えると、今回できる操作は各辺に対してその辺をつなぐ2点のどちらかをonに出来るということに対応する。連結成分ごとに考えてみると(連結成分の頂点数をとする)、連結成分が木なら、全部の頂点をonにするということ以外は出来るので、
通りが出来る。木ではなく、閉路が1つでもできるなら全ての通りを実現できるので
通りが出来る。
