AtCoder Beginner Contest 234 参加記

2022/1/8に開催されたAtCoder Beginner Contest 234に参加しました。

2022年最初のABCコンテストになります。今年は昨年より競プロに力を入れて、どんどん上を目指していきたいので、今回はとりあえずレート上げを達成して初回のコンテストを終えられるようにという気持ちで臨むことにしました。

Rated参加します。2022年最初のコンテストは好結果で終えて良いスタートを切りたいもんですな。
AtCoder Beginner Contest 234 - AtCoder https://t.co/tI9ntY6RYQ
— devgenjin77 (@devgenjin77) 2022年1月8日

今回の結果

んで、今回の結果は5完。E問題に大分時間を取られたので、タイムは大分遅めだったという印象です。

パフォーマンスは緑の上位。とりあえずレートを上げることはできたので、最低限の目標は達成しました。

5完緑パフォでレート上げ！
この調子で今年中に水色行けるように頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 234での成績：1887位
パフォーマンス：1116相当
レーティング：1019→1029 (+10) :)
Highestを更新しました！#AtCoder #ABC234 https://t.co/0XtED2Zi9t
— devgenjin77 (@devgenjin77) 2022年1月8日

振り返り

D問題までは順調にいってましたが、E問題でやたらと時間を取られてしまいました。

A問題

A - Weird Function

関数 $f(x)=x^{2}+2x+3$ を定義し、関数を再帰的に呼び出して答えを求めるという問題。

問題文のとおりに実装し、ACを取ることができました。

提出コード

https://atcoder.jp/contests/abc234/submissions/28381813

B問題

B - Longest Segment

二点間の距離の最大値を求める問題。制約上の最大は $N=100$ であり計算するパターン数としては最大でも $100 \times 99$ 程度なので、２重ループの実装で問題なし。

こちらも問題なくACが取れましたとさ。

提出コード

https://atcoder.jp/contests/abc234/submissions/28388630

C問題

C - Happy New Year!

入力例2を参考に愚直に小さい方から数え上げてみると、 $2,20,22,200,202,220,222,2000,2002,2020,2022$ という感じで確かに $2022$ が11番目に小さい数字となる。

で、よくよく考えるとこの数字の動き方が2進数を小さい方から数え上げたものに対して1を2に置換しただけのように見える。

確かに、11を2進数にすると1011となるので、結局答えは、入力を2進数の文字列に変換し、1を2に置換すればOK。

ということで、あとは実装だけしてACが取れましたとさ。

提出コード

https://atcoder.jp/contests/abc234/submissions/28391968

D問題

D - Prefix K-th Max

この問題は、もう少し単純に考えればよかったかと後悔しました。

先頭から愚直に $K$ 番目に大きな数値を求めようとすると、TLEになりそうなこの問題。ということで先頭からでなく、配列の一番後ろまで先読みする方法が有効ではないかと思い付いた。

$i = N$ の場合、 $K$ 番目に大きな値は $N - K +1$ で確定。この値を $Kth$ として定義し、解答用の配列に追加
順列 $P$ を後ろから見ていく。 $P_N$ を参照し、 $Kth$ より大きい場合は、現在の $Kth$ を使用済みの数値の集合 $S$ に追加し、 $Kth$ は集合 $S$ に含まれない値になるまで1ずつマイナスしていく。 $Kth$ が確定したら、解答用の配列に追加。
2の処理の要領で $P_{N-1}$ から $P_K$ まで順次処理する。
解答用の配列を、後ろから出力していく。