AtCoder Beginner Contest 259に参加しました。
結果
A,B,C,Dの4問正解でした。
今日はずっと問題文をちゃんと読んでいなくて何かしらの情報を見落としたまま解いてて、入力例の答えが一致しなかったり提出したらWAになったりしてた。
ちょっと集中できていなかったのかなあ。
A - Growth Record
等差数列の指定された項の値を答える問題に見えた。
普通の等差数列と違って項数が決まっている、もしくは上限が決まっていてある項以降は同じ値な等差数列。
等差数列として考えると、初項がわかれば簡単に指定された項数の値を求められるので、
まずはN,T,X,Dをもとに初項を計算した。
N<=Xかどうかでちょっと処理が分かれるけどとりあえず計算できる。
あとは指定された項数＝Mが上限値なのかどうかを判断して計算して答える。
B - Counterclockwise Rotation
指定された座標をd度回転させた座標を答える問題。 考察どうこうとかではなく座標空間上での座標の回転をどうやって処理するのかを知っていて正確に実装できるのかどうかな問題だと思った。
座標空間で回転だったので回転行列で処理した。ただ、計算式の＋と－を間違えてて 1回WAだった。
C - XX to XXX
一方の文字列を指定の処理方法でもう一方の文字列に変換可能かどうかを判断する問題。
文字列の最大サイズがなのでO(文字列のサイズ)くらいで処理できないとTLEになりそう。
操作も難しさしそうに書いているけど結局、2文字以上同じ文字が連続していたら任意の個数まで増やせるというだけ。
文字列のサイズが大きいままだとTLEになりそうだし複雑な処理もできないので（文字,連続している文字数）と言う形でペアの配列にしてサイズの圧縮をした。（解説を読むとランレングス圧縮とか言うらしい。）
2つの文字列をそれぞれ圧縮して、文字の登場順や各文字の連続している個数を確認して文字列Sを指定の操作で文字列Tに変換できるかを判断していった。
D - Circumferences
円をグラフとか木のノードと考えて、指定されたノードと指定されたノードがつながっているかどうかを判断する問題。
円の個数も最大で3000程度なのでO()でもTLEにはならなさそう。
解き方は大きくは2つ思いついた。
1つ目は
初めに書いたみたいに円をノードとみなして、2つの円の中心の距離が半径の和以下ならその2ノードはつながっている。距離が半径の和より大きいならつながっていないとみなしてグラフを作っていく。
後は指定された始点がどのノードで終点はどのノードなのかを調べて、幅優先探索やダイクストラ法などの経路探索アルゴリズムで始点から終点へたどり着くかどうかを調べる。
2つ目は
UnionFind木で指定された始点と終点が同じグループにいるかどうかを確認して答える方法。
ある2つの円の中心距離が半径の和以下ならその2つは同じグループと判断して統合していくっていうのを全組み合わせで実施して木を作っていく。最後に始点と終点が同じグループかどうかを確認して答える。
今回は実装が楽そうに思って2つ目の方法で解いた。
