盤面を操作できる設定
枝刈り探索が根本的に計算量改善することを示せることがある！！！ 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…
AtCoder
AGC-D
最適化問題で変数を固定して考える
盤面を操作できる設定
文字列問題
回文
DP
LCS
二次元シーケンシャルDP
操作
操作をK回まで行える
AtCoder900点
操作によって出来上がるものの最適化問題
面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …
こういうの超苦手系だけど、苦手なりに解法を詰められたのは成長の証で嬉しい！ olphe たん、ナンさんとチームを組んでいて、olphe たんに考察を話して、詰めてくれて、爆弾周りの見落としがあって詰まって、みんなでデバッグして...とチーム戦ならではの考…
グリッド上をスタートからゴールまで行く系の問題において、しばしばある 盤面に対し、何らかの形でコストを払ったりスコアを獲得したりしながら変更を加えられる という設定の問題。その設定が加わると難しい問題になることも多いが、この問題は比較的素直…
