BottomCoder SRM 386 div2

SRM 386 div2

points	result	time
250	AC	4m?
500	AC	13m
1000	AC	24.6m

1000がこんなに(ry

250

左から右へ1列にトロフィーが並んでいる(||<=50)。各トロフィーの高さが与えられたとき、これらを左からみたときに見えるトロフィーの数と、右から見たときに見えるトロフィーの数を答えよ。

なんのことはなく、左・右側から狭義単調増加な部分列をgreedyに取り出せば良いだけ。

public class TrophyShelf {

	public int[] countVisible(int[] trophies) {
		int n = trophies.length;
		int t = 0;
		int lct = 0;
		for(int i = 0;i < n;i++){
			if(trophies[i] > t){
				lct++;
				t = trophies[i];
			}
		}
		t = 0;
		int rct = 0;
		for(int i = n - 1;i >= 0;i--){
			if(trophies[i] > t){
				rct++;
				t = trophies[i];
			}
		}
		return new int[]{lct, rct};
	}

}

500

英大文字のみからなる同じ長さ(<=10)の文字列がN(<=50)個与えられる。superkeyとは、異なる整数の集合として、文字列に対しその整数に対応するインデックスだけを取り出してくっつけた文字列が、N個の文字列でどれも異なっているものをいう。candidate superkeyとは、superkeyで、その部分集合がどれもsuperkeyにならないようなものをいう。candidate superkeyの最小要素数と最大要素数を答えよ。存在しない場合は空配列を返せ。(意訳)

方法を考えるのに手間取ったが、やはり20以下はbit!だった。文字列の長さがMのとき、superkeyのパターンは各インデックスを採用するかしないかの2^M-1通り。candidateを調べる都合上昇順で走査する。
あるパターンxについて、candidateかどうかを調べる。x未満の(x&y)==yとなるパターンyでcandidateなものが一つでもあればout.
次に、部分文字列をN個すべてについてつくって、一致したものが1組でもあればout. それ以外はcandidateとなる。超愚直にやればO(MN^2)だが、これでもぎりぎり間に合うんじゃなかろうか。自分は26^10までのハッシュ？を積み上げてソートして比較したのでO(MN+NlogN)ぐらい。たかだか50個しかないのでHashSetでもいけそう。

こうしてできたcandidateたちのビット数をみて、最大最小を求めれば良い。

import java.util.Arrays;
import java.util.BitSet;

public class CandidateKeys {

	public int[] getKeys(String[] table) {
		int n = table.length;
		int m = table[0].length();
		
		BitSet bs = new BitSet();
		outer:
		for(int i = 1;i < 1<<m;i++){
			for(int j = 1;j < i;j++){
				if((i&j)== j && bs.get(j)){
					continue outer;
				}
			}
			
			long[] pp = new long[n];
			for(int k = 0;k < m;k++){
				if((i&1<<k)!=0){
					for(int j = 0;j < n;j++){
						pp[j] = pp[j] * 26 + table[j].charAt(k)-'A';
					}
				}
			}
			Arrays.sort(pp);
			for(int j = 0;j < n - 1;j++){
				if(pp[j] == pp[j+1])continue outer;
			}
			bs.set(i);
		}
		
		int min = 9999;
		int max = 0;
		for(int i = bs.nextSetBit(0);i != -1;i = bs.nextSetBit(i+1)){
			min = Math.min(min, Integer.bitCount(i));
			max = Math.max(max, Integer.bitCount(i));
		}
		if(min == 9999)return new int[]{};
		
		return new int[]{min, max};
	}

}

1000

N(<=100)頂点の木がある。あるノードV以下の部分木をもぎとって、Vのある祖先Uの子としてV以下の部分木をくっつける操作を行う。この操作にはコストL(V)-L(U)-1だけかかるとする。(L(A)はノードAのルート(0)からの深さ). どのノードまでの深さもheight以下にするまで操作を行うときの最小コストを求めよ。

まさかのgreedy. まず、ルートから各ノードへの距離(深さ)を出す。N<=100なのでWarshall-FloydでもOK. そしてその昇順(浅い順)に、次の操作を繰り返す。
該当ノードV以下の部分木で一番深いノードの深さがheightになるまで部分木を引き上げるか、Vをルートまで引き上げるかどちらかコストが小さい方を選んでそれを行う。
操作を行ったあとは深さが更新されることに注意。浅いところにあるノード以下の部分木の引き上げは、そこより深いところにあるノード以下の部分木より、明らかに同コストでも上位の引き上げ効果を持つ。つまり、引き上げる必要があるならば、浅い方からめいっぱい引き上げれば良い、ということになる。

import java.util.Arrays;
import java.util.Comparator;

public class LittleTree {

	public int minCost(int N, String[] edges, int height) {
		StringBuilder sb = new StringBuilder();
		for(String e : edges)sb.append(e);
		int[][] g = new int[N][N];
		for(int i = 0;i < N;i++){
			Arrays.fill(g[i], 999999);
			g[i][i] = 0;
		}
		for(String ss : sb.toString().split(" ")){
			String[] sp = ss.split(",");
			int f = Integer.parseInt(sp[0]);
			int t = Integer.parseInt(sp[1]);
			g[f][t] = 1;
		}
		
		for(int k = 0;k < N;k++){
			for(int i = 0;i < N;i++){
				for(int j = 0;j < N;j++){
					g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
				}
			}
		}
		
		final int[] dep = g[0];
		Integer[] ord = new Integer[N];
		for(int i = 0;i < N;i++)ord[i] = i;
		Arrays.sort(ord, new Comparator<Integer>(){
			public int compare(Integer x, Integer y)
			{
				return dep[x] - dep[y];
			}
		});
		
//		tr(ord);
		int cost = 0;
		for(int i = 1;i < N;i++){
			int max = 0;
			for(int j = 0;j < N;j++){
				if(g[ord[i]][j] < 9999){
					max = Math.max(max, g[ord[i]][j]);
				}
			}
			max += g[0][ord[i]];
			int minus = Math.min(max - height, g[0][ord[i]] - 1);
			if(minus > 0){
				cost += minus;
				for(int j = 0;j < N;j++){
					if(g[ord[i]][j] < 9999){
						g[0][j] -= minus;
					}
				}
//				tr(minus, g[0]);
			}
		}
		
		return cost;
	}

	static void tr(Object ...o){System.out.println(Arrays.deepToString(o));}
}