競プロ日記009: ABC276 - カメヲラボ

ABC参加8回目

ABC275は一度お休みして，AtCoder Beginner Contest 276に参加しました．ABCDの4問を解きました．E問題に目を通したのが残り10分ちょいでしたがマラソンマッチでよく書くタイプの問題だったので「いけるかも！」と思ったけど間に合いませんでした😢

解く順番をちょっと変えてみた

これまではA問題から解いていたんですが，データセットのダウンロードに時間がかかってしまったため待ち時間の間にB問題に目を通していました．そうすると頭の中がB問題になってしまったのでBACDという順番になりました．全体的な出来には対して影響しなかったけれども，無駄な待ち時間は数十秒くらい減ったので悪くないかも．C以降の問題も見た方が良いのかもしれない．

C問題: Previous Permutation

どうやらprev_permutationという関数があるらしいけど知らなかったので，真面目に考えました．数字列の後の部分が単調増加している区間を見つけて，そのひとつ前（単調増加が崩れている箇所）から並び変える感じですね．

9 8 6 5 10 3 1 2 4 7

という例なら，

3 1 2 4 7

という部分で，3と2を入れ替えて，

2 1 3 4 7

のようにして，2より後の部分を降順にソートします．

2 7 4 3 1

解説とかは見てないので想定解かどうかは知らない．

D問題: Divide by 2 or 3

結果的にそのまま実装すればよかっただけなのだけど，ここら辺までくると余計なことを考えて迷ってしまうことに気付きました．「本当にそれだけで良いの？何か高速に計算しないとダメ？」みたいな．大きいテストケースを想定したときの時間感覚が身についていなくてそういう思考になるのだろうなと思うので，やっぱり過去問等使って練習しないと早解きは難しそうですね．

3つ以上の数の最大公約数を求める方法がパッと思いつかなかったのでものすごくややこしい実装をしてしまいましたが，よく考えたら3つ以上でも順番に計算すれば良いだけでしたね．焦りは禁物．