れとろのメモ置場

とあるSEのメモ置場

AtCoder Beginner Contest 261

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

結果

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

D問題がDPで解く問題だと判断して実装していたけど微妙に時間がかかった。 C問題までは比較的簡単な気がした。

最近はD問題まで早解きしてパフォーマンスを稼げていたので、今回レーティングの最高値を更新できた。 あと100くらい上げたら水色になれる。

A - Intersection

赤色で塗られている部分と青色で塗られている部分の位置関係のパターンは3通りくらいなので場合分けしても解けそう。

紙に線を引いて考えてみると、共通部分があったとしてその左端はmax(赤の左端、青の左端)になるし、右端はmin(赤の右端、青の右端)になるので、共通部分の両端を求めて距離を計算して答えた。

B - Tournament Result

2重ループで全組み合わせを確認して矛盾がないがどうかを確認する問題。

ループの使い方がわかっているのかと文字列の扱いを確認する問題なのかな。

C - NewFolder(1)

i-1までに文字列S _ {i}が何回出てきているのかを管理して指定された文字列を作成・出力する問題。

どの文字列が何回出てきたのかを連想配列を使って管理すればそれほど難しくない問題。
連想配列を知っているかどうかな問題だと思う。

D - Flipping and Bonus

結論から言うとDPで解く問題。

DP[コイントスの回数][カウンターの数]として、

DP[i][j] = DP[i-1][j-1] + X _ {i} + j連勝のボーナス でDPを更新していけば良い。