【ABC153】F - Silver Fox vs Monster
解法
モンスターは昇順に並び替えておく。
一番初めのモンスターに爆弾を当てるには最大で、X[0] + D * 2 までの座標で使用する必要がある。
なるべく別のモンスターに当てたいので、ギリギリ倒せる座標で使用した方がいい。
これを全てのモンスターで繰り返す、貪欲法をすれば答えを出せる。
ただし、後のモンスターは前のモンスターを倒すために使った爆弾のダメージを受けている可能性があるため、うまく処理する必要がある。
なぜ貪欲できると分かるのか
端のモンスターを倒す時には、そのモンスターにギリギリ当たる座標で爆発させるのが効率がよく、それ以外の座標で爆発させて端のモンスターを倒すメリットがないため。
端のモンスターを倒した後は、その隣にいるモンスターが次の端のモンスターに変化すると考えられる。
よって、同じことを繰り返すことによって答えが出せる。
実装
座標圧縮＋いもす法みたいな感じで実装する。
モンスターの座標を挿入したmultisetを準備しておく。
爆弾の爆発範囲外の座標もmultisetに挿入し、爆発の蓄積ダメージの計算に使う。
爆弾を爆発させた時に蓄積ダメージとして、ダメージを追加しておき、爆発の範囲端で減らしておく。
これで前のモンスターを倒すために使った爆弾の影響ダメージを計算できる。
void solve(long long N, long long D, long long A, std::vector<long long> X, std::vector<long long> H){ multiset<pair<ll, ll>> st; REP (i, N) st.insert({X[i], H[i]}); // zahyo: 現在の座標 // damege: 蓄積ダメージ // ans: 答え ll zahyo = 0, damage = 0, ans = 0; auto iter = st.begin(); // イテレータ // 蓄積ダメージの計算に使用 // first: 爆弾の爆発範囲端の座標, second: 爆発ダメージ map<ll, ll> mp; while (iter != st.end()) { // st.second() // 爆弾の爆発範囲端の場合: -1, それ以外の場合モンスターのヘルス if ((*iter).second != -1) { // 現在の対象モンスターが射程のギリギリになるように爆弾を使用 zahyo = (*iter).first + D*2; // 爆弾の使用回数 ll cnt = max(0LL, myceil((*iter).second-damage, A)); ans += cnt; damage += A * cnt; // 蓄積ダメージを追加 mp[zahyo+1] = A * cnt; // first: 爆発範囲の範囲外の座標 st.insert({zahyo+1, -1}); } else { // 蓄積ダメージを減らす damage -= mp[(*iter).first]; } iter++; } cout << ans << endl; }
【ABC157】E - Simple String Queries
解法
クエリの内容的にセグメント木を使いたくなる。
セグ木には、区間の文字がそれぞれ何個ずつあるかという情報を乗せたい。
文字列に関する問題でよくあるのは、英小文字が26文字しかないことを利用するパターンだ。
この問題も利用できる。
具体的には、区間をマージするときに26回ループを回して、それぞれの文字が何個ずつあるかを足し合わせれば良い。
これで更新&探索をそれぞれO(logN)で行うことができる。
全体計算量はO(QlogN)になる。
実装
struct SegTree { int n; // 葉の数 vector<vector<int>> node; // 完全2分木 // 初期化 SegTree(string S) { int sz = S.size(); n = 1; while (n < sz) n *= 2; // 与えられた数列の項数以上の2^n個、葉を作る node.resize(n*2-1, vector<int>(26, 0)); // 0で初期化 for (int i = 0; i < sz; i++) node[n-1+i][S[i]-'a']++; for (int i = n-2; i >= 0; i--) { REP (j, 26) node[i][j] = node[i*2+1][j] + node[i*2+2][j]; } } // 更新 void update(int i, int co, int cn) { i += n-1; // 葉はn-1から始まる node[i][co]--; node[i][cn]++; while (i > 0) { // 親に更新を伝搬 i = (i-1)/2; // 親の添字 node[i][co]--; node[i][cn]++; } } // クエリ処理 // [s, t)を探す // 再帰的に探索するために呼び出す側を別の関数に void find(int s, int t, set<int> &ans) { find_query(s, t, 0, n, 0, ans); } void find_query(int s, int t, int l, int r, int n, set<int> &ans) { if (r <= s || t <= l) return; // 範囲外なら終了 // [s, t)が[l, r)を内包しているとき else if (s <= l && t >= r) { REP (i, 26) if (node[n][i]) ans.insert(i); } else { // (r+l)/2は区間の中心, 区間の中心を左端にするか、右端にするかで分岐する find_query(s, t, l, (r+l)/2, n*2+1, ans); // 左下の子を探索 find_query(s, t, (r+l)/2, r, n*2+2, ans); // 右下の子を探索 } } }; int main(){ ll N, Q; string S; cin >> N >> S >> Q; // セグ木 auto segtree = SegTree(S); REP (i, Q) { int q; cin >> q; if (q == 1) { int j; char c; cin >> j >> c; // 更新 segtree.update(j-1, S[j-1] - 'a', c - 'a'); S[j-1] = c; } else { int l, r; cin >> l >> r; set<int> ans; // 探索 segtree.find(l-1, r, ans); cout << ans.size() << endl; } } return 0; }
【C++】set, multisetに関するメモ
適当に追加していきます。
最大値の取り方
set<int> st; st.insert(1); st.insert(2); auto mx = st.rbegin(); // 最大値へのイテレータ cout << *mx << endl; // 2 st.erase(mx); // 最大値を削除する cout << *mx << endl; // 1
multisetで一つだけ要素を消去する
eraseにイテレータを渡すと一つだけ削除できます。
↓最大値を削除する
multiset<int> st; auto iter = st.rbegin(); st.erase(iter);
値を指定したい場合はfindを挟んでイテレータへ変換します。
multiset<int> st; int a = 10; // aを消去する st.erase(st.find(a));
【ABC142】E - Get Everything
解法
それぞれの鍵を買うか否かの選択をM回することになるので、愚直に全探索しようとするとO(2M)になるが、制約的に時間が足りない。
そこでDPができないかを考えてみる。
愚直解がO(2n)になってしまう時、DPを使うと無駄な計算を省いて高速化できることがよくある。
次のDPを考える。
dp[i][S] ← i番目までの鍵を見ていった時、既に開けることができる宝箱の集合S
状態として、既に開けることができる宝箱の集合を持つ必要がある。
集合を状態として持つDPは、bitDPと呼ばれる。
なぜbitなのかというと、集合に含まれているかどうかを2進数で表現するから。
下からi番目のbitが1であるとき、集合にiが含まれていることを表す。
DPは次のように遷移する。
- i番目の鍵を買わない時
- dp[i + 1][S] ← min(dp[i + 1][S], dp[i][S])
- i番目の鍵を買う時 (xをi番目の鍵で開けることができる宝箱の集合とする)
- dp[i + 1][S ∪ x] ← min(dp[i + 1][S ∪ x], dp[i][S] + a[i])
初期状態では、どの宝箱も開けることができないので、
dp[0][0] ← 0
それ以外 ← INF
とする。
そして、全ての宝箱を開ける必要があるので、 答えはdp[M][2N-1]になる。
実装
C++だと2Nは、1<<Nで表すことができる。
int main(){ int N, M; cin >> N >> M; vector<ll> a(M), b(M); vector<vector<ll>> c(M); REP (i, M) { cin >> a[i] >> b[i]; c[i].resize(b[i]); REP (j, b[i]) cin >> c[i][j]; } // dpテーブル vector<vector<ll>> dp(M+1, vector<ll>((1 << N), INF)); dp[0][0] = 0; REP (i, M) { REP (j, (1 << N)) { // i番目の鍵を買わない場合 chmin(dp[i+1][j], dp[i][j]); ll x = j; REP (k, b[i]) { // c[i][k]を集合xに含める(既に含まれている場合、何もしない) x |= (1 << (c[i][k]-1)); } // i番目の鍵を買う場合 chmin(dp[i+1][x], dp[i][j] + a[i]); } } cout << (dp[M][(1<<N)-1] == INF ? -1 : dp[M][(1<<N)-1]) << endl; return 0; }
【ABC217】E - Sorting Queries
解法
クエリ1とクエリ2だけだった場合、queueを使うだけで解けるのでとても簡単。
ただ、クエリ3が与えられるたびにソートしていると、全体計算量O(N2 logN)になって間に合わない。
上記のように、クエリ1とクエリ2はqueueで実現できるので、問題はクエリ3のソートをどうするかという点である。
そこで、挿入時に数の大小によって並び替えられるデータ構造を使うというアイデアが思い浮かぶ。
C++だと、std::setとかstd::priority_queueが使える。
今回はpriority_queueを使うことにする。
priority_queueは、デフォルトだと降順に並び替えられるので昇順に設定し直しておくこと。
具体的には、次のような操作をする。
- クエリ1
- queueにxを追加する
- クエリ2
- priority_queueが空でない場合、priority_queueから一つ取り出して出力する
- priority_queueが空の場合、queueから一つ取り出して出力する
- クエリ3
- queueに入っている数を全て取り出し、priority_queueに入れ替える
priority_queueへの挿入、取り出しはO(logN)であるため、全体でO(NlogN)の計算量になり間に合う。
priority_queueで実装
priority_queueは降順になるようにしておきましょう。
int main(){ ll Q; cin >> Q; queue<ll> que; // 降順にしておくこと priority_queue<ll, vector<ll>, greater<ll>> heapq; REP (i, Q) { ll t; cin >> t; if (t == 1) { // クエリ1 ll x; cin >> x; que.push(x); } else if (t == 2) { // クエリ2 if (!heapq.empty()) { c(heapq.top()); // priority_queueで最小の数を出力 heapq.pop(); } else { c(que.front()); que.pop(); } } else { // クエリ3 while (!que.empty()) { // priority_queueからqueueに移し替え heapq.push(que.front()); que.pop(); } } } return 0; }
multisetで実装
コンテスト本番はmultisetを使って実装しました。
priority_queueを使う方が楽なのは、コンテスト終了後に気付きました。
multisetから要素を削除するときに、値を渡してしまうと同じ値の要素が複数消去されてしまうので注意。
一個だけ消したい時はイテレータを渡します。
↓参照
この仕様は知っていたのですが1WAしてしまいました。
int main(){ ll Q; cin >> Q; queue<ll> que; multiset<ll> st; ll cnt = 0; // multiset内の要素数 REP (i, Q) { ll t; cin >> t; if (t == 1) { ll x; cin >> x; que.push(x); } else if (t == 2) { if (cnt) { c(*st.begin()); // 一番小さい数を出力 st.erase(st.begin()); // 一番小さい数を消去 cnt--; } else { c(que.front()); que.pop(); } } else { while (!que.empty()) { // 移し替え st.insert(que.front()); que.pop(); cnt++; } } } return 0; }
感想
コンテスト終了後に気づいたけど、問題タイトルが凄いヒントになってますね。
次からはタイトルも見ておくことにします。
【ABC217】D - Cutting Woods
木を切る問題が出ると二分探索を思い出す。
解法
データ構造に切断点の位置を挿入しながら、二分探索をする。
二分探索をして、切断点の左端と右端がどこかを高速に調べることができる。
二分探索をするにはソートされている必要があるので、挿入時に数字の大小によって順序が保たれるデータ構造が必要になる。
C++だと、std::setが使える。
実装
最初に0とLを挿入しておくといい気がする。
答えは、右端-左端になる。
std::setを使う場合は、std::lower_bound()を使うとO(N)になってしまうことに注意する。
void solve(long long L, long long Q, std::vector<long long> c, std::vector<long long> x) { set<ll> st; st.insert(0); st.insert(L); REP (i, Q) { if (c[i] == 1) { st.insert(x[i]); } else { auto iter = st.lower_bound(x[i]); // 二分探索 ll right = *iter; // 右端 --iter; ll left = *iter; // 左端 cout << right - left << endl; } } }
【ABC190】F - Shift and Inversions
解法
k=0の時は元の数列のまま、転倒数を求めればよい。
愚直に求めようとするとO(N2)になるが、BITを使うとO(NlogN)で求めることができる。
具体的には、下の記事がわかりやすい。
あとはk=1~N-1の時を考えればよいが、k=iからk=i+1に変化するとき、
1、先頭のa[i]が削除される
2、Aの末尾にa[i]が追加される
という2つの操作が行われる。
操作1によって、転倒数はa[i]だけ減る。
また、操作2によって、転倒数はN-a[i]-1だけ増える。
これで、O(1)で転倒数の変化を求めることができた。
実装
struct BIT { int n; vector<ll> bit; BIT(int n_) : n(n_ + 1), bit(n, 0) {} void add(int i, ll x) { for (int idx = i; idx < n; idx += (idx & -idx)) { bit[idx] += x; } } ll sum(int i) { ll s = 0; for (int idx = i; idx > 0; idx -= (idx & -idx)) { s += bit[idx]; } return s; } }; void solve(long long N, std::vector<long long> a){ auto tree = BIT(N); ll cnt = 0; // 転倒数 REP (i, N) { cnt += i-tree.sum(a[i]+1); tree.add(a[i]+1, 1); } c(cnt) REP (i, N-1) { cnt += N - a[i] - 1; cnt -= a[i]; c(cnt) } }
