日本レジストリサービス（JPRS）プログラミングコンテスト2023(AtCoder Beginner Contest 324)参加記

2023/10/14に開催された、日本レジストリサービス（JPRS）プログラミングコンテスト2023(AtCoder Beginner Contest 324)に参加しました。

先週は、ABC、ARCと、立て続けに惨敗してしまい、あっという間の緑落ちを喰らってしまいました。

再度の入水に向けて地道にレートを稼いでいこうということで、今回も水パフォ目標で頑張っていきます。

Rated参加します。
先週で緑落ちしてしまったので、再度入水に向けて頑張ります✊

日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324） - AtCoder https://t.co/gwQUK9y1qH
— devgenjin77 (@devgenjin77) 2023年10月14日

今回の結果

なんとか５完を達成しました。

パフォーマンスは、水色中間というところ。再度の入水に近づくことが出来ました。

５完水パフォでした😃
devgenjin77さんの日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324）での成績：1298位
パフォーマンス：1398相当
レーティング：1149→1177 (+28) :)#AtCoder #ABC324 https://t.co/JxlnSHItqB
— devgenjin77 (@devgenjin77) 2023年10月14日

振り返り

相変わらず、小さいミスが続いてしまったことが反省材料です。

A問題

A - Same

数列 $A$ の値が全て同じかを判定する問題。ループで判定すれば良いので、やるだけの実装をしました。1分17秒で1完。

提出コード

https://atcoder.jp/contests/abc324/submissions/46521548

B問題

B - 3-smooth Numbers

$N$ を $2$ と $3$ で割れるだけ割った後、 $1$ になっているかを判定すれば良い。

これもやるだけの実装でACが取れました。2分56秒で2完です。

提出コード

https://atcoder.jp/contests/abc324/submissions/46526045

C問題

C - Error Correction

文字列 $S_i$ が、文字列 $T$ と最大１文字違いであるのかを判定する問題。

愚直に判定していくしかなさそうで、なかなかシンプルに実装するのが難しそうな感じ。

仕方なく、 $|S_i| = |T|$ の場合、 $|S_i| = |T| + 1$ の場合、 $|S_i| + 1 = |T|$ の場合それぞれでループを回し、最大１文字違いなのかを判定する実装をしました。

初回の提出では、答えが０件の場合を考慮できておらず、REを喰らいましたが、修正してなんとかAC。23分10秒1ペナで3完です。

提出コード

https://atcoder.jp/contests/abc324/submissions/46544237

D問題

D - Square Permutation

平方数を全探索して、問題の条件に合うように各ケタの数字の数が合っているかを判定していけば解けるだろうという感じの問題。

で、実装して提出してみたら、惜しいところで１WA。。

直感で、 $0$ のケースが抜けてるのかと思い、ググってみると、 $0$ も平方数に入るとのこと。こういうケアレスミスもなんとかしないといけないなあと。

とりあえず、修正してなんとかAC。37分15秒2ペナで4完でした。

提出コード

https://atcoder.jp/contests/abc324/submissions/46553939

E問題

E - Joint Two Strings

最初、難しめの文字列アルゴリズムを使うやつかとおもってましたが、よくよく考えると、単純に解ける問題だとわかりました。

文字列 $S_i$ が $T$ を先頭または末尾から見て、最大何文字を部分文字列として含んでいるかが分かれば、あとは単純な計算で解ける筈。

具体的には、

数列 $A$ を $A_k:=$ 配列 $S$ のうち、 $T$ と $S_i$ をそれぞれ先頭から見て、最大 $k$ 文字を部分文字列として含んでいる文字列の個数とする。
数列 $B$ を $B_k:=$ 配列 $S$ のうち、 $T$ と $S_i$ をそれぞれ末尾から見て、最大 $k$ 文字を部分文字列として含んでいる文字列の個数とする。
連結の先頭にする文字列が、 $T$ の先頭から $k$ 文字を部分文字列に含んでいるとすると、連結の末尾には $T$ の末尾から $|T| - k$ 文字以上を部分文字列に含んでいれば良い。
数列 $A$ でループし、上記の考え方で、答えに足し込んでいく。累積和を使えば、計算量は $O(N)$ に収まる。