Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 259

4完1WA。

各問題

A - Growth Record

MがX以上なら答えはもちろんTです。そうでなければ、まずT - (D * X)で0歳時点の身長を求め、それに(D * M)を足せばM歳時点の身長が求められます。

B - Counterclockwise Rotation

行列なり三角関数なりで計算すればよいです。

C - XX to XXX

まず同じ文字のかたまりを一つとして捉えたとき、SとTのそれが一致していなければ"No"です。

一致しているとき、各かたまりについて、S側のかたまりが一文字のときT側のかたまりも一文字でなければなりません。一文字だけの場合増やすことができません。 また、S側のかたまりが二文字以上のとき、T側のかたまりはS側以上の文字数でないといけません。いくらでも増やすことはできますが、減らすことはできません。

D - Circumferences

AとBが交わっていてBとCが交わっていればAとCも行き来可能ですから、これはUnion-Find (DSU)で管理できます。それぞれの円が交わっているかどうかは中心間の距離と半径を使って判定可能です。(中心間の距離 <= それぞれの半径の和なら交わっている)

次に、点sと点tについて、どの円の円周上にあるかどうかを全探索して、共に円周上にある場合は、それぞれの円が繋がっているかどうかを先ほどのUnion-Findを使ってチェックすればよいです。

なお、小数をつかうと誤差でだめな気がしますのでsqrtを使わず二乗で扱うとよいです。

E - LCM on Whiteboard

結構愚直にsetやmapを駆使して実装すると9つほどTLEがでて、それを最後まで解消することができませんでした。データ構造の使い方が悪いのか、もっと効率のよい解き方があるのか...。

まとめ

Dで少々もたついて、水パフォは取れたもののレートは微増止まり...。