atcoder.jp 解法 クエリの内容的にセグメント木を使いたくなる。 セグ木には、区間の文字がそれぞれ何個ずつあるかという情報を乗せたい。 文字列に関する問題でよくあるのは、英小文字が26文字しかないことを利用するパターンだ。 この問題も利用できる。 …

atcoder.jp 解法 香辛料の消費量は、整数以外も選択できるがどこかで調整すればすべて整数にすることができるので、最初から整数で考えてよい。 ナップザックDP感があるので、普通にDPするしようとすると、 dp[i][w] ← i番目までの料理を作った時、香辛料をw…

atcoder.jp 解法 ぱっと見、部分和問題かなと思うが、O(N2)になってしまうため間に合わない。 他の方法を考えてみると、 ・なぜか区間が与えられている ・Kが小さい ・区間は共通部分を持たない と怪しい部分がたくさんあることに気づく。 区間を利用して高…

セグメント木 セグメント木は、区間更新・区間上の最小値や和などをO(logn)で求めることができるデータ構造です。 セグメント木を理解するために役立つリソース かつっぱさんの動画です。説明が丁寧なのでわかりやすいです。 part1では、セグメント木の雰囲…

問題 nodeの値を保存しているだけではどの値がいつ更新されたモノなのかがわからないので、更新された時間も保持しておくことにする。 値を取得するときは、子から見ていって最新の更新時刻を持つnodeの値が現在の値になる。 管理する情報が増えただけで後は…

問題 RSQのコードを少し弄れば解ける。 具体的には、一点更新→一点取得、区間取得→区間更新、のように取得と更新の役割を逆転させる。 かつっぱさんの動画がわかりやすい。 実装 #include <bits/stdc++.h> using namespace std; struct RAQ_SegTree { int n; // 葉の数 vect</bits/stdc++.h>…

問題 RMQでは0-indexedだったのに、こっちは1-indexedになってて引っかかった。 RMQのコードを少し弄っただけです。 実装 何をやっているかはコメントに書いてあります。 #include <bits/stdc++.h> using namespace std; struct RSQ_SegTree { int n; // 葉の数 vector<long long> node</long></bits/stdc++.h>…

問題 RMQは、与えられた区間の最小値を求めるというもの。 セグメント木を使って解きます。 実装 セグメント木の実装の中で何をしているかはコメントに書いてあります。 AOJのテストケースはパスしましたが、バグが潜んでいるかもしれません。 #include <bits/stdc++.h> usi</bits/stdc++.h>…