AtCoder

スポンサーリンク
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)$ を根とする全域有向木を数えればよいと分かります。 固...
AtCoder

Yakiniku(code festival 2014 上海 [F])

概要 問題文 → ■公式解説 → なさそう?自分の提出 → ■ 解法 scorched:時刻 $T$ のイベント終了後の時点で、肉がグリルに置かれているunderdone:時刻 $T$ のイベント終了直前の時点で、肉が...
スポンサーリンク
タイトルとURLをコピーしました