イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。

99. AtCoder参加記録（AtCoder Regular Contest 138）

プログラミング AtCoder

現状です。13回参加でレート 992 です（14回参加するまでレート補正期間中）。

ARCデビュー戦は惨敗でした。

f:id:ibako_piyo:20220409233827p:plain

f:id:ibako_piyo:20220409234055p:plain

今回はパフォーマンス 845 で、なかなかやらかしています（ワースト2）。

Aを通して、BはWAで、CDEFは未解答です。Aで3ペナです（ひどい）。

f:id:ibako_piyo:20220409234309p:plain

各問題の感想です。

A

とりあえず $K+1$ 項め以降に $K$ 項めまでの最小値（ $m$ とします）より大きい値がないとダメだな、と問題を整理。ここから、最も $K$ 項めに近い、 $m$ より大きい値を持って来ればよさそう？と考えました。

色々パターンを考えて、結局、 $A_i (i \le K)$ , $A_j (j \gt K)$ で $A_i \lt A_j$ を満たすペアを全て見て、 $j - i$ の最小値が答えになると分かりました。愚直にやるのは無理なので、各 $A_i (i \le K)$ について $A_i$ 以下の値があるインデックスの最大値を Dictionary に保存し、MultiSet で $A_i$ 集合を記録して、 $A_j(j \gt K)$ について UpperBound から $A_j$ 未満のキーを取得し、上記 $j - i$ の値を求めて最小値を出せば $O(N \log N)$ で答えを出せます。

…ということに開始15分くらいで気付いていたのですが、太文字にした「以下の」最大値を保存するという処理が抜けていて、WAの原因が分からず完全に焦ってしまいました。

結局、40分くらいで諦めてB問題に移りました。

そして、B問題を諦めてから戻ってきたときにバグに気付き、かなり焦りながら修正してなんとか105分で通しました（ひどい）。

B

Aでやらかした焦りから完全に見当外れな解き方を試みていました。Aをなんとか通してから戻ってみると、素直に（？） $A$ を1手ずつ戻していけば解けそうでは…？と気付きましたが、時すでに遅しでした。

C, D, E, F

見てないです。

今回はかなり反省点の多いコンテストでした。普通に0完も見えていたので…。

複雑なアルゴリズムになった場合、一度文章で整理してから実装に落とし込む方が無難
変なバグらせ方してるなら早めに次の問題を見に行くべき
ちょっと焦りすぎ…