AtCoder Beginner Contest 241 (Sponsored by Panasonic) 参加記

2022/2/26に開催されたAtCoder Beginner Contest 241 (Sponsored by Panasonic) に参加しました。

実はこの日は飲み会などがあり、直前まで参加するかどうか迷ってたのですが、コンテスト開始の10分前に帰宅できたので、この際参加してみることにしました。

とりあえず毎度のことですが、レートが上げられるように頑張ろうという感じです。

飲み会後ですが、ギリギリ間に合ったのでRated参加します。とりあえずレート上げできるようにがんばります✊

AtCoder Beginner Contest 241（Sponsored by Panasonic） - AtCoder https://t.co/ZPRzBHwjoO
— devgenjin77 (@devgenjin77) 2022年2月26日

今回の結果

で、、今回のABCはなんと3完という体たらく。。うーん、まあ比較的Dが難し目だったかなー。

今回も緑下位ぐらいのパフォーマンスということで、都合4連敗目を喰らう羽目になりましたとさ。

3完緑パフォで4連敗目を喰らいました😭😭😭😭
明日頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 241（Sponsored by Panasonic）での成績：2577位
パフォーマンス：983相当
レーティング：1026→1021 (-5) :(#AtCoder #ABC241（SponsoredbyPanasonic） https://t.co/gIaYr5ZXut
— devgenjin77 (@devgenjin77) 2022年2月26日

振り返り

D問題で完全に判断を誤ってしまいました。

A問題

A - Digit Machine

$k = 0$ を初期値として、 $k = a_k$ という処理を3回行った時の $k$ が答えとなる。

実装して、問題なくACを取ることが出来ました。

4分3秒で1完。

提出コード

https://atcoder.jp/contests/abc241/submissions/29664853

B問題

B - Pasta

配列 $A,B$ 双方を昇順ソートしておき、マッチング処理を行う。

配列 $B$ の要素が全てマッチする場合はYesと表示、それ以外はNoとする。

ちょっと、実装でもたついてしまい、時間は少しかかりましたが、こちらも問題なくACを取れました。

19分48秒で2完。

提出コード

https://atcoder.jp/contests/abc241/submissions/29677674

C問題

C - Connect 6

問題を一読すると、なんか五目並べならぬ、六目並べという感じがするこの問題。

全てのマスについて、右方向、下方向、右上方向、右下方向の連続6マスをチェックし、6マスの内4マス以上が黒く塗られていれば、あとは高々2つを塗ることで黒6つ以上の連続は可能となる。

あとは、範囲外の参照に気をつけながら実装すればOK。

ということで、少し実装に苦労したものの、あっさりとACが取れてくれましたとさ。

41分7秒で3完。ここぐらいで、2000位以内には行っていたので、もしかすると好成績いけるかという感触はありました。

提出コード

https://atcoder.jp/contests/abc241/submissions/29687610

D問題

D - Sequence Query

クエリを処理していく系の問題。愚直に実装するとTLEになるやつなので、なんらかの工夫は必要という感じだが、すぐにはわからん感じ。

とりあえず、ソート処理を全体で1回に抑えようという方針にしてみる。

数列 $A$ を、ペアオブジェクト( $x$ , 何回目のクエリで追加されたか)として配列で管理し、全てのクエリを先読みして数列に値を追加して1度昇順ソートする。その後、2と3のクエリを処理する際、二分探索で配列を探索する位置を決定し、何回目のクエリで追加された数字かを考慮しながら順に探索するという実装を行なってみた。