devgenjin77’s blog

AtCoder Beginner Contest 245 参加記

AtCoder 競プロ ABC

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

この日は仕事上の付き合いで飲み会があり、家に帰ったのが午後8時半ぐらいというところ。コンテストに参加するか微妙なコンディションでしたが、とりあえず前回の負けが取り返せれば、という思いで参加してみることにしました。目標はとりあえず5完です。

Rated参加します。飲み会後の参加で多少不安もありますが、なんとか5完はできるように頑張ります。

AtCoder Beginner Contest 245 - AtCoder https://t.co/bbGsQTAw8Y
— devgenjin77 (@devgenjin77) 2022年3月26日

今回の結果

で、今回の結果ですが、なんと3完で終了という非常に残念な結果となりましたとさ。

ABC245結果

んで、、久しぶりに茶パフォを叩き出してしまい、レートは暴落。。再度3桁落ちという結果になりましたとさ。

3完で久々の茶パフォを叩き出してしまい、
レートは暴落😭😭3桁落ちとなりましたとさ😱

また、初心に立ち返って精進します。
devgenjin77さんのAtCoder Beginner Contest 245での成績：3693位
パフォーマンス：719相当
レーティング：1025→998 (-27) :(#AtCoder #ABC245 https://t.co/umETBQLARC
— devgenjin77 (@devgenjin77) 2022年3月26日

振り返り

Dを解き切ることすらできませんでした。

ABC245提出結果

A問題

A - Good morning

アルコールが入っているせいか、A問題を読み解くのにも少し苦労しました。。

とりあえず愚直に $A$ と $B$ の時間の比較のIF文を書き、その後 $A=B$ の場合は $C$ と $D$ の分の比較をするという要領。

後で考え直せば、単位を分にまとめるなどで実装をシンプルにできたかというところでしたねー。

4分3秒で1完。今日はコーディングのスピードもイマイチです。

提出コード

https://atcoder.jp/contests/abc245/submissions/30430889

B問題

$A$ の全要素をSetに突っ込んだ後、0から順番に、その数字がSetにあるかどうかを見ていけば良い。

ということで、あとは実装と提出を行い、ACが取れました。

8分7秒で2完。ここまでは、まあままの結果かなという印象です。

提出コード

https://atcoder.jp/contests/abc245/submissions/30437136

C問題

C - Choose Elements

今回のCはDPの問題。ひと昔前のC問題といえば、全探索のゴリ押しでクリアできるイメージだったが、最近はDPもよく出るようになったなぁと。

で、まずはどんなDPを作ろうかということで、以下のようなDPの配列を立ててみる。

$dp\lbrack i \rbrack \lbrack 0 \rbrack :=$ 数列 $N$ の $i$ 番目として $A_i$ が採用できる場合 $True$
$dp\lbrack i \rbrack \lbrack 1 \rbrack :=$ 数列 $N$ の $i$ 番目として $B_i$ が採用できる場合 $True$

あとは、以下の要領でDP配列を埋めていく。

$dp\lbrack i \rbrack \lbrack 0 \rbrack = True$ 且つ $| A_i - A_{i+1} | \le K$ の場合、 $dp\lbrack i + 1 \rbrack \lbrack 0 \rbrack = True$
$dp\lbrack i \rbrack \lbrack 1 \rbrack = True$ 且つ $| B_i - A_{i+1} | \le K$ の場合、 $dp\lbrack i + 1 \rbrack \lbrack 0 \rbrack = True$
$dp\lbrack i \rbrack \lbrack 0 \rbrack = True$ 且つ $| A_i - B_{i+1} | \le K$ の場合、 $dp\lbrack i + 1 \rbrack \lbrack 1 \rbrack = True$
$dp\lbrack i \rbrack \lbrack 1 \rbrack = True$ 且つ $| B_i - B_{i+1} | \le K$ の場合、 $dp\lbrack i + 1 \rbrack \lbrack 1 \rbrack = True$

と、まあこんな感じの実装でACは取れたのですが、ここまでの考察に時間がとられたり、実装にもたついたりして、かなりタイムを消費してしまいました。

41分6秒で3完。この時点では、5完は厳しそうかなーという印象でした。

提出コード

https://atcoder.jp/contests/abc245/submissions/30457890

D問題

D - Polynomial division

一見して、なんか訳わからん方程式が出てきたー、という印象のD問題。

とりあえず、 $B$ の中で、一番高次の係数と、0次の係数は簡単に求まりそうだが、それ以外をどう求めるかの計算がややこしそう。。

アルコールも入っているせいか、あまり頭が回っておらず、ノートに方程式の展開を書いてみるも、考えをまとめるのにやたらと苦労する。

とりあえず、それなりの実装をしてサンプルが通ったところまでは頑張ってみたものの、結果はWAとRE (多分ゼロディバイド)のダブルパンチで通らず。。

その後も、どうすれば良いかあれこれ考えてみたものの、結局ACには至らずで時間切れとなりましたとさ。

E問題

E - Wrapping Chocolate

コンテスト中は問題すらみておらず。あと見ても解法はわからんので後で解説ACするしかないかというところ。

F問題

F - Endless Walk

コンテスト中は問題すらみておらずだったが、終了後のぞいてみると、これ強連結成分分解するやつじゃね？という印象。。

最近、強連結成分分解の典型問題を勉強していたので、もしかするとFのほうがワンチャンあったかもしれません。。。

G問題

G - Foreign Friends

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

Ex問題

Ex - Product Modulo 2

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

これまでの実績

レートは再度3桁落ち。。なかなか上抜けできないもどかしい展開が続きます。

コンテスト実績

総括

今日は、コンディションが万全でなかったということもありましたが、まだまだ計算力が足りていないなーというのを思い知らされた回でした。

とはいえ、これでへこたれていては、一生上のレートにはいけません。これに懲りずに精進を続けていこうと思います。

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