- やった回: ABC331
- 成績: ABC3完 / 0ペナ(＋未AC7ペナ) / 13:40(ペナ込み)
- パフォーマンス: 949
レーティングの話だけで言えば、私にしては珍しく早解きに助けられた回。ただこのEは解きたかったなぁ…
Dもあとでupsolveしなきゃとは思っている。
A問題: ABC331-A Tomorrow
日→月→年の順に地道に繰り上がり判定をしていきました。
競プロ女子会で感想会してて話の流れで「キーエンスコンのときのタイムゾーン処理がすごい嫌でした、あれ前回でしたっけ」とか言ってたんですが、それは私がバチャったのが先週の日曜日というだけでした……
B問題: ABC331-B Buy One Carton of Milk
この間みたいに変に策を弄そうとして悩み、でもよく考えたらこれも全探索でいいじゃんとなり素直に実装しました。すんなり通ってよかったです。
C問題: ABC331-C Sum of Numbers Greater Than Me
受け取った配列と、それをコピーしてソートした累積和の配列を作っておいて、全体の合計と部分の累積和との引き算をする。引き当てるインデックスは二分探索で求められる。
競プロ女子会の感想会でコードを共有したら変数名を褒められてとても嬉しかったです。
E問題: ABC331-E Set Meal
(upsolveコード) atcoder.jp
単純に考えれば主菜も副菜も一番高いものを持ってくればそれが一番高い定食になる。が、NGな組があるのでちょっと話がややこしくなる。
何故か掛け算九九の表を見ながらすごい悩み、PriorityQueueだのDFSだのまで持ち出したんだけど結局解けずに終了。
最終的に着地した解法としては、制約から考えてありうる選択肢が1個しかなければ主菜と副菜の組み合わせの総数は105以下なので十分全探索出来るし、NとMが105あるなら半分弱はありうる組み合わせ*1なのでシンプルに配列のインデックスを保存できるデータ構造でソートしておいて、それぞれの主菜に対してありうる一番高い副菜を組み合わせた最大値を探索していけばいい、という感じでRubyのACコードを参考にしつつどうにかAC。
1/24追記: D問題 ABC331-D Tile Pattern
(upsolveコード) atcoder.jp
予想外の累積和問題。言われてみれば確かに～と言う感じ。
Rails Girlsの競プロ同好会のフリー回(？)にべーたさんといしりば～さんとわちゃわちゃしながら解きました。
解説を読んでも「とりあえず累積和ということは理解したがどうなってるのこれ」という感じだったので、コンテスト当日にACしていたRubyコードの中で解説に近いものを見つけ、写経してみましたという感じのコードになっています。
何をしているのかは概ね理解したが、正直同じ問題を出されてソラで解ける気はまだしない。さすが水diff問題。
とりあえず二次元の累積和と言う概念を理解できたのでヨシとしましょう、という感じの締めになりました。
ということで今週も対ありでした！
*1:これも一種の鳩の巣原理ってことでいいんだろうか
