AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）参加記

AtCoder 競プロ ABC 企業主催コンテスト

2023/2/26に開催された、AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）に参加しました。

atcoder.jp

アルゴリズムのレートは、ここ何ヶ月にも渡って停滞中というもどかしい状態。しかしながら、可能な限りコンテストにはRatedで参加し続けようという気持ちだけで続けています。

とりあえず、昨日のARCは負けだったので、今回はその分を取り戻せればという気持ちで臨むこととしました。

今回の結果

ABCEの変則４完でした。

ABC291結果
ABC291結果

パフォーマンスは、現レートより少し低い結果になりまして、結局今回も負けという結果になりましたとさ。

振り返り

D問題は、ド典型のようでしたが解けずでした。。

ABC291提出結果
ABC291提出結果

A問題

A - camel Case

大文字判定なんて大分久しぶりな感じなので、一瞬どう実装したらいいか戸惑いました。

結局、文字列を前から見ていってASCIIコードがA以上Z以下である箇所を出力するという愚直実装でACを取りました。

2分2秒で1完。あとで考えたら、isUpperCaseなどのメソッドを使った方が実装的に良かったかも。

提出コード

https://atcoder.jp/contests/abc291/submissions/39226609

B問題

B - Trimmed Mean

配列Xをソートしてから、\sum^{4N}_{i = N}X_{i}を計算し、3Nで割った値が答え。

結果がdouble型で計算されるように気をつけて実装。問題なくACが取れましたとさ。

4分36秒で2完。

提出コード

https://atcoder.jp/contests/abc291/submissions/39230412

C問題

C - LRUD Instructions 2

過去にいたことがある座標をSetに突っ込んで、移動する度に移動後の座標がSetに入っているかをチェックすれば良い。

想定解としては、pairを使う形になるかと言うところだが、Javaの場合はデフォルトでpairが無いので、(x \times 1000000) + yのlong値を座標の代用として使用。問題なくACが取れましたとさ。

11分41秒で3完。この時点で順位は1700位ぐらい。みんな早解きが上手だなあ。。

提出コード

https://atcoder.jp/contests/abc291/submissions/39237682

D問題

D - Flip Cards

開始10分程度でだいぶAC数が上がっていたので、この問題も解けないとヤバいかという印象。

んで、実際問題を一読してみると、多分DPの典型かなと言うような形をしている。

が、、どうにもこうにも、どういうDPをしていけばいいかという肝心な所が思いつかず。。。

一度、先頭を表裏それぞれで固定して、そこから2枚目以降の表裏が使えるかというDPを組んでみたが、どうにもサンプルと答えが合わず。

結局、30分以上溶かしても見通しが立たない状態なので、ここは一旦諦め。次のE問題に進みました。

E問題

E - Find Permutation

一読した感じ、多分グラフ問題に帰着するのかなあという感想から、サンプルケースを有向グラフとして書いてみる。すると、長さN-1のパスがあればYesなのかなあという感じでした。

ということで、とりあえず入力を頂点X_iからY_iへの有向グラフとして処理し、一つだけ存在するはずの入次数０の頂点からスタートする形で実装。

そこから、出次数が２以上の時は、相手先の頂点の入次数が１の頂点が一つだけ存在する場合、そこに遷移するようにし、他の遷移先の頂点の入次数を１減らすように調整。最後にN-1回遷移できたらOK。これらに矛盾が生じたらNGという感じで組んでみたらなんとかサンプルが通ってくれました。

提出してみたら問題なくAC。78分15秒で4完です。

これも結構AC数が多かったのでパフォーマンスが出てくれるかは微妙でしたが、なんとか爆死を免れたというところです。

提出コード

https://atcoder.jp/contests/abc291/submissions/39261259

F問題

F - Teleporter and Closed off

これも結構AC数が上がっている問題なので、残り20分程度でもなんとかなってくれという感じで取り組んでみる。

一読した感じ、グラフというよりは、各頂点に対してスタートから何手で行けるかを管理すれば十分かなという印象でしたが、よくよく実装してみると、各頂点からゴールまで何手かかるかも管理し、各kを飛ばした場合の最短手数をシミュレーションする感じになるかというのがわかってきました。

が、、、いかんせん解法の見通しが立った時点で残り時間は数分というところ。。結局実装すら完成せずで時間切れになりましたとさ。

G問題

G - OR Sum

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

Ex問題

Ex - Balanced Tree

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

これまでの実績

典型のDが解けなかったにしては、かすり傷で済みました。

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

総括

典型であろうDが解けなかったことと、F問題も多分解けそうだった感じからすると、今回は６完行けてもおかしくないぐらいだったのですが、結局４完どまり。。これも実力なのかもしれませんな。

まだまだ典型の知識に抜けがあるという課題が見えた回かと思います。今回の反省を踏まえ、またぼちぼちと典型の復習をしていこうと思います。

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