2022/11/12に開催された、大和証券プログラミングコンテスト2022 Autumn(AtCoder Beginner Contest 277)に参加しました。
先週のABCでは、なんとか連敗を止めることができました。今回は、この流れを止めないようにということで、水パフォを目標として挑むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2022年11月12日
今回も水パフォ目標で頑張ります✊
大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277) - AtCoder https://t.co/tuFIfArKsZ
今回の結果
今回は、3完で終了。。
ABCでは、だいぶ久々の茶パフォという結果に。。再度レートを大きく落としてしまう結果になりましたとさ。
3完😭😭
— devgenjin77 (@devgenjin77) 2022年11月12日
次頑張ります。
devgenjin77さんの大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)での成績:3026位
パフォーマンス:794相当
レーティング:1135→1105 (-30) :(#AtCoder #大和証券プログラミングコンテスト2022Autumn(ABC277) https://t.co/lXRN5YA7Tr
振り返り
D問題で派手に事故ってしまいました。
A問題
題名の意味がよくわからんが、が、配列の何番目にあるかを探すだけの問題。やるだけの実装で問題なくACが取れました。
2分9秒で1完。
提出コード
https://atcoder.jp/contests/abc277/submissions/36408646
B問題
それぞれのについて、1文字目と2文字目をバリデーションし、Setを使って重複を検知すれば良い。あとはやるだけの実装。
9分38秒で2完。ここまでは、まあまあの結果。
提出コード
https://atcoder.jp/contests/abc277/submissions/36415566
C問題
C問題なのに、グラフに座標圧縮とUnion-Findの問題が出てくるのか?という印象。
ただ、一読してやれる解法がこれぐらいしか思いつかなかったので、上記の解法でいくことにしました。
1階及び、入力ので与えられる階数をSetに突っ込んでからソート。あとは、各要素のIndexをグラフの頂点とみなす。
次に、とを元にUnion-Findで連結し、最後に1階と連結である最大の階数を求める。
とまあ、こんな感じの実装で、なんとかACが取れましたとさ。
26分56秒で3完。
提出コード
https://atcoder.jp/contests/abc277/submissions/36424792
D問題
ざっくりとした解法を検討してみると、配列をで分類してからソートし、隣同士の要素のの値が1違う場合は、連結とみなし、最後に連結成分で最大の合計を、全部の合計から引けばよいかという感じだった。
ということで実装し、サンプルが通ったので提出したら、これがWA。。。
よくよく考えると、がになった時に連結になるケースを考慮できていなかったので、配列を2ループ分探索することで、対策してみる。
が、、これも提出したらWA。。。
結局、このWAが何をやってみても解決せずでドツボにハマってしまう。。結局残り20分を切ったところでこの問題は諦めることにしました。
で、コンテスト終了時に、バグの原因が判明。結局答えがになるケースで引きすぎてしまっていたというオチでした。。
E問題
なんか、ダイクストラ法に少し工夫をする問題という印象。残り20分弱でどの程度いけるかわからんが、実装してみる。
解法としては、ダイクストラ法で処理していく中で、スイッチを押した回数を保持しておき、スイッチを押した回数と、辺の初期状態から使える辺を切り分けることと、スイッチがある頂点に居る場合に、スイッチを押す、押さない両方のケースを試すことの2点でいけるかと思った。。
で、実装をすすめてみるも、いかんせん実装量に比べて時間が足りない。。
結局、全ての処理を書ききれないままで、時間切れという結果になりましたとさ。うーん、もう少しはやくD問題を見切っておくべきだったか。。
F問題
問題すら見れておりません。
G問題
G - Random Walk to Millionaire
問題すら見れておりません。
Ex問題
問題すら見れておりません。
これまでの実績
レートは大きく落ちて、さらに水色が遠いものになってしまいましたとさ。
総括
今回は、大いにバグらせてパフォーマンスを落としてしまうという残念な結果となりました。
ただ、コンテスト全体を見てみると、C問題は、少し前なら緑Diffぐらいあってもいいぐらいの難易度とは思うし、D、Eもだいぶ解かれすぎな印象はありますね。大分他の参加者のレベルが高くなっているのを感じています。
このままでは、現状維持すらも危ういという危機感を持たないといけないですね。今回の結果をおおいに反省して、次に向けて準備していきたいと思います。
ということで、また次回も頑張ります。