回文検出は、以下の記事で書いたManacherのアルゴリズムを使えばで解けるが、かければDPでも解くことが出来る。 DPの方が遅いが、コード的にはかなりシンプルに書けるのでメモしておく。klee.hatenablog.jp 個人的にはManacherは偶数長の時とか、探索範囲の…

本番中に解けずに泣いた。 WAを出しまくったので自戒を込めて書く。 atcoder.jp 考察 愚直に上からペアになった石を取っていけば良いか？山の数的に探索が間に合わなさそう。(解説を見ると上手くやると間に合うらしい...) 各山を見て行った時に、特定の数字…

典型90問楽しい。 前にも似た問題を解いた記憶があったので、45度変換を使ってすんなり解けたが、そういえばなんでその原理で解けるのか記憶が薄れていたので復習がてらまとめておく。 マンハッタン距離からチェビシェフ距離への変換 ２次元座標系の2点を考…

昨日のABC188、Dが解けず３完だった。atcoder.jpいもす法と座表圧縮かなと思いつつ、座標圧縮への理解が曖昧だった＋本番の焦りもありACできなかった。 最近なんとなく解法が浮かぶのは成長だなと思いつつも、あと一歩詰めきれないところが甘いので書いてい…

atcoder.jp 有名なDPの問題なので知ってはいたが、ややこしそうなので後回しにしていた。 先日買ったけんちょんさん(@drken1215)の本を進めていたら章末問題に載っていたので、もりもり鍛えるべく重い腰を上げて解いてみた。アルゴリズムとデータ構造をげっ…

atcoder.jp素朴に配るDPを実装するとになりTLEとなる(なってしまった....)。 例えば下記の入力だと遷移数がマス目の長さと同じオーダになるので通らない。 200000 1 1 200000 こういう時は累積和でdpを高速化するのが定番らしい。解説動画が非常に分かりやす…

何を解きたいか ご存じのように回文とは,のような逆順でも変化しない文字列のことです。このとき、ある文字列の部分文字列で作られる回文の最大長さや数を問う問題を解きたい場合を考えます。ナイーブに解こうとすると二重のfor文で全ての部分文字列を生成し…