geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 292 備忘録

コンテストページ: AtCoder Beginner Contest 292 - AtCoder

コンテスト中AC: A〜D
コンテスト後にE,Fを解説ACしました。要点ををまとめておきます。

D - Unicyclic Components

Union-Findで連結成分の何らかのデータを統合していく問題はよく出題されます。今回は、連結成分に属する辺の個数をデータとして持ちます。

e=(u,v)が与えられた時、u,vが同一の連結成分に属するなら、その連結成分の辺の個数を+1する。そうでないなら、u,vをマージした後に+1すれば良いです。
マージする際は、辺の個数のデータを統合します。

データは常に、Union-Findの各連結成分における根に保持するよう調整が必要なので、その点は注意が必要です。

実装: Submission #39422939 - AtCoder Beginner Contest 292

E - Transitivity

公式解説の要点

  • ある頂点について、その頂点から(元々隣接していない)全ての到達可能な頂点に有向辺を新たに追加する必要がある。

  • ある頂点から辺を新たに追加しても到達可能な頂点の集合は変わらない。(ある辺を追加することで新たに辿り着ける頂点が増えるということはない)

  • 以上から、全ての頂点からBFSして、到達可能であって距離が2以上の頂点をカウントすればよい。

実装: Submission #39524065 - AtCoder Beginner Contest 292

F - Regular Triangle Inside a Rectangle

公式解説では、正三角形の縦の長さはl\sin\thetaとなっていました(2023/3/9現在)が、自分の考え方ではl\sin(\theta + 60^{\circ})だったので、それで書きます。

要点

  • 正三角形の頂点のうち1つは、最も左下、右下、左上、右上のいずれかとなる(鳩の巣原理により、証明できる) 。正三角形に平行移動と反転を行うことで、長方形の左下の頂点と正三角形の頂点を一致させることができる。

  • 長方形の下の辺と正三角形の下の辺の角度を\thetaとすると、辺の長さlの正三角形の縦の長さ、横の長さ、角度の制約から以下の条件が得られる。
    0\lt l\cos \theta \leq A
    0\lt l\sin (\theta + 60^\circ) \leq B
    0 ^\circ \leq \theta \leq 30^\circ

  • 上記式に対して二分探索を行えばよい。角度の条件の範囲内において、\cos\thetaは単調減少、\sin\thetaは単調増加なので、0\lt l\cos \theta \leq A0 ^\circ \leq \theta \leq 30^\circを同時に満たす\thetaのうち、最大のものが0\lt l\sin (\theta+60^\circ )\leq Bを満たすか判定する。

自分の補足

0\lt l\cos \theta \leq A0 ^\circ \leq \theta \leq 30^\circを同時に満たす最大の\thetaの求め方
0 ^\circ \leq \theta \leq 30^\circにおいて、\cos\thetaは、\frac{\sqrt{3}}{2}\leq \cos\theta \leq 1です。

0\lt l\cos \theta \leq A0 ^\circ \leq \theta \leq 30^\circを同時に満たす最大の\thetaは、
\frac{A}{l}\lt \frac{\sqrt{3}}{2}なら、解なし
\frac{\sqrt{3}}{2} \leq \frac{A}{l} \leq 1 なら、 \frac{A}{l}
 \frac{A}{l}\geq  1 なら、1
です。

実装: Submission #39504396 - AtCoder Beginner Contest 292