AtCoder Beginner Contest 158

AtCoderはじめてました

今の会社に入るにあたってコーディング試験があったのですが、その時に時間制限の中でコーディングをするのが圧倒的に苦手になっていたことが解りました。これの対策として、2019/03 くらいからAtCoderをやっており現在まで継続しています。

2019/10 までに緑コーダーになるのを目標としていましたが、断片的にしか勉強していないこともあって 2020/02 にようやく緑になりました。

A - Station and Bus

入力が AAA or BBB の時はバスが不要でそれ以外は必要になるので、そのまま出力します。

B - Count Balls

青ボールをB, 赤ボールをR と表現すると、A=3, B=1 のとき最終的なボールの並びは BBBRBBBRBBBR...BBBR と4個ずつの繰り返しとなって表現できます。 N=10 のとき、先頭10個のボールは BBBR × 2 + BB という形になりますが、これは N ÷ (A+B) の商( BBBR の繰り返し回数)とあまり( BB の文字列長)として計算できます。

桁がデカそうなので多倍長整数を使いましたが、後から見返すと64ビット整数で十分に表現可能でした・・

C - Tax Increase

こういう問題で浮動小数点を使うとだいたい合わないので、愚直に小さい順に計算していきます。入力条件の A, B は最大で100と大変小さいので、0から20,000くらいの税抜き価格を順番に計算して条件を満たし次第出力すればOKです。 20,000 までで条件を満たさなければ -1 です。

D - String Formation

クエリの度に文字列を反転したり、生成する処理をしてるとTLEで死にそうなやつです。 元の文字列S, 頭に付与していく文字列, 尻に付与していく文字列 をそれぞれストックしていきます。

反転クエリが奇数回登場していると反転状態なので、それは状態として持っておきます。

Fi = 1 かつ非反転状態 or Fi = 2 かつ反転状態 のときは頭につける
それ以外の時は尻につける

という感じで文字列をストックしていき、最終的な出力の際にも反転クエリの回数を鑑みていい感じに反転出力すればよいです。 D言語では string とか char[] を使うと動的長なのがネックになりやすいので、私は雑に固定長で処理しました。

E - Divisible Substring

愚直に多倍長整数でやったら5桁の時点でTLEとなることが解り、提出しませんでした。ジャッジに無駄な負担をかけないのは淑女の嗜みなのです。

F - Removing Robots

ロボットを左から順番に並べて「右側にいるロボットを何台巻き込んで消えるのか」を計算しておきグループ分けをしました。グループごとに組み合わせ数を出して、それを累乗していくと答えがでてくれるのではないだろうか、と思いますが時間も思考も足りませんでした。

締め

きりみんちゃんの記事が競プロについての話を最高にまとめてくれているので、気になる人はこっちを見ましょう qiita.com