最近全然コンテストに出ていない+来週も出る予定がなく、振り返りとかまったくしていないので気まぐれで思考過程を振り返ります。

A - Full House

なにも問題を読んでいなかったせいで、入力として与えられるのが英小文字だと勝手に思い込んで、そんなコードを書きました。 結果8分。普通に焦りましたが、まあ問題を読んでいなかったのが悪いです。

提出33809097

B - Ancestor

既出(ABC163-C: management)です。既出ですが、これがBに出るんだという気持ちになりました。 よくよく考えるとwhile文ないし、for文とbreakが使えれば確かに解くことはできるので、Bで妥当かなという気持ちになりました。

コンテスト終了後に、想定解がDPであることでちょっと荒れてましたが、まあ、全人類N番目の人から辿ってると思うので無問題だと思います。

提出 #33811485

C - Monotonically Increasing

これも多分既出です。本当に既出かは知りませんが、制約見て5秒でDFS書きました。

提出 #33814276

D - Left Right Operation

ようやく競プロらしい問題が出てきました。 同時に考えると面倒な要素は分解できるか考えましょう。

片方の端点がもう片方の端点を飛び越えない( $x > N-y+1$ みたいにならない)ようにするとして、こういうのは片方を固定したい気分になります。 左側を固定するとして、適当に$x$を定めたとき、書き換えた分の総和は$x \times L$になります。 また、このとき右側をどれだけ伸ばすかという話になりますが、「$y$を$i$までとしたときの数列の総和」という配列をいい感じに作っておいて、$(x, N]$でRange Minを問い合わせることにします。 RMQする配列の初期化を$N \rightarrow 1$という感じに行うと、左側の動きに関係なく右側を動かしたときの数列の和を得られるので、これを使います。 この問題では数列の和の最小化が問われているので、数列の和を小さくできるなら貪欲に小さくしたほうが嬉しいです。

で、いい感じにやることで、$\text{左を書き換えた分}\times L + \text{右を書き換えた分}\times R + 何も書き換えていない部分の和$という感じの式になって、何も書き換えていない部分の和は累積和でいい感じに処理できます。

正当性がイマイチ微妙で、実装も「やりたくねー」などといってTwitterを見ていたので、15分くらいのロスです。 他にも、

  • しゃくとり法か? (違う…)
  • DPか? (それでも行ける)
  • 二分探索か? (違う…)
  • 累積和もって片方決め打つか

みたいな感じだったので、空振りが多かったですね。

提出 #33831113

E - Sugoroku 3

まともに見てません。 確率DPの部類かなーということはなんとなくわかりました。

総評

問題文を読みましょう。解法があるなら面倒くさがらずにコードを書きましょう。

借金返済まではあともうすこしかかりそうです。