はじめに
人は忘れる2
2021/9 ~
2回目無料，最短路問題
DAGで2人の最短路 -> TTPC-F
一般グラフはへのさん，snukeさんのツイッターで議論されている
https://t.co/KM2KTaRvlh
— heno (@heno_code) 2020年8月17日
リンク先は辺が2回目以降無料の問題なんですが、それを書き換えました。
dist[i][j]:=行きの現在位置がi,帰りの現在位置がj(帰りはt->sではなく逆順のs->tで遷移させたい)とすると、
・iとjをswapする(両側で同じi->j pathを通る)
・片側を1進める
・両側を同じ頂点に進める
これは同じように一般グラフで2人が最短路，街に訪れる際にもコストがかかるが，2人目はいらない https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324
周期tの文字列
任意のiでs[i + t] == s[i]が成立するとき，周期tの文字列と呼ぶなら，条件の言い換えが可能で， s[i, |S|-t] == s[i+t, |S|]と言い換えられる．これは頑張れば割と普通に示せる．
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2711&lang=jp
