AtCoder Beginner Contest 242 参加記

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

atcoder.jp

ここ最近のRatedコンテストの成績は惨憺たるもので、現在5連敗中。レートの方も3桁落ち目前というところまで落ちてしまいました。。

ということで、なんとか今回こそ連敗を阻止するぞ、という気持ちで臨むこととしました。

今回の結果

で、、、そんな思いも虚しく、今回も3完という結果となりました。。。

ABC242結果
ABC242結果

パフォーマンスは、またまた緑の下というところで、今回も下げ。結局、レートは3桁落ちになりましたとさ。

振り返り

今回は、ジャッジのトラブルやこちら凡ミスもあり、なんかグダグダになってしまいました。

ABC242提出結果
ABC242提出結果

A問題

A - T-shirt

X \le Aの場合は必ずもらえるので、確率は1。

X \gt Bの場合はもらえないので、確率は0。

あとは上記以外の場合をどうするかというところですが、とりあえずそれっぽい計算をしてから提出。

で、、結果を確認しようとしたら、WJ...のまま一向に判定される気配がない。

明らかになにかおかしいと思いつつも、ツイッターとかみても何もアナウンスはなさそうなので、とりあえずB問題に進みました。

・・・・・

で、C問題を出そうとしたぐらいで、Aの提出がWAになってることに気づく。というか、そもそも出力すらしていないという凡ミス。。。

で、とりあえず標準出力に答えを出すようにして提出したら、これもWA。。。というか、確率の計算がめちゃくちゃだった。。。

で、確率計算を\frac{C}{B - A}という形でちゃんと実装したらやっとこさACが取れましたとさ。

24分9秒の2ペナで3完。大分グダグダになってしまいました。。。

提出コード

https://atcoder.jp/contests/abc242/submissions/29881116

B問題

B - Minimize Ordering

文字列S中の文字を昇順ソートして出力するだけの問題。

とりあえず実装して、サンプルまで通ったので提出。が、、待てど暮せど、ジャッジ待ちのまま。。。

とりあえず、結果はそっちのけでC問題に進みましたが、後で確認するとACでした。

8分4秒で1完だったようです。

提出コード

https://atcoder.jp/contests/abc242/submissions/29871536

C問題

C - 1111gal password

なんかDPを使う系の問題のような気がする。最近のABCのC問題はDPを出してくるのか。。

とりあえず、DP配列を作る。dp \lbrack i \rbrack \lbrack j \rbrack := i桁目がjであり問題の条件を満たす数のパターン数とする。

あとは、漸化式を適切に立てて計算するだけ。実装して提出みたら、あっさりとACが取れてくれましたとさ。

あとで解説で復習したら、だいたい同じことをやっていたので、妙に安心しました。

22分15秒で2完。で、ここでまだA問題が通ってないということに気づいてしまいました。。

提出コード

https://atcoder.jp/contests/abc242/submissions/29880123

D問題

D - ABC Transform

超絶ややこしそうな問題という印象のD問題。

解法を立ててみるまで、サンプルの文字列の遷移をメモ帳に起こしたりして法則性がないかをみるなどし、だいぶ長考しました。

で、思いついた内容としては以下の通り。

  • t = 0の場合、答えはS_kとなる。

  • k = 1の場合、答えはS_1からt文字分進めた文字になる。

  • kが偶数の場合、答えはS^{t}k - 1文字目から1文字分進めた文字になる。

  • kが奇数の場合、S^{ (t - 1) }\lceil \frac{k}{2} \rceil文字目から1文字分進めた文字になる。

  • tkの制約がやたらと大きいが、S^{ (t - 1) }の状態を見る時に、kを2で割る計算が行われるため、最大でも60回程度の状態遷移を行えば答えに辿り着きそう。

ということで、なんとか実装に漕ぎつけようとしましたが、サンプルすら通せずで時間切れという結果になりましたとさ。。

で、悔しかったので、コンテスト終了後もなんとか解説を見ずに粘って実装したところ、なんとかコンテスト後だけどACがとれました。

https://atcoder.jp/contests/abc242/submissions/29905495

結局ノーヒントで解くことはできたけど、コンテスト時間内で解くのはまだまだ厳しいなーというところです。

E問題

E - (∀x∀)

問題をチラ見してみて、なんとか解けそうな見た目をしているという印象だったが、まずはD問題を解こうと思ったので今回は諦め。

また、自力で解いてみることにします。

F問題

F - Black and White Rooks

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

G問題

G - Range Pairing Query

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

Ex問題

Ex - Random Painting

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

これまでの実績

現状、6連敗中。。。レートも3桁に落ち、水色がどうとか言える状態ではなくなりつつあります。

コンテスト実績
コンテスト実績

総括

ここ最近は、難易度の高い問題を中心に精進を続けているのですが、コンテストでの結果が全く出ずという状態です。

普通なら、このへんで心が折れるというところかもしれませんが、あまり悲観的になっても仕方がありません。淡々と精進とコンテスト参加を継続していこうと思います。

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