結果
順位 795th / 6812 パフォーマンス 1489 レーティング 1779 → 1753(-26)
D問題までの4完でレート減。しかしレート下がってもそんなに悲しくならないくらい今は競技プログラミングへのモチベーションが落ちている。コンテストに出ることは継続しているけれど振り返りを一切しないようになっていて、流石にそれではまずそうなのでここらで再開。
A - Poor
長さ3のstd::vectorに受け取ってソートして上手くできるのかと思って書きかけたが、なんか結局面倒なことになりそうだったので方針転換して条件をベタ書きした。2分以上かかる。
B - Papers, Please
問題文が理解できず頭の悪さを感じた。"APPROVED"、"DENIED"をコピペせず手打ちするという勇者プレイ(普通に通った)。
C - Poll
std::mapで出現回数を数えてから最大のものだけstd::setに詰め直す。range-based forを使うとき、CLionが指摘に従って律儀にconst auto&にするタイプの人間。
D - Pairs
「番目に来る数が
である⇔積が
以下になるペアが
個以上になるような最小の
」が正しいのに、最初の方はずっと「
番目に来る数が
である⇔積が
未満になるペアが
個未満になるような最大の
」をと勘違いしていた。これだと積として存在しない
を答えにしようとするのでWAになる。
まぁそれは些細な話として、この問題は実装をどうするかが要点だったんだろう。自分は最初に「std::upper_boundを使おう！」と心に決めて実装を始めた。
を見ながら比較関数をラムダで書いて与える形式std::upper_bound(begin, end, value, comp)が使えるはずだと確認したところまでは良かったが、ここから罠が多い。まずこのページの「trueとなるすべての要素が、その式がfalseとなるすべての要素よりも前になければなりません」は逆では？ と思ったが、これは!comp(value, element)についての記述なので逆が正しい。ここに気づくのにかなり時間がかかった。またvalueはcompのどっち側の引数に入るかも、上の式を冷静に見れば左側だとわかるんだけど混乱していたので何回も間違えた。混乱していた理由としてはstd::lower_boundだと引数が入る順番が逆になる。
これ本当に難しくて、比較関数を自前で実装するならstd::upper_boundとstd::lower_boundはどっちでも良いんだけど、問題で正と負の場合で2回実装しなければならなくて、それで片方は等号含み、片方は含まないから適切な方を使わなければ？ とか思うと適切な方ってどっちだとみたいな感じになり脳が爆発する。
時間はかかってパフォーマンスは崩壊したけど、なんとか最終的にはそこそこ綺麗には書けた気がするので満足感はある。最近はコンテスト中もわりと綺麗なコードを書きたいという気持ちが強くなってきた。using ll = int64_tすら外しているのもその一環で、タイピング速度はやや落ちている気はするので損はあるんだけど、気持ちの問題。
E - Payment
D問題でさんざん混乱した頭ではこれを30分で処理することなんてできない。桁ごとに見ていって繰り下がりを考慮しながらどうにかこうにかするんだろうということはわかるが、それを適切に実装するのは一日明けて今日実装していても大変だった。桁DPだという気持ちを持っていた方が楽だったのかな。まぁ難しいです。
F問題は解説PDFを読んでもはぁという感じだったのでまた後日。
