読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

Codeforces #361 (Div.2) D. Friends and Subsequences

問題 問題概要 [l, r]の区間を考えた時に, al, .. , ar の最大値と bl, .. , br の最小値が一致する区間の総数を求める. 解法 区間の左端を固定して, 右端を伸ばしていくと, aの最大値は単調増加, bの最小値は単調減少していくので, 区間を伸ばしていくとど…

ARC 045 B - ドキドキデート大作戦高橋君

問題 問題概要 N人の人がM個の教室を掃除する. 一人が掃除する連続区間の教室が与えられる. ひとつの教室につき一人以上が掃除をしていればいい. どの区間を掃除する人はさぼることができるか. さぼる人は 同時に1人として考える. 解法 まずimos法を利用して…

ARC 033 C - データ構造

問題 問題概要 タイプ 1 : S に数 X を追加する。 タイプ 2 : S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する。 この2つを高速に行うことができるデータ構造を使えばよい。 解法 今回の問題は、Xがあまり大きくない。よって、バ…

ABC 032 C - 列

問題 問題概要 省略 解法 しゃくとり法をやるだけなんだけど、すぐにうまくできない。 ミス 尺取り法バグらしまくってうまくできない。 コード 尺取り法 #include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #de</algorithm></vector></set></cstdio></iostream>…

yukicoder No.151 セグメントフィッシング

問題 問題概要 省略。 解法 区間に値を足して、区間の和がわかればいいので、segtree使えばいいぽい。けど、 魚を加えるO(1) 区間の数を数得るO(n) 1マスずらすO(n) よって、O(q * n)でできる。ギリ通るかも。 ミス 平衡二分探索木の練習だったけど、スライ…

yukicoder No.59 鉄道の旅

問題 問題概要 区間の和と1つの要素に値を加算減算を拘束にできればいい. 解法 BITを使った. BITは -区間の和 -1つ要素に値を加える ことができるデータ構造. 今回の問題では積荷をBITで管理した. w>0の時はw以上の重さのものがk個より少なければ、その積荷…

天下一プログラマーコンテスト2016予選B D - 天下一数列にクエリを投げます

問題 問題概要 区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。 解法 segtreeぽいな感はある。90度回転させてみるのは思いつかない。 解法は公式解説がわかりやすい。 https://tenka1-2016-qualb.contest.atcoder.…

yukicoder No.230 Splarraay スプラレェーイ

問題 問題概要 区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。 解法 この問題とほぼ同じことをするだけ. mmxsrup.hatenablog.com 変更するのは以下の3点 (1)遅延情報の適用方法 -segは区間におけるAとBの色の数を…

yukicoder No.318 学学学学学

問題 問題概要 区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。 解法 さっぱりわからなかった。蟻本に書いてある、segtreeで範囲に対する最小値を求めるRMQは変更する値が1つなので、値を変更するのに(logn)で済む…