今日解いた競プロの問題。

Typical DP Contest-I: 自力AC。区間DPするだけだろうと思ったがちょっと罠がいくつかあった。

まず最初ちょっと勘違いしていたのだが、「全て取り去れる区間の最大の長さ」ではなく「最大で何回操作できるか」なので、取り去る部分は繋がっていない場合がある。「iwiiiiwi」だったら両端からそれぞれiwiと取り去れる。ということで、まず連続してiwiを取り去れる区間を調べ、その上で繋がっていない部分を含んでどれだけ取り去れるかをDPした。

それから、連続してiwiを取り去れる区間を調べるところでもミスをした。

• 「(取り去れる区間)+iwi」
• 「i+(取り去れる区間)+wi」
• 「iw+(取り去れる区間)+i」
• 「iwi+(取り去れる区間)」

はまた取り去れる区間になるということでDPしたのだが、「i+(取り去れる区間)+w+(取り去れる区間)+i」というパターンを見逃していた。実装を考え直した結果、

• iwiを取り去って「i」に出来る区間
• iwiを取り去って「iw」に出来る区間
• iwiを取り去って空文字列に出来る区間

をそれぞれDPテーブルとして持つ実装にした。

---

課題の処理を進めた。工学系なのだが数学的議論を真面目にやった結果、積分の微分をやる必要が出てきて、久しぶりに微分を定義からちゃんと確認して計算する羽目になった。

$\frac{d}{dx}\int_a^b f(x,y)dy=f(x,b)\frac{\partial b}{\partial x}+\int_a^b\frac{\partial f(x,y)}{\partial x}dy$

---

筋トレをやった。今日は腹筋。

腕立てとスクワットの筋肉痛がなかなか取れない。

---

この連休の間で早寝を極めている。いつも寝るのが遅くなるのは基本的に競プロの1日1ACの影響がでかい。この連休の間は昼頃に済ませるようにしており、上手くいっている。

風呂とかも早めに済ませて23時くらいに寝ているが、朝は9時くらいに起きている。うそだろ、6時に起きるためには20時に寝なければならないというのか…？