れとろのメモ置場

とあるSEのメモ置場

AtCoder Beginner Contest 297

AtCoder Beginner Contest 297に参加しました。

結果

A,B,C,Dの4問正解でした。

E問題が解けなかった。愚直に解くとTLEになりそうでなんか解き方ないかなと思ってDPで攻めてみてた。

A - Double Click

N個の数値が入力されるので数値間の差がD以下かどうかを判断し、 D以下のものが1個以上あるかどうかを答える問題。

入力を配列にでも入れて、数値間の差分を計算できれば解ける問題だと思う。

入力を配列に入れるのと演算、分岐ができれば答えられる問題だと思う。

B - chess960

文字列が与えられるのでその文字列が複数の条件すべてを満たしているかどうかを答える問題。

文字ごとのインデックスをどうにかして管理できれば答えられると思う。

先頭から1文字づつ見ていって、この文字は何番目と何番目にあるみたいなのを配列ででも管理すれば良さそう。

C - PC on the Table

H個の文字列が与えられるので各文字列に対してTTをPCに置換し、置換後の文字列H個を出力する問題。

文字列1個に対してTTをPCに置き換えられればそれをH個分繰り返せば良い。 文字列を1文字ずつ確認できて、文字列中の任意の文字の置換ができれば解ける問題だと思う。

D - Count Subtractions

A,Bが与えられたときに大きい方を 大-小の答えに置き換え続けてA=Bになるまでに何回置き換えたかを答える問題。

A>Bとして何回A-Bができるかを考えるとA-BがB以下になるまでなのでA/B回になりそうで、 最終的にAは何に置き換えられるのかなと考えるとA mod Bの答えに置き換えられそうだと考えた。
商と余りを使うような気がして、ユーグリッド互除法っぽさを感じた。

適当な値で考えてみると、 何回A-BができるかはA/Bの商だけBを引けて、
置き続けた最終結果はA mod Bになるっぽいとわかった。

なのでA=BになるまでA/BとA mod Bを計算し続けて(AをA mod Bに置き換えて、AとBをスワップしながら常にA>Bとして処理を行う)、A/Bの答えを足し続けていく。
A=Bのときの置き換え処理だけは余計なので、最終的な結果から1引いたものを答える。