はまやんはまやんはまやん

hamayanhamayan's blog

Recover a Tree From Preorder Traversal [LeetCode 1028]

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

Longest Arithmetic Sequence [LeetCode 1027]

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

Maximum Difference Between Node and Ancestor [LeetCode 1026]

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…

Divisor Game [LeetCode 1025]

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

Serval and Rooted Tree [Codeforces Round #551 (Div. 2) D]

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

Serval and Parenthesis Sequence [Codeforces Round #551 (Div. 2) C]

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

Handstand [AtCoder Beginner Contest 124 D]

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

Coloring Colorfully [AtCoder Beginner Contest 124 C]

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

Great Ocean View [AtCoder Beginner Contest 124 B]

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

Buttons [AtCoder Beginner Contest 124 A]

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

ジジ抜き [yukicoder No.814]

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

ユキちゃんの冒険 [yukicoder No.813]

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…

Change of Class [yukicoder No.812]

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

競技プログラミングにおけるダブリング問題まとめ

工事中 ダブリング ~~~ 問題

約数の個数の最大化 [yukicoder No.811]

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

割った余りの個数 [yukicoder No.810]

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

かけ算 [yukicoder No.809]

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

Cake 123 [AtCoder Beginner Contest 123 D]

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

Five Transportations [ AtCoder Beginner Contest 123 C]

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

Five Dishes [AtCoder Beginner Contest 123 B]

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

Five Antennas [AtCoder Beginner Contest 123 A]

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

Lynyrd Skynyrd [Codeforces Round #549 (Div. 1) B]

https://codeforces.com/contest/1142/problem/B長さNの順列Pと、長さMの数列Aがある。 数列Aの要素は[1,N]である。 これについて以下のクエリに答える。 A[L,R]の部分列でvalidな部分列が存在するなら1, 存在しないなら0を答える。 valid ⇔ 順列Pを0回以上…

The Beatles [Codeforces Round #549 (Div. 1) A]

https://codeforces.com/contest/1142/problem/A円状に頂点1から頂点nkまで並んでいる。 1, K+1, 2K+1, ...のようにN個のお店がある。 最初に頂点sと距離lを決める。 s, s+l, s+2l, ... のように距離lで頂点の数が増える方向に移動して、sに戻ってきたら操作…

Modulo Operations [エクサウィザーズ 2019 D]

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d 前提知識 動的計画法 解説 https://atcoder.jp/contests/exawizards2019/submissions/4770817 DPテクを組み合わせる。 「2. 選択するものを最初にソートしておくと、DPできたり、状態を…

Snuke the Wizard [エクサウィザーズ 2019 C]

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_c 前提知識 二分探索 解説 https://atcoder.jp/contests/exawizards2019/submissions/4778445check(x) := x番目にあるゴーレムが全呪文を終えた後にある位置 これを作ってみると、 -1 -1 -…

Red or Blue [エクサウィザーズ 2019 B]

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_b 解説 https://atcoder.jp/contests/exawizards2019/submissions/4764937BとRの数を数えて、B<RならYesと答える問題。 どんなふうに数えてもいいが、map<char,int>で数えている。 int …

Regular Triangle [エクサウィザーズ 2019 A]

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_a 解説 https://atcoder.jp/contests/exawizards2019/submissions/4778304正三角形となるのは、全ての辺の長さが等しいときである。 なので、それを確かめればいい。 int A, B, C; //-----…

We Like AGC [AtCoder Beginner Contest 122 D]

https://atcoder.jp/contests/abc122/tasks/abc122_d 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc122/submissions/4712538条件を満たす文字列を良い文字列と呼ぶことにする。 dp[s] := 最後の3文字がsである良い文字列の組合せ 最初はdp["###…

GeT AC [AtCoder Beginner Contest 122 C]

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最初の考察が一番むずかしいと思うが、本題よりもう少し簡…

ATCoder [AtCoder Beginner Contest 122 B]

https://atcoder.jp/contests/abc122/tasks/abc122_b 解説 https://atcoder.jp/contests/abc122/submissions/4702739Sの長さがとても短いので、Sの部分文字列すべてについて考えることができる。 部分文字列S[L...R]について、ACGT文字列であるかを判定する…