devgenjin77’s blog

AtCoder Beginner Contest 240 参加記

AtCoder 競プロ ABC

2022/2/20に開催されたAtCoder Beginner Contest 240に参加しました。

ここ2回のコンテストでは思うようなパフォーマンスが出せず、共にレート下げという結果を食らっています。今回はなんとか連敗を止めようという思いで臨むこととしました。

Rated参加します。直近のコンテストで2連敗中のため、連敗を止めるべく頑張ります✊
AtCoder Beginner Contest 240 - AtCoder https://t.co/KjtgehZE6I
— devgenjin77 (@devgenjin77) 2022年2月20日

今回の結果

で、、今回のABCも結果は4完となりました。。。

ABC240結果

パフォーマンスはぎりぎり緑というところで、今回も大きな下げを喰らうこととなりましたとさ。

4完のギリギリ緑パフォで下げとなりました😭😭
来週取り戻せるようになんとか頑張ります！
devgenjin77さんのAtCoder Beginner Contest 240での成績：2820位
パフォーマンス：844相当
レーティング：1044→1026 (-18) :(#AtCoder #ABC240 https://t.co/64oym18IdK
— devgenjin77 (@devgenjin77) 2022年2月20日

振り返り

Aでつまづき、Cで遅れをとり、Eはまったくわからずでした。

ABC240提出結果

A問題

A - Edge Checker

$b - a = 1$ だけが条件というわけではなく、 $b$ が10、 $a$ が1の時も考えないといけないなーという感じの問題。

そこでmodをとれば1つのシンプルな式に収まるのでは？という思いがふとよぎった。ということで、

$\left| (a \% 10) - (b \% 10) \right| = 1$ が成立すればYesという感じで実装して提出。うむ、非常にシンプルに収まった！

が、、これがあえなく1WAを喰らって撃沈しました。。というか、 $a = 9, b = 10$ の時に対応できてない。。

ということで、 $b = 10$ のときに、 $a = 1 or a = 9$ ならYesという雑な判定文を追加したりしてなんとかACを取ることが出来ましたとさ。

6分22秒の1ペナで1完。先が思いやられます。。

提出コード

https://atcoder.jp/contests/abc240/submissions/29513354

B問題

B - Count Distinct Integers

配列 $a$ の各数値を全てSetに突っ込んでサイズを出力するだけの問題。こちらは問題なくACを取れました。

8分48秒の1ペナで2完。多少遅れを取り戻しました。

提出コード

https://atcoder.jp/contests/abc240/submissions/29515769

C問題

C - Jumping Takahashi

一読してわからず。。全探索すると、最悪 $2^{100}$ のパターンを計算しないとなので、これはTLE間違いなし。

かといって、全部試す以外に解く方法など思いつかずということで、完全に手詰まりとなり、途方に暮れてしまいました。。

10分以上考えて良い考えが浮かばすなので、一旦D問題を解いてみることに。。

・・・

で、、なんとかD問題を解いた後にこの問題の制約を見直してみると、これナップサックDP問題やんということがわかった！

ということで、DP配列は、 $dp\lbrack i \rbrack\lbrack j \rbrack := j$ 回目のジャンプで、座標 $i$ にいる場合 $1$ とする。

遷移は、 $dp\lbrack i \rbrack\lbrack j - 1 \rbrack = 1$ の場合、 $dp\lbrack i +a_i \rbrack\lbrack j \rbrack = 1$ および $dp\lbrack i + b_i \rbrack\lbrack j \rbrack = 1$ とする。

最後に、 $dp\lbrack X \rbrack\lbrack N \rbrack = 1$ の場合、Yesと出力すればよいかと。

ということで、実装してみたら、あっさりとACが取れてくれましたとさ。

64分42秒の1ペナで4完。なんとか爆死を免れたかと。。

提出コード

https://atcoder.jp/contests/abc240/submissions/29536964

D問題

D - Strange Balls

一読して、スタックを使えば実装できるかな？と思ったが、普通に配列のみを使用してもなんとかなるかと予想。

とりあえず、筒の状態を管理する2次元配列を以下の内容で定義する。

$dp\lbrack i \rbrack\lbrack 0 \rbrack :=$ 現在筒の中の下から $i$ 番目にあるボールの種類
$dp\lbrack i \rbrack\lbrack 1 \rbrack :=$ $i$ 番目のボールは、何個連続している状態か

また $r$ を現在筒の中にあるボールの個数として定義する。あとは以下の要領で実装。

$r = r + 1$ とし、 $dp\lbrack r \rbrack \lbrack 0 \rbrack$ に $a_i$ をセットする。
$dp\lbrack r - 1 \rbrack \lbrack 0 \rbrack = a_i$ の場合、 $dp\lbrack r \rbrack \lbrack 1 \rbrack = dp\lbrack r - 1 \rbrack \lbrack 1 \rbrack + 1$ とする。
$dp\lbrack r - 1 \rbrack \lbrack 0 \rbrack \ne a_i$ の場合、 $dp\lbrack r \rbrack \lbrack 1 \rbrack = 1$ とする。
$dp\lbrack r \rbrack \lbrack 0 \rbrack = dp\lbrack r \rbrack \lbrack 1 \rbrack$ の場合、ボールを消す処理を行う。 $r = r - a_i$ とする。

以上の要領で、配列 $a$ の全要素について処理を行い、最後に $r$ の値を出せば終了。

少し不安もありましたが、なんとか一発でACを取ることが出来ました。

35分56秒の1ペナで3完。この後解けてなかったC問題と解いたりなどしました。

提出コード

https://atcoder.jp/contests/abc240/submissions/29528456

E問題

E - Ranges on Tree

昨日に引き続き、苦手なグラフ問題がEに登場。。。

さらに問題文を見てみましたが、あまり見慣れない集合に関する記号がふんだんに使われており、これがイマイチ何を言いたいのかよくわからない。。。

とりあえず、AC数は多そうなのでなんとかなるかと検討に取り組んでみましたが、とりあえず解法への糸口が見えない。なんだろう。。木DPとやらをするんだろうか。。。

ということで、木に関するDPについて調べたりなどしましたが、結局なにもわからずのままで時間切れという結果となりましたとさ。

F問題

F - Sum Sum Max

ワンチャンあるかとチラ見をしてみるも、何もわからずで諦め。

G問題

G - Teleporting Takahashi

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

Ex問題

Ex - Sequence of Substrings

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

これまでの実績

水色に向けての道のりも、また一歩後退する形となりました。

コンテスト実績

総括

今回の土日連続ABCコンテストはともに4完で連敗。苦手分野がE辺りにくると大分厳しいという印象です。

ただ、こういう苦手を克服していかないと上の色は目指せないことは明白なので、苦手意識をなくす為にもコツコツと復習に臨むしかないというところです。

だた、AHC008は一応登録しているので終了までに最悪提出だけはしておこうかと思ってるのでこれの対応も必要。うーん、リアルの業務より忙しい。。

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