https://leetcode.com/contest/weekly-contest-132/problems/maximum-difference-between-node-and-ancestor/二分木が与えられる。 頂点Aが頂点Bの祖先であるときの、abs(A.val - B.val)の最大値を求めよ。頂点数≦5000 解説 https://leetcode.com/contest/we…

https://leetcode.com/contest/weekly-contest-132/problems/divisor-game/AliceとBobがいる。 最初に数Nが書いてある。 順番に「書いてある数Nの約数dを1つ選び、N-dに書き換える。x=1でターンが来たら負け」をする。 Aliceが勝つならtrue, Bobが勝つならfa…

https://codeforces.com/contest/1153/problem/D頂点1が根、N頂点の根付き木がある。 各頂点にはmin, maxが付いている。 木の葉の数をKとすると、木の葉には1～Kを1つずつ割り当てられる。 葉でない頂点の数は子のminかmaxになる（頂点についているmin,maxに…

https://codeforces.com/contest/1153/problem/C長さNの不完全かもしれないカッコ列がある。 ?を適切に(か)に変えて、以下の条件を満たすものを構築せよ。 構築できないなら:(を出力。 全体が正しいカッコ列 全体以外の全ての接頭文字列が正しいカッコ列でな…

https://atcoder.jp/contests/abc124/tasks/abc124_d 前提知識 尺取法 解説 https://atcoder.jp/contests/abc124/submissions/4966633まず、気づくべき性質として 「ある区間を全て1にするには、その区間に含まれる0のグループの個数分の支持回数が必要にな…

https://atcoder.jp/contests/abc124/tasks/abc124_c 解説 https://atcoder.jp/contests/abc124/submissions/4963281最終的な形は「101010...」か「010101...」しかないので、どちらも試す。 最終的な目標と違っている個数分だけ塗り替えが必要なので、その…

https://atcoder.jp/contests/abc124/tasks/abc124_b 解説 https://atcoder.jp/contests/abc124/submissions/4962119今までの最大値よりも小さいなら、海が見られないので、今までの最大値を持ちながら、 答えをカウントしていこう。 int N, H[20]; //------…

https://atcoder.jp/contests/abc124/tasks/abc124_a 解説 https://atcoder.jp/contests/abc124/submissions/4962028場合分けをして解くことにする。 A=Bなら、どっちも取るのが最適。 そうでないなら、大きい方を2回取るのが最適。 int A, B; //-----------…

https://yukicoder.me/problems/no/814 前提知識 二分探索 解説 https://yukicoder.me/submissions/338394問題文にもあるように、ジジは奇数枚・他は偶数枚になっている。 使えそうな性質がこれなので、これを使って解法を考えていく。 ある数以下のカードの…

https://yukicoder.me/problems/no/813 解説 https://yukicoder.me/submissions/338365公式解説にもあるが、門を1つにまとめ上げることで答えを求めよう。 逃走率p1、通過率q1の門、逃走率p2、通過率q2の門を1つにまとめると、逃走率 p=(p1+q1*q1*p2/(1-p1*p…

https://yukicoder.me/problems/no/812 前提知識 ダイクストラ 解説 https://yukicoder.me/submissions/3382671日経過するたびに、距離が2の人と友達になる。 次の日もまた、距離が2の人と友達になる。 これで友達になっている人を考えると もともと距離1→も…

工事中 ダブリング 個人メモ 数列の K 項間漸化式はダブリング DP で O(K^2 log N) で解ける。max の漸化式でも同じテクが使える 問題 https://yukicoder.me/problems/no/572 http://codeforces.com/contest/932/problem/D SRM778 Div1 Med

https://yukicoder.me/problems/no/811 前提知識 エラトステネスの篩の計算量 解説 https://yukicoder.me/submissions/338186今回は答えを全探索する。 答えの候補MがNと共通の素因数をK個以上持つかは、2つの数を素因数分解して、同じ数の個数のうち少ない…

https://yukicoder.me/problems/no/810 解説 https://yukicoder.me/submissions/338175Mで割った余りを並べてみると、 0 1 2 3 ... M-1 0 1 2 3 ... となる。 ここからどこでもいいので、連続してM個取り出すとそれはすべて異なっていることが分かる。 よっ…

https://yukicoder.me/problems/no/809 解説 https://yukicoder.me/submissions/338172解法を考えるときは、全探索対象を探すという汎用的なテクがあり、 今回はAを全探索して考える。 普通に全探索すると、10^9かかるが、A＜Bと考えると、sqrt(10^9)に収ま…

https://atcoder.jp/contests/abc123/tasks/abc123_d 前提知識（と使える知識） 二分探索 枝刈り全探索 （解説にあって面白いので紹介） 解説1:全部二分探索 https://atcoder.jp/contests/abc123/submissions/4870889どこから初めていいか分からないと思うが…

https://atcoder.jp/contests/abc123/tasks/abc123_c 解説 https://atcoder.jp/contests/abc123/submissions/4870666数学の問題。 A～Eの中の最小の区間がボトルネックであることが言える。 この最小をmiをすると、その部分がボトルネックとなって、毎回mi人…

https://atcoder.jp/contests/abc123/tasks/abc123_b 解説 https://atcoder.jp/contests/abc123/submissions/4870610料理を注文する順番を全探索する。 これはC++だとnext_permutationを使うといい。 注文順が確定したら、あとはシミュレーションをする。 注…

https://atcoder.jp/contests/abc123/tasks/abc123_a 解説 https://atcoder.jp/contests/abc123/submissions/4870584最も直接通信ができない可能性があるアンテナは、端のアンテナ同士の通信なので、 その距離が直接通信できる距離かを判定する。 int A[5], …