zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC127-C「Prison」です。
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
// min_Rの初期値はRとして取りうる最大値10^5に+1しておいたものに設定
int N=0, M=0, L=0, R=0, max_L=0, min_R=pow(10,5)+1;
int main(){
cin >> N >> M;
rep(m, M){
cin >> L >> R;
// 左側の最大値
max_L = max(max_L, L);
// 右側の最大値
min_R = min(min_R, R);
}
// 共通部分が無い場合は引き算の結果が負になるので0とのmaxをとる
cout << max(0, min_R - max_L + 1) << endl;
}ポイント
今回おさえるべき内容
共通部分の抽出方法をおさえる
共通部分を求めるという頻出問題です。一次元の共通部分は，各領域の「左端の最大値」と「右端の最小値」の区間幅を出力すればOKです。注意するべきなのは，共通部分が無い場合に区間幅が負になってしまう点です。ですので，最終的な出力は0とのmaxをとってあげればOKです。
コメント