何の話かと言うと atcoder.jp上記の問題の簡単な解説です。（特に捻りはありません・・・。） 単調増加部分列の長さ 基本は、与えられた数列を順番にスキャンしながら、・dp[k] = v # 長さ k の部分列を取り出した際の最後の値（の最小値）が vを更新してい…

何の話かと言うと atcoder.jpこの問題、公式解説では、「新たな頂点を追加してリンク数を削減する」というテクニックが紹介されています。実は、これを知らなくても、もう少し自然な発想で「本質的に同じ解法」にたどり着けるという話をします。 基本的な考…

何の話かと言うと atcoder.jpこの問題をネタに「重み0のリンクで結合されたノードを同一視する」という話をします。 一般的な解法 まず、この問題の一般的な解法は、01-BFS になります。方向転換を考慮する必要があるので、座標 (x, y) + 方向（上下方向 or …

何の話かと言うと atcoder.jpこの問題、公式解説では、最小カット問題（＝最大フロー問題）に帰着して、Dinic 法で解くという解法が紹介されていますが、もうちょっと素朴な「ナップサック問題」としても解ける（解けた）ので紹介します。 ナップサック問題…

何の話かと言うと atcoder.jpこの問題をネタに、「頂点についてのループと辺についてのループ」の話をします。・・・・というのは、ちょっと無理矢理感があって、ぶっちゃけは、別解を紹介したいだけです。 辺についてのループ 一般に、グラフの問題は、「N …

何の話かと言うと atcoder.jpこの問題をネタにして、条件によってアルゴリズムを場合分けする、という話をします。 2つの解法 まず、この問題の模範解答は「遅延評価セグメント木」を使った解法になります。詳しくは、公式解説を参照してください。一方、も…

何の話かと言うと atcoder.jpこの問題をネタに、「（閉路を含む）有向グラフの深さ優先探索」の実装方法に関する話をします。問題の解法については公式解説に譲りますが、解法の中で「強連結成分分解」が使われており、これを実装する際に、「（閉路を含む）…

何の話かと言うと atcoder.jp上記の問題をネタに、計算量の観点から解法を考える、という話をしたいと思います。 問題の内容 問題では、円周上の点になっていますが、点 1 のすぐ左で切って円を開けば、1 〜 N の区間に複数の区間 (-----) がばら撒かれてお…