Codeforces VK Cup Round1(2012/03/12)

上位700人のみが通過．

メモ

A Dress'em in Vests!

貪欲に考える．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class A{
	Scanner sc=new Scanner(System.in);

	int n, m, x, y;
	int[] a, b;

	void run(){
		n=sc.nextInt();
		m=sc.nextInt();
		x=sc.nextInt();
		y=sc.nextInt();
		a=new int[n];
		b=new int[m];
		for(int i=0; i<n; i++){
			a[i]=sc.nextInt();
		}
		for(int i=0; i<m; i++){
			b[i]=sc.nextInt();
		}
		solve();
	}

	void solve(){
		sort(a);
		sort(b);
		ArrayList<Pair> list=new ArrayList<Pair>();
		for(int i=0, j=0; i<n&&j<m;){
			int left=a[i]-x;
			int right=a[i]+y;
			if(left<=b[j]&&b[j]<=right){
				list.add(new Pair(i+1, j+1));
				i++;
				j++;
			}else if(b[j]<left){
				j++;
			}else if(b[j]>right){
				i++;
			}
		}
		StringBuilder sb=new StringBuilder();
		sb.append(list.size());
		sb.append("\n");
		for(Pair pair : list){
			sb.append(pair.u);
			sb.append(" ");
			sb.append(pair.v);
			sb.append("\n");
		}
		println(sb.toString());
	}

	class Pair{
		int u, v;

		Pair(int u, int v){
			this.u=u;
			this.v=v;
		}
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new A().run();
	}
}

B Discounts

椅子を入れたカゴの値引き額は，椅子の額の半分より大きくはならないので，機械的に書くことが出来る．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class B{
	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	int k, n;
	int[] c, t;

	void run(){
		n=sc.nextInt();
		k=sc.nextInt();
		c=new int[n];
		t=new int[n];
		for(int i=0; i<n; i++){
			c[i]=sc.nextInt();
			t[i]=sc.nextInt();
		}
		solve();
	}

	void solve(){
		ArrayList<R> lists=new ArrayList<R>();
		ArrayList<R> listp=new ArrayList<R>();
		for(int i=0; i<n; i++){
			if(t[i]==1){
				lists.add(new R(c[i], 1, i+1));
			}else{
				listp.add(new R(c[i], 1, i+1));
			}
		}
		int ns=lists.size();
		int np=listp.size();
		sort(lists);
		sort(listp);
		@SuppressWarnings("unchecked")
		ArrayList<Integer>[] cart=new ArrayList[k];
		for(int i=0; i<k; i++){
			cart[i]=new ArrayList<Integer>();
		}
		long half=0;
		long normal=0;
		if(ns>=k){
			for(int i=0; i<k-1; i++){
				R r=lists.get(i);
				cart[i].add(r.index);
				half+=r.c;
			}
			int min=INF;
			for(int i=k-1; i<ns; i++){
				R r=lists.get(i);
				cart[k-1].add(r.index);
				normal+=r.c;
				min=min(min, r.c);
			}
			for(int i=0; i<np; i++){
				R r=listp.get(i);
				cart[k-1].add(r.index);
				normal+=r.c;
				min=min(min, r.c);
			}
			normal-=min;
			half+=min;
		}else{
			for(int i=0; i<ns; i++){
				R r=lists.get(i);
				cart[i].add(r.index);
				half+=r.c;
			}
			int d=k-ns; // k-ns>0
			for(int i=0; i<np; i++){
				R r=listp.get(i);
				cart[i%d+ns].add(r.index);
				normal+=r.c;
			}
		}
		StringBuilder sb=new StringBuilder();
		String cost;
		if(half%2==0){
			cost=(normal+half/2)+".0";
		}else{
			cost=(normal+half/2)+".5";
		}
		sb.append(cost);
		sb.append("\n");
		for(int i=0; i<k; i++){
			sb.append(cart[i].size());
			for(int index : cart[i]){
				sb.append(" ");
				sb.append(index);
			}
			sb.append("\n");
		}
		println(sb.toString());
	}

	class R implements Comparable<R>{
		int c, t, index;

		R(int c, int t, int index){
			this.c=c;
			this.t=t;
			this.index=index;
		}

		@Override
		public int compareTo(R r){
			return -c+r.c;
		}
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new B().run();
	}
}

D Distance in Tree

あるノードを根として，そこから深さ優先探索をしていく．あるノードに関する再帰関数の返り値を配列：memo[i]=（そのノードからの距離がiであるノードの個数）として，どんどんマージしながら距離がkとなるものを数えていく．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class D{
	Scanner sc=new Scanner(System.in);

	int n, k;
	int[] a, b;
	long ans;

	void run(){
		n=sc.nextInt();
		k=sc.nextInt();
		a=new int[n-1];
		b=new int[n-1];
		for(int i=0; i<n-1; i++){
			a[i]=sc.nextInt()-1;
			b[i]=sc.nextInt()-1;
		}
		solve();
	}

	ArrayList<Integer>[] es;
	boolean[] visited;

	@SuppressWarnings("unchecked")
	void solve(){
		es=new ArrayList[n];
		for(int i=0; i<n; i++){
			es[i]=new ArrayList<Integer>();
		}
		for(int i=0; i<n-1; i++){
			es[a[i]].add(b[i]);
			es[b[i]].add(a[i]);
		}
		ans=0;
		visited=new boolean[n];
		dfs(0);
		println(""+ans);
	}

	int[] dfs(int v){
		int[] is=new int[k+1];
		is[0]=1;
		visited[v]=true;
		for(int u : es[v]){
			if(visited[u]){
				continue;
			}
			int[] js=dfs(u);
			for(int i=k; i>0; i--){
				js[i]=js[i-1];
			}
			js[0]=0;
			for(int i=0; i<=k; i++){
				ans+=(long)is[i]*js[k-i];
			}
			for(int i=0; i<=k; i++){
				is[i]+=js[i];
			}
		}
		return is;
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new D().run();
	}
}

Result

oo-o- 3040pts. 342nd
1981 -> 1983