2022-04-12

回文検出(DP)

アルゴリズム競プロ

回文検出は、以下の記事で書いたManacherのアルゴリズムを使えば $O(N)$ で解けるが、 $O(N^2)$ かければDPでも解くことが出来る。
DPの方が遅いが、コード的にはかなりシンプルに書けるのでメモしておく。

klee.hatenablog.jp
個人的にはManacherは偶数長の時とか、探索範囲の記述でバグを埋めそうで怖い。(ライブラリ化してるからよっぽど問題はないが)

どう解くか

以下のような2次元配列でDP配列の状態を定義する。

$dp[l][r]=s[l]+s[l+1]+...+s[r]$ が回文か?
このDPテーブルを以下のルールに従って埋めていく。

$i=j$ の時

必ず $s[i]==s[j]$ なので $dp[i][j]=true;$

$j-i=1$ の時

$s[i]==s[j]$ の時、 $dp[i][j]=true;$

$j-i>=2$ の時

まず $s[i]==s[j]$ である必要がある。ただし、この条件だけでは不十分で、これに加えて一個内側の部分文字列が回文であれば良い。
これは $A="abcba"$ と $B="abcca"$ の $l=0,r=4$ をそれぞれ考えればわかるが、 $B$ では明らかに内側である $l=1,r=3=>"bcc"$ が回文ではないので $l=0,r=4$ も回文にならないが、 $A$ は問題ない。
遷移の計算時、 $dp[i][j]$ の更新のためには $dp[i+1][j-1]$ が必要になるので、 $i$ は逆順で探索する必要があることに注意する。

実装

#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n, s) for (int i = (s); i < (n); i++)
#define rrep(i, n) for (int i = (n - 1); i >= 0; i--)
#define rreps(i, n, s) for (int i = s; i >= n; i--)

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int max_len = 0;
    int l, r;
    rrep(i, n) {//逆順
        reps(j, n, i) {
            if (j - i <= 1) {
                dp[i][j] = (s[i] == s[j]);
            } else {
                dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j]);
            }
            if (dp[i][j] && max_len < j - i + 1) {
                max_len = j - i + 1;
                l = i;
                r = j;
            }
        }
    }
    string res = s.substr(l, r - l + 1);
    cout << res << endl;
    return 0;
}

簡単で安心。
計算量が許せばこっちを書きたい。

2022-04-10

C++の順序付多重集合について

C++ 競プロ

最近multisetを使うと簡単に解ける問題がちょくちょくAtCoderで出題されて解けなかったりしたので、簡単にC++のmultisetについてまとめる。

C++のmultisetとは

順序付多重集合、つまり順序を保持しつつ要素の重複を許容した集合を効率的に管理するためのデータ構造であり、以下の操作を $O(logN)$ で行うことができる。

insert
erase
find
lower_bound
upper_bound
count

更に詳しくは以下。
vivi.dyndns.org

※注意その1

lower_bound,upper_bound等はstd::lower_bound,std::upper_boundを使うと $O(N)$ となってしまう罠があるため、multisetに定義されたものを使うこと。
詳しくは以下。
betrue12.hateblo.jp

※注意その2

multiset内の要素を削除するとき、s.erase(v);のように書くとs内のvが全て削除される。一つだけ削除したい場合はiteratorを指定してやる必要があり、例えば以下のように書けば良い。

auto itr = s.find(v);
s.erase(itr);

典型的な問題

要素を更新しつつ2分探索をする必要がある問題などで有効な場合があり、例えばこの問題なんかは典型的。
atcoder.jp
この問題は、以下の手続きで解くことができる。

色グループ毎の値を保持するデータ構造を定義する
右から順に要素を見ていく
既存の色グループの中で、最小値が今着目している値より大きいものがあるか？
1. YES→該当する色グループに加える
2. No→新たな色グループを作る
全ての要素を見終わった時点で存在している色グループの数が答え

ここで、処理3に着目したとき色グループ毎に全ての値を保持する必要はなく、ある色グループに値を加えられるかどうかはあくまで最小値のみが関係することがわかる。
よって、各色グループの最小値のみを保持し、今着目している値より大きい最小値を持つグループがあるかどうかを高速に判定できれば良い。
この処理はmultisetのupper_boundで $O(logN)$ で実現できる。よって要素を見ていく計算量と合わせて全体で $O(NlogN)$ で解くことができた。

実装

#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n, s) for (int i = (s); i < (n); i++)
#define rrep(i, n) for (int i = (n - 1); i >= 0; i--)
#define rreps(i, n, s) for (int i = s; i >= n; i--)

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    multiset<ll> s;
    for (int i = n - 1; i >= 0; i--) {
        auto it = s.upper_bound(a[i]);
        if (it != s.end()) { s.erase(it); }
        s.insert(a[i]);
    }
    cout << s.size() << endl;
    return 0;
}

類題

以下の問題は最小値ではなくk番目の値だが、同様にmultisetで解ける。
atcoder.jp

2022-02-08

入門監視第Ⅰ部を読んだ

読書記録 DevOps

チームで自律的に開発を進められる体制を作るためには、DevだけではなくOpsのスキルも身につけて、チーム単位で所謂DevOps的な動きができることが重要になってくる。自分の働くスタートアップのような小規模の会社だと、分業するのがそもそもリソース的に難しいという事情もあるが。

そんなわけで、あまりこれまで勉強してこなかったOps周りの知識を最近勉強中であり、その一環で監視に関する下記書籍を読み進めているので備忘録として自分の理解をまとめていく。

www.oreilly.co.jp

要約

1章監視のアンチパターン

この章では陥りがちな5つのアンチパターンが紹介されている。

1. ツール依存

自分たちの会社の状況にあうツールを都度選ぶべきであり、あるツールを使う前提で問題に対処するのは良い結果に繋がらない。例えば、他社事例で上手くいったツールや構成を踏襲して自社のシステムを構築したとしても、自社の解決したい問題などの背景の違いによって上手くいかないケースは往々にしてある。なので、自社の課題を正しく認識してそれに合うツールを選択すべき。
また、必要であればツールを増やすことを恐れないことも重要。ツールが増えて認知コストが上がることよりも、目的に沿わない統合的なツールを使う場合の方が不利益を生む傾向にある。(ここはトレードオフだと思うのでどの辺が分岐点かは判断する必要がありそう。)

2. 役割としての監視

専任の監視ロールを作って集中できるようにすることは、一見良さそうに思える。しかし、完全にDevとOpsを分断するような専任チームを作ってしまうと監視責任者はよく知らないアプリケーションの監視を管理運用するということになり、それはあまり上手くいかない。監視とは役割ではなくスキルであるという認識をして、チーム内の全員が一定のレベルに達していることが重要。

3. チェックボックス監視

メトリクスを見ること＝監視ではない。例えば、CPU使用率がコンスタントに99%であろうとリクエストが無事に捌けているのであれば問題はない。動いている、ないしはユーザに問題なく価値提供できているとはどういう状態なのかを正しく認識し、そのためのメトリクスが設計できていることが重要。

4. 監視を支えにする

監視はあくまで通知であり、問題を修正するわけではない。障害が起きた場合は、それに関する問題の修正が可能かどうか検討する必要がある。ひどいコードを監視でなんとかしようと思ってはいけない。

5.手動設定

監視の設定にかける時間は監視自体にかけるよりも長い時間を要するので、より良い監視システムを目指すのであれば監視の設定は全て自動化すべき。

2章監視のデザインパターン

この章では4つのデザインパターンが紹介されている。

1. 組み合わせ可能な監視

モノリシックな統合されたツールを使うよりも、専門的なツールを組み合わせて監視の仕組みを作る。組み合わせを考えるにあたって監視を構成する要素を下記の5つに分解して考える。
■データ収集
どう集めるかという観点ではプッシュとプル型が存在し、プッシュ型の方がポーリングをする中央サーバが不要であり、分散アーキテクチャでのスケール性は良いというのが筆者の経験則だが場合によるだろう。
何を集めるかという観点ではメトリクスとログが存在する。さらにメトリクスも、カウンタとゲージに分解される。カウンタは単調増加する計数量であり、例えば1日のリクエスト回数のようなもの。ゲージはある時点での瞬時値であり、例えば車の速度系の値などであり、過去の履歴の情報などを単体では含まない点に注意する必要がある。
ログは、連続した文字列でありJSONのような構造化されたものもあれば、非構造化された単なる文字列のものもある。構造化ログの方がログ単体での解釈が容易であり、可能ならば構造化ログを使う。しかし、ログの用途が人間が読むだけで、システムにパースする必要などがない場合は非構造化ログの方が楽なケースもある。

■データストレージ
データの種類に応じて適切な場所へ保存する。時系列データはTSDB(RRDやGraphiteのWhisperなど)に入れる。高度な検索をしたい場合などには、ElasticSearchなどの検索エンジンへ格納する。

■可視化
GraphanaやSmashingのようなダッシュボード製品やフレームワークを活用する。最高のダッシュボードは1つのサービス、あるいは1つのプロダクトのステータスを表示することに焦点を絞ったものであり、サービスを最もよく理解している人によって管理運用されるべき。

■分析とレポート
監視データの種類によっては分析レポートが必要となる。例えばSLAのレポーティングなどである。SLAのレポーティング時はメトリクスのサンプリング周期などに注意する。

■アラート
監視の目的はアラートを出すこと自体ではなく、アラートによって質問を投げかけることにある。(どう行動すべきかというインシデント対応フローまでセットにする必要があること？)

2. ユーザ視点での監視

まず監視を追加すべきなのは、ユーザとアプリケーションのやりとりが発生する箇所。シンプルな方法ではHTTPレスポンスコード(特に5xx番台)を使う。ただし、これによって何か問題が起きていることは分かるが、何が原因で問題が起きていることまでは分からないため、シンプルな方法を足掛かりにして広げて行くことが重要。

3. 作るのではなく買う

SaaSサービスを利用することで監視の仕組みをすぐに立ち上げることができる。多くの企業はSaaS->FOSS(Graphite,Prometheusなど)->独自プラットフォームという変遷を辿る傾向にあるが、最初の5年は少なくともSaaSサービスで十分だろう。

4. 継続的改善

組織の成熟度や規模の変化に応じて適切な監視要件は変化する。継続的に改善しよう。

3章アラート、オンコール、インシデント管理

この章ではより良いアラートを作るためのヒントや運用体制について述べられている。

どうしたらアラートをよくできるか

アラートの内容に応じて適切な場所に送ることが重要。アラートはすぐに応答が必要なのであればPagerDutyなどに送る。すぐにアクションが不要ならチャットなどに送る。また、アラートには対象サービスへの手順書リンクを貼っておくことで対応フローが明確化できるが、手順書に書かれている作業を行うだけのフローになっている場合はそもそも自動化を検討すべき。
その他には、前述されているようにそもそもアプリケーションを改善することや適切なメトリクスを用いることなども重要である。

オンコール

オンコール対応は多大にストレスがかかるため、ローテーションすべき。また、アラートをチューニングするための動きとして、オンコール担当が前日のアラート一覧から各アラートが改善、または削除できないかを定期的に検討すると良い。また、オンコールの際に収集した情報を元に次のスプリントでアプリケーション自体の安定性向上計画を組むことも有効。その他にも、PagerDutyなどのツールを使ってエスカレーションパス構築などのオンコールの仕組みを補強すると良い。

インシデント管理

発生した問題を扱う手順についての紹介。インシデント発生時には、例えば以下のような役割に分かれて対応するフローを組むと良い。
■現場指揮官
直接的に調査にはかかわらず監督する役割。
■スクライブ
誰がいつ何をやったかなどを記録する、書記のような役割。
■コミュニケーション調整役
ステークホルダーと最新状況を都度共有する。
■SME
実際に手を動かして調査する人。

PagerDutyのドキュメントは参考になるので読むと良い。
response.pagerduty.com

感想

アンチパターンは、どれも「そうですね」という感じではあるが人間は慣れると思考をショートカットしてしまう傾向にあるのでこういったパターンがあるということをしっかり認識しておくことは重要。
デザインパターンについては、5つのコンポーネントに分割してプラットフォーム構成を考えるという観点は無かったので勉強になった。

2021-08-29

Pair of Balls(ABC216D)

競プロアルゴリズム

本番中に解けずに泣いた。
WAを出しまくったので自戒を込めて書く。
atcoder.jp

考察

愚直に上からペアになった石を取っていけば良いか？山の数的に探索が間に合わなさそう。(解説を見ると上手くやると間に合うらしい...)
各山を見て行った時に、特定の数字の深さの大小関係が保存されていれば全部の石を取れそう->実装しよう。
深さの大小関係が保存されているというのがどういうことかというと、例えば下記のような山が3つあるとき、1個目の山の2->4->1に着目した時、それらの要素は2つ目の山中でも(5)->2->4->(3)->1となっており深さの大小関係が等しい。

2 4 1
5 2 4 3 1
5 3

逆にこれが下記のようになっている場合、2つ目の山は(5)->4->2->(3)->1となっているので、1つ目の山の要素の深さの大小関係と矛盾する。こういうときはどう頑張っても取れない。
よって、これを実装していけば良い。

2 4 1
5 4 2 3 1
5 3

実装

各玉は2個ずつしかないので、入力を取るときにhashmapで各玉の各個体の所属する深さをメモしておく。

    map<int, vector<pair<int, int>>> memo;
    rep(i, m) {
        int k;
        cin >> k;
        rep(j, k) {
            int v;
            cin >> v;
            c[i].pb(v);
            memo[v].pb({i, j + 1});
        }
    }

そして、順に山を見ていき、他方の玉の所属する山と深さをメモしつつ、深さの大小関係が崩れた場合に答えを"No"にしておけば良い。

 rep(i, m) {
        map<int, int> d;
        for (int v : c[i]) {
            if (memo[v][0].first == i) {
                int idx = memo[v][1].first;
                int depth = memo[v][1].second;
                if (d[idx] > depth) { res = "No"; }
                d[idx] = depth;
            }
        }
    }

ただ、この実装ではエッジケースが残る。（本番中にこれが解消できなかった....。）
例えば同じ山に同じ玉が所属している場合はどう足掻いても玉を取りきれない。
よって、これをチェックすればおしまい。

    for (auto v : memo) {
        if (v.second[0].first == v.second[1].first) res = "No";
    }

反省

最初に問題文を雑に読んでしまい、隣接した2つの山からのみ玉が取れると勘違いしたのが本当に良くない....。
問題文をよく読みましょう。

2021-05-11

マンハッタン距離の変換(典型36 Max Manhattan Distance)

アルゴリズム競プロ

典型90問楽しい。

前にも似た問題を解いた記憶があったので、45度変換 $(x,y)=>(x-y,x+y)$ を使ってすんなり解けたが、そういえばなんでその原理で解けるのか記憶が薄れていたので復習がてらまとめておく。

マンハッタン距離からチェビシェフ距離への変換

２次元座標系の2点 $(x_a,y_a),(x_b,y_b)$ を考える。
このときマンハッタン距離は下記の式で表される。

$D_{manhattan}=|x_a-x_b|+|y_a-y_b|$
この時、絶対値を取る演算が
$|v|=max(-v,v)$
のように、最大値を取る演算で置き換えられることを用いると、 $D_{manhattan}$ は以下のように変形できる。
$\begin{align} D_{manhattan}=max(x_a-x_b+y_a-y_b,x_a-x_b-(y_a-y_b),-(x_a-x_b)+y_a-y_b,-(x_a-x_b)-(y_a-y_b)) \end{align}$
更にこの式を、点a,bそれぞれ毎の変数でまとめると以下のようになる。
$\begin{align} D_{manhattan}&=max(x_a+y_a-(x_b+y_b),x_a-y_a-(x_b-y_b),-(x_a-y_a)+(x_b-y_b),-(x_a+y_a+(x_b+y_b)) \end{align}$
このようにまとめると、 $x+y,x-y$ で式全体が構成されていることがわかる。
この時 $x'=x-y,y'=x+y$ とおき、先程の式に代入してみると
$\begin{align} D_{manhattan}&=max(y'_a-y'_b,x'_a-x'_b,-x'_a+x'_b,-y'_a+y'_b)\\ &=max(|x'_a-x'_b|,|y'_a-y'_b|) \end{align}$
となる。このように変形することで、x軸の絶対値とy軸の絶対値をそれぞれ独立に計算し、その最大値を取れば良いという演算になり、問題によってはかなり有用な性質となる。
また、このように軸毎の距離の最大値を取るような距離尺度のことをチェビシェフ距離と呼ぶ。（チェスの動かし方のアレ）
ja.wikipedia.org

典型36での応用

今回の典型問題36を通常のマンハッタン距離の演算式で解こうとすると、
2点の全組み合わせについて $D_{manhattan}$ を計算する必要があり $O(N^2)$ となり間に合わない。
そこで先程のような座標変形 $x'=x-y,y'=x+y$ を行う。すると、ある点から見て各軸毎の最も遠い点が分かればあとはその最大を取れば良いことが分かる。
更に、最も遠い点は必ず各軸の両端のいずれかになる。よって、事前に $N$ 個の点の中でのx軸方向での最小、最大値、y軸方向での最小、最大値さえ求めておけば、ある点から見て最も遠い点の探索自体は下記の式で $O(1)$ で解ける。

$\begin{align} D_{max}=max(|x'-x'_{max}|,|x'-x'_{min}|,|y'-y'_{max}|,|y'-y'_{min}|) \end{align})$
よって、この問題は事前準備の最小、最大値の探索に $O(N)$ かかるので、全体 $O(N)$ で解ける。(正確には $N,Q$ のうち小さい方に依存するので $O(min(N,Q))$ ???記法がわからない...)

実装

#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n, s) for (int i = (s); i < (n); i++)
#define rrep(i, n) for (int i = (n - 1); i >= 0; i--)
#define rreps(i, n, s) for (int i = s; i >= n; i--)

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, q;
    cin >> n >> q;
    vector<ll> xs(n), ys(n);
    rep(i, n) {
        ll x, y;
        cin >> x >> y;
        xs[i] = x - y;
        ys[i] = x + y;
    }
    ll min_x = *min_element(xs.begin(), xs.end());
    ll max_x = *max_element(xs.begin(), xs.end());
    ll min_y = *min_element(ys.begin(), ys.end());
    ll max_y = *max_element(ys.begin(), ys.end());
    rep(i, q) {
        int j;
        cin >> j;
        j--;
        ll res = max(max(abs(xs[j] - min_x), abs(xs[j] - max_x)), max(abs(ys[j] - min_y), abs(ys[j] - max_y)));
        cout << res << endl;
    }
    return 0;
}

2021-01-19

AtCoder用のRustテンプレートを作った

競プロ Rust

Rustの勉強を最近初めた。
準備運動代わりにAtCoderの問題を解いたりすることがあるのだが、自分にとって使い勝手の良いtemplateが見当たらなかった。
というわけで作ってみた。

github.com

コンテスト用に1プロジェクトで5ファイルのbinを生成(a〜f.rs)
vscode用に整理しており各ファイル毎にF5でbuild->debug可能

使い方

$ cargo generate --git https://github.com/kashee337/rust_atcoder_template.git

参考

Cargo.tomlのdependencyでAtCoderで使えるクレートについては下記のrepositryを参考にさせていただいた。
github.com

ぼちぼちやってく

2021-01-11

座表圧縮 (ABC188D)

競プロアルゴリズム

昨日のABC188、Dが解けず３完だった。

atcoder.jp

いもす法と座表圧縮かなと思いつつ、座標圧縮への理解が曖昧だった＋本番の焦りもありACできなかった。
最近なんとなく解法が浮かぶのは成長だなと思いつつも、あと一歩詰めきれないところが甘いので書いていく。

座標圧縮

座標圧縮とはある数列に対して位置関係や大小関係などを保存しつつ、より小さい数値で表現し直す手法。
例えば、 $30,100000,500000,2$ という数列に対して大小関係を保持しつつ数値変換を行うと $2,3,4,1$ のように表現できる。
この時、当然スケールの情報は失われるが位置関係や大小関係が重要な問題などでは有効な場合がある。

どう適用するか

今回のABC188 Dは区間の問題である。問題文から、imos法を知っていれば明らかにそれ(いもす法で解くやつ)だなとわかる。
ただし、今回はありうる区間の座標が1e9のため、そのままではシミュレートができない。
そこで座標圧縮で区間の位置関係を保持しつつ小さい値へ変換を行う。
具体的には、あり得る座標群を取得し、それに対して昇順でindexを付ければ良い。
C++ならば例えば下記のように実現できる。

/* a,bは区間の始点終点を保持したvector */
//あり得る座標群を重複なしで取得
set<int> day_set;
rep(i, n) {
    day_set.insert(a[i]);
    day_set.insert(b[i]+1); // いもす法用に+1しておく
}
//座標群を昇順にsort
vector<int> day_list(day_set.begin(), day_set.end());
sort(day_list.begin(), day_list.end());
//この時点でday_listに保持された順序が圧縮後の座標になる

これで座標圧縮できたが、いもす法を行うために実座標->圧縮座標への変換用のhash mapを持っておくと便利なので作っておく。

//実座標->圧縮座標への変換hash mapを作る
map<int, int> real2comp;
rep(i, L) { real2comp[day_list[i]] = i; }

これで前準備ができたので、いもす法を行なっていく

vector<long long> dp(L + 1, 0);
//メモ
rep(i, n) {
    dp[real2comp[a[i]]] += c[i];
    dp[real2comp[b[i]+1]] -= c[i];
}
//シミュレート
rep(i, L) { dp[i + 1] += dp[i]; }

最終的に計算すべき料金は期間を通しての合計料金なので、実座標での期間を考慮しつつ加算していけばok

// 元座標の区間長さを考慮しながら加算していく
long long res = 0;
rep(i, L - 1) { res += (day_list[i + 1] - day_list[i]) * min(C, dp[i]); } //prime料金Cとdp[i]の低いほうを選ぶのが最適

全コード

#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n, s) for (int i = (s); i < (n); i++)
#define rrep(i, n) for (int i = (n - 1); i >= 0; i--)
#define rreps(i, n, s) for (int i = s; i >= n; i--)

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, C;
    cin >> n >> C;
    vector<ll> a(n), b(n), c(n);
    rep(i, n) {
        cin >> a[i] >> b[i] >> c[i];
        b[i] += 1;  //いもす法での立ち下がり点
    }

    //あり得る座標群を重複なしで取得
    set<ll> day_set;
    rep(i, n) {
        day_set.insert(a[i]);
        day_set.insert(b[i]);
    }
    //座標群を昇順にsort
    vector<ll> day_list(day_set.begin(), day_set.end());
    sort(day_list.begin(), day_list.end());
    ll L = day_list.size();  //座標圧縮後の座標の長さ

    //実座標->圧縮座標への変換hash mapを作る
    map<ll, ll> real2comp;
    rep(i, L) { real2comp[day_list[i]] = i; }

    //圧縮後の座標でいもす法をやっていく
    vector<ll> dp(L + 1, 0);
    //メモ
    rep(i, n) {
        dp[real2comp[a[i]]] += c[i];
        dp[real2comp[b[i]]] -= c[i];
    }
    //シミュレート
    rep(i, L) { dp[i + 1] += dp[i]; }

    // 元座標の区間長さを考慮しながら加算していく
    ll res = 0;
    rep(i, L - 1) { res += (day_list[i + 1] - day_list[i]) * min(C, dp[i]); }

    cout << res << endl;

    return 0;
}

おまけ

今回の問題に関しては解説における解のように、sort＋変化点だけに着目して前から見てく方式の方がコード自体はシンプル。

#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n, s) for (int i = (s); i < (n); i++)
#define rrep(i, n) for (int i = (n - 1); i >= 0; i--)
#define rreps(i, n, s) for (int i = s; i >= n; i--)

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, C;
    cin >> n >> C;

    vector<pair<ll, ll>> event;

    rep(i, n) {
        ll a, b, c;
        cin >> a >> b >> c;
        event.pb({a, c});
        event.pb({b + 1, -c});
    }
    sort(event.begin(), event.end());

    ll res = 0, t = 0, fee = 0;
    for (auto v : event) {
        if (v.first != t) {
            res += min(C, fee) * (v.first - t);
            t = v.first;
        }
        fee += v.second;
    }

    cout << res << endl;
    return 0;
}