問題解説 [yukicoder] No.925 紲星 Extra
概要
問題文 → ■公式解説 → ■自分の提出 → ■
実装が易しめの平方分割解。あまり他の提出になさそうだったので一応書きます。
解法
列の平方分割により解きます。
数列 $A$ を、長さ $s$ の区間に区切る...
問題解説 AtCoder ギガ国の道路事情（GigaCode 2019 [G]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説が読み解けておらず…。
木の圧縮パートを除くと大差ないかもしれません。なかなか実装が大変になってしまいました。
解法
グラフの変形
葉を縮約していき...
AtCoder 連結（JAG 夏合宿 2015 Day2 [J]）
概要
問題文 → ■公式解説 → なさそう
解法
必要条件
連結であることが必要です。MST の辺の重みの和が、頂点の重みの総和以上であることが必要です。
十分性 ＋ 構築アルゴリズム
以上の必要条件...
AtCoder むこのどうぶつたち と しんりんのはかい（IOIer Japan Programming Contest #1 [A]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
解法
頂点を削除するとたくさん連結成分が増える可能性があってややこしいので、辺削除の操作に分解します。辺を削除したときに、元の連結成分の大きさがどう変化するかを計...
AtCoder Divide Both（abc206 [E]）
概要
問題文 → ■公式解説 → ■, ■
解答例 （Python）：解答例（C++）：
公式解説より良い計算量 $O(R^{0.75})$ 時間計算量での解法を紹介します。
半開区間
本解説（および、リンク先の解答例...
AtCoder グランド・グラフ（pakencamp-2018-day2 [G]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説より良い計算量になっていますね。たぶん、$3$ の指数が半分という感じ。
解法
前計算1：パスの場合
長さ $n$ のパスの場合に、次の $2$ つ...
AtCoder XORAND（code festival 2014 上海 [J]）
概要
問題文 → ■公式解説 → なさそう？自分の提出 → ■
解法
$O(NQ)$ 時間計算量の解法で AC になりました。非想定計算量でしょうかね。
$L = \lg \max A_i \leq 30$ とし...
AtCoder Obstruction（code festival 2014 上海 [I]）
概要
問題文 → ■公式解説 → なさそう？自分の提出 → ■
解法
ゴールへ到達可能だと判明しているマス全体の集合 $S$ を、以下のルールで生成します。
ゴールマスは $S$ に含まれる隣接している黒マスのい...
AtCoder Dungeon（code festival 2014 上海 [H]）
概要
問題文 → ■公式解説 → なさそう？自分の提出 → ■
解法
鍵に $1, 2, \ldots, n$ の番号をつけておきます。宝箱に、$1, 2, \ldots, m$ の番号をつけておきます。
まず、...
AtCoder Ammunition Dumps（code festival 2014 上海 [G]）
概要
問題文 → ■公式解説 → なさそう？自分の提出 → ■
読解！
解法
問題文に書かれている、同一視の基準をよく読みます。$(a,b)$ を根とする全域有向木を数えればよいと分かります。
固...