https://leetcode.com/contest/weekly-contest-132/problems/recover-a-tree-from-preorder-traversal/二分木がある。 これをpreorder dfsで探索して、[深さ][頂点に書かれている数]を順番に書いてつなげた文字列が与えられる。 preorder dfsはある頂点に来…
![はてなブックマーク - Recover a Tree From Preorder Traversal [LeetCode 1028]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/14/130905)
https://leetcode.com/contest/weekly-contest-132/problems/longest-arithmetic-sequence/N要素の配列Aがある。 ここから、等差数列である連続でなくてもよい部分列を取り出すときの、長さの最大値を求めよ。N≦2000, A[i]≦10000 前提知識 動的計画法 解説 h…
![はてなブックマーク - Longest Arithmetic Sequence [LeetCode 1027]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/14/130851)
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…
![はてなブックマーク - Maximum Difference Between Node and Ancestor [LeetCode 1026]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/14/130836)
https://leetcode.com/contest/weekly-contest-132/problems/divisor-game/AliceとBobがいる。 最初に数Nが書いてある。 順番に「書いてある数Nの約数dを1つ選び、N-dに書き換える。x=1でターンが来たら負け」をする。 Aliceが勝つならtrue, Bobが勝つならfa…
![はてなブックマーク - Divisor Game [LeetCode 1025]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/14/130818)
https://codeforces.com/contest/1153/problem/D頂点1が根、N頂点の根付き木がある。 各頂点にはmin, maxが付いている。 木の葉の数をKとすると、木の葉には1～Kを1つずつ割り当てられる。 葉でない頂点の数は子のminかmaxになる（頂点についているmin,maxに…
![はてなブックマーク - Serval and Rooted Tree [Codeforces Round #551 (Div. 2) D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/14/110609)
https://codeforces.com/contest/1153/problem/C長さNの不完全かもしれないカッコ列がある。 ?を適切に(か)に変えて、以下の条件を満たすものを構築せよ。 構築できないなら:(を出力。 全体が正しいカッコ列 全体以外の全ての接頭文字列が正しいカッコ列でな…
![はてなブックマーク - Serval and Parenthesis Sequence [Codeforces Round #551 (Div. 2) C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/14/103201)
https://atcoder.jp/contests/abc124/tasks/abc124_d 前提知識 尺取法 解説 https://atcoder.jp/contests/abc124/submissions/4966633まず、気づくべき性質として 「ある区間を全て1にするには、その区間に含まれる0のグループの個数分の支持回数が必要にな…
![はてなブックマーク - Handstand [AtCoder Beginner Contest 124 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/14/100439)
https://atcoder.jp/contests/abc124/tasks/abc124_c 解説 https://atcoder.jp/contests/abc124/submissions/4963281最終的な形は「101010...」か「010101...」しかないので、どちらも試す。 最終的な目標と違っている個数分だけ塗り替えが必要なので、その…
![はてなブックマーク - Coloring Colorfully [AtCoder Beginner Contest 124 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/14/001053)
https://atcoder.jp/contests/abc124/tasks/abc124_b 解説 https://atcoder.jp/contests/abc124/submissions/4962119今までの最大値よりも小さいなら、海が見られないので、今までの最大値を持ちながら、 答えをカウントしていこう。 int N, H[20]; //------…
![はてなブックマーク - Great Ocean View [AtCoder Beginner Contest 124 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/13/231937)
https://atcoder.jp/contests/abc124/tasks/abc124_a 解説 https://atcoder.jp/contests/abc124/submissions/4962028場合分けをして解くことにする。 A=Bなら、どっちも取るのが最適。 そうでないなら、大きい方を2回取るのが最適。 int A, B; //-----------…
![はてなブックマーク - Buttons [AtCoder Beginner Contest 124 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/13/231648)
https://yukicoder.me/problems/no/814 前提知識 二分探索 解説 https://yukicoder.me/submissions/338394問題文にもあるように、ジジは奇数枚・他は偶数枚になっている。 使えそうな性質がこれなので、これを使って解法を考えていく。 ある数以下のカードの…
![はてなブックマーク - ジジ抜き [yukicoder No.814]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/13/170958)
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…
![はてなブックマーク - ユキちゃんの冒険 [yukicoder No.813]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/13/155413)
https://yukicoder.me/problems/no/812 前提知識 ダイクストラ 解説 https://yukicoder.me/submissions/3382671日経過するたびに、距離が2の人と友達になる。 次の日もまた、距離が2の人と友達になる。 これで友達になっている人を考えると もともと距離1→も…
![はてなブックマーク - Change of Class [yukicoder No.812]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/13/095027)
工事中 ダブリング ～～～ 問題
https://yukicoder.me/problems/no/811 前提知識 エラトステネスの篩の計算量 解説 https://yukicoder.me/submissions/338186今回は答えを全探索する。 答えの候補MがNと共通の素因数をK個以上持つかは、2つの数を素因数分解して、同じ数の個数のうち少ない…
![はてなブックマーク - 約数の個数の最大化 [yukicoder No.811]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/13/014518)
https://yukicoder.me/problems/no/810 解説 https://yukicoder.me/submissions/338175Mで割った余りを並べてみると、 0 1 2 3 ... M-1 0 1 2 3 ... となる。 ここからどこでもいいので、連続してM個取り出すとそれはすべて異なっていることが分かる。 よっ…
![はてなブックマーク - 割った余りの個数 [yukicoder No.810]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/13/013302)
https://yukicoder.me/problems/no/809 解説 https://yukicoder.me/submissions/338172解法を考えるときは、全探索対象を探すという汎用的なテクがあり、 今回はAを全探索して考える。 普通に全探索すると、10^9かかるが、A＜Bと考えると、sqrt(10^9)に収ま…
![はてなブックマーク - かけ算 [yukicoder No.809]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/13/013025)
https://atcoder.jp/contests/abc123/tasks/abc123_d 前提知識（と使える知識） 二分探索 枝刈り全探索 （解説にあって面白いので紹介） 解説1:全部二分探索 https://atcoder.jp/contests/abc123/submissions/4870889どこから初めていいか分からないと思うが…
![はてなブックマーク - Cake 123 [AtCoder Beginner Contest 123 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/07/113100)
https://atcoder.jp/contests/abc123/tasks/abc123_c 解説 https://atcoder.jp/contests/abc123/submissions/4870666数学の問題。 A～Eの中の最小の区間がボトルネックであることが言える。 この最小をmiをすると、その部分がボトルネックとなって、毎回mi人…
![はてなブックマーク - Five Transportations [ AtCoder Beginner Contest 123 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/07/104037)
https://atcoder.jp/contests/abc123/tasks/abc123_b 解説 https://atcoder.jp/contests/abc123/submissions/4870610料理を注文する順番を全探索する。 これはC++だとnext_permutationを使うといい。 注文順が確定したら、あとはシミュレーションをする。 注…
![はてなブックマーク - Five Dishes [AtCoder Beginner Contest 123 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/07/103225)
https://atcoder.jp/contests/abc123/tasks/abc123_a 解説 https://atcoder.jp/contests/abc123/submissions/4870584最も直接通信ができない可能性があるアンテナは、端のアンテナ同士の通信なので、 その距離が直接通信できる距離かを判定する。 int A[5], …
![はてなブックマーク - Five Antennas [AtCoder Beginner Contest 123 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/04/07/102756)
https://codeforces.com/contest/1142/problem/B長さNの順列Pと、長さMの数列Aがある。 数列Aの要素は[1,N]である。 これについて以下のクエリに答える。 A[L,R]の部分列でvalidな部分列が存在するなら1, 存在しないなら0を答える。 valid ⇔ 順列Pを0回以上…
![はてなブックマーク - Lynyrd Skynyrd [Codeforces Round #549 (Div. 1) B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/03/31/105753)
https://codeforces.com/contest/1142/problem/A円状に頂点1から頂点nkまで並んでいる。 1, K+1, 2K+1, ...のようにN個のお店がある。 最初に頂点sと距離lを決める。 s, s+l, s+2l, ... のように距離lで頂点の数が増える方向に移動して、sに戻ってきたら操作…
![はてなブックマーク - The Beatles [Codeforces Round #549 (Div. 1) A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/03/31/104108)
https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d 前提知識 動的計画法 解説 https://atcoder.jp/contests/exawizards2019/submissions/4770817 DPテクを組み合わせる。 「2. 選択するものを最初にソートしておくと、DPできたり、状態を…
![はてなブックマーク - Modulo Operations [エクサウィザーズ 2019 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/03/31/013133)
https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_c 前提知識 二分探索 解説 https://atcoder.jp/contests/exawizards2019/submissions/4778445check(x) := x番目にあるゴーレムが全呪文を終えた後にある位置 これを作ってみると、 -1 -1 -…
![はてなブックマーク - Snuke the Wizard [エクサウィザーズ 2019 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/03/31/010300)
https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_b 解説 https://atcoder.jp/contests/exawizards2019/submissions/4764937BとRの数を数えて、B＜RならYesと答える問題。 どんなふうに数えてもいいが、map＜char,int＞で数えている。 int …
![はてなブックマーク - Red or Blue [エクサウィザーズ 2019 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/03/31/005216)
https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_a 解説 https://atcoder.jp/contests/exawizards2019/submissions/4778304正三角形となるのは、全ての辺の長さが等しいときである。 なので、それを確かめればいい。 int A, B, C; //-----…
![はてなブックマーク - Regular Triangle [エクサウィザーズ 2019 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/03/31/005053)
https://atcoder.jp/contests/abc122/tasks/abc122_d 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc122/submissions/4712538条件を満たす文字列を良い文字列と呼ぶことにする。 dp[s] := 最後の3文字がsである良い文字列の組合せ 最初はdp["###…
![はてなブックマーク - We Like AGC [AtCoder Beginner Contest 122 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/03/25/232610)
https://atcoder.jp/contests/abc122/tasks/abc122_c 前提知識 https://www.hamayanhamayan.com/entry/2017/07/04/020117:titl=累積和 解説 https://atcoder.jp/contests/abc122/submissions/4712429最初の考察が一番むずかしいと思うが、本題よりもう少し簡…
![はてなブックマーク - GeT AC [AtCoder Beginner Contest 122 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/03/25/231455)
https://atcoder.jp/contests/abc122/tasks/abc122_b 解説 https://atcoder.jp/contests/abc122/submissions/4702739Sの長さがとても短いので、Sの部分文字列すべてについて考えることができる。 部分文字列S[L...R]について、ACGT文字列であるかを判定する…
![はてなブックマーク - ATCoder [AtCoder Beginner Contest 122 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/03/25/230649)