大和証券プログラミングコンテスト2022 Autumn(AtCoder Beginner Contest 277)参加記

2022/11/12に開催された、大和証券プログラミングコンテスト2022 Autumn(AtCoder Beginner Contest 277)に参加しました。

atcoder.jp

先週のABCでは、なんとか連敗を止めることができました。今回は、この流れを止めないようにということで、水パフォを目標として挑むこととしました。

今回の結果

今回は、3完で終了。。

ABC277結果
ABC277結果

ABCでは、だいぶ久々の茶パフォという結果に。。再度レートを大きく落としてしまう結果になりましたとさ。

振り返り

D問題で派手に事故ってしまいました。

ABC277提出結果
ABC277提出結果

A問題

A - ^{-1}

題名の意味がよくわからんが、Xが、配列Pの何番目にあるかを探すだけの問題。やるだけの実装で問題なくACが取れました。

2分9秒で1完。

提出コード

https://atcoder.jp/contests/abc277/submissions/36408646

B問題

B - Playing Cards Validation

それぞれのS_iについて、1文字目と2文字目をバリデーションし、Setを使って重複を検知すれば良い。あとはやるだけの実装。

9分38秒で2完。ここまでは、まあまあの結果。

提出コード

https://atcoder.jp/contests/abc277/submissions/36415566

C問題

C - Ladder Takahashi

C問題なのに、グラフに座標圧縮とUnion-Findの問題が出てくるのか?という印象。

ただ、一読してやれる解法がこれぐらいしか思いつかなかったので、上記の解法でいくことにしました。

1階及び、入力のA,Bで与えられる階数をSetに突っ込んでからソート。あとは、各要素のIndexをグラフの頂点とみなす。

次に、A_iB_iを元にUnion-Findで連結し、最後に1階と連結である最大の階数を求める。

とまあ、こんな感じの実装で、なんとかACが取れましたとさ。

26分56秒で3完。

提出コード

https://atcoder.jp/contests/abc277/submissions/36424792

D問題

D - Takahashi's Solitaire

ざっくりとした解法を検討してみると、配列Amod Mで分類してからソートし、隣同士の要素のmod Mの値が1違う場合は、連結とみなし、最後に連結成分で最大の合計を、全部の合計から引けばよいかという感じだった。

ということで実装し、サンプルが通ったので提出したら、これがWA。。。

よくよく考えると、mod M0になった時に連結になるケースを考慮できていなかったので、配列を2ループ分探索することで、対策してみる。

が、、これも提出したらWA。。。

結局、このWAが何をやってみても解決せずでドツボにハマってしまう。。結局残り20分を切ったところでこの問題は諦めることにしました。

で、コンテスト終了時に、バグの原因が判明。結局答えが0になるケースで引きすぎてしまっていたというオチでした。。

E問題

E - Crystal Switches

なんか、ダイクストラ法に少し工夫をする問題という印象。残り20分弱でどの程度いけるかわからんが、実装してみる。

解法としては、ダイクストラ法で処理していく中で、スイッチを押した回数を保持しておき、スイッチを押した回数と、辺の初期状態から使える辺を切り分けることと、スイッチがある頂点に居る場合に、スイッチを押す、押さない両方のケースを試すことの2点でいけるかと思った。。

で、実装をすすめてみるも、いかんせん実装量に比べて時間が足りない。。

結局、全ての処理を書ききれないままで、時間切れという結果になりましたとさ。うーん、もう少しはやくD問題を見切っておくべきだったか。。

F問題

F - Sorting a Matrix

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

G問題

G - Random Walk to Millionaire

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

Ex問題

Ex - Constrained Sums

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

これまでの実績

レートは大きく落ちて、さらに水色が遠いものになってしまいましたとさ。

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

総括

今回は、大いにバグらせてパフォーマンスを落としてしまうという残念な結果となりました。

ただ、コンテスト全体を見てみると、C問題は、少し前なら緑Diffぐらいあってもいいぐらいの難易度とは思うし、D、Eもだいぶ解かれすぎな印象はありますね。大分他の参加者のレベルが高くなっているのを感じています。

このままでは、現状維持すらも危ういという危機感を持たないといけないですね。今回の結果をおおいに反省して、次に向けて準備していきたいと思います。

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