2018-01-01から1年間の記事一覧
G - Tapu & Tapi 2最終的にたぷちゃんとたぴちゃんの両方が存在するような連結成分が存在しなければOKなのでそれ以外の3つの状態をすべて持つことにします。$dp1[u] :=$ $u$ を含む連結成分にたぷちゃんもたぴちゃんも存在しないもので有効な状態にする最小…
参加しました。https://beta.atcoder.jp/contests/bitflyer2018-final開始前、wifiが接続できない感じで不安でしたが、近くにnuipさんがいたおかげで安心してコンテストに臨めました。コンテスト中、ほぼすべての時間を使ってFとGを解こうとしました。Fを解…
今年も神戸大学のチームとして、アルゴリズムのプロkimiyukiさん、マラソンマッチのプロkurenai3110さん、えんぴつ画を描くのが上手な僕KokiYmgch、の3人で出ました。僕はいま東京に住んでいるので朝7時に出発して神戸大学に向かいます。ワクワク！11時半に…
全方位木dpについてです。基本的にここにまとまっていて、僕自身もこの記事から学びました。本記事では、これよりもわかりやすく簡潔な実装します。名前が大げさですが、普通の木dpを少し拡張するだけです。上のサイトの例題 $1$ にもありますが、次のような…
木上のパスが含む辺の中で、その重みの最大値(最小値)を対数時間で求めるライブラリです。よく知られたダブリングというテクニックを使っています。ダブリングについてはここでは書きませんが、parmax[k][u] というのは、頂点 $u$ から根に向かってパスを $2…
二重頂点連結成分分解木のライブラリです。誰も使わないと思います。これの続きです。任意の無向グラフから二重頂点連結成分と関節点を頂点とする木を構築できます。それをやってくれるライブラリです。 //e2i[edge] -> index of the edge //tree index : [0…
二重頂点連結成分分解の実装です。追記：誤りがあったので大幅に変更しました。名前が似ていますが、二重辺連結成分分解とは異なります。そちらについてはこの記事をご覧ください。任意の無向グラフを、その部分グラフであって「その部分グラフにおける関節…
二重辺連結成分分解の実装です。二重頂点連結成分分解についてはこちらの記事をご覧ください。無向グラフ上で、橋が存在しない部分グラフを一つの頂点につぶすと、橋を辺とする木ができます。以下は、それをそのまま実装しています。 struct LowLink { set<pair<int, int>> </pair<int,>…
H - Generalized Insertion Sort 解法 まず制約に注目すると、$25000 \geq n \log n$ にしか見えないので、そのような計算回数を実現するアルゴリズムを考えたい気持ちになります。木に関するアルゴリズムであって、計算量に $\log$ が現れるものは僕は現時…
CS Academy 解法 木を最小個数のパスで被覆する問題。選ぶパスは重複して良いことに注意します（もし重複を許さないなら、それはオイラー閉路を適切に構築してそれを出力する問題です）。とりあえず、葉は必ずパスの端点として選ぶ必要がありそうです。よっ…
E - Frequency他の人の実装を見るとなんだかあっさり実装されているので、より簡単な解法がありそうです。 解法 数列に出現する数 $x$ について、数列全体に $x$ 以上の数が何個あって、その一番左の数の $index$ が何であるのかがわかれば答えがわかりそう…
E - Prefix-free Game 解法 まず文字列は $0$ と $1$ しか含まないので、完全二分木で考えました（この考え方は、一般的な文字列においても使えるらしく $Trie$木と呼ばれているらしいです）。すると、木の頂点を順に塗りつぶしていく問題に変わります。ある…
F - XOR Tree 解法 $XOR$ の性質を使ってかなりきれいに解けます。まず、パスに関する操作が非常に扱いにくいため、なんとかしたい気持ちになります。$XOR$ の性質で重要なものとして、任意の数について、それ自身との $XOR$ は$0$ になるというものがありま…
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)とは、無向グラフにおいて、辺で繋がれた頂点同士が、互いに異なる色でなければいけないという制約のもとで、すべての頂点…
D - 辺彩色 解法 まず辺に色を塗っていく操作を、逆順から見ていきます。この発想は以下のような問題でも使えます。B - Splatter Paintingそうすると、一回塗った辺はもう変更することができないという操作に変えることができます。すると、各辺は条件を満た…
Problem - E - Codeforcespekempeyさんが書かれたコードから学びました。わかりやすすぎてありがたすぎます。 解法 まず、ある文字の集合を適切に並べると回文になるという条件は、出現回数が奇数である文字の種類が $1$ 個以下である、という条件に言い換え…
はじめに $Hirschberg's\ Algorithm$ に関する解説を丁寧に書きました。English version is available here. 問題 まず次の問題をご覧くださいCS Academy概要：各マスに数字が書かれたグリッドが与えられ、そのグリッド上で左上のマスから右下のマスまで最短…
追記 2018/01/22 ・重心を求めるアルゴリズムを変更して高速化しました。 ・最後に実践的な例題を置きました。 はじめに アリ本に載っているものよりも、（個人的に）わかりやすく整理した重心分解による分割統治法の一般形について書きます（アリ本でばっち…
問題 CS Academy 感想 変わった問題でおもしろいです。 解法 自明 $DP$ 解を書くと、やばいくらい $MLE$ します。$O(nm)$ のグリッドを用意するだけで $MLE$ するので注意です。空間計算量を落としたいので、$Hirschberg's\ algorithm$ (参考)という最高のア…
Atcoder Regular Contest 063 E. 木と整数 / Integers on a Tree E - 木と整数 / Integers on a Tree 感想 ふつうに木の上で計算しました。 解法 まず頂点 $0$ を根として考えることにします。明らかな性質として、深さが同じような頂点に書かれた値すべての…
Atcoder Regular Contest 088 F. Christmas Tree F - Christmas Tree 感想 木をいくつかのパスで被覆する、よくありそうな問題です。CSA Flip the Edgesに似ています。 解法 まずパスの両端の次数は奇数でそれ以外は偶数である（それはそう）という性質から…
第4回ドワンゴからの挑戦状予選 E. ニワンゴくんの家探し E - ニワンゴくんの家探しかなり好きな問題だったので、本番で通したかった。 解法 まず分割して考えていきたい気持ちになるので、重心に注目します。重心が二つある場合は、その重心の $2$ 頂点でク…
お寿司をできるだけたくさん食べるアルゴリズム みなさんお寿司は好きですか？ 僕は好きです。というわけで、できるだけたくさんの種類のお寿司を食べるためのアルゴリズムについて書きます。さて、早速たくさん食べる方法について考えていきます。まずお寿…
Atcoder Grand Contest 013 F. Two Faced Cards F - Two Faced Cards 解法 解法がかなりきれいで、よい問題だと思いました。editorialの英語版がわかりやすかったので、そこに書かれているように実装しました。まず定石ですが、$c$ はソートして座圧し、$c$ …
木の重心列挙アルゴリズム English version is available here.木の重心を列挙するアルゴリズムです。重心の性質をよく知っている方にとっては自明な木$dp$を実装するだけだと思います。これで $verify$ しています。計算量は $O(n)$ です。中のアルゴリズム…
