考えたこと 括弧列で定番の+1/-1の累積和とか考えるけどよくわからないので実験する 括弧列の長さがnのとき、LCSがn-1の括弧列が絶対につくれる気がする 1文字をずらしていったような括弧列はLCSがn-1になるはず 括弧を飛び越すようなずらし方をすれば異なる…

考えたこと 全てのマスを一回ずつ通って始点に戻るような経路(ハミルトン閉路)があればその経路をぐるぐる回ればいいのでどんなKでも必ずできる 実験してるとRかCの片方でも偶数であればハミルトン閉路が絶対にあることがわかる 奇数 * 奇数のときにハミルト…

考えたこと bitDPをしてくださいみたいな雰囲気をしている 制約的に考えると dp[S] = (集合Sのセルを実行しているときの最小コスト) みたいな持ち方になりそう n個全部を実行したことについての判定をどうするかちょっと悩んだけど命令s[i]の和集合が全て実…

考えたこと この間勉強した全方位木DPを思い出す 頂点数n<=50なのでただの木DPでO(n^2)でいい 頂点iの部分木の頂点を全部訪れるのにかかる手数は一番深いところを後回しにすればいいので簡単に求まる 頂点iの部分木の頂点を全部訪れるわけではないので dp[i]…