LINE Verda プログラミングコンテスト(AtCoder Beginner Contest 263)参加記

2022/8/6に開催された、LINE Verda プログラミングコンテスト(AtCoder Beginner Contest 263)に参加しました。

atcoder.jp

前回は、ギリギリ水パフォを確保できたものの、小ミスが続くなど反省点がたくさんあった回でした。

今回のABCは、なんとか前回の反省点をクリアして、最低水パフォは出そうという感じで臨むこととしました。

今回の結果

で、今回は4完という、可も無く不可も無くといった内容で終了しました。

ABC263結果
ABC263結果

肝心のパフォーマンスは、なんとか現レートの少し上まで出てくれまして、なんとかレート上昇。とりあえず勝ちという結果になりました。

振り返り

しょうもないミスをする癖は未だ治らずで、結局パフォーマンスを下げてしまいました。

ABC263提出結果
ABC263提出結果

A問題

A - Full House

フルハウスが成立する条件ということで、数字は2種類の筈。とりあえず出現した5つの数字をSetに突っ込んで、サイズが2ならYesとかいう実装で出してみる。

が、、これはあえなくWA。。。よくよく考えると、フォーカードの時もサイズが2になるやないかい!

ということで、各数字の出現回数を一度カウントして、3個出現の数字と2個出現の数字が両方ある場合のみYesとする実装で出す。これでなんとかACが取れました。

4分57秒1ペナで1完。今週もまた、しょうもないミスをしました。。

提出コード

https://atcoder.jp/contests/abc263/submissions/33805454

B問題

B - Ancestor

Nから始めて、Pの情報を元に先祖を辿っていき、最終的に、人1に到達するまで何回掛かるかをカウントする。

最終的に、人1に到達しないケースなどあるかと考えてみたが、他に方法も浮かばすなので、この実装で提出。なんとかACが取れました。

9分28秒1ペナで2完。

提出コード

https://atcoder.jp/contests/abc263/submissions/33810231

C問題

C - Monotonically Increasing

とりあえず、DFSで探索し、出力していく実装で解いてみる。

この手のDFSは、結構久々の実装なので、少し手間取りましたが、なんとか提出してACが取れました。

23分51秒1ペナで3完。

提出コード

https://atcoder.jp/contests/abc263/submissions/33819373

D問題

D - Left Right Operation

厳密な証明はできていないが、Lで置き換える処理と、Rで置き換える処理は、それぞれ独立に考えられると思った。

ということで、まず、x0からNまで試し、合計が最小となる状態を探索。整数列Aも合計が最小となる状態で更新しておく。

次に、更新されたAに対して、yNから0まで試し、合計が最小となる状態を探索。ここで計算された最小値を答えとする。

以上の実装でサンプルが通ったので、提出したらWA。。なにか考慮漏れでもあるのだろうか。。。

何がダメだったか、よくわからなかったが、考え方を切り替えて以下のDPを組み立ててみる。

  • \ dpl\lbrack i\rbrack :=x \le iの時、元の合計値との差の最小値。

  • \ dpr\lbrack i\rbrack :=y \ge iの時、元の合計値との差の最小値。

これらを前計算で求めて dpl \lbrack i \rbrack + dpr \lbrack i + 1 \rbrackの最小値を計算。元の合計値に足すことで答えとする。

この実装で、なんとかACを取り切ることができました。

79分24秒3ペナで4完。順位的には2000位前後まで来たので、なんとか負けは回避したかと。

提出コード

https://atcoder.jp/contests/abc263/submissions/33835461

E問題

E - Sugoroku 3

問題を一読して、これと似たような問題をどっかでみたような気がしたが、思い出せず。

また、ぶっちゃけ期待値の計算方法などは少しやった記憶があるが、自分の手に馴染んでいないようで、どのように計算すれば良いのかがよく分からん。

ということで、この問題は早々に諦め。

F問題

F - Tournament

ワンチャンあるかと、問題を見てみましたがよく分からず。

G問題

G - Erasing Prime Pairs

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

Ex問題

Ex - Intersection 2

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

これまでの実績

レートは微増するも、水色へはまだ遠い状態が続いております。

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

総括

A問題のしょうもないペナルティと、Dに時間かけすぎなのが、今回の残念ポイント。やはりまだ精進が不足しているようですね。

来週は、盆休みで時間も結構取れるので、次回に備えて精進していこうと思います。

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