問題リンク atcoder.jp 問題概要 長さ\(N\)の整数列\(A_i\)と\(B_i\)が与えられていて、\(A_i \leqq B_i\)が成り立つ。 各iに対して\(A_i \leqq X_i \leqq B_i\)となる整数\(X_i\)をとった時、\({X_i}\)の中央値として有り得る値はいくつあるか。 解法 まず\…

問題リンク atcoder.jp 問題概要 省略 解法 Knapsack for All Segmentsの類題。 \(dp[i][j] =\) {\(A_1,...,A_i\)の各部分集合に対する、和がjとなる部分集合の数} と置いてDPする。 遷移は \(dp[i+1][j] = 2dp[i][j] + dp[i][j-A_{i+1}]\) となる。 右辺の…

個人的に コンテスト中に解ききれなかった 解法が思い浮かばず解説ACした などの理由で特に悔いが残る問題をまとめておく。 ABC F - Negative Traveling Salesman F - Usual Color Ball Problems F - Virus 2 F - Square Subsequence G - Increasing K Times…

未証明です。 問題リンク atcoder.jp 問題概要 3つの非負整数A,B,CとN個の文字列(AB,AC,BCのいずれか)が与えられる。 \(1\leqq i \leqqN\)に対し、i番目の文字列がABならば「Aに1足しBから1引く」「Bに1足しAから1引く」のいずれかを選ぶ(AC,BCについても同…

問題リンク atcoder.jp 問題概要 \(N\)要素の数列\(A_i\)が与えられる。 これらのうち2つを選んで得られる\(N(N-1)/2\)個のペアのうち、iとjの差の絶対値が\(A_i + A_j\)に等しいものはいくつあるか。 解法 \(|i-j|=A_i+A_j\)を変形すると \(i > j\)のとき\(…

本番中は勘で解いた。 問題リンク atcoder.jp 問題概要 1以上\(10^9\)以下の整数Xが与えられる。 整数A,Bの組で\(A^5-B^5=X\)を満たすものを1つ示せ。 ただし、答えとなる(A,B)が存在することは保証されている。 解法 \(A \neq B\)としてよい。 因数分解する…

問題リンク atcoder.jp 問題概要 N頂点の木グラフと、各頂点に対して整数\(a_i\)が与えられている。 \(1 \leqq k \leqq N\)の全ての整数に対して、次の問題を解け。 問題k: 頂点1から頂点kまでの最短経路上にある頂点の整数をこの順に並べた数列の、最長増加…