AtCoder Beginner Contest 247に参加しました。
結果
A,B,C,D問題の4問正解でした。 E問題は問題文を読んで多分尺取り法だとは思ったけどうまく実装できなかった。尺取り法で解く問題の練習不足だった。
A - Move Right
問題文の通りに実装する。文字列の扱い方がわかっているかどうかに関する問題かな。
解き方はいろいろあると思うけど要するに、与えられた文字列の左端に"0"を付け足して、先頭から4文字を表示させればいい。1文字目の0は確定なので直接表示させても良さそう。
B - Unique Nicknames
問題文を理解するのに時間がかかった... 要するにほかの人の姓名を被らないように姓か名を選べるかどうかを判定すればいい。
制約を見るとNが小さいので二重ループで確認していくので十分間に合う。
C - 1 2 1 3 1 2 1
Nが小さいので事前にを計算して入力されたNに対応する
を表示させればいい。
は
がわかっていればすぐに作れるので
から順番に作っていけば特に苦労することもなく用意できる。
D - Cylinder
問題文を読むと、配列の後ろに要素を追加しつつ、先頭から要素を順番に取り出しせれば良さそうなのでキューが適してそうに思う。次に制約を確認すると1度に個を出し入れする可能性もあるのでc個の要素を出し入れする際に1個ずつ処理していたらTLEになりそうだと予想できる。
どうにかして要素の出し入れで処理の省略が必要そう。簡単に思いつくのは、どの要素が何個続くのかをペアにしてキューに入れる。その場合ペア1個分で必要以上に要素を取り出す場合があるので(ペア1個で個分を表現しているから)、取り出したペアを更新してキューの先頭に戻す必要が出てくる。
ここまで考えて、双方向キューを使いつつ要素には数xがc個連続していることを表すペアを使うことにして解いていった。
実際に実装してみると、キューを取り出したあとcを更新してキューに戻す部分が少しややこしくなったけど無事ACできた。
E - Max Min
問題文を読むと、数列から条件を満たす区間の数え上げ問題とみなせる。二重ループで解けば一応答えは出せるけど、制約を確認すると数列の要素数が最大で個になるので二重ループだとTLEになる。TLEにならないようにするには
くらいのアルゴリズムで解く必要がある。
で条件を満たす区間の数え上げだと尺取り法で解けそうだと考えた。
あとは実装するだけだったけど、区間の伸ばす条件がわからなくて実装できなかった…
尺取り法の問題の練習不足だった。尺取り法自体は理解していてコードも何回か前のABCで何度も書いたんだけどなあ。
