ABC183振り返り

投稿者: | 2020年11月16日

ここ2週間ABCに参加していなかったのですが、研究室の後輩から質問が来たので、答えるついでにD問題まで解きました。

1.A問題

問題:A - ReLU

キーワード:やるだけ,if文

if文書けますか?という問題。三項演算子の練習にも丁度いいんじゃないですかね?

2.B問題

問題:B - Billiards

キーワード:二次元平面,数学

中学校で習う相似ができればわかる問題。ただ単純に中点じゃね?っていうコードを書いたらダメです。

それぞれのy座標から相似比を出して、x座標の差を相似比で分けてあげて、どっちかからその分動かすと答えが出ます。

3.C問題

問題:C - Travel

キーワード:全探索

next_permutationが使えれば解ける問題です。1から出発して1に戻ってくるというのがめんどくさいので、先頭に1を追加、末尾に1を追加して完全なルートを作成しています。

変数を表示させてるあたり、まあまあ苦労してました。原因は27行目のループ回数が2つ多かったことです。

4.D問題

問題:D - Water Heater

キーワード:いもす法

問題を読めば、1分毎に必要な量がわかれば良さそうだということが読み取れます。つまり、毎分の必要量をタイムラインのようにもち、毎分ごとの必要量と供給可能量を比較してあげればよさそうです。

それを愚直に実装すると次のようになります。

s分からt分までの区間に必要量pリットルを足しています。

しかし、この方法だと、s=0,t=2e5のみの入力があった場合、vector全体をN回も書き込みに行くことになります。どう考えてもTLEになります。

そこで、いもす法と呼ばれるアルゴリズムを用います。競プロでお馴染みの累積和を発展させたアルゴリズムらしいです。

先程の方法では、ある区間を何度も書き込んでいたので低速になりました。ならば、区間の最初と最後に行う演算結果だけを記入しておいて、最後にvector全体で累積和を取れば高速化できます。

imosu.png

これを実装すると次のようになります。

典型問題らしいので覚えておこうと思います。

5.おわりに

参加していませんが、参加していてもC問題をACしてD問題でTLEしていたと思います。

ただ、競プロ界隈ではいもす法は有名らしいので、こういう典型問題がD問題に出たときはちゃんとACできるように勉強したいと思いました。

6.参考文献

いもす法

AtCoder ABC 183 D - Water Heater (茶色, 400 点)

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください