AtCoder Beginner Contest 038 D プレゼント

問題

abc038.contest.atcoder.jp

考え

部分点までは自力で行けたけど、満点解法は分からずで、解説などを見て通しました。

主に2通りの解き方があるらしい。

1つ目は公式解説であるようなセグメントツリーというデータ構造を使う方法。

セグメントツリーは蟻本にも載っているので、要チェックです。

• まず、w[i]を昇順に、h[i]を降順に並べ替える。
• セグメントツリーを使って入れ子になる箱の最大値を更新していく。

参考

公式解説：http://abc038.contest.atcoder.jp/data/abc/038/editorial.pdf

セグメントツリーについて：プログラミングコンテストでのデータ構造

ソースコード（セグメントツリー解法）

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;
 
public class Main {
	static int MAX_H = (int)1e5 + 7;
	int N;
 
	//セグメントツリー
	private static class SegmentTree {
		int n;
		int[] dat;
 
		public SegmentTree(int n_) {
			n = 1;
 
			while (n_ > n) n *= 2;
			dat = new int[n * 2 - 1];
		}
 
		//kの場所にaを更新する
		public void update(int k,int a) {
			k += n - 1;
			dat[k] = Math.max(dat[k],a);
 
			//親ノードにさかのぼる処理
			while (k > 0) {
				k = (k - 1) / 2;
				dat[k] = Math.max(dat[k * 2 + 1],dat[k * 2 + 2]);
			}
		}
 
		public int query(int a,int b,int k,int l,int r){
			if(r <= a || b <= l){
				return 0;
			}
 
			if(a <= l && r <= b){
				return dat[k];
			}
 
			int left = query( a, b, k * 2 + 1, l, (l + r) / 2);
			int right = query( a, b, k * 2 + 2, (l + r) / 2, r);
			return Math.max(left, right);
		}
	}
 
	private class P implements Comparable<P> {
 
		int w, h;
 
		public P(int w, int h) {
			this.w = w;
			this.h = h;
		}
 
		public int compareTo(P other) {
			if (this.w < other.w) {
				return -1;
			} else if (this.w > other.w) {
				return 1;
			}
 
			if (this.h < other.h) {
				return -1;
			} else if (this.h > other.h) {
				return 1;
			}
 
			return 0;
		}
	}
 
	public void solve() {
		N = nextInt();
 
		P[] ps = new P[N];
 
		for (int i = 0; i < N; i++) {
			int W = nextInt();
			int H = nextInt();
			//Hに-をかけることで、Hを降順にしやすくする
			ps[i] = new P(W, -H);
		}
 
		Arrays.sort(ps);
 
		SegmentTree segTree = new SegmentTree(MAX_H);
		int ans = 0;
 
		for(int i = 0;i < N;i++){
			int H = -ps[i].h;
			int v = segTree.query(0, H, 0, 0, segTree.n) + 1;
			ans = Math.max(ans,v);
			segTree.update(H, v);
		}
 
		out.println(ans);
	}
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
 
	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;
 
	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}
 
	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}
 
	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}
 
	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}
 
	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}
 
	public int nextInt() {
		return Integer.parseInt(next());
	}
 
	public long nextLong() {
		return Long.parseLong(next());
	}
 
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

2つ目はLIS(Longest Increasing Subsequence)最長増加部分列という考え方を使って解く方法です。
LISも蟻本に載っています。

• w[i]を昇順に、h[i]を降順にソートしておき、LISで入れ子の最大値を求める。

参考
LIS：
最長増加部分列 | 動的計画法 | Aizu Online Judge
pekempeyさんのプロットの図が分かりやすかったので参考にさせていただきました。
pekempey.hatenablog.com

ソースコード（LIS解法）

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;
 
public class Main {
	static int INF = (int)1e9 + 7;
	int N;
	P[] ps;
	
	private class P implements Comparable<P>{
 
		int w,h;
 
		public P(int w,int h){
			this.w = w;
			this.h = h;
		}
 
		public int compareTo(P other){
			if(this.w < other.w ){
				return -1;
			}else if(this.w > other.w){
				return 1;
			}
			
			if(this.h < other.h){
				return -1;
			}else if(this.h > other.h){
				return 1;
			}
			
			return 0;
		}
	}
 
	public void solve() {
		N = nextInt();
		ps = new P[N];
		for(int i = 0;i < N;i++){
			int W = nextInt();
			int H = nextInt();
			
			ps[i] = new P(W,-H);
		}
		
		Arrays.sort(ps);
		
		int[] dp = new int[N];
		Arrays.fill(dp,INF);
		
		for(int i = 0;i < N;i++){
			int left = -1;
			int right = N - 1;
			while(right - left > 1){
				int mid = ((left + right) >>> 1);
				if(dp[mid] < -ps[i].h){
					left = mid;
				}else{
					right = mid;
				}
			}
			dp[right] = -ps[i].h;
		}
		
		int l = -1,r = N;
		while(r - l > 1){
			int m = ((l + r) >>> 1);
			if(dp[m] < INF){
				l = m;
			}else{
				r = m;
			}
		}
		out.println(r);
	}
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
 
	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;
 
	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}
 
	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}
 
	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}
 
	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}
 
	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}
 
	public int nextInt() {
		return Integer.parseInt(next());
	}
 
	public long nextLong() {
		return Long.parseLong(next());
	}
 
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

セグメントツリーとかLISは名前知ってるだけみたいなところがあったので、これを機にもっと色んな解法に挑戦していきたい。