AtCoder Beginner Contest234に参加しました。
結果
A,B,C,D問題の4問正解でパフォーマンスが840でした。 D問題が割と解けるようになってきたので次はE問題が安定して解けるようになりたい。
A - Weird Function
問題文を読むとめんどくさそうな数式があったからどうしようと思ったけど、を関数として定義すれば簡単に解けるので数式を全部関数化して解いた。
自作関数を作成して使えるかどうかの問題だと思った。
B - Longest Segment
聞かれている内容自体は距離の最大値はどれくらいかという簡単な問題。制約を確認するとなので二重ループを使った全通りでも間に合うと判断した。
なので二重ループで全組み合わせを試しつつ、2点間の距離を計算して最大値を更新していけば解ける。
C - Happy New Year!
1番小さいものからいくつかを考えてみるとKを2進数表記しつつ1を2に置き換えた値がそのまま答えになると気づいた。
なので、受け取ったKを2進数に変換して1を2に置き換えた文字列を出力する。
始めはKを受け取りつつ、ビット全探索でiビット目が1かどうかを判断する処理を流用して処理しようとしたけどサンプルの時点で何故か一部の答えが合わなかったので諦めて2進数への変換処理に置き換えて解いた。
D - Prefix K-th Max
始めはDP使って解くのかなと思いつつ、手計算していくとDPじゃなさそうとなった。
ちょっと考えてみると、K番目に大きい値は、新しく注目するの値によって現状維持か、K-1番目に大きかった値と入れ替わるかのどちらかになることに気づいた。今答えた値より
が小さい場合は現状維持。
今答えた値より
が大きい場合は答える値が更新される。なので１～K-1番目までをソートして管理しつつ
が大きかったときは
を含めたK個の中から最小のものを取得できれば良さそう。
ここまで考えて、１～K-1の値を優先度付きキューで管理すればソートも最小の値の取得も簡単にできるので、優先度付きキューを使って解いていった。
