AtCoder Beginner Contest 292 備忘録
コンテストページ: AtCoder Beginner Contest 292 - AtCoder
コンテスト中AC: A〜D
コンテスト後にE,Fを解説ACしました。要点ををまとめておきます。
D - Unicyclic Components
Union-Findで連結成分の何らかのデータを統合していく問題はよく出題されます。今回は、連結成分に属する辺の個数をデータとして持ちます。
辺が与えられた時、が同一の連結成分に属するなら、その連結成分の辺の個数を+1する。そうでないなら、をマージした後に+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
公式解説では、正三角形の縦の長さはとなっていました(2023/3/9現在)が、自分の考え方ではだったので、それで書きます。
要点
正三角形の頂点のうち1つは、最も左下、右下、左上、右上のいずれかとなる(鳩の巣原理により、証明できる) 。正三角形に平行移動と反転を行うことで、長方形の左下の頂点と正三角形の頂点を一致させることができる。
長方形の下の辺と正三角形の下の辺の角度をとすると、辺の長さの正三角形の縦の長さ、横の長さ、角度の制約から以下の条件が得られる。
上記式に対して二分探索を行えばよい。角度の条件の範囲内において、は単調減少、は単調増加なので、とを同時に満たすのうち、最大のものがを満たすか判定する。
自分の補足
• とを同時に満たす最大のの求め方
において、は、です。
とを同時に満たす最大のは、
なら、解なし
なら、
なら、
です。