目次
SMBCプログラミングコンテスト #2(AtCoder Beginner Contest 481)E,F,G問題メモ
E - Most Brilliant Starry Sky
問題文
- $xy$ 平面上に $N$ 個の星があります。$i$ 個目の星は、座標が $(X_i,Y_i)$ である点として表されます。
- 原点を通りどの星も通らない直線を $1$ 本引き、その直線によって分けられる二つの領域のうちどちらか一方の領域を選びます。
- 選んだ領域に含まれる星の個数としてありうる最大値を求めてください。
- $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- $1 \le T \le 2 \times 10^5$
- $1 \le N \le 2 \times 10^5$
- 全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
- $-10^9 \le X_i,Y_i \le 10^9$
- $(X_i,Y_i) \ne (0,0)$
- $(X_i,Y_i) \ne (X_j, Y_j) ~ (i \ne j)$
- どの相異なる $2$ 個の星についても、それらと原点が一直線上に並ぶことはない
- 入力される値はすべて整数
解法
偏角ソート。
直線の傾きを、$-\infty~\infty$ までぐり~んと回転させることを考える。
- 「$x \gt 0$」または「$x=0$ で $y \gt 0$」の点の個数を $p$、そうでない点の個数を $q$ とする。
- 傾きが $-\infty$ の時、一方は $p$ でもう一方が $q$ である。
- $x=0$ 以外の点を $y/x$ でソートし、その順に点を見ていく。
- 見ている点が最初 $p$ 側の点だった場合、その傾きを境に点は $p$ から $q$ へ移る。$p-=1,q+=1$
- 見ている点が最初 $q$ 側の点だった場合、その傾きを境に点は $q$ から $p$ へ移る。$p+=1,q-=1$
この過程で、$p,q$ の値として出現した最大値が答えとなる。
ただし、今回の $-10^9 \le X_i,Y_i \le 10^9$ という制約だと、 精度が足りず単なる $y/x$ のソートでは正しい値を保証できなくなる。 (目安として、実数でのソートで正しさが保証されるのは $2^{26} \simeq 6.7 \times 10^7$)
Python なら、分子と分母を分けて持って cmp_to_key で比較するか、または Fraction を使うと正確にソートできる。
速度は落ちるが、今回のように単純に全体を1回ソートするだけなら問題ない。
または、miztom氏のユーザー解説 のように、$y$ を十分大きくして多倍長整数で持つのも手。
F - Evil Shortest Path
問題文
- $N$ 頂点 $M$ 辺の有向グラフが与えられます。
- $i$ 番目の辺は頂点 $A_i$ から頂点 $B_i$ へと向かう辺であり、この辺には $1$ 以上 $9$ 以下の数字 $C_i$ が書かれています。
- 辺の向きに従って移動するとき、通った辺に書かれた数字を通った順につなげて得られる整数を、その移動のスコアと呼びます。
- 例えば、通った辺に書かれた数字が順に $3,1,4$ であるとき、その移動のスコアは $314$ です。同じ頂点や辺を複数回通ってもかまいません。
- $v=2,3,\ldots,N$ のそれぞれについて、頂点 $1$ から頂点 $v$ へ移動するときのスコアの最小値を $998244353$ で割ったあまりを求めてください。
- ただし、入力として与えられる有向グラフは、頂点 $1$ から他のすべての頂点へ、辺の向きに従って移動できることが保証されます。
制約
- $2 \le N \le 2\times 10^5$
- $N-1 \le M \le 2\times 10^5$
- $1 \le A_i,B_i \le N$
- $1 \le C_i \le 9$
- 入力される値はすべて整数
- 頂点 $1$ から他のすべての頂点へ、辺の向きに従って移動できる
解法
$1→u$ のスコア最小値を $S(u)$ とすると、$1→u→v$ のような経路のスコア最小値は必ず $S(u)$ を接頭辞に持つ。
「$1→u$ の2番目以降のスコアが、実は $1→u→v$ では最適になる」ようなことはない。
よって、巨大な整数同士の比較コストを無視すれば、スコアをそのまま距離とした Dijkstra が使えはするのだが、、、
①--1→○--2→○→...→○--3→○→...○--5→○--6--,
`--1→○--2→○→...→○--4→○→...○--5→○--6→②
|-------ほぼ一緒------| ↑ |-----ほぼ一緒------|
僅かに違う
こんな時、①→②は上と下とどちらの経路がいいのか比較できない。 スコアをそのまま持ったらTLE or MLE になるし、modを取ったら大小は失われる。
スコアをベースとして考える。 ①を根として、それぞれから1~9の辺が生えるTrieをイメージする。
①
1↙ 2↙....8↘ 9↘
○ ○ ○ ○
↙↓↘ ↙↓↘ ↙↓↘ ↙↓↘ ※書き切れないだけで、各頂点からの辺は9本
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
これらの辺・頂点は、元のグラフと区別して「Trie上の辺」「Trie上の頂点」と呼ぶことにする。
グラフ上の辺とコストが同じ辺を Trie でたどった時、 $1→v$ までのあり得る経路スコア(=辿り着くTrie上の頂点)は複数あるが、 その内「Trie上で最も上の階層、階層が同じなら最も左の頂点」が、$v$ のスコアの最小値を表すことになる。
元グラフ Trie
①--1→②--3--, ① グラフ頂点と対応するTrie頂点
| ↓2 ↓ 1↙↓2↘3... ②: (a) →最小は(a)
`--1→③--2→④ (a) (b) (c) ③: (a)と(e) →最小は(a)
1↙↓2↘3... ④: (e)と(f)と(g) →最小は(e)
(d) (e) (f)
↓2
(g)
よって、Trie上の幅優先探索(同じ頂点からは、末尾に付けた数字が小さい方がキューに先に入る)順に従うと、 巨大な数値を直接扱わなくても、$v$ に初めて対応することとなるTrie上の頂点が、$v$ のスコアの最小値であると保証される。
$v$ のスコアの最小値を表すTrie上の頂点を $t$ とする。 上例②と③のように、異なるグラフ上の頂点 $u_1,u_2,...,u_k$ が、同じ $t$ となることもありえる。
$t$ が同じとなるような $u_1,...,u_k$ はまとめて処理する。 つまり、単なる幅優先探索なら、頂点優先で
- $u=u_1,u_2,...,u_k$ の順に、
- $c=1,2,...,9$ の順に、
- 辺コスト $c$ の辺 $u→v$ に対し、$v$ が未訪問なら、$v$ のスコア $S(v)$ を $10S(u)+c$ で確定する
としてしまうが、これだと $u_2→v$ の辺に $u_1→v$ よりよいコストがあっても、見つけることができない。
- ○: コスト優先
- $c=1,2,...,9$ の順に、
- $u=u_1,u_2,...,u_k$ の順に、
- 辺コスト $c$ の辺 $u→v$ に対し、$v$ が未訪問なら、$v$ のスコア $S(v)$ を $10S(u)+c$ で確定する
とすると、上手くいく。
G - Half-Baked
問題文
- あなたは $N$ 個のパンケーキを焼き、$1$ 個の山に積み上げることにしました。
- $i$ 番目のパンケーキを焼いたときの大きさは、確率 $1/2$ で $A_i$ に、確率 $1/2$ で $B_i$ になります。この事象はパンケーキごとに独立です。
- $N$ 個のパンケーキを焼き終えた後、上から大きさが昇順になるように $1$ 個の山に積み上げます。
- 上から $k$ 番目に積まれるパンケーキの大きさの期待値を $f(k)$ とします。
- このとき、$f(k) \times 2^N$ は整数になることが証明できます。
- $k=1,\dots,N$ について、$\left( f(k) \times 2^N \right) \bmod 998244353$ の値を求めてください。
制約
- $1 \leq N \leq 120\,000$
- $1 \leq A_i \lt B_i \lt 998244353$
- 入力される値はすべて整数
解法
期待値で考えて、最後に $2^N$ 倍する。
パンケーキの大きさ $A_i,B_i$ は全て異なるとする。 もし同じのがあっても、「同じ場合は番号が小さい方が小さい」などとして、適当に順序を決めておく。
やりたいこと
あるパンケーキの大きさが $a$ になった時、期待値にどう寄与するかというと、
- $B_i \lt a$(必ず自身より小さくなる)ような、自身以外のパンケーキの個数を $L$
- $A_i \lt a \lt B_i$(自身より小さくなったり大きくなったりする)ような、自身以外のパンケーキの個数を $M$
- (残りは $a \lt A_i$ で、必ず自身より大きくなる $N-L-M-1$ 個)
とした時、$a$ の位置としてあり得るのは上から $L+1~L+M+1$ 番目の $M+1$ 通りである。
その中のどれになるかは、$M$ 個中、$a$ より小さい方になるパンケーキが何個かに依る。 $l$ 個の時に $L+l+1$ 番目となり、その確率は二項分布となる。
■a が k 番目になる確率p L=5, M=4 k 1 2 3 4 5 6 7 8 9 10 11 12 ... p 0 0 0 0 0 1 4 6 4 1 0 0 ... ※p は、これに a 自身が大きさ a になる確率 1/2、 および M 個がそれぞれどちらになるかの 1/(2^M) をかけたものとなる
よって、この例の場合、期待値への寄与は以下のようになる。
- $k=6,7,8,9,10$ に対して、$\dfrac{a}{2^{M+1}},\dfrac{4a}{2^{M+1}},\dfrac{6a}{2^{M+1}},\dfrac{4a}{2^{M+1}},\dfrac{a}{2^{M+1}}$
これを、全てのパンケーキ、各2通りの大きさの $2N$ 個をそれぞれ $a$ とした場合について足し合わせたものが答えとなる。 当然、そのままでは $O(N^2)$ なのでTLEとなる。
分割統治
例えば以下のような3つの大きさがあったとき、 (※煩雑になるので $\frac{1}{2^{M+1}}$ 倍するのは省略しているが、本質的には同じこと)
大きさ L M 1 2 3 4 5 6 7 8 9 10
1 1 5 1 5 10 10 5 1 二項係数5の段×1
10 3 4 10 40 60 40 10 二項係数4の段×10
100 3 6 100 600 1500 2100 1500 600 100 二項係数6の段×100
-------------------------------------------------------------
1 5 120 650 1565 2141 1510 600 100
この部分さえ計算して合成しておけば、
大きさ L M 1 2 3 4 5 6 7 8 9 10
1 1 5 1 1 - - - - 二項係数1の段×1
10 3 4 10 - - - - 二項係数0の段×10
100 3 6 100 200 100 - - - - 二項係数2の段×100
-------------------------------------------------------------
1 1 110 200 100
これに、二項係数の $4$ の段をかけると、元の結果と等しくなる。
(1, 1, 110, 200, 100) × (1, 4, 6, 4, 1) = (1, 5, 120, 650, 1565, 2141, 1510, 600, 100)
このように、何個かまとめたアイテムの中で最小の $M$ を基準として($M'$ とする)、長さ $M'$ は後からまとめて伸ばせる。 言い換えれば、暫定結果の配列を $M'$ だけ短い状態で持て、伸ばすのを“保留”できる。
形式的冪級数的には、3つそれぞれの式から $x^2(1+x)^4$(オフセットと、保留してる分)をくくりだしているイメージ。
- $(1 \times x^2(1+x)^5) + (10 \times x^4 (1+x)^4) + (100 \times x^4(1+x)^6)$
- $=x^2(1+x)^4(1 \times (1+x)^1 + 10 \times x^2 + 100 \times x^2(1+x)^2)$
この“保留”が分割統治全体で上手く効き、$O(\log{N})$ 段ある各段での合成結果の配列の長さの合計が $O(N)$ で抑えられる。
$(L,M)$ でソートした順で、$[l,m)$ と $[m,r)$ の結果をマージするとき、左右の以下の情報があれば良い。
- 区間最小の $L$
- 区間最小の $M$
- $M$ だけ伸ばすのを保留している、$L$ からの合成結果の配列
- 上例 $[1,1,110,200,100]$ に相当するもの
新しく保留できるのは $M_{l,r}=\min(M_{l,m},M_{m,r})$ なので、保留できるのが短くなった方を畳み込みで伸ばした上で、 $L$ のズレ分だけずらして足し合わせれば良い。

