ABC014-C 備忘録 p.47

itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。

C - AtColor

考察の流れ

imos 法か？

適当な配列（例えば table[10^6] ）を用意して、取得のたびに table[a_i]++;  table[b_i+1]--; していく

入力例1 の場合、すべてのアンケート情報をまとめると下記のようになる
　table[0] = 1
　table[1] = 0
　table[2] = 2
　table[3] = -1
　table[4] = -1
　table[5] = 0
　table[6] = 0
　table[7] = -1

累積和をとる！

#include <stdio.h>
#define MAX(x,y)	((x)>(y)?(x):(y))
int main(){
	int n, a, b, table[1000001]={0}, sum[1000001]={0}, maxb=0, ans;
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d%d",&a,&b);
		table[a  ]++;
		table[b+1]--;
		maxb = MAX(maxb, b);
	}
	for(int i=0; i<=maxb+1; i++){
		if(i>0){ sum[i] = sum[i-1] + table[i-1]; }
		ans = MAX(ans, sum[i]);
	}
	printf("%d\n",ans);
	return 0;
}

まとめ

・imos 法の存在はなんとなく知っていたが、実装するのはこれが初めて（記事は前後しています）
・次元の拡張については未理解
・昔の問題とはいえ、初水色 AC は感慨深い

引き続き、のんびり精進します。

#備忘録 #AtCoder #ABC #プログラミング #競プロ #C言語 #imos法 #累積和