8時ごろ、雨音に叩き起こされた。4時間くらいしか寝ていないので眠い。先日傘をどこかに置き忘れたあと、代替を用意してなかったことを思い出して絶望する。しかたなく近くのコンビニへ濡れながら向かった。傘を買うついでにやよい軒で朝食。350円で健康的な朝ごはんが食べられるのはありがたい。 家に戻ると眠気が鎌首をもたげてきたので、二度寝した。12時ごろに目が覚める。眠かったので布団のなかで競プロの考察をして、解けたので布団から這い出て実装をした。 atcoder.jp
解法と感想（クリックで展開）
一見不可能に見えたので制約を見直すと、 がともに小さいことに気がついた。あとはbool値でDPをしてやればよい。余裕で間に合うと思っていたが、実際は959msもかかっていた。
- 800 pound gorilla 「無視できないもの」
- arrow in the quiver 「手段の一つ」
- pizzazz 「活気」
- take-no-prisoners attitude 「強硬な態度」
- deep-six 「放棄する」
- dragoon 「無理やりなにかをさせる」
どれも響きや語源が面白く、頭に残りやすい。自分は地道に単語帳を覚えるという作業が苦手なので、楽しく語彙を増やすことができるこういう本はありがたい。 家に帰り、食事をとる。人参やもやしが余っていたので、昨日にひきつづき野菜炒めを作った。話はそれるが、一人暮らしを始めた当初、その辺のスーパーで適当に購入する食材や日常品の質の悪さに驚くことが多かった。ぱっと思いつくところでは、スーパーの安いハムや、日用品でいうとラップや歯磨き粉など、実家で何気なく使っていたそれらと比べて大きく質が劣る。実家にいたころは気がつかなかった親の気配りをいまさらになって感じる。 21時ごろから、高校同期とAmong Usをした。前半は調子がよかったが、後半インポスターで2敗してしまった。自分がインポスターで負けるときの要因として、序盤に慎重になりすぎて、中盤から終盤で雑なキルをせざるを得なくなって吊られる、というのが多い。もう少しキルに積極的になってもいいかもしれない。 0:30ごろにお開きとなり、そのあと2時間くらい駄弁っていた。最近、友人との話題も就職や院試、研究に関することが多くなってきて、時の経過を感じる。喋りながら青diffの問題を眺めて、解けそうなものを2問解いた。
解法と感想（クリックで展開）
ベルマンフォードを初めて書いた。頂点から到達できない、または頂点
に到達できない負閉路は考慮に入れないようにする必要がある。自分は前処理としてBFSを各頂点から回し、到達可能性を調べておく方法を取った。正解したあとにGoogleで検索すると、どうやら嘘解法が大量に通ってしまった問題らしい。以下のページの記述が参考になった。
ABC137-E:Coins Respawn ~負閉路検出について~ - 思考の墓場
atcoder.jp
解法と感想（クリックで展開）
木の直径を求めるだけ。試験管青diffはこういった問題が多く、典型の復習になる。
明日は昼から実験があるので、12時には起きたい。
