AtCoder Regular Contest 135 参加記

AtCoder 競プロ ARC

2022/2/13に開催されたAtCoder Regular Contest 135に参加しました。

atcoder.jp

ここ最近のARCは良くて2完という感じなので、今回はなんとか2完はいけるかという気持ちで臨むこととしました。

今回の結果

で、今回の結果は、なんとか1完を確保という体たらく。。これが現在の実力という所でしょう。

ARC135結果
ARC135結果

パフォーマンスは、現レートより少し悪いぐらいで収まり、ちょい冷えという結果になりましたとさ。

振り返り

Bを解き切ることが出来ませんでした。

ARC135提出結果
ARC135提出結果

A問題

A - Floor, Ceil - Decomposition

とりあえず黒板にある4を超える数字については、操作を行う方が最終的な積は大きくなりそう。ということで求める答えをf(X)とし、以下の式を立ててみる。

  • f(X) = f(\lfloor \frac{X}{2} \rfloor) \times f(\lceil \frac{X}{2} \rceil) (X \gt 4)
  • f(X) = X (X \le 4)

あとはこれをDFSを使って再帰的に解いていくプログラムを書けば解けるか、ということでサンプルが通った実装を提出したらTLEを食らってしまいました。。

ということで、最近書いていないメモ化DFSをなんとか思い出しながら実装することに。なんとか完成までこぎつけて、ACを取る事が出来ました。

32分53秒プラス1ペナという遅めの内容で1完。

提出コード

https://atcoder.jp/contests/arc135/submissions/29306502

B問題

B - Sum of Three Terms

とりあえず、サンプルケースを元に色々考えてみるが、全く解法が思いつかずで小一時間椅子を温める羽目になってしまいました。。

あまりにもわからないので、諦めて他の問題を見ようかと思うも、順位表をみるとB問題が他に比べて圧倒的にAC数が多いため、この問題以外は見てもあまり解ける見込みは無いものと推察。結局、この問題で最後まで時間を使うことにしました。

で、1時間以上あれこれ検討して、得た考察としては以下のとおり

  • 問題文にある計算式を組み替えてみると、
    A_{4} = A_1 + (S_{2} - S_{1})、A_{5} = A_2 + (S_{3} - S_{2})、A_{6} = A_3 + (S_{4} - S_{3}) 、
    A_{7} = A_4 + (S_{5} - S_{4})、A_{8} = A_5 + (S_{6} - S_{5})、A_{9} = A_6 + (S_{7} - S_{6})
    という感じになり、配列の位置のmod3でグループ分けすることができそう。
  • S_{i + 1} - S_{i}の値がマイナスになる場合、A_1,A_2,A_3のいずれかを調整し、Aの全要素についてマイナスにならないように調整する必要がある。
    逆にその条件が満たせない場合は解答がNoとなる。

というところまで考えてみたが、実装まで辿り着けずであえなく時間切れ。。

うーん、あと1時間ぐらいあれば解答できたかなーという感じでしたが、実装力と考察力がなさすぎでした。

C問題

C - XOR to All

少し目を通してみたものの、何もわからずで諦め。

D問題

D - Add to Square

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

E問題

E - Sequence of Multiples

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

F問題

F - Delete 1, 4, 7, ...

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

これまでの実績

今回はちょい冷え。水色への道のりはまだまだ遠いです。

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

総括

今回のB、C問題は水色Diffだったようですが、まだまだこれらを自力で解き切る実力が付いてないということを思い知らされるコンテストでした。

当面の目標は、水色コーダーになることですので、今回のB、Cが解けるぐらいの実力をつけたい所。とりあえず地道に今回の問題を復習して地道に力をつけていくことにします。

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