AtCoder Beginner Contest 153に参加しました。

今回は無念の三完でした……！

５５００人中５０００人がD問題まで解くという比較的簡単なコンテストだったようです。

レート変化

f:id:youmizuno:20200128214022p:plain

パフォーマンスは前回１７０→今回９０と非常に落ちていました。絶対評価でなく「周りの人が解けない問題を、周りの人より早く解ける」ということで評価されます。

自分が参加しているのは「競技」プログラミングなんだ、ということにようやく思い至った感じです。スピードと技術……！　私はスピードよりもデータ処理手法の概念と実装に関心があるので、早く解くことよりも、他の人が解けない問題を多く、という方向に注力していきたいです。「いもす法」とか「FFT」とか使いこなしたいぜ、という願望があります。

ざらっと全部の問題を見てみると、E問題は正解者が１０００人ほどしかいません。DPを使えるかどうかが一つの区切りようです。ということで、DPへの関心が非常に高まったコンテストでした。

パフォーマンスは落ちましたが、ひとまずレートは＋３されました。

今回解けなかった問題

https://atcoder.jp/contests/abc153/tasks/abc153_e

D問題です。頑張ればできたかもしれないけどC問題に時間をかけすぎました……！

再帰を利用する典型的な問題だったようです。解説を見たらとても短くシンプルに解答していてすごいなと思いました。

類似の問題に当たったときは、数字の小さなほうから具体例を調べ、答えが再帰関数ｆを使った漸化式で表せないかチェックしたほうが良さそうです。

Atcoderの講座では難しくて飛ばしていた再帰ですが、今読むと役に立つツールとして利用できるかも、と思えるので、多少はコーディング慣れしてきた感じはあります。

また、D問題が簡単だったのでE問題もやってみました。こちらは方針も立たないので、動画解説を見ながら解答しました。理解できていない部分はありますが、DPは各種束縛条件に対して最小値or最大値をテーブルに記録していく手法だというところまではわかりました

DP表を埋めていく過程をイメージしながら実装できるようになりたいですね……！

まとめ

競技プログラミングは相対評価の厳しい世界です（当たり前でした）。