55. AtCoder参加記録（AtCoder Beginner Contest 237）

現状です。4回参加でレート530です。ここまでが調整期間で、次回からちゃんとしたレートが出るようになるみたいです。

f:id:ibako_piyo:20220131083634p:plain

f:id:ibako_piyo:20220131083906p:plain

今回はパフォーマンス974でした。ABCDを通して、EFGExは未解答です。

f:id:ibako_piyo:20220131084056p:plain

各問題の感想です。

A

恒例のやるだけ問題です。

前回は3分24秒で通したので、だいぶ良い感じに速くなっています。

B

今回のコンテストは、開始5分後くらいまでB問題に何故かD問題が掲載されているという不具合がありました。Aを爆速で解いた結果、見事これに引っ掛かってしまいました。

解いている最中は「Bにしては重い問題だな…」と思っていたのですが、Bなのであまり考えず適当に書いて提出した時、何故か400点問題として表示されてることに気付き、「あれっ」となりました。そしてリロードすると知らない問題が出てきて焦りました。

適当に提出して（＝BにDの解答を提出した扱いになった）のは後ほど運営側から無効化されて、成績には影響ありません。

オリジナルのB問題自体は行列の転置をするだけということで、本当にどうってことない問題でした…。

C

回文判定ですが、「先頭に好きな数だけ a を付けられる」という条件付きです。

ここから「"基本的に" 先頭・末尾の a は無視できる」と考えました。つまり、先頭・末尾のスキャン用インデックスをそれぞれ持ち、a 以外が出てくるまでスキャンして、そこから回文判定を行えば良いです。先頭・末尾のスキャンインデックスが「先頭 <= 末尾」を満たさなくなった時点で回文判定は成功です。

ただし a を好きに付けて良いのは先頭だけなので、先頭の a の数が末尾のそれより多い場合は失敗となります。その例外判定だけ気を付けます。

これで $O(|S|)$ で解けて間に合います。Cにしては若干罠がある問題だな、と思いました。

D

初めはBとして表示されていた問題。適当に書いたやつをそのまま提出したら TLE になりました。いや、Dだと分かった時点でもう少しちゃんと考えるべきだった…。

List.Insert を使っていたのですが、追加に $O(N)$ 掛かるので全体で $O(N^2)$ となってしまい間に合っていません。ただ、ちょっと考えると追加は $O(1)$ で出来そうでした。L でも R でも関係するのは「直前に見ていた数字と、その前後」のみです。なので、それを記憶しつつ双方向リストを書いてやればいいな、と思いました。