TopCoder SRM 340 - tsubosakaの日記

開催していた時間帯は別のことをしていたため参加せず．

今日は暇ができたのでSRM 340のDivision 1の問題を解いてみることにしたのだけど，なんか全然プログラムが書けなくなっている．というかアルゴリズムがまともに考えられなくなっている．

250点問題
- 2乗の自明なアルゴリズムを書く．線形時間ないしはn log nのアルゴリズムがあるかどうかは不明．
500点問題
- 単純なDPなのはわかるのだが，DPの逆再生と辞書順に出せというのができない．そのうち，この程度のプログラムが一時間以上たっても書けない自分の無能さに腹が立ってきたので，諦めてPKUに逃げることにする．その後，落ち着いて来た順路を保存していくという方針で書いたら20分ぐらいで書けた．
1000点問題
- 読んですらない

250点問題

数字のリストが与えられて，それを前から順番に選んでいくのだが1個飛ばしまでしか許されておらず，また選んだ数字の集合の最小の数字と最大の数字がある差以上になったら終了してよい．取らなければならない数字の最小個数を求めよ．必ず取る二つの数字の組を決めて，その差について条件を満たすかどうか判定する．

public class ProblemsToSolve {
	public static int minNumber(int[] pleasantness, int variety){
		if(variety==0)return 1;
		int min = pleasantness.length;
		for(int i=0;i<pleasantness.length;i++){
			for(int j=i+1;j<pleasantness.length;j++){
				int diff = Math.abs(pleasantness[i]-pleasantness[j]);
				if(diff<variety)continue;
				int turn =1;
				turn += (i+1)/2;
				turn += (j-i+1)/2;
				min = Math.min(turn, min);
			}
		}
		return min;
	}
}

500点問題

いくつかの講義(高々50)がある．各講義にはtheoreticalValue(以下tV)とpracticalValue(以下pV)の2つの値が定まっている．また，講義がいついつまで終わるということも決まっている．

学生は最初tV=0,pV=0の状態であり，講義を取ることによりtV = max(tV,講義のtV),pV = max(pV,講義のpV)とすることができる．ただし，講義は(学生のtV)>=(講義のtV)-1かつ(学生のpV)>=(講義のpV)-1でなければとることができない．

できるだけ少ない講義数で学生がtVとpVをある値以上になるような講義の取り方をもとめよ．ただし，回答が複数ある場合はそのなかで辞書順でもっとも最初に来るものを出せ．

要は単なる最短路だろうと適当に書いていったら，辞書順に出せという条件ではまる．ということでコードを1から書き直して取り順を覚えていくという方針で書いた．

import java.util.*;
class Course{
	int tVal;
	int pVal;
	int expire;
	Course(int t,int p,int e){
		this.tVal = t;
		this.pVal = p;
		this.expire = e;
	}
}
class Point implements Comparable<Point>{
	int tVal;
	int pVal;
	List<Integer> path;
	Point(int t,int p){
		tVal = t;
		pVal = p;
		path = new ArrayList<Integer>();
	}
	public int compareTo(Point o) {
		if(path.size()==o.path.size()){
			for(int i=0;i<path.size();i++){
				int val = path.get(i) - o.path.get(i);
				if(val!=0)return val;
			}
			return 0;
		}
		return path.size()-o.path.size();
	}
}
public class CsCourses {
	public static int[] getOrder(int[] theoreticalValue, 
								 int[] practicalValue, 
								 int[] expire, 
								 int skillBound){
		Course cs[] = new Course[theoreticalValue.length];
		for(int i=0;i<cs.length;i++){
			cs[i] = new Course(theoreticalValue[i],practicalValue[i],expire[i]);
		}
		int memo[][] = new int[51][51];
		for(int i=0;i<memo.length;i++)Arrays.fill(memo[i],Integer.MAX_VALUE);
		memo[0][0] = 0;
		boolean flags[][] = new boolean[51][51];
		Point start = new Point(0,0);
		Queue<Point> q = new PriorityQueue<Point>();
		q.add(start);
		while(!q.isEmpty()){
			Point cp = q.poll();
			if(flags[cp.tVal][cp.pVal])continue;
			if(cp.pVal>=skillBound && cp.tVal >= skillBound){
				int arr[] = new int[cp.path.size()];
				for(int i=0;i<arr.length;i++){
					arr[i] = cp.path.get(i);
				}
				return arr;
			}
			for(int i=0;i<cs.length;i++){
				Course c = cs[i];
				if(cp.tVal>=c.tVal && cp.pVal >= c.pVal)continue;
				if(cp.tVal<c.tVal-1 || cp.pVal < c.pVal-1)continue;
				if(cp.path.size()>=c.expire)continue;
				Point next = new Point(0,0);
				next.tVal = Math.max(cp.tVal,c.tVal);
				next.pVal = Math.max(cp.pVal,c.pVal);
				if(memo[next.tVal][next.pVal]>=cp.path.size()+1){
					memo[next.tVal][next.pVal] = cp.path.size() + 1;
					for(int in:cp.path){
						next.path.add(in);
					}
					next.path.add(i);
					q.add(next);
				}
			}
			flags[cp.tVal][cp.pVal] = true;
		}
		return new int[0];
	}
}