AtCoder Beginner Contest 210に参加しましたのでその感想を書いていきます。問題はこちらから。

結果はこんな感じでした。

ABC（16:05+0WA）
順位：1939 / 8876
パフォーマンス：1134 

難しかったです。DとEどちらも考えましたが、手も足も出ず、といった感じです。こうかな？っていう候補はいくつか上がりましたが、結局実装に着手することもできず。完敗です。やられました。

A問題

いっぱい買うとお得になる問題です。まず、問題文の理解に手間取りました。何といっても、入力が４つもあるのでどれがどの値を表しているのか混乱しました。

無事入力を受け取りまして、いざ実装。

と、勢いよく飛び出したはいいものの、場合分け難しくないですかね？

A+1個以上買う場合に、A個までは高くて、A+1個目からN個までの、N-A個は安くなる。でも、Ａ個以下しか買わない場合にはN個まで高い値段のまま。

私の脳を破壊するのには十分な情報量です。うわああ、となりましたので、おとなしくfor文を書きました。

スマートにO(１)で解きたかったものですが、まあ、よしとします。ここまでで、4分ほどかかりました。強敵でしたね。

B問題

先ほどよりもシンプルな問題です。上からカードを引いていくので一つずつ判定をしていけばおしまいです。

ただし、Ａ問題とはうって変わり非常に落ち着いていました。

もし、負けのカードが一枚もなければどうすればいいんですか？

これがコーナーケースになりうると思って、プログラムを訂正。でも問題文に「負けカードがないということはない」と書いてありました。

ちゃんと問題を読みましょう。

C問題

パッと問題をみて累積和かなと思いました。が、

1 2 4 2 3

で破綻したので、考え直し。結局、尺取り法みたいに愚直に前から計算をすれば解けました。このとき、出現する数字の管理にはmapを使うのをお忘れなく。

D問題

難しかったです。

まず二分探索が浮かびました。ですが、判定にO({HW}^2)かかるので、この方針はすぐに捨てました。次に

マンハッタン距離は45°回転だ！

ということで回転させました。回転させたところで何も浮かびません。困りました。その後、左上からdpを回せばうまく計算できるんじゃないか？、と思いましたが遷移はおろか、どんな状態を管理すればいいのかもわからずじまいです。

このまま、長らく考えていましたが時間切れです。途中、最短経路か？みたいなこともちょっとだけ浮かびましたが、まあ違うでしょう。

残念です。

E問題

ちょっとだけ見ました。連結にならない条件について10分ぐらい考えてD問題に戻りました。

F問題

みてないです。

あとがき

今回は３完でした。ABCでペナルティを出さなかったことだけが救いでしょうか。そのおかげかちょっとだけレートも上がりました。今まで6連続で下がっていたので、なんだかんだで嬉しいです。

次回はD問題を解きたいですね。しっかりと復習をして次回に臨みたいと思います。