AtCoder Beginner Contest 221 参加記

2021/10/2に開催された AtCoder Beginner Contest 221に参加しました。

atcoder.jp

ここ最近は安定して緑パフォが取れており、レートの方も上昇傾向が続いています。

とりあえず、緑コーダーに復帰したいので今回も4完の緑パフォあたりを目指してコンテストに臨むこととしました。

今回の結果

そして今回も4完達成となりました。最近の精進の結果が出ているのかもしれません。

ABC221結果

ABC221結果

パフォーマンスは、超久々の4桁。緑復帰がだんだんと見えてきました。

振り返り

Dまでは順調でしたが、Eを解ききることができませんでした。

ABC221提出結果

ABC221提出結果

A問題

A - Seismic magnitude scales

問題文のとおり実装。32^{A-B}を求めて出力することでACが取れました。

提出コード

https://atcoder.jp/contests/abc221/submissions/26277082

B問題

B - typo

愚直に全ての操作のパターンを試行する方針で実装。これも問題なくAC。

提出コード

https://atcoder.jp/contests/abc221/submissions/26284562

C問題

C - Select Mul

Nより、大きい数字から順次取り出し、2つの整数のうち数の小さい方の末尾に付け加えるような形で振り分ければよい。この処理で行けば制約より0始まりの数字に分離されることが無い。

この要領でACが取れました。

提出コード

https://atcoder.jp/contests/abc221/submissions/26295363

D問題

D - Online games

問題を一読して、いもす法で解くやつだというのは分かったが、制約を見ると単純な配列で実装するのは無理そうだということが分かった。

ということで、サービス開始からの日数をキーとして、その日にログインした人からログアウトした人を引いた数を管理するHashMapを作成する方針で実装。

HashMap上にデータを投入できたら、キー順でソート。隣り合う要素のキーの値の差から日数を求め、値は、いもす法の要領で求めることで、ACを取ることができました。

提出コード

https://atcoder.jp/contests/abc221/submissions/26309280

E問題

E - LEQ

自分的には珍しく、E問題の内容がなんとなく理解できたので、これはなんとか解けるかという思いで残りの40分を全て投入することにしました。

求めるべき答えは明確で、1 \le i \lt j \le Nを満たす全ての(i,j)について、

A_i \le A_jの場合、2^{j-i-1}を答えに加算すればOK。

で、そのとおり実装してみて、サンプルが通ったんでいけるかと思ったら、残念なことにTLEを喰らってしまいました。。

2^{j-i-1}をメモ化することで多少改善できるかと思いきや全然ダメで再度TLEを喰らう。。。

結局、これ以上の改善方法がわからずじまいで時間切れとなりました。

で、、解説を見ると、BITを使うなど色々工夫が必要だったとのことで、結構難易度も高めでした。まあ、BITあたりは一度ライブラリの勉強などで使ったことがあるので、この問題は解説ACするなどして、次回同種の問題が出る時に備えようかと思います。

F問題

F - Diameter set

問題すら見れておりません。

G問題

G - Jumping sequence

問題すら見れておりません。

H問題

H - Count Multiset

問題すら見れておりません。

これまでの実績

レートは大幅に回復。緑復帰が現実的に見えてきました。

コンテスト実績

コンテスト実績

総括

ここ数回は安定して緑パフォが出せており、あと数回で緑復帰ができそうな勢いです。

この勢いを保つべく、今回の問題の復習と並行して、過去問の緑、水色パフォあたりを解いていき次のABCに臨もうと思います。

ということで、また次回も頑張ります。