PAST009H LCSと同様． \(s,t\) の最後の文字 \(s_{i}, t_{j}\) を使うかどうかで場合分け． \(s_{[0,i)}, t_{[0,j)}\) に対する答えを \(dp_{i,j}\) とおく． \(s_{i} \neq t_{j}\) のとき：使った方が良い． 言い換えると，使う最適な選び方が存在する． こ…

PAST009J類題:ABC199C - IPFL 補助的な盤面 回転や反転を愚直に実装すると， \(O(N^2)\) かかるので， クエリごとに計算しては間に合わない． そこで，回転や反転をどの程度行ったを記録しておいて， 盤面自体は回転させずに保持する．つまり， (実際の盤面)…

PAST009K ガソリンスタンドが \(K \leq min(N-1,20)\) と少ないので，そこから考える． ガソリンスタンドを経由するせいで，逆に簡単． ガソリンスタンド \(x\) を一つ固定してこれを経由する \(s \rightarrow t\) の最短距離は， \(dis[x][s] + dis[x][t]\)…