AtCoder Beginner Contest 181 C,D,E,F問題メモ

AtCoder Beginner Contest 181

ぴったり2000で黄色に戻った。完璧な調整ですね。

C - Collinearity

• $xy$ 座標の $N$ 個の点が与えられるので、同一直線上に並ぶ3点があるか判定せよ
• $3 \le N \le 100$

$P,Q,R$ が同一直線上＝ベクトル $\overrightarrow{PQ}$ と $\overrightarrow{PR}$ の向きが同じ。

$\overrightarrow{PQ}=(x_1,y_1), \overrightarrow{PR}=(x_2,y_2)$ とすると、$(d \times x_1,d \times y_1)=(x_2,y_2)$ を満たす適当な実数 $d$ があればよい。

これは、比の計算などと同じく $x_1 \times y_2 = x_2 \times y_1$ かどうかで調べられる。等しければ同一直線上。
今回はどれも整数座標なので、小数点以下の誤差を気にする必要は無い。

$N$ が小さいので全ての3点について調べて $O(N^3)$ が十分間に合う。

Python3

D - Hachi

• $1～9$ の数字のみからなる数字列 $S$ が与えられる
• 好きに並べ替えて、8の倍数が作れるかどうか判定せよ
• $1 \le |S| \le 2 \times 10^5$

8の倍数かどうかは、下3桁で決まる。
というのも1000が8で割りきれるので、作る数の並びをたとえば $ABCDEF$ とすると、$ABC \times 1000 + DEF$ と分解すると $ABC$ の部分は何の数字が来ようと割り切れる。

なので、たとえば1000～2000の8の倍数の下3桁を調べて、3つの数字が全て $S$ に含まれるような組が1つでもあれば大丈夫。

何故かそんな気がするんだ そう思えてしまったんだ。

S = 1257
        下3桁  結果
1000 →  000    ×
1008 →  008    ×
...
1152 →  152    ○

なお、$|S|$ が3つに満たない場合は全探索でよい。

Python3

E - Transformable Teacher

• $N$ 人（奇数）の児童と先生が1人いる
• 先生を含め $N+1$ 人で2人ペアを作る
• $i$ 番目の児童の身長は $H_i$
• 先生は $M$ 個の変身形態を持ち、身長を $W_1,W_2,...,W_M$ のいずれかに変えられる
• 適切に変身形態とペアの組み方を決めた時の、ペアになった2人の身長差（の絶対値）の和の最小値を求めよ
• $1 \le N,M \le 2 \times 10^5$
• $1 \le H_i,W_i \le 10^9$

ふんふん、お遊戯の時間かな？と問題文を読んでいくと、いきなり変身形態とか出てきておい待てやとツッコみたくなる。

とりあえず先生の身長が決まっていたら、身長の低い方から順にペアにしていくのが最適なことはまぁわかる。

先生を除いた児童を $H_i$ 順にソートしておいて、「前から2人ずつペアにしたときの身長差の累積和」「後ろから2人ずつペアにしたときの身長差の累積和」を計算しておく。

H    1   3   6  10  12  15  20
前       2       6       9        (1,3) (6,10) (12,15) をペアにしたときの身長差の累積和
後      10       7       5       (15,20) (10,12) (3,6) をペアにしたときの身長差の累積和

先生は、ある変身形態で身長 $w$ の時、最も身長の近いところに入れ込むのが最適である。
その位置を二分探索で求める。

w = 11           ↓Teacher
  1   3   6  10  11  12  15  20
  `---'   `---'   `---'   `---'

そうしたとき、身長差の和は以下の合計になる。

• 前からの、先生とペアになる児童の直前までの累積和
• 後からの、先生とペアになる児童の直後からの累積和
• 先生とペアになる児童の身長差

     1   3   6  10  (11)  12  15  20
前       2      [6]            9      ┐
後      10       7            [5]     ┼  6+5+1 = 12
先生ペア               [1]            ┘

これを全形態について調べ、最小値を取ればよい。

ソートに $O(N \log{N})$、先生の身長を決めたときのスコアを求めるのに $O(M \log{N})$ かかり、全体で $O((N+M)\log{N})$ となる。

Python3

F - Silver Woods

• $xy$ 平面上の、$y=100$ と $y=-100$ に壁がある
• また $N$ 本の釘が打たれていて、$i$ 番目の釘は $(x_i,y_i)$
• 玉を $(-\infty, 0)$ から $(\infty,0)$ へ動かす
  • パチンコのように、玉は釘や壁にめり込むことはできない
  • 釘の太さは無視できる
• 釘に引っかかることなく移動させることのできる玉の最大半径を、精度 $10^{-4}$ まで求めよ
• $1 \le N \le 100$
• $|x_i|,|y_i| \lt 100$

玉の直径 $R$ を固定したとき、それが通り抜けられるかどうかをそれなりに高速に判定できるなら、二分探索が使える。

通り抜けられないときがどういう時か？を考える。

「壁と釘の間隔」「釘と釘の間隔」をまとめて「隙間」と呼ぶことにして、 上の壁から下の壁まで、$R$ 未満しか空いていない隙間によって分断されていたら、無理だと分かる。

なので、$N$ 本の釘と上の壁 $S$、下の壁 $T$ を頂点と見なして、グラフを作る。

• $S$ から釘 $i$ に、距離 $100-y_i$ の辺を張る
• 釘 $i$ から $T$ に、距離 $y_i+100$ の辺を張る
• 釘 $i$ と釘 $j$ の間に双方向に、その2点間の距離の辺を張る

そして、「距離 $R$ 未満の辺だけを辿って」$S$ から $T$ に到達できたら、分断されているということになり、直径 $R$ の玉は通り抜けられないことになる。

これで判定できるので、十分な精度になるまで二分探索で調べればよい。

Python3

公式解説にある通り、二分探索の必要はない。

壁・釘の全ての隙間を小さい順にソートして、Union-Findで管理して $S$ と $T$ が同じ連結成分になるまで辺を追加し続けると、はじめて同じ連結成分になってしまう隙間が、ボトルネックであり、玉が取れる最大の直径となる。