tokuminiさんのＳｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 289）での成績：419位
パフォーマンス：1937相当
レーティング：1849→1858 (+9) :)
https://atcoder.jp/users/tokumini/history/share/abc289?lang=ja
E問題まで20分もかからない良いペースで解けていたのに、そこでビタッと止まってしまった。
自分の競プロスタイルをプロ棋士でたとえるなら、早見え早指しマッハ田村だということで。
A - flip
変にテクいことはしようとせず、普通に分岐させる。
B - レ
難しいB問題。進めるところまで進んで、そこまで逆順で出すことを繰り返す。
C - Coverage
ビット全探索します。
D - Step Up Robot
DPします。モチがあるところからは遷移を始めないようにブロックするが、そこへ到着すること自体はできるという点に若干注意を払った。
E - Swap Places
問題設定自体は難しい遷移を要求されているが、N2もM2も許されているので頂点も辺も拡張したグラフでダイクストラ法をやると通っていた。
F - Teleporter Takahashi
問題を理解する程度までは触ってみたが、「操作列を1つ構成してください」系の問題がそもそもあまり得意な印象もない、かつ順位表を見てもGの方が解かれていた、ので飛ばした。
G - Shopping in AtCoder store
F問題と比べて、こちらの方が馴染みのありそうな問題設定なのでこちらに1時間ちょいの時間をほぼ全て投入する。
BもCもソートしておいて考えると、Cの先頭にC=0というものがあると考えて、そこからCが徐々に増えると「人数分×Cが増えた分」がどんどん増えていく感じ。
最初の30分は遅延セグメント木で解けるかと勘違いして溶かした。
残りの30分ちょいは、解説にあったように「y=ax+bの直線がN本あって、M箇所でそれらのうちの一番上の値が欲しい」という問題に帰着することを考えていて、いかにも典型で解けそうなのに解けないとずっと苦しんでいた。傾きの順番に考えて、どこから今までの直線群を上回るかを考えて管理していくという発想自体は悪くなさそうだったが……。
