AtCoder Beginner Contest 243 参加記

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

atcoder.jp

直近のRatedコンテスト成績は絶賛6連敗中。ジリジリとレートが削られていく状況が続いており、競プロに対するモチベーションも下がりがちのため、そろそろこの悪い流れを断ち切りたいところ。

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

今回の結果

で、、、いままで3完続きだったABCでなんとか4完を確保することができましたとさ。

ABC243結果
ABC243結果

で、なんと今回は4完でも水色パフォーマンスが出てくれまして、なんとか連敗を阻止することに成功!レートの方も4桁に戻すことができましたとさ。

振り返り

D問題まではまずます好調でしたが、E以降がさっぱりでした。

ABC243提出結果
ABC243提出結果

A問題

A - Shampoo

もう少しうまいやり方もあるかと思いつつ、下手に効率化すると逆にドツボにハマりそうという懸念もあり、単純な解法で解くこととした。

Vから、A,B,C,A,B,C,...と引いていき、最終的に、答えがマイナスになった時の変数で場合分けして結果を出力すればよい。

あとは、実装して提出後、問題なくACが取れましたとさ。

4分27秒で1完。少しコーディングに時間がかかってしまっている印象です。

提出コード

https://atcoder.jp/contests/abc243/submissions/30029232

B問題

B - Hit and Blow

とりあえず、配列Aの中身をすべてHashSetに突っ込んでみる。

その後、配列Bの値を先頭から見ていき、

  • A_i = B_iの場合、答え1に1追加

  • A_i \ne B_i且つ、B_iの値が、配列Aの値を入れたHashSetの中に含まれている場合は答え2に1追加

以上の要領で実装し、問題なくACが取れましたとさ。

8分35秒で2完。ここまでは、まあまあのタイムという印象。

提出コード

https://atcoder.jp/contests/abc243/submissions/30034335

C問題

C - Collision 2

少しややこしめだが、解法を考えるのにはそんなに苦労しないという印象の問題。

入力に対して、平面上の位置、X,Yと歩く向きの方向(LR)を持つオブジェクトを定義する。

その後、Y座標の位置が同じ且つ、向きがRのオブジェクトのX座標が、向きがLのオブジェクトのX座標より小さいものが存在するかを判定する。

実装時、バグがありサンプルが通らずで苦戦するも、なんとか解決してACを取ることができました。

30分22秒で3完。もう少し早く通せたらなーという印象。

提出コード

https://atcoder.jp/contests/abc243/submissions/30049551

D問題

D - Moves on Binary Tree

この問題に関しては、早めに解法が浮かんだので助かった。

現在位置Xに対して、二分木上の移動後の位置は以下の式で計算できる。

  • Uの場合、\lfloor X \div 2 \rfloor

  • Lの場合、X \times 2

  • Rの場合、(X \times 2) + 1

で、これをまともに計算するとlong型の最大値を普通に超えてしまうので、2進数に変換した値を文字列として扱い、上記の計算を行うようにする。

すなわち、現在位置Xを2進数の文字列表現に変換したSに対して、

  • Uの場合、Sの最後の文字を削除。

  • Lの場合、Sに、0を追加。

  • Rの場合、Sに、1を追加。

これを最後まで処理し、long型に戻した値を答えとすればOK。

なかなか早い時間でACを取ることができました。

38分59秒で4完。順位を確認すると、1200位前後ぐらいだったので、なんとか連敗は止まりそうというところで、少しほっとしました。

提出コード

https://atcoder.jp/contests/abc243/submissions/30054108

E問題

E - Edge Deletion

順位表のAC数から見て、やたらと難しそうな印象という問題。。

とりあえず、見覚えのありそうな解法から試してみる。

まず各辺より、コストの低い順に優先的に採用し、グラフを連結にするために必要な辺の数をすべての辺の数から引いた値が答えとする。が、、これはサンプルでWA。

それならばと、コストの高い方を優先にしてみたら、、と実装を変えてみるも通るわけなく、サンプルでWA。。

で、落ち着いて制約を見てみると、なんかワーシャルフロイド法を使えと言っている感じがするので、とりあえずワーシャルフロイド法を書いてみる。

その後、入力された各辺のコストより、最短経路のコストが小さいケースの数を答えとするという実装をしてみる。が、、これもサンプルが通らず。。。

で、いろいろ試行錯誤してみたものの、サンプルが通らずで結局時間切れということになりましたとさ。。

で、解説を見てみると、ワーシャルフロイド法を使うところまではあっていた模様。辺のコストが同一の回り道がある場合の考慮が必要だったようですなー。。

F問題

F - Lottery

コンテスト中、チラ見はしてみたものの何もわからず。

G問題

G - Sqrt

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

Ex問題

Ex - Builder Takahashi (Enhanced version)

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

これまでの実績

とりあえず、連敗を6で止めることができました。

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

総括

今回、パフォーマンス的には大分Eの難易度に救われた感じがします。

最近の負けパターンとしては、緑上位、もしくは水色下位当たりの問題が解けずで結局パフォーマンスが緑下位でとどまってしまうというのが多かったのですが、今回はDまでが少し早めに解けてくれて、水色パフォを維持したまま逃げ切りというような感じですね。

ということで、連敗は止まったものの、まだまだ楽観はできません。今できることは水色にふさわしい実力をつけるべく精進を重ねていくしかないというところでしょう。

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