AtCoder Educational DP Contest T - Permutation こちらの問題の解法を理解したので書き残す。 …と思ったけど、言葉にできるほどきちんと理解していないことに気付いた。 とりあえず、中途半端な状態だけど書き残すことにする。 順列の位置を横軸、要素の値…

問題 https://atcoder.jp/contests/abc147/tasks/abc147_f 考察 普通に全探索すると、列挙だけで\(O(2 ^ N)\)かかるので間に合わない。ここで高橋君の取る要素の数を\(k\)とおくと、\(S - T\)は以下の式で表せる。 $$kX + tD - ((N - k)X + aD)$$ \(t\)は高…

コンテスト本番だと解けそうにない…。 問題 https://atcoder.jp/contests/abc150/tasks/abc150_d 考察 条件式を変形すると「任意の\(k\)に対して\(\frac{X}{a_k} - \frac{1}{2}\)が非負整数か」と言い換えられ、\(a_k = 2b_k\)とおくと更に「任意の\(k\)に対…

問題 https://atcoder.jp/contests/abc152/tasks/abc152_f 考察 次のようなDPを定義する。 dp[i][j] := 通り数 i : 頂点番号 j : 満たす制約の集合 あらかじめ、「ある辺を黒で塗ったときにどの制約を満たすか」を求めておく。その上で、根付き木上でDPを行…

AtCoder ABC152 F - Tree and Constraints https://atcoder.jp/contests/abc152/tasks/abc152_f 解けなくて悔しい。まだ解説に目を通していない。 解けるまで考えるか、解説を見てしまうか悩む。 おそらく言い換えることで簡単な問題になると思うけど、言い…

atcoder.jp 概要 \(N\)頂点\(M\)辺の単純な無向グラフがあります。以下のクエリが\(Q\)個与えられるので答えてください。 頂点\(A, B, C\)について、同じ辺を2度通らないパス\(A\)→\(B\)→\(C\)は存在するか 制約：\(3 \le N \le 10 ^ 5\)、\(1 \le M \le 2 \…