ほとんど同じ問題を考えたことがあったので割りと一瞬でした。 問題 xmascontest2015noon.contest.atcoder.jp 解法 X = (A*X + B) mod C というのは, 行列計算で言うと mat[0][0] = A, mat[0][1] = B, mat[1][0] = 0, mat[1][1] = 1 というのを使って mat * …

なんとなくマラソンマッチっぽい問題だと思いました。 問題 arc024.contest.atcoder.jp 解法 解説を参考にして解きました。 AtCoder Regular Contest 024 解説 from AtCoder Inc. www.slideshare.net今, [xl, xr) の間で条件を満たそうとしているとします。…

問題 utpc2013.contest.atcoder.jp 解法 N const int INF = 1e9+7; bool ok(const vector<int>& A, int m) { int n = A.size(); set<int> S; vector<int> B(m+1, INF); for (int i = 0; i < n; i++) { B[m-n+i] = A[i]; S.insert(A[i]); } for (int i = m-1; i >= 1; i--) {</int></int></int>…

問題 utpc2013.contest.atcoder.jp 解法 2 つのグラフの直径, 半径を求めて, 最大値については, (直径1) + (直径2) + 1 最小値については, max((半径1) + (半径2) + 1, max((直径1), (直径2))) を求めれば良いです。直径, 半径は O(nm) で求められるので計算…

問題 abc003.contest.atcoder.jp 解法 ちょっとアホな方法で通してしまったんですが, 後で紹介します。まず前提として, この問題は結局「X*Y の長方形を作るように D+L 個の物体を配置する方法は何通りあるのか」というのが求められれば, あとはそれに comb[…

問題 xmascontest2015.contest.atcoder.jp 解法 S: (禁止されている辺の集合), unvisit: (現時点でまだ訪れていない頂点の集合) とします。で, ある頂点 v に訪れた時は, unvisit の頂点を見ていって, (u, v) が S に含まれるものでなかったら v -> u に辺を…

Chokudai Contest 001 に参加しました。CodeVS でマラソンマッチ楽しい〜となったので参加したいと思っていたんですが, btk さんがチームメイト募集してたので一緒に参加しました。@btk15049 一緒に出たい気がします(途中で抜けちゃうかもですが)— マヨ子@大…

問題 arc049.contest.atcoder.jp 解法 タイプ 1 の制約は, 「y -> x という順番で塗る」という制約であると考えることが出来ます。順序関係は有向グラフで表せます。タイプ 1 の制約しかないと考えた場合, 閉路があるところを除いてすべての頂点を通ることが…

問題 arc049.contest.atcoder.jp 解法 二分探索します。「時間 t ですべての頂点が一箇所に集まることが出来るか」というのを判定したいです。そのために, i 番目の高橋ノルム君がどの範囲を動けるのかをまず調べてみると, これは 「Xi, Yi を中心とする, 一…

問題 arc018.contest.atcoder.jp 解法 解説を読みました。 AtCoder Regular Contest 018 解説 from AtCoder Inc. www.slideshare.net要するに「最小全域木のコストとそれを構成する場合の数を求めよ」という問題です。解くための前提として, 行列木定理とい…

問題 arc018.contest.atcoder.jp 解法 まず全体を(値, 行, 列) についてソートすることによって, 生徒がそれぞれどの行に行くか, というのが決定します(同じ点数の場合は, 行順にソートするのが明らかに得)。で, そうすると各行に対して, 「誰をどの列に配置…

問題 abc004.contest.atcoder.jp 解法 よく考えたら最小費用流解が何も考えず出来て頭良いですが, 普通に解きました。まず考察ですが, 赤, 緑, 青のマーブルはそれぞれ連続に置くのが明らかに得です。 「緑のマーブルの左端をどこにするか」というのを決める…

問題 abc008.contest.atcoder.jp 解法 まず 99 点の部分点解法を考えてみます。一回金塊を取ると, 長方形は 4 つに分断されます。分断された各長方形からは, 別れた他の長方形の金塊を取りに行くことは出来ません。よって, 区間 dp 的に, dp[dlX][dlY][urX][…

昔の ABC 難しくないですか… 問題 abc008.contest.atcoder.jp 解法 あるコイン C[i] が表を向く確率をそれぞれの i について求める, という方針で行きます。C[i]%C[j] = 0 かつ i != j を満たす j の集合を S, S の大きさを cnt とします(つまり C[i] の約数…

問題 abc025.contest.atcoder.jp 解法 1 から順番に数を入れていくことを考えます。この時, ある数 a を入れる場所に応じて場合分けをしてみます。上下に対しても同じようにできるので, 左右についてのみ考えます。 a が端っこにある時 … a がなんであろうと…

問題 abc034.contest.atcoder.jp 解法 ヒントに書いてあるとおり, 食塩水の濃度 x について二分探索します。濃度が x 以上になるかどうかは以下のようにしてわかります。食塩水全体の質量を S, 食塩の量を T とすると, 条件は T/S >= x i.e. T - x*S >= 0 と…

問題 utpc2013.contest.atcoder.jp 解法 ペアプロの動画で一緒に解きました。 続・ペアプログラミング - YouTube頂点 v から子でも親にもなっていない頂点は, v から dfs して行けない点, および u -> ... -> v と dfs して到達できる点ではない点, …

問題 arc048.contest.atcoder.jp 解法 解説スライドを見るとわかりやすいです。 AtCoder Regular Contest 048 from AtCoder Inc. www.slideshare.netまず, 配列 L の中で, 一番値の小さいものについては, そこに書く数字は何でも大丈夫です(一番値の小さいの…

問題 qupc2014.contest.atcoder.jp 解法 「最大 2 枚」の切符しか使えないので, s -> i -> g というように切符を使うか, s -> g に切符 1 枚を使うかの 2 通りしか考えられないです。s から i, i から g への最小費用はダイクストラを使えば簡単に計算できま…

問題 tdpc.contest.atcoder.jp 解法 まず強連結成分分解して, DAG の形にします(下のコードでは SCC ライブラリを使わないで Warshall-Floyd を使っていますが)。そしたら, DAG のあるノードに訪れたとすると, そのノードに含まれる頂点数(強連結成分の数)分…

問題 mujin-pc-2016.contest.atcoder.jp 解法 正しい括弧列は, 「'(' の数が ')' の数を下回ることなく進んでいき, 最終的に '(' と ')' の数が等しくなる文字列」と解釈することも出来ます。これ結構よく出るので覚えておいたほうが良いです。そう考えると,…

MUJIN プログラミングチャレンジ に参加しました。企業紹介がとても面白かったです。 問題 mujin-pc-2016.contest.atcoder.jp 解法 C は「奇数長 閉路」でぐぐったら答えがわかった— マヨ子@だがしかし可視化 (@mayoko_) 2016年2月27日ググりましょう。する…

問題 discovery2016-final.contest.atcoder.jp 解法 valid な括弧列は木構造になっています。例えば入力例 3 では, でっかい括弧から, 小さい括弧 2 つに向かって辺が伸びている木グラフであると考えることが出来ます。一つの頂点は 2 つの括弧 () に対応し…

問題 discovery2016-final.contest.atcoder.jp 解法 ある時間 t までに得られる最大の美味しさを priority_queue で管理します。時間 t には, t 個のビュッフェを取ることが出来ますが, どのように取るのが良いかというと, 美味しさが大きいものから取るのが…

問題 dwango2016-honsen.contest.atcoder.jp 解法 速度 v に対して二分探索します。check(v) = (速度 v で足りるかどうか) というのは, dp で確かめることが出来ます。dp[l][r][rflag] = (区間 [l, r] は既に到達済みという状態になるための最短時間(rflag =…

問題 dwango2016-honsen.contest.atcoder.jp 解法 考察です。 ニコニコ数は 18*2 = 36 個程度しかない L, x*L, ... とか言うように L を小さい順に並べるのではなく, つかう L の数を大きい順に並べていくと考えると, 「大きい数から貪欲に使っていく」とい…

問題 arc021.contest.atcoder.jp 解法 5000*5000/2 のすべての辺を貼ってから最小全域木のアルゴリズムを適用しても間に合いませんが, 最小全域木に使われる可能性の高い辺のみに注目して辺を貼れば, 最小全域木に近いものを作ることが出来ます。今回の場合,…

問題 arc021.contest.atcoder.jp 解法 まず浮かぶのは, priority_queue に値を突っ込んでいく形でコストが小さい順に貪欲にやることです。ただ, K そこで, K 回の増築の中で, 最もコストのかかる増築のコスト x について二分探索しましょう。コスト x 以下で…

問題 discovery2016-qual.contest.atcoder.jp 解法 まず部分点解法を考えてみます。K == 1 の場合は, O(NM) で処理すれば大丈夫です。 K > 1 の場合は, 2 回の操作で交換をなかったことにする 1 回の操作で交換をなかったことにする というテクニックが使え…

問題 abc033.contest.atcoder.jp 解法 各頂点 i について i 以外の頂点について偏角ソートします。あるペア (j, k) (j pi/2 であったら, 三角形(i, j, k) は確実に鈍角三角形であると言えます。また, 直角や鈍角になる場所はたかだか 1 つしかないので, 重複…