昨日ファミコンの改造のために5時近くまで起きていたので起きたら13時くらいだった。

---

ジョギングした。2.5km。

---

ABC305に参加した。

A: やるだけ

B: いろいろ実装法ある気がするが、A～Gを0～6に対応付けて累積和の配列のキーにした。

C: 空白の上下左右を見てクッキーが2個以上あるならそこは食べられた隙間と分かる。

D: まず実装方針として、時刻0～tの睡眠時間の総和を求められれば差分を取ればよいことが分かる。あらかじめ累積和を作っておき、時刻tがどの区間に入るかをにぶたんで求めて睡眠中かそうでないかを場合分けしてうんとこしょとやればよい。

E: 頂点N+1を追加で作り、そこから各警備員の頂点にコスト(maxH – Hi)の辺を張る。頂点N+1から各頂点への距離をダイクストラで計算し、maxH以下ならその頂点は警備されている。

F: 変な見た目だが、一度通った頂点を祖先とみなせればもう普通の木と思ってDFSしてしまえる。オイラーツアーの長さは最大でも2N回を上回らないのでこれで解ける。ちょっと自信が無くてデバッグに時間をかけてしまったが、特にバグはなかった。

G: 時間にそこまで余裕がなかったが、落ち着いてコーディングしてACできた。嬉しいが400人解いてるってマジ？？？どうやらFをすっ飛ばした人がそれなりにいたらしい。

6文字のパターンは2^6通りしかないので全探索できる。6文字以下の場合はそれでよく、クソでかい場合、まず愚直なDPをどう書けばいいか考えると、最後の6文字だけを状態として持てばよい。2^6通り→2^6通りの2^12通りの遷移パターンは全部調べて持ってしまうことができ、あとは行列累乗で高速化できる。