AtCoder Regular Contest 158 参加記

2023/3/12に開催されたAtCoder Regular Contest 158に参加しました。

atcoder.jp

最近、ARCではなかなか良い結果が出せておらず、直近では5連敗中という有様。

典型が出てくるABCとは違い、問題との相性にも結果が左右されるというところはありますが、ここまで連敗が続くと完全に実力不足という感じになってしまいますね。

ということで、今回はなんとか連敗を止めようという感じで臨みます。

今回の結果

ついに!0完爆死を喰らってしまいましたー。

ARC158結果
ARC158結果

しかも、超久々の灰パフォを取ってしまい、レートは一気に暴落。またまた入水が遠くに行ってしまいました。

振り返り

時間いっぱいA問題に取り組みましたが、通しきることができませんでした。

ARC158提出結果
ARC158提出結果

A問題

A - +3 +5 +7

今回はサクッと解こうと思っていたA問題でしたが、蓋を開けると、数学的な要素が含まれた苦手っぽい問題でした。。

とりあえず、差が奇数の場合は達成不可能っぽいなあという印象しかなく、その次の考察が進みません。

とはいっても、0完で終わるわけにはいかないということで、ノート上であれこれ試行錯誤しつつ、大分時間をかけてできた解法っぽいものがこちら。

  • 最初に入力をソートし、 X_1 \leq X_2 \leq X_3の状態にする。

  • X_3 - X_1 = 0の場合、X_1 = X_2 = X_3の筈なので、答えは0

  • D_1 = X_2 - X_1, D_2 = X_3 - X_2と隣同士の差を取る。このとき、D_1,D_2のいずれかが奇数なら達成不可。偶数なら、一旦D_1,D_22で割る。

  • 操作後の差も2で割った数で考えると、+3, +3, 0か、+3, 0, 0 が操作2回で可能である。

  • よって、D_1 = 0D_2 = 0の場合、D_1 + D_23の倍数でない場合達成不可。それ以外は、(D_1 + D_2) \times 23で割った数が答え。

  • あとは、 X_1 \le X_2 \le X_3のケースだが、X_1 = X_2にするか、X_2 = X_3にするかどちらかで操作回数が少ない方をまず選んでから、先ほどの2項が同じ場合の計算をすればOK?

という感じで組んでみて、なんとかサンプルが通る実装ができたものの、提出してみたらWA。。

この後も、時間切れまで色々試しましたが、結局解法が間違いなのか、なんかバグっているのかがよくわからずのまま終わってしまいました。

B問題

B - Sum-Product Ratio

A問題が解けないので、ワンチャンあるかと問題文をチラ見しましたが、何もわからずでした。。

が、、本番後によくよく考えると、正の数、負の数それぞれから絶対値の大きいものと小さいものをピックアップして全探索すればいいのでは?と思ってたらその通りだったので軽くショック。

諦めが早いのもいけませんなあ。。

C問題

C - All Pair Digit Sums

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

D問題

D - Equation

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

E問題

E - All Pair Shortest Paths

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

F問題

F - Random Radix Sort

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

これまでの実績

この回だけで、レートを大分落としてしまいました。ここまできたら、もう開き直るしかないですな。

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

総括

毎回なんとか避けていた0完爆死を、今回は喰らってしまいました。ただ、今回の問題も見直してみると、決して本番で解けなさそうな問題ではなかったですね。

今回の結果は、単なる実力不足。今後もARC過去問を復習し考察力を上げていくことと、ARCはRatedで参加し本番の参加回数をこなすことを継続して実力を付けていこうと思います。

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