今日マジでなにもしてない気がする。
12時くらいに起きて、なんかいろいろしてた気がするが、寝ぼけていてあまり記憶にない。卒論の指導教員を誰にするかで悩んだり、『しっかり学ぶ数理最適化』をめくったりしていたと思う。
16時ごろバイトに行って、20時半ごろ帰宅した。夕食を食べてすぐに、Educational Codeforces Round 110のバチャをした。
Aはやるだけ。Bは偶数を前に持ってきて愚直に計算すればいい。Cで沼にはまった。ついおととい尺取り法の実装について考えていたので、それで解くことに固執してしまい、?の処理で悩んでいた。結局、各 について直前に連なる
?の数を前計算しておき、 としたDPで解いた。Dはセグ木の実装を思い出して、番号付けを丁寧にやればいい。E以降はあまり見れていないので、後日upsolveする。
こどふぉはAtCoderに比べて実装が面倒な問題が多くて、速度が出ないのが悩み。まあ毎日のようにバチャをしていれば慣れるだろう。
24時に卒論配属の抽選作業があって、無事希望の教員に配属された。かなり解析よりのことをやるので、関数解析の勉強をする必要がありそう。結構わくわくしている。
TDPC-Rを解説ACした。強連結成分分解したあとのDAG上で、2本の（点素とは限らない）パスが通る頂点の重みの和の最大値を求める問題。この「点素とは限らない」の部分をどう処理したらいいか全くわからなかったので、解説を見た。DAGの推移閉包を取ることで、「2本の点素とは限らないパスが通る頂点の重みの和の最大値」を「2本の点素パスが通る頂点の重みの和の最大値」に言い換えることができる。最長パスのDPをプロトタイプに、点素性を保ってDPをする。頂点の重みを
とする。
として、
と初期化し、トポロジカルソート順で
であるようなペアについてのみ遷移を行うことにする。
であるような頂点
に遷移してしまうと、パスの点素性が保証されないので、これは無視することにして、
であるような
についてのみ、
と
を更新していけばいい。グラフすべてが1点につぶれるような場合を同様に扱うために、全頂点へ辺が伸びている超頂点を事前に追加しておくと楽。
