リンク

http://arc014.contest.atcoder.jp/tasks/arc014_4

問題概要

n項の数列{L_i}とm個のクエリ(x_j,y_j)が与えられる。各jについて、区間集合{[L_i-x_j, L_i+x_j]}のunionの被覆する格子点の個数を求めよ。

制約

1<=L_i<=10^9
n<=10^5, m<=10^5, {L_i}は昇順

解き方

L_1の前と、L_nの後は自明で、\min(L_1-1, x_j), \min(all-L_n, y_j). 残りの間隔について考える。間がw個あいているとき、一律に\min(x_j+y_j, w)個が計上される。覆う区間の幅が全部同じため、これは他の間隔の影響を受けない。
\min(x_j+y_j, w)をwのグラフとしてみると、w=x_j+y_jで折れ曲がっている折れ線グラフになっている。折れ線のどちらの領域にいくつの間隔が属するかがわかれば和を計算できる。これはwをソートしておいて、にぶたんすればよい。min値がwの領域に属する間隔がt個ならば、和は(x_j+y_j)(n-1-t)+(t個のwの和)となる。これにnと、最初のmin2個を足せば答えが出る。
intを超える可能性がある事に注意。

いろいろ

C問題として出したつもりがD問題になっていました。たまにはDが簡単な回もいいよね!HTML直している時に他の問題には高橋君の記述があったのにDにはなかったので書き加えておきました。

コード

+ ...
package writer;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
 
public class ARCGrep {
	static Scanner in;
	static PrintWriter out;
	static String INPUT = "";
 
	static void solve()
	{
		int all = ni(), n = ni(), m = ni();
		int[] L = new int[n];
		for(int i = 0;i < n;i++)L[i] = ni();
		long[] sp = new long[n-1];
		for(int i = 0;i < n-1;i++){
			sp[i] = (L[i+1] - L[i] - 1)*2L;
		}
		Arrays.sort(sp);
		long[] cum = new long[n];
		for(int i = 0;i < n-1;i++){
			cum[i+1] = cum[i] + sp[i]/2;
		}
 
		for(int i = 0;i < m;i++){
			int b = ni(), a = ni();
			int ind = Arrays.binarySearch(sp, (a+b)*2L+1);
			long mid = cum[n-1] - cum[-ind-1] - (long)(b+a)*(n-1-(-ind-1));
			out.println(all - mid - Math.max(L[0]-1-b, 0) - Math.max(all-L[n-1]-a, 0));
		}
	}
 
	public static void main(String[] args) throws Exception
	{
		in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);
		out = new PrintWriter(System.out);
 
		solve();
		out.flush();
	}
 
	static int ni() { return Integer.parseInt(in.next()); }
	static long nl() { return Long.parseLong(in.next()); }
	static double nd() { return Double.parseDouble(in.next()); }
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
 

タグ:

ARC
最終更新:2013年06月16日 21:29