2020-01-14

第6回ドワンゴからの挑戦状予選 E - Span Covering

本番中実装しきれなかったけど、公式解説と違う方法で解いたので記録。

解法

包除原理の適用

土地を $X$ 個のマスが並んだものとして扱います。このマスのうち0個以上のマスを選んだ集合 $z$ について、 $z$ に含まれるマスだけに全てのシートを置く（ $z$ の全てのマスを埋める必要はない）ような置き方の数を $C(z)$ とします。 $z$ として考えられる $2^{X}$ 個全ての集合からなる集合を $Z$ とすると、包除原理より答えは

$\displaystyle \sum_{z\in Z} (-1)^{X-|z|}C(z)$

となります。

この $z$ を全て数えるのはもちろん無理なので上手くまとめます。 $z$ に含まれるマスの、連続しているマスの長さの組に注目します。例えば $z$ に含まれるマスを o、含まれないマスを . として $X$ 個の並びが ..ooo..o..o. のようになっている場合、連続しているマスの長さは順に $3, 1, 1$ です。これを $A(z) = \lbrace 3, 1, 1\rbrace$ のように配列として書くことにします。

$z$ にシートを置く置き方の総数はこの $A(z)$ のみに依存します。そしてある配列 $A$ に対応するような $z$ の個数は、連続しているマス領域の数 $n$ と $z$ に含まれるマスの総数 $s$ を用いて $_{X-s+1}C_{n}$ と計算できます。

f:id:betrue12:20200115060113p:plain

つまりこの $n, s$ が等しいような $A$ についても扱いをまとめて良いことになります。そのためやるべきことは、

$s$ 個のマスを連続する $n$ 個のマス領域に分割する方法 $A$ 全てについての、その $A$ に全てのシートを置く置き方の個数の総和

を全ての $s, n$ について求めることになりました。これに係数 $_{X-s+1}C_{n}(-1)^{X-s}$ を掛けて合計したものが答えになります。

DPを組む

ではこれをどのように求めましょうか。連続するマス領域を1つずつ増やしていくDPを検討します。

まず、各シートについて「そのシートを置ける場所の数」は独立です。これを全てのシートについて掛け合わせたものが置き方の総数になります。

長さ $x$ の連続マス領域を1つ追加した場合、長さが $x$ 以下のシートそれぞれについて置ける場所の数が増えます。具体的にシートの長さが $L_{i}$ である場合、置ける場所は $\max(0, x-L_{i}+1)$ 個増えます。本解法でやりたいことは、このときのシートの置き方の総数の変化を変化前後で変動する倍率を掛けるように扱うことです。

f:id:betrue12:20200115061647p:plain

そしてこの比率を計算するのに $A$ の要素を全て覚えておく必要はありません。シートの長さが $L_{i}$ であり、 $A$ のうち長さ $L_{i}$ 以上の連続マス領域だけについてその領域数が $n$ 、マス総数が $s$ であったとします。このときこのシートを置ける場所の数は $s-nL_{i}+n$ 個あります。そして $L_{i}$ より短い連続マス領域は置ける場所数に影響しません。

このことから、連続マス領域を長いものから順に足していくと扱いやすくなります。なぜならば連続マス領域を足した時に影響を受けるシートが徐々に減っていき、そして影響を受けるシートについては $n, s$ の値だけを用いて連続マス領域を足す前後のシートの置き方を計算できるという非常に良い性質が生まれるからです。これを用いて以下のようなDPの遷移を計算できます。

$dp\lbrack x \rbrack\lbrack n \rbrack\lbrack s \rbrack$ ： $s$ 個のマスを長さ $x+1$ 以上の連続マス領域 $n$ 個に分割する方法 $A$ 全てについての、その $A$ に全てのシートを置く置き方の個数の総和

$dp\lbrack x \rbrack\lbrack n \rbrack\lbrack s \rbrack$ から長さ $x$ の連続マス領域を $k$ 個置いて遷移することを考えます。遷移先は $n_{2}=n+k, s_{2}=s+xk$ として $dp\lbrack x-1 \rbrack\lbrack n_{2} \rbrack\lbrack s_{2} \rbrack$ です。このときの係数を計算します。

都合上 $n \gt 0$ 、つまり遷移前に1つ以上の連続マス領域が既に存在しているとします。長さ $x$ の連続マス領域を足す際には、 $L_{i} \le x$ であるようなシート $i$ について置ける場所の数が変動します。これまで追加されている連続マス領域は全て長さが $x$ より大きいので、これらのシートを置ける場所数の積は

遷移前： $\prod_{L_{i} \le x}(s-nL_{i}+n)$

として計算され、長さ $x$ のシートを $k$ 個置いた後は先ほどの $n_{2}, s_{2}$ を用いて

遷移後： $\prod_{L_{i} \le x}(s_{2}-n_{2}L_{i}+n_{2})$

と計算されます。これらの値は $L_{i}$ を予めソートして、各 $n, s$ ごとに累積「積」を前計算しておけば $O(1)$ で得られます。

$dp\lbrack x \rbrack\lbrack n \rbrack\lbrack s \rbrack$ にこの遷移前後の比を掛け、さらに $k$ 個の領域を既存の $n$ 個の領域の並びにどう混ぜるかの係数 $_{n+k}C_{k}$ を掛けて、 $dp\lbrack x-1 \rbrack\lbrack n_{2} \rbrack\lbrack s_{2} \rbrack$ に遷移させれば良いです。

$n=0$ からの遷移を含めると少し面倒なのですが、以下リンク先のACコードでは以下のように対処しています。

遷移前に $n=0$ であり、最初に追加する連続マス領域の長さが $x \lt \max L_{i}$ である場合には遷移しない。（一番大きいシートの置き場所がなくなってしまうため）
遷移前に $n=0$ である場合、遷移前の置ける場所数は $1$ とする。
遷移後も $n_{2}=0$ である場合、遷移後の置ける場所数も $1$ とする。
最後に答えを計算する際に、 $n=0$ であるようなものは答えに算入しない。（これは本来 $0$ であるべきだが、上記の計算手順を踏むと $dp\lbrack 0 \rbrack\lbrack 0 \rbrack\lbrack 0 \rbrack = 1$ となってしまうため）

計算量について

最後にこの解法の計算量を評価しておきます。前計算は $O(NX^{2})$ です。

DPパートは $x, n, s, k$ についての4重ループです。ここで $n$ は遷移前に長さ $x+1$ 以上の連続マス領域を置いた個数、 $k$ は長さ $x$ の連続マス領域を新しく置く個数なので、最大値はおよそ $\frac{X}{x}$ になると考えられます。 $s$ は評価が難しいのでおよそ $X$ 通りだとしておきます。

するとループが回る回数はおよそ $X\sum_{x=1}^{X}(\frac{X}{x})^{2}$ と見積もることができて、正整数のマイナス2乗和は定数に収束するので $O(X^{3})$ と評価できます。

ACコード

Submission #9501341 - Dwango Programming Contest 6th

2020-01-12

第6回ドワンゴからの挑戦状予選 C - Cookie Distribution

AtCoder プログラミング競技プログラミング

C - Cookie Distribution

解法

式変形と言い換え

全てのクッキーの配り方の集合を $S$ 、答えを $A$ とします。答えは $(c_{1}\times\cdots\times c_{N})$ の期待値に全ての配り方の通り数を掛けたものなので、 $(c_{1}\times\cdots\times c_{N})$ を全ての配り方について合計したもの、つまり以下のように表現できます。

$A = \displaystyle \sum_{s\in S} \left(c_{1}\times\cdots\times c_{N}\right)$

実際には各 $c_{i}$ は配り方 $s$ に依存するので $c_{i}(s)$ などと書くべきですが、煩雑になるので省略しています。

期待値、および期待値とほぼ同等な数え上げ（「全ての場合について○○の値を合計したものを求めよ」タイプ）の問題で非常によく使うのが「期待値の線形性」です。確率変数の和の期待値は、それらが独立であるかどうかに関わらずそれぞれの期待値の和に分離できるので、とても強力です。

一方この問題で問われているような積の形はとても扱いにくいです。ということで、展開して和として考えましょう。

「人 $i$ が日 $d$ にクッキーをもらったなら $1$ 、もらっていないなら $0$ 」という値を $x_{id}$ として表記します（これも配り方 $s$ に依存する値です）。そうすると $c_{i} = x_{i1} + \cdots + c_{iK}$ となります。

簡単のため $N=K=2$ として、答え $A$ を以下のように展開してみます。

$A = \displaystyle \sum_{s\in S} \left((x_{11}+x_{12})\times(x_{21}+x_{22})\right) = \sum_{s\in S}\left(x_{11}x_{21} + x_{11}x_{22} + x_{12}x_{21} + x_{12}x_{22}\right)$

このシグマは各項ごとにばらせます。これがまさに「期待値の線形性」です。

$\displaystyle A = \sum_{s\in S}x_{11}x_{21} + \sum_{s\in S}x_{11}x_{22} + \sum_{s\in S}x_{12}x_{21} + \sum_{s\in S}x_{12}x_{22}$

各項は

それぞれの人 $i$ について「この日にクッキーをもらったかどうかに注目することにする」という日 $d_{i}$ を選ぶ選び方

と対応しているので、それら全てについて

全ての $x_{id_{i}}$ が $1$ である、つまり全ての人 $i$ がそれぞれ注目した日 $d_{i}$ においてクッキーをもらっているような配り方の数

を合計したものが答えになる、と解釈することができます。図示すると以下のようなイメージです。

f:id:betrue12:20200112153100p:plain

ここまでの式変形と言い換えが第1ステップです。

DPで数える

この値をDPで求めます。先ほど見たように、答えは「それぞれの人 $i$ が注目する日 $d_{i}$ を選ぶ選び方」に対する「全ての人 $i$ が日 $d_{i}$ にクッキーをもらっている配り方の数」の合計なので、これを同時にDPで処理していかないといけません。

日を1つずつ見ていくDPを組みます。状態を以下のように定義します。

日 $1$ から日 $k$ までを見て、これらの日のクッキーの配り方が決まり、これらの日のうちのどれかを注目する日 $d_{i}$ とするような人についてだけ $d_{i}$ が決まっていて、その人数が $n$ 人であるとする。このような状態に含まれる、「既に決まっている $n$ 人についての注目する日 $d_{i}$ の選び方」と「 $n$ 人全てがそれぞれ日 $d_{i}$ にクッキーをもらっているようなクッキーの配り方」のペアの個数を、 $dp\lbrack k \rbrack\lbrack n\rbrack$ とする。

ややこしいですね。例を以下のように図示します。

f:id:betrue12:20200112154840p:plain

$dp\lbrack k-1 \rbrack\lbrack n\rbrack$ からの遷移を考えます。 $k$ 日目において、新しく $d_{i} = k$ とするような人の人数を $j$ とします。そうすると $dp\lbrack k-1 \rbrack\lbrack n\rbrack$ から $dp\lbrack k \rbrack\lbrack n+j\rbrack$ に遷移するときに掛かる係数は、

まだ $d_{i}$ を決めていない人 $N-n$ 人から $j$ 人を選ぶ選び方 $_{N-n}C_{j}$
この $j$ 人にはクッキーを配ることが確定しているので、残り $a_{k}-j$ 枚のクッキーを渡す人を $N-j$ 人から選んで配る配り方 $_{N-j}C_{a_{k}-j}$

の積です。 $j$ としてはこれらの2項係数が適切に定義できる、つまり $j \le \min(N-n, a_{k})$ であるものだけを考えれば良いです。

これを最後まで計算すれば、 $dp\lbrack K \rbrack\lbrack N\rbrack$ が答えになります。

まとめ

なかなか大変な問題でした。 $(c_{1}\times\cdots\times c_{N})$ という式をそのまま扱おうとすると、日を軸にしても人を軸にしても「それまでに○枚クッキーを配った人が△人いる」みたいな情報を分割数のようなもので細かく管理しないといけないので、今回の制約では全く間に合いません。

期待値の問題においては「数え上げの軸を変え、線形性を利用してバラし、上手く独立に計算できるようにする」というのが王道なので、 $0,1$ 変数にバラして全部展開という多少強引な手段を使ってでも線形性を使える形に持ち込む、という考え方が重要になりました。

ACコード

Submission #9423985 - Dwango Programming Contest 6th

2020-01-12

第6回ドワンゴからの挑戦状予選 D - Arrangement

AtCoder プログラミング競技プログラミング

D - Arrangement

公式解説の読解がちょっとつらいので、それよりは分かりやすい解法になっているはず…

解法

まずは貪欲に作ってみる

「カード $i$ の右隣のカードがカード $a_{i}$ であってはならない」という条件は、そんなに厳しい条件ではないように思います。なのでまずは前から貪欲に順列を作ってしまい、そこから修正していく方針が取れないか考えてみましょう。

というわけで、まずは前から貪欲に以下のような置き方をしてみます。

1枚目にカード $1$ を置く。
2枚目から $N-1$ 枚目までを順に決める。このとき残っているカードの中で一番小さいカードを置ける（1つ前のカードの $a_{i}$ の値と異なる）ならそれを置き、置けない場合は2番目に小さいカードを置く。

この方法で $N-1$ 枚目までは必ずカードを置くことができます。またこれより辞書順で小さい順列を作ることは絶対にできません。もし最後に残ったカードを $N$ 枚目としてそのまま置けるなら、これが答えです。

最後が置けない場合の修正案

最後のカードが置けない場合を考えます。このときは既に置いた $N-1$ 枚のカードを崩すことになります。辞書順最小の答えを得るためには、既に置いたカードの順番を先頭からできるだけ長く保ちたいです。

カードを並べた状態が次の図のようになっているとしましょう。

f:id:betrue12:20200112090303p:plain

最後に残ったカードを $B$ とします。そして末尾に連続する $a_{i} = B$ であるカード群の先頭を $C$ 、そのさらに前を（存在する場合） $D$ とします。このとき $a_{D} \ne B$ であり、さらに $C$ を置けていることから $a_{D} \ne C$ でもあります。

このとき、先頭から $C$ までの順番を保持して $C$ より後ろを組み替えても、 $B$ をどのカードの後ろにも置けないので絶対に条件を満たせません。

では先頭から $D$ までの順番を保持して、 $C$ とそれ以降のカードを一旦取り除き、 $C$ があった位置に他のカードを置きます。このとき代わりに置ける可能性があるのは $B$ だけです。ここに $B$ 以外のカードを置いても、 $B$ をどのカードの後ろにも置けないという状況は全く同じだからです。

そして $B$ の次は「残っている中で最小のカード、ただしそれが $a_{B}$ と一致する場合は2番目」のカードを置きます。 $B$ を置いた時点で余りカードが2枚以上残っているならば、このとき必ず置けるカードが存在します。

これ以降、「次に置いてはいけないカード」は全て $B$ になります。そして $B$ はもう既に使っているので、残ったカードはどんな順番で置いても良いです。小さい順に貪欲で置けば答えを求められます。

$B$ の次を置けない場合

最後に残ったケース、先ほどの方法で $B$ の次に置けるカードが存在しない場合を考えます。

これはどのような状態になっているでしょうか。 $C$ とそれ以降を取り除いて $B$ を置いた時点で余りカードが2枚未満ということは、 $C$ は $N-1$ 枚目のカードだったということになります。そして $B$ の後ろに余りカード（つまり $C$ ）を置けないということは、以下のような状態になっているはずです。

f:id:betrue12:20200112090315p:plain

この図のように $a_{C} = B, a_{B} = C$ であり、さらに $D$ の位置にカードが存在する場合 $a_{D} \ne B, a_{D} \ne C$ です。

そのため以下の2つの置き方はいずれも $a_{B}, a_{C}, a_{D}$ の条件に違反せず、 $D$ のさらに前にあるカードの条件を考慮しても少なくとも一方は正当な並べ方であることが分かります。これらをどちらも試し、正当なもののうち辞書順で小さいものを答えとすれば良いです。

f:id:betrue12:20200112084418p:plain

※後のリンク先ACコードでは少し違う処理をしていて、 $C$ が $N-1$ 枚目のカードだった時点で $B, C, D$ の末尾での並べ方6通りのうち少なくとも1つは条件を満たすので、これを全探索しています。

ただし入力例2にある

2
2 1

の場合、この $D$ にあたるカードも存在せず、条件を満たす順列は存在しません。-1を出力するケースはこれだけです。

ACコード

Submission #9422728 - Dwango Programming Contest 6th

2020-01-07

Codeforces Round #612 (Div. 1) D. LCC

Codeforces プログラミング競技プログラミング

Problem - D - Codeforces

異常実装になったけどなんとか自力で解けた…

問題概要

数直線上に $n$ 個の粒子がある。粒子 $i$ は初期位置 $x_{i}$ 、速さ $v_{i}$ 、右に動く確率 $p_{i}$ で特徴づけられる。

この粒子を用いて以下の実験を行う。

まず各粒子の移動方向を確率に従って決める。粒子 $i$ が右に動く確率は $p_{i}$ 、左に動く確率は $1-p_{i}$ である。
全ての粒子が時刻 $0$ にそれぞれの初期位置 $x_{i}$ からスタートし、先ほど決めた向きにそれぞれの速さ $v_{i}$ で動く。
いずれか2つの粒子が衝突した時点で実験を終了し、その時刻を実験の経過時間とする。ただし永遠に粒子が衝突しない場合は経過時間 $0$ とする。

実験の経過時間の期待値を求めよ。この値は有理数になるので $\bmod 998244353$ の形式で出力せよ。

制約

$1 \le n \le 10^{5}$
$-10^{9} \le x_{1} \lt \cdots \lt x_{n} \le 10^{9}$
$1 \le v_{i} \le 10^{6}$
$p_{i}$ は百分率で与えられ、 $0 \le p_{i} \le 100$

解法

記法

連続するいくつかの粒子の移動方向を、L と R を並べたものとして記します。例えば2つの粒子が向かい合って移動していることを RL のように表記します。

以降の説明では $p_{i}$ は百分率の値ではなく確率そのものとして扱います。

衝突として考えるべきもの

いずれかの粒子が衝突した時点で終わりなので、考えるべき衝突は隣り合う2つの粒子のものだけです。粒子 $i$ と粒子 $i+1$ の衝突として以下のような場合があり得ます。

2粒子の移動方向が向かい合っている（RL）場合：時刻 $\frac{x_{i+1}-x_{i}}{v_{i+1}+v_{i}}$ で衝突する。
2粒子の移動方向がともに左（LL）であり、 $v_{i} \lt v_{i+1}$ である場合：時刻 $\frac{x_{i+1}-x_{i}}{v_{i+1}-v_{i}}$ で衝突する。
2粒子の移動方向がともに右（RR）であり、 $v_{i} \gt v_{i+1}$ である場合：時刻 $\frac{x_{i+1}-x_{i}}{v_{i}-v_{i+1}}$ で衝突する。

ここで、向かい合っている場合に衝突する時刻のほうが、同じ方向に動く場合に衝突する時刻より必ず早いことに注意しておきます。

全ての2粒子間においてこれらの衝突候補時刻を計算し、時刻順にソートしておきます。時刻は有理数として持っておいて、ソートのための比較関数では通分すると誤差がなくて良いです。

期待値を計算するアウトライン

まず期待値計算の概略を説明します。

時刻 $t$ で実験が継続している確率を $P(t)$ とします。 $P(0) = 1$ であり、この値は先ほど計算した衝突候補時刻でのみ減少します。

$P(t)$ を以下の図の赤線として図示すると、求めたい期待値は青く塗りつぶした領域の面積として計算できます。

f:id:betrue12:20200106233513p:plain

衝突候補時刻 $t$ において $P(t)$ が減少した量を $\Delta(t)$ と書くことにすると、この面積は $t\times\Delta(t)$ を全ての衝突候補時刻について合計したものとして計算することができます。図の青領域を横に短冊状に切るイメージです。

これでこの問題は、各衝突候補時刻を順番に見ていきながら「各粒子の移動方向が、それまでに起こりうる衝突が全て発生しないような組み合わせになっている確率」を計算し続ける問題に帰着できました。

向かい合う衝突だけを考慮した確率計算

まず簡単のため、向かい合う衝突だけを考慮します。「向かい合う向きであってはいけない」という2粒子間をUnion-Find等で連結することにすると、非連結な成分同士は独立に計算できるので、結局「連続するいくつかの粒子において、どの隣り合う2粒子間も RL の関係でない」という確率を求めれば良いことになります。

例えばインデックス $1, 2, 3$ の3粒子がこのような関係だとすると、衝突しないような向きの組み合わせは LLL, LLR, LRR, RRR の4通りです。その確率は

$S(1, 3) = (1-p_{1})(1-p_{2})(1-p_{3}) + (1-p_{1})(1-p_{2})p_{3} + (1-p_{1})p_{2}p_{3} + p_{1}p_{2}p_{3}$

と計算できます。上記のような計算を区間 $\lbrack l, r\rbrack$ について行った結果を $S(l, r)$ と表記することにします。

これを任意のインデックス区間について求めたいです。これは少しトリッキーなセグメント木を使って計算することができます。

それぞれの区間では、先ほどの $S(l, r)$ とともに

$L(l, r) = (1-p_{l})\cdots(1-p_{r})$
$R(l, r) = p_{l}\cdots p_{r}$

を持っておきます。区間 $\lbrack l, m\rbrack$ と区間 $\lbrack m+1, r\rbrack$ をマージする際には、

$L(l, r) = L(l, m)L(m+1, r)$
$R(l, r) = R(l, m)R(m+1, r)$
$S(l, r) = L(l, m)S(m+1, r) + S(l, m)R(m+1, r) - L(l, m)R(m+1, r)$

として計算できるため、これをマージ演算とするセグメント木で任意区間の計算結果を求めることができます。計算のイメージは以下の図のような感じ。

f:id:betrue12:20200107000152p:plain

Union-Findで連結成分を管理し、時刻 $t$ の時点での連結成分ごとの $S(l, r)$ の値を全て掛け合わせたものが $P(t)$ になります。

同じ向きでの衝突を考慮

同じ向きでの衝突を考慮するとさらに面倒になりますが、先ほどの延長で考えることができます。

同じ向きでの衝突が起こる時刻は向かい合う衝突が起こる時刻より遅いので、既に先ほどの連結成分となった区間に対して追加の条件が課されることになります。

以下の図を具体例として見てみます。

f:id:betrue12:20200107001541p:plain

LL や RR になってはいけない箇所があることで、先ほどの $S(l, r)$ の計算式のうち前の項・後ろの項がそれぞれ潰されます。つまり先ほどの連結成分に、前後どこまでの項が潰されているかの情報を追加で持たせればよいです。この生き残っている項の合計は、この図を例にすると $L(1, 1)S(2, 3)R(4, 5)$ と計算できるので、先ほどの延長で計算できます。生き残っている項がなくなった場合は衝突しない確率 $0$ 、つまり実験が必ず終了することを意味します。

これで全てのケースが処理できました。あとは実装を頑張りましょう。

ACコード

Submission #68322973 - Codeforces

2020-01-05

Codeforces Hello 2020 E. New Year and Castle Construction

Codeforces プログラミング競技プログラミング

Problem - E - Codeforces

問題概要

座標平面上に $n$ 個の点があり、 $i$ 番目の点の座標は $(x_{i}, y_{i})$ である。これら $n$ 個の点からなる集合を $s$ と表記する。全ての点は相異なり、どの3点をとってもそれらが一直線上に存在することはない。

点 $p\in s$ のスコア $f(p)$ を、「 $s$ に含まれる4点の選び方のうち、その4点を結ぶ四角形が点 $p$ を内部（辺上は除く）に含むものの個数」と定義する。全ての点 $p\in s$ についてのスコア $f(p)$ の総和を求めよ。

制約

$5 \le n \le 2500$
$-10^{9} \le x_{i}, y_{i} \le 10^{9}$
全ての点は相異なり、どの3点をとってもそれらが一直線上に存在することはない

解法

点 $p$ を全通り試します。点 $p$ が原点となるよう、その他の $n-1$ 個の点の座標を平行移動します。

$n-1$ 個の点から4点を選ぶ選び方のうち、四角形が点 $p$ を内部に含まないようなものを数えて $_{n-1}C_{4}$ から引くことにします。これはどのように判定できるでしょうか。

f:id:betrue12:20200105135727p:plain

この図のように、4点を偏角の順に並べたときに、1点目→2点目、2点目→3点目、3点目→4点目、4点目→周回後の1点目、のいずれかの点間において偏角が180度以上進んでいることが、四角形が原点を内部に含まない必要十分条件になります。

ここで3点が一直線上にないという制約により、「偏角差がちょうど180度」という状況はあり得ないことに注意します。もし偏角差がちょうど180度である2点がある場合、原点 $p$ を含めて3点が一直線上に並んでしまうからです。同様の理由で、偏角が等しい2点が存在することもありません。

このことから、先ほどの4つの点間のうち偏角差が180度以上である（180度を超える）ものは高々1つであることが分かります。これによって重複カウントを防ぐことができます。

具体的には、 $n-1$ 個の点を偏角でソートし、2周分の要素を確保しておきます。1点目を順番に試し、「今1点目としている点から見て、偏角が180度以上進んでいるものはどの点以降か」を尺取り法などで管理します。偏角が180度以上進んでいる点が $k$ 個ある場合、この中から残りの3個を選ぶことで点 $p$ を内部に含まない四角形ができるので、 $_{k}C_{3}$ を答えから引いていきます。

点 $p$ を全通り試して、それぞれについて残りの点のソートを行うので、全体計算量 $O(n^{2}\log n)$ となります。

誤差に影響されない偏角の扱い方

座標の値が大きいので、偏角を求めたり180度の境界を求めるところで誤差によって答えがずれてしまい大変でした。全体的に long double の精度を確保することで通ったようですが、極力小数を用いないような処理方法を考えてみます。

まず整数座標の点を偏角でソートする場合は、偏角を std::atan2 などで求めるのではなく「符号付き面積」を用いることができます。

参考：符号のある面積

原点を $O = (0, 0)$ とし、点 $A = (a_{1}, a_{2})$ と点 $B = (b_{1}, b_{2})$ と原点の3点が相異なるとします。三角形 $OAB$ の符号付き面積は $\frac{1}{2}(a_{1}b_{2} - b_{1}a_{2})$ と定義されます。これは一般的な座標平面において $O, A, B$ が反時計回りに結ばれている時に正、時計回りに結ばれている時に負となります。

この値は、点 $A, B$ の原点からの距離をそれぞれ $|A|, |B|$ 、偏角をそれぞれ $\theta_{A}, \theta_{B}$ としたときに、 $\frac{1}{2}|a||b|\sin(\theta_{B} - \theta_{A})$ と一致します。つまり $|A|, |B|$ が正であれば $(a_{1}b_{2} - b_{1}a_{2})$ と $\sin(\theta_{B} - \theta_{A})$ は符号が一致することになります。

これを利用して偏角ソートができます。まず偏角の範囲をどう取るかを決めましょう。例えば度数法で $\lbrack 0, 360)$ であるとします。

ソートしたい点を、まず4象限に分けます。それぞれの象限の内部においては、偏角の差は90度以下であることが保証されます。このとき同じ象限に含まれる2点 $A = (a_{1}, a_{2})$ と2点 $B = (b_{1}, b_{2})$ について、 $(a_{1}b_{2} - b_{1}a_{2})$ と $\sin(\theta_{B} - \theta_{A})$ の符号が一致し、偏角差が90度以下であることから $(\theta_{B} - \theta_{A})$ とも符号が一致します。つまり座標値が整数であれば、比較関数において $(a_{1}b_{2} - b_{1}a_{2})$ の符号を確認することで誤差なく象限内での偏角ソートを行うことができます。あとは決めた偏角の範囲に合うように象限ごとに並べれば偏角ソート完了です。

同様に尺取り法で偏角が180度以上進んでいるかどうか調べるときも、符号付き面積の値の符号を見ることで誤差なく判定することができます。

以下のリンク先ACコードでは、これらの方法を用いて小数を一切使わない実装にしています。

ACコード

Submission #68206915 - Codeforces

コード中の偏角ソート関数はこの問題の制約下では正しく動きますが、原点が含まれていると壊れると思います。あと int に収まらない座標値が来た場合も $(a_{1}b_{2} - b_{1}a_{2})$ を計算する時にオーバーフローで壊れます。

2020-01-05

Codeforces Hello 2020 D. New Year and Conference

Codeforces プログラミング競技プログラミング

Problem - D - Codeforces

問題概要

講演会において $n$ 個の講演がある。A会場とB会場の2つがあり、講演 $i$ をA会場で行う場合の講演時間は時刻の閉区間 $\lbrack sa_{i}, ea_{i}\rbrack$ で、B会場で行う場合の講演時間は時刻の閉区間 $\lbrack sb_{i}, eb_{i}\rbrack$ で表される。

2つ以上の講演の集合 $s$ のうち、以下のようなものが存在するかを判定せよ。（存在しない場合に YES、存在する場合に NO を出力せよ）

$s$ に含まれる講演を、ある片方の会場で全て行った場合には講演時間に共有点を持つ2つの講演が存在し、他方の会場で全て行った場合にはそのようなものが存在しない。

制約

$1 \le n \le 100000$
与えられる各時刻は $1 \le t \le 10^{9}$ を満たす

解法

上記の問題概要は多少要約しているのでバレバレなのですが、集合 $s$ としてはちょうど2つの講演からなるものだけを考えれば十分です。

会場Aにおいて共有点を持ち、会場Bにおいて共有点を持たない2つの講演が存在するかを調べます。逆も同様に調べます。

会場Aにおける各講演の開始・終了時刻をそれぞれソートし、時刻を順番に進めていくシミュレーションを行います。こうしながら「今見ている時刻を会場Aでの講演時間に含む講演の集合」を管理します。

この集合が変化した各タイミングにおいて、「集合の中に、会場Bの講演時間において共有点を持たないような2つの講演が存在するか？」をチェックします。実際には、講演が終わっただけの時刻では条件を「満たしにくく」なるだけなので、いずれかの講演が始まる時刻についてだけチェックすれば良いです。

これをチェックする方法としては、集合に含まれる講演の会場Bでの開始時刻と終了時刻をそれぞれ多重集合として持っておきます。その開始時刻の最大値を $s_{(B, \max)}$ 、終了時刻の最小値を $t_{(B, \min)}$ とすると、会場Bの講演時間において共有点を持たない2つの講演が存在する必要十分条件は $t_{(B, \min)} \lt s_{(B, \max)}$ が成立することです。

これはC++の std::multiset など順序付き集合が存在する言語ならそのまま、存在しない言語なら座標圧縮+BIT二分探索や優先度付きキューを工夫して用いる等の方法で求めることができます。

ACコード

Submission #68175586 - Codeforces

2019-12-24

第一回日本最強プログラマー学生選手権決勝 F - Count Permutations Many Times

AtCoder プログラミング競技プログラミング

お題箱より。

F - Count Permutations Many Times

難しめの（とはいえ上級者には比較的知名度が高い）テクニックを複数使いこなす必要がある問題です。公式解説では多項式の係数に対応させて解いていますが、そうではない方法で説明しようと思います。

解法

まずは1つのクエリだけを考える

まずはこの問題を、あるクエリ（区間） $\lbrack L, R\rbrack$ 1つだけについて解くことを考えましょう。

「 $p_{j} \ne A_{j}$ である」よりも「 $p_{j} = A_{j}$ である（違反状態である）」のほうが数えやすいので、包除原理を適用します。 $N$ 個の整数の集合を $S = \lbrace 0, ..., N-1\rbrace$ として、その部分集合 $s$ を考えます。 $s$ に含まれる整数が全て違反状態である（含まれない整数はどちらでもよい）ような場合の数を $C(s)$ とすると、求めたい答えは包除原理から

$\displaystyle \sum_{s\subset S}(-1)^{|s|}C(s)$

と計算することができます。ここで $|s|$ は $s$ の要素数を示します。

$C(s)$ の求め方を考えます。ある $s$ についてその要素を $x_{1}, ..., x_{|s|}$ と書きます。このときクエリで指定された区間 $A_{L}, ..., A_{R}$ に含まれている整数 $x$ の個数を $n(x)$ とすると、これは以下のように考えることができます。

まず $x_{1}, ..., x_{|s|}$ を置く場所を順番に決めてしまう。このとき整数 $x_{i}$ が違反する置き場所として取れるものは $n(x_{i})$ 通りあり、これらの場所は異なる整数間で重複することはない。
先に上記の $|s|$ 個を置き終わったら、残っている $N-|s|$ 個の整数を残っている $N-|s|$ 個の場所に自由に置く。

ということで、 $C(s)$ は以下のようになります。

$\displaystyle C(s) = \prod_{x \in s}n(x) \times (N-|s|)!$

これを全ての $s \subset S$ について個別に求めるのは当然できません。求めたい答えの計算において、サイズ $|s|$ が同じ部分集合には同じ係数 $(-1)^{|s|}(N-|s|)!$ が掛かることに注目すると、残った $\prod_{x \in s}n(x)$ をサイズが同じ集合ごとに合計したものが分かれば良さそうです。

ということで以下のDPを組みます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 整数 $0, ..., i-1$ までのうち $j$ 個を含むような集合全てについて、それぞれの集合を $s$ としたときの $\prod_{x \in s}n(x)$ の値を合計したもの。

これを最後まで計算したときの

$\displaystyle \sum_{j=0}^{N} \left( dp\lbrack N \rbrack\lbrack j \rbrack\times (-1)^{j}(N-j)!\right)$

の値が答えになります。

このDPにおける $dp\lbrack i \rbrack\lbrack j \rbrack$ からの遷移は次の2通りです。

整数 $i$ を集合の要素として採用する。 $n(i)$ を掛けて $dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack$ に足す。
整数 $i$ を集合の要素として採用しない。そのまま $dp\lbrack i+1 \rbrack\lbrack j \rbrack$ に足す。

これでクエリが1つの場合は $O(N^{2})$ のDPで解くことができました。このようにシンプルな遷移であることが後々効いてきます。

複数クエリではどうするか？

クエリとして区間が与えられるので、まず考えるのはセグメント木等です。ただこの問題の場合、2つの区間に対する計算結果（DPテーブル）をマージするのが難しいです。遷移の係数となっている $n(0), ..., n(N-1)$ が全部変わる可能性があるため、DPを最初から全部やりなおすことになります。

区間クエリの処理方法としてもう1つ重要テクニックがあります。Mo's Algorithm です。使える条件/やり方/計算量についてはリンク先を参照して欲しいのですが、これは

オフラインクエリである（いわゆるクエリ先読みができる）
区間を1要素分伸ばす/1要素分縮めて、答えを更新するという操作が妥当な計算時間でできる

という条件を満たす時に使えるテクニックです。

伸び縮みの計算量を $O(\alpha)$ として全体計算量は $O(\alpha(N+Q)\sqrt{N})$ 。 $N, Q$ が大きいと $O(\alpha)$ として許せる計算量は $O(1)$ や $O(\log N)$ くらいなのですが、今回は制約が小さいので $O(N)$ くらいならOKそうです。

要素を増やす/減らす処理を上手くやるには？

ある区間 $A_{L}, ..., A_{R}$ について、先ほどのDPの最終結果が求められているとします。そこから区間の要素を1つだけ増やす/減らすという処理を上手くやる方法はあるでしょうか？

このとき増えた/減った要素の値を $d$ とすると、DP遷移の係数となっている $n(0), ..., n(N-1)$ のうち変化するのは $n(d)$ だけです。そして先ほどのDPは、「戻すDP」というテクニックが適用できる形になっています。これは

今回の $0, ..., N-1$ の整数のように、DPの計算において見ていく順番が変わっても問題ない。
DPの遷移が単純で、 $dp\lbrack N \rbrack\lbrack\cdot\rbrack$ から $dp\lbrack N-1\rbrack\lbrack\cdot\rbrack$ を逆算することができる。