https://leetcode.com/contest/weekly-contest-132/problems/recover-a-tree-from-preorder-traversal/二分木がある。 これをpreorder dfsで探索して、[深さ][頂点に書かれている数]を順番に書いてつなげた文字列が与えられる。 preorder dfsはある頂点に来…

https://leetcode.com/contest/weekly-contest-132/problems/longest-arithmetic-sequence/N要素の配列Aがある。 ここから、等差数列である連続でなくてもよい部分列を取り出すときの、長さの最大値を求めよ。N≦2000, A[i]≦10000 前提知識 動的計画法 解説 h…

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...」しかないので、どちらも試す。 最終的な目標と違っている個数分だけ塗り替えが必要なので、その…