AtCoder Beginner Contest 250 参加記

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

先週はABCの開催がなかったので、2週間ぶりのRatedコンテスト参加。

ゴールデンウイーク中は、過去問の見直しなども結構こなしており、練習は積み重ねたつもりなので、その成果を出すべく水パフォ目標で臨むこととしました。

Rated参加します。
目標は水パフォ。頑張ります✊

AtCoder Beginner Contest 250 - AtCoder https://t.co/NhV0brJS7Y
— devgenjin77 (@devgenjin77) 2022年5月8日

今回の結果

終わってみれば、4完終了。目標達成は微妙なところとなりました。。。

結局、パフォーマンスはわずかに水色に届かずというところ。一応レートは上がったので、その点はヨシとしましょう。

4完緑パフォでレート上昇しました😂
水パフォまでもう少しでしたが、また来週頑張ります
devgenjin77さんのAtCoder Beginner Contest 250での成績：1582位
パフォーマンス：1187相当
レーティング：1042→1057 (+15) :)#AtCoder #ABC250 https://t.co/SEpYK4VHbL
— devgenjin77 (@devgenjin77) 2022年5月8日

振り返り

E問題を解き切ることが出来ませんでした。

A問題

A - Adjacent Squares

A問題にしては少しややこしそう見た目という印象。

上手いやり方があるかと考えましたが、すぐには思いつかず。とりあえず愚直にマス $(R, C)$ から上下左右を見たときに、盤面の範囲外にならない場合のみ答えにプラス１する実装としました。

途中、実装をバグらせてしまい、タイムロスをしましたがなんとかAC。

8分10秒で1完。少し時間が掛かりすぎです。

提出コード

https://atcoder.jp/contests/abc250/submissions/31518723

B問題

B - Enlarged Checker Board

これもだいぶ面倒な問題かという印象。

マス目 $(i,j)$ を見たときに、 $i$ を $A$ 、 $j$ を $B$ で割れば、現在のマス目に対応するタイル $(a, b)$ が分かる。

あとは、 $a$ と $b$ の偶奇で場合分けし、黒か白かを判断すればよい。

ということで、上記の要領で実装して、ACを取る事が出来ました。

16分5秒で2完。まだ、時間が掛かりすぎているという状況です。

提出コード

https://atcoder.jp/contests/abc250/submissions/31523141

C問題

C - Adjacent Swaps

一瞬、 $x_i$ が右端だったら、先頭の数字と入れ替えるのかと誤読しそうになったが、なんとか踏みとどまった。。

なんかこの手の問題はどこかでやったことがあるかもという既視感を覚えたが、解法はすんなりと出来上がりました。

索引を指定して、何の値が入っているかを管理する配列と、値を指定して、何番目に入っているかを管理する配列をそれぞれ用意し、あとはクエリを順番に処理してにシミュレーションをしていけばよい。

あとは実装と提出を行い問題なくACが取れました。

30分5秒で3完。前回ABCではC問題を落としましたが、今回はすんなり通せたので多少安心しました。

提出コード

https://atcoder.jp/contests/abc250/submissions/31528912

D問題

D - 250-like Number

一読して、制約より $p \lt q \lt 10^{6}$ になることが明らかなので、あとはその範囲で素数を全部探索すれば良いかという印象。

ということで、まず $p \lt 10^{6}$ となる素数全てについて、ぞれぞれに対応する $q$ が何個あるかを数え上げていく方法を取る。

$p$ に対応する $q$ が取りうる範囲は、 $p \lt q$ 且つ $q^{3} \le \lfloor \frac{N}{p} \rfloor$ となるので、あとはその範囲で素数表を素数の数を数え上げをしていけばよい。

当初、素数表をどの範囲まで作れば良いかが不明で、とりあえず最大値をローカルで試したところ、80万ぐらいまで作っとけばいける模様。TLEしないか少し心配でしたが、提出してみたら無事ACが取れましたとさ。

55分16秒で4完。個人的にな印象では、5完目いけるかどうかは微妙な情勢です。

提出コード

https://atcoder.jp/contests/abc250/submissions/31536381

E問題

E - Prefix Equality

途中まで考察したものの、実装が間に合わず。

$dp \lbrack i \rbrack \lbrack 2 \rbrack$ := $A$ の先頭 $i$ 個目までの集合が、 $B$ の先頭 $dp\lbrack i \rbrack \lbrack 0 \rbrack$ 個目から $dp\lbrack i \rbrack \lbrack 1 \rbrack$ 個目までの集合と同一。（存在しない場合は、-1）