Learning Algorithms

アルゴリズムの勉強メモ

CS Academy 069 D. Cover the Tree

CSA

CS Academy 解法 木を最小個数のパスで被覆する問題。選ぶパスは重複して良いことに注意します(もし重複を許さないなら、それはオイラー閉路を適切に構築してそれを出力する問題です)。とりあえず、葉は必ずパスの端点として選ぶ必要がありそうです。よっ…

Atcoder Regular Contest 069 E. Frequency

E - Frequency他の人の実装を見るとなんだかあっさり実装されているので、より簡単な解法がありそうです。 解法 数列に出現する数 $x$ について、数列全体に $x$ 以上の数が何個あって、その一番左の数の $index$ が何であるのかがわかれば答えがわかりそう…

Atcoder Regular Contest 087 E. Prefix-free Game

E - Prefix-free Game 解法 まず文字列は $0$ と $1$ しか含まないので、完全二分木で考えました(この考え方は、一般的な文字列においても使えるらしく $Trie$木と呼ばれているらしいです)。すると、木の頂点を順に塗りつぶしていく問題に変わります。ある…

Atcoder Petrozavodsk Contest 001 F. XOR Tree

F - XOR Tree 解法 $XOR$ の性質を使ってかなりきれいに解けます。まず、パスに関する操作が非常に扱いにくいため、なんとかしたい気持ちになります。$XOR$ の性質で重要なものとして、任意の数について、それ自身との $XOR$ は$0$ になるというものがありま…

Atcoder Petrozavodsk Contest 001 I. Simple APSP Problem

I - Simple APSP Problem$2000$ 点の問題ですが、以下のアルゴリズムで使う発想ができれば、解くことができます。Hirschberg's Algorithmについて - Learning AlgorithmsEnglish version is available here. 解法 グリッドを適当に二つに分割することを考え…

二次元累積和のライブラリ

二次元累積和のライブラリです。手で書いた方が早いレベルですが、何も考えずに求めたいときは貼ります。グリッド上で任意の長方形に含まれる数の総和を $O(HW)$ の初期化の後に $O(1)$ で求めます。antaさんがこれをRectangleSumと名付けて使っていた気がす…

辺を構築していく問題を解くためのテクニックについて

はじめに 辺を構築していく問題を解くテクニックについて書きます。全然一般的には使えませんが、とりあえず以下の $2$ 問が似たような感じで解けます。C - 3 Steps F - Blackoutどちらの問題も距離を適切に定義してやると簡単に解けます(というか二問目は…

二部グラフのライブラリ

二部グラフのライブラリです。この問題で $verify$ しています。$DFS$ を実装するだけですが、持っておくと便利な時がたまにあります。二部グラフかどうかを判定したい無向グラフの隣接リストgを投げて使います。二部グラフではない場合は、-1が返ってきて、…

彩色数を求めるアルゴリズム

はじめに 彩色数を求めるアルゴリズムについて書きました。English version is available here. 彩色数とは 彩色数(chromatic number)とは、無向グラフにおいて、辺で繋がれた頂点同士が、互いに異なる色でなければいけないという制約のもとで、すべての頂点…

Atcoder Regular Contest 041 D. 辺彩色

D - 辺彩色 解法 まず辺に色を塗っていく操作を、逆順から見ていきます。この発想は以下のような問題でも使えます。B - Splatter Paintingそうすると、一回塗った辺はもう変更することができないという操作に変えることができます。すると、各辺は条件を満た…

Codeforces 458 E. Palindromes in a Tree

Problem - E - Codeforcespekempeyさんが書かれたコードから学びました。わかりやすすぎてありがたすぎます。 解法 まず、ある文字の集合を適切に並べると回文になるという条件は、出現回数が奇数である文字の種類が $1$ 個以下である、という条件に言い換え…

Hirschberg's Algorithmについて

はじめに $Hirschberg's\ Algorithm$ に関する解説を丁寧に書きました。English version is available here. 問題 まず次の問題をご覧くださいCS Academy概要:各マスに数字が書かれたグリッドが与えられ、そのグリッド上で左上のマスから右下のマスまで最短…

重心分解による分割統治法の一般形について

追記 2018/01/22 ・重心を求めるアルゴリズムを変更して高速化しました。 ・最後に実践的な例題を置きました。 はじめに アリ本に載っているものよりも、(個人的に)わかりやすく整理した重心分解による分割統治法の一般形について書きます(アリ本でばっち…

CS Academy 065 E. Classic Task

CSA

問題 CS Academy 感想 変わった問題でおもしろいです。 解法 自明 $DP$ 解を書くと、やばいくらい $MLE$ します。$O(nm)$ のグリッドを用意するだけで $MLE$ するので注意です。空間計算量を落としたいので、$Hirschberg's\ algorithm$ (参考)という最高のア…

Atcoder Regular Contest 063 E. 木と整数 / Integers on a Tree

Atcoder Regular Contest 063 E. 木と整数 / Integers on a Tree E - 木と整数 / Integers on a Tree 感想 ふつうに木の上で計算しました。 解法 まず頂点 $0$ を根として考えることにします。明らかな性質として、深さが同じような頂点に書かれた値すべての…

Atcoder Regular Contest 088 F. Christmas Tree

Atcoder Regular Contest 088 F. Christmas Tree F - Christmas Tree 感想 木をいくつかのパスで被覆する、よくありそうな問題です。CSA Flip the Edgesに似ています。 解法 まずパスの両端の次数は奇数でそれ以外は偶数である(それはそう)という性質から…

第4回ドワンゴからの挑戦状予選 E. ニワンゴくんの家探し

第4回ドワンゴからの挑戦状予選 E. ニワンゴくんの家探し E - ニワンゴくんの家探しかなり好きな問題だったので、本番で通したかった。 解法 まず分割して考えていきたい気持ちになるので、重心に注目します。重心が二つある場合は、その重心の $2$ 頂点でク…

お寿司をできるだけたくさん食べるアルゴリズム

お寿司をできるだけたくさん食べるアルゴリズム みなさんお寿司は好きですか? 僕は好きです。というわけで、できるだけたくさんの種類のお寿司を食べるためのアルゴリズムについて書きます。さて、早速たくさん食べる方法について考えていきます。まずお寿…

Atcoder Grand Contest 013 F. Two Faced Cards

Atcoder Grand Contest 013 F. Two Faced Cards F - Two Faced Cards 解法 解法がかなりきれいで、よい問題だと思いました。editorialの英語版がわかりやすかったので、そこに書かれているように実装しました。まず定石ですが、$c$ はソートして座圧し、$c$ …

木の重心列挙アルゴリズム

木の重心列挙アルゴリズム English version is available here.木の重心を列挙するアルゴリズムです。重心の性質をよく知っている方にとっては自明な木$dp$を実装するだけだと思います。これで $verify$ しています。計算量は $O(n)$ です。中のアルゴリズム…

木の直径のパスを一つ挙げるライブラリ

木の直径のパスを一つ挙げるライブラリ 木の直径のパスを一つ挙げるやつをライブラリ化しました。これを解いている時に必要になって、自明なのに妙に実装に時間がかかったので作りました。この問題でverify済みです。中のアルゴリズムは非常に簡単で、次の通…

Educational Codeforces 035 div.2 F. Tree Destruction

Educational Codeforces 035 div.2 F. Tree Destruction Problem - F - Codeforces 解法 まず直径をできるだけ残しておくべきであることがわかります。なぜなら、直径を残している間は、それ以外の辺を破壊していくときに、その辺を破壊したときに得られる最…

CS Academy 062 E. Trees Partition

CSA

CS Academy 062 E. Tree Partition CS Academy 解法 なんらかの方法によって、各部分木の頂点集合とその補集合が即座にわかればよさそうです。しかし各ノードに部分木の頂点集合のsetを持たせるのはさすがに厳しいです。そこで、各頂点に乱数を割り振って、…

CS Academy 061 F. Xor the Graph

CSA

CS Academy 061 F. Xor the Graph CS Academy 解法 これを読んでいるとこの解法がかなり自然に見えます。まず明らかに同じ辺を3回以上使うメリットはありません。そのような構造は、パスの個数を増やすことなく、パスの長さを小さくできるからです。すべての…

平面上のロシアゲー(構築ゲー)を解くためのそこそこ一般的なテクについて

平面上のロシアゲー(構築ゲー)を解くためのそこそこ一般的なテクについて この記事はCompetitive Programming Advent Calendar 2017の12月13日の記事です。 ロシアゲーとは 「ある条件を満たすものを何でもいいから一つ出力しなさい」という形式の問題のこ…

CS Academy 060 E. Flip the Edges

CSA

CS Academy 060 E. Flip the Edges CS Academy 感想 DPの書き方がよくわからなかったので、pekempeyさんより解説をいただきました。 解法 まず二度以上選ぶ辺は存在しないことが言えます。なぜなら、もし仮にそのような部分があるとき、そのような部分は反転…

競プロにおけるオイラー路とその応用について

この記事はCompetitive Programming Advent Calendar 2017の12月8日の記事です。 競プロにおけるオイラー路とその応用について 目次 ・はじめに ・オイラー路とは? ・無向グラフのオイラー路 ・有向グラフのオイラー路 ・無向オイラー路の構築 ・有向オイラ…

CODE THANKS FESTIVAL 2017 参加記

CODE THANKS FESTIVAL 2017 参加記 CODE THANKS FESTIVAL 2017 - AtCoder 前日 前日はボードゲームの会に参加しました。会う予定の人は全員初対面だったため、もちろん緊張でヒザがガクガク震えていました。Tikeさん、TsutaJさん、フェリンさん、らてあさん…

Inverse of factorialsをO(N)で列挙する

Inverse of factorialsをO(N)で列挙する はじめに 素数 $p$ を法として、 $n$ 以下の階乗の逆元を $O(n)$ で列挙しちゃおうというアレを知っていますか?(僕は知りませんでした。。。)(コードが読みにくくなる割には)そんなに高速になるわけではないため…

CS Academy 058 E. Path Inversions

CSA

CS Academy 058 E. Path Inversions CS Academy 解法 ある長さ $k$ のパスを固定して考えると、このパス上の転倒数の個数とこのパスを逆に進むようなパス上の転倒数の個数の和は、書かれている数に関わらず常に、${}_{k + 1} C _2$ となることがわかる。これ…