AtCoder Beginner Contest 157 に参加したので、各問題の考察を書いていきます。結果はE完でした。

前回: 競プロ参戦記 #72 Modularness | ABC 156
問題一覧: https://atcoder.jp/contests/abc157/tasks

A - Duplex Printing

問題概要: N ページからなる書類を両面印刷する。必要な用紙の枚数を求めよ。

A: 考察

N が偶数なら N/2 枚です。N が奇数なら、最後の1枚は片面にだけ印刷することになりますが、(N+1)/2 枚です。

Rust の整数の除算は端数切り捨てなので、どちらにせよ (N+1)/2 という式で書けます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc157/submissions/10437055

B - Bingo

問題概要: 3x3 のビンゴカードが与えられる。左上から y 列目、x 行目に整数 A(y, x) が書かれている。N 個の整数 b(1), ..., b(N) が選ばれたとき、ビンゴが達成されたか判定せよ。(A において縦・横・斜めのいずれか1列に並んだ整数がすべて b に含まれるとき、ビンゴが達成される。)

制約: N≤10

B: 考察

ビンゴの条件を満たすラインがあるか、縦・横・斜めの8通りすべて確認すればよいです。

各ライン上のマスの座標は、i = 0, 1, 2 に対して以下のように表せます。

縦 A(i, x) (x = 0, 1, 2)
横 A(y, i) (y = 0, 1, 2)
左上から右下 A(i, i)
右上から左下 A(i, 2 - i)

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc157/submissions/10434579

C - Guess The Number

問題概要: 次の条件を満たす 0 以上の整数が存在するか判定し、存在するなら最小値を求めよ。

10進表記でちょうど N 桁
- ただし、0 は1桁とする。0 以外の整数は、先頭に 0 をつけた表記は認めない。
左から s(i) 桁目の数字は c(i) である。

制約: N≤3

C: 考察

解が存在するかどうか、解が 0 かどうか、それ以外 (解が存在して1以上) に場合分けします。

解が存在しないケース:

2桁以上で先頭が 0
- つまり N≥2 で、s(i)=0, c(i)=0 という条件が与えられているとき
条件に矛盾がある
- つまり s(i)=s(j), c(i)≠c(j) という条件が与えられているとき

解が 0 になるケース:

N=1 で、すべての i について c(i)=0

それ以外の場合、先頭の桁に数字が指定されていなければ 1 にして、先頭以外の数字が指定されていない桁は 0 にすれば最小です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc157/submissions/10436787

D - Friend Suggestions

問題概要: N 人の間に M 組の友達関係と K 組のブロック関係が定まっている。推移的に友達である相異なる2人は、直接の友達関係もブロック関係も持たない限り、友達候補である。各人の友達候補の人数を求めよ。

制約: 友達関係とブロック関係の両方を持つペアは存在しない。

D: 考察

元の問題文の友達候補の定義の4番目がややこしいので、確認しておきます。人 a, b は、次の条件を満たすとき「推移的に友達である」ということにします。

1 以上 N 以下の整数から成るある数列 c0,c1,c2,⋯,cL が存在し、c0=a であり、 cL=b であり、 i=0,1,⋯,L−1 について、人 ci と人 ci+1 は友達関係にある。

L=1 のとき、数列は a=c(0), c(1)=b という形です。a, b が(直接の)友達関係にあるなら a, b は推移的に友達であるといえます。

L=2 のとき、数列は a=c(0), c(1), c(2)=b という形です。a と c(1) が友達で、c(1) と b が友達なら、つまり a と b が「友達の友達」なら、a と b は推移的に友達です。

L=3 も同様で、a と b が「友達の友達の友達」なら、a と b は推移的に友達であることになります。

結局、「推移的に友達」は平たくいえば a と b が「友達の友達の……友達」であることを指しています。

人を点、友達関係を辺とするグラフにおいて、同一の連結成分に含まれていること、とも言い換えられます。

制約もややこしいので見ておきます。

Ai≠Bi
Ci≠Di

自分が自分の友達であったり、自分自身をブロックするということはないことを表しています。

(Ai,Bi)≠(Aj,Bj)(i≠j)
(Ai,Bi)≠(Bj,Aj)
(Ci,Di)≠(Cj,Dj)(i≠j)
(Ci,Di)≠(Dj,Cj)

この4つは友達関係やブロック関係が重複して入力されることがないことを表しています。

(Ai,Bi)≠(Cj,Dj)
(Ai,Bi)≠(Dj,Cj)

この2つは友達関係とブロック関係の両方を満たすペアがいないことを表しています。今回の解法では重要なポイントです。

友達候補は推移的友達から以下を除いたものです。

自分
直接の友達
ブロックしている推移的友達

これら3つには被りがないので、推移的友達の人数からそれぞれ引けばよいです。

はじめに、DFS や UnionFind で連結成分分解することで、推移的友達を特定します。人 u が属する連結成分を c(u) とします。以下の3つの処理により、求める人数を数えられます。

各友達関係 (a, b) につき、c(a), c(b) の人数を 1 ずつ増やす
各友達関係 (a, b) につき、c(a) = c(b) なら、a, b の友達の人数を 1 ずつ増やす
各ブロック関係 (a, b) につき、c(a) = c(b) なら、a, b のブロックしている推移的友達の人数を 1 ずつ増やす

なお友達関係やブロック関係からなるグラフを構築する際に、辺を2つずつ隣接リストに挿入している場合は、人数がすべて2倍カウントされてしまうので注意です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc157/submissions/10447094

E - Simple String Queries

問題概要: 英小文字からなる長さ N の文字列 S が与えられる。以下の2種類のクエリが合計 Q 個与えられるので、順番に処理せよ。

クエリ (t=1, i, c): 文字列 S の i 文字目を文字 c に変更する。
クエリ (t=2, l, r): 文字列 S の区間 l..r に含まれる文字の種類の個数を出力する。

制約: N≤5・10^5, Q ≤2・10^4

E: 考察

この手のクエリは Range Sum Query と呼ばれている典型的なものです。セグメントツリーやバイナリインデックスツリー (BIT) を使ったり、平方分割により解けることが多いです。

英小文字が26種類しかないことに注目すると、各英小文字 c (= 'a', ..., 'z') について「S の区間 l..r に文字 c が含まれるか？」を調べることで、文字の種類の個数が求まります。そのため英小文字の種類ごとに別々に処理して OK です。

英小文字 c ごとに長さ N の配列 Xc を用意して、次のように値を決めます。

Xc(i) = (S(i) == c なら 1、そうでなければ 0)

「S の区間 l..r に含まれる文字 c の個数」が「Xc の区間 l..r の総和」で求まるので、この値が 1 以上か否かみれば、文字 c が区間に含まれるか否か判定できます。

Xc を通常の配列ではなく BIT で持てば、区間和を高速に求められます。各クエリを O(log N) で処理できるので間に合います。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc157/submissions/10452320

BIT については以前に書いた記事を参照:

参考: 競プロ参戦記第10回「転倒数」 Chokudai Speed Run 001 [J]

解説 PDF によると set (二分探索木) を使うのが想定解のようですが、まだ BTreeSet::range が使えないので、Rust でやるのは厳しそうです。

F - Yakiniku Optimization Problem

問題概要: 2次元平面上にある N 個の肉が与えられる。i 番目の肉は座標 (x(i), y(i)) にあり、火の通りにくさが c(i) である。1個の熱源を好きな座標 (X, Y) においたとする。i 番目の肉は、c(i) √((X - x(i))^2 + (Y - y(i))^2) 秒後に焼きあがることが分かった。K 枚目の肉が焼けるまでにかかる時間を求めよ。

制約: N≤60

F: 考察

T 秒以内に K 枚以上の肉が焼けるかどうかを二分探索することにします。そのためには次の条件を満たす肉の枚数が K 以上であればよいです。

c(i) √((X - x(i))^2 + (Y - y(i))^2) ≤ T

変形すると、

(X - x(i))^2 + (Y - y(i))^2 ≤ (T/c(i))^2

となり、これは中心 (x(i), y(i))、半径 (T/c(i)) の円盤上に熱源 (X, Y) があれば、i 枚目の肉が T 秒以内に焼けることを表しています。

K 個以上の円盤が重なっている点があれば、そこに熱源を置くことで条件を達成できます。そのような点を熱源候補と呼ぶことにします。

円盤が重なっているとき、円周が交差するケースと、交差しない (一方が他方に完全に覆われている) ケースがあります。そこで、熱源候補は以下の2種類のどちらか (あるいは両方) があります。

「円周が全く交差しない K 枚以上の円盤」が重なっている場合
- 一番小さい円盤の中心も熱源候補
「円周が交差するペアを含む K 枚以上の円盤」が重なっている場合
- 円周の交点のいずれかも熱源候補

そのため、各肉の位置と、円周の交点をすべて列挙して、それが熱源候補かどうか判定すればよいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc157/submissions/10530603

2つの円の交点

2つの円の交点を考えます。次の図を見てください。中心 p、半径 r の円 (青) と、中心 q、半径 s の円 (赤) があり、交点の片方を u とします。

△upq に注目します。辺 up, uq の長さは、円の半径であることから、それぞれ r, s です。もう1つの辺の長さを d = |p-q| とおきます。左下の角 a = ∠upq に余弦定理を適用すると、$\operatorname{cos} a = \frac{r^2 + d^2 - s^2}{2rd}$ を得ます。

X軸と円の中心を結ぶ直線 pq のなす角を t とおきます。これは atan2 という関数を使って計算可能です。

以上により、交点 u は点 p から距離 r、偏角 t+a に位置することが分かりました。全体が円の中心を結ぶ直線 pq に関して対称なので、もう一方の交点は点 p から距離 r、偏角 t-a です。

なお、そもそも円同士が交点を持つかどうかは、中心間の距離 d と半径の和 r+s を比較すれば分かりますが、この問題では考慮する必要はありません。

相対誤差

ところで、提出したコードに入力例2を流すと、次のように出力例とは異なる結果になります:

期待される出力: 7411.2252
実際の出力: 7411.22527937061

「小数点以下4桁までしか合わない……なんで……」 としばらく悩んでいたのですが、問題文に但し書きがあるとおり「想定解答との絶対誤差または相対誤差が 10^-6 以下であれば正解として扱われる」ので、実はこれで正解です。

そういうわけで、いまさらになって誤差の定義を確認しました。

参考: はじめての誤差論 - 武内＠筑波大

理論上の真の値 (厳密解) を真値、二分探索の計算結果 (近似解) を 測定値 と呼んでいます。絶対誤差と相対誤差の定義式は以下の通りです。

絶対誤差 = (測定値) - (真値)
相対誤差 = $\frac{(測定値) - (真値)}{(真値)}$

例えば入力例2では:

絶対誤差 = 7411.22527937061 - 7411.2252 = 0.00007937061 ≒ 10^-4
相対誤差 = (7411.22527937061 - 7411.2252)/7411.2252 ≒ 1.07・10^-8

相対誤差は 10^-6 より2桁も小さく、十分です。

その他の注意点

浮動小数点数 (f32/f64) には丸め誤差 (無限小数を有限桁で打ち切ったことによる誤差) があるため、例えば数学的には x <= y が true になるはずの計算でも、誤差のせいで false になることがあります。代わりに、適当に小さい数 ε を使って x < y + ε と書くのが常套手段です。
整数の二分探索では区間幅 (r - l) が十分に小さくなったら終了ですが、浮動小数点数の二分探索では微妙で、代わりに十分な回数のループを回すのが常套手段です。

参考: トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター (4/4)