と、思ったのですが、Macでやろうと思うとなんだか面倒だったのでクロスコンパイル用のコンテナを作った。 かなりニッチだと思いますが、せっかく作ったので整理して下記に置いた。 github.com 使い方 事前にbuildしたいソース一式をgithubに配置して置く必…

atcoder.jp TSP！ Traveling Salesman Problem 巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り…

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

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

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

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

はじめました。 競プロやったり、自作キーボード組んだりするのが好きです。 一応今年中にAtCoderで水色到達を当面の目標にしてるんですが、アルゴリズムの勉強とかしたそばから忘れていくので、記憶定着目的でいろいろ書いてく。