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

最近multisetを使うと簡単に解ける問題がちょくちょくAtCoderで出題されて解けなかったりしたので、簡単にC++のmultisetについてまとめる。 C++のmultisetとは 順序付多重集合、つまり順序を保持しつつ要素の重複を許容した集合を効率的に管理するためのデー…

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

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

Rustの勉強を最近初めた。 準備運動代わりにAtCoderの問題を解いたりすることがあるのだが、自分にとって使い勝手の良いtemplateが見当たらなかった。 というわけで作ってみた。github.com コンテスト用に1プロジェクトで5ファイルのbinを生成(a〜f.rs) vsco…

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

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

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

包除原理を応用する問題が出題されて本番中は手も足も出なかった。 いろんな解説を見てACしたので理解をまとめる。 atcoder.jp 包除原理とは ものすごくざっくり書くと、複数の集合から構成される全体集合を重複なく求めるための考え方。基本的には全体を足…

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