Codeforces Beta Round #83 Div. 2 Only

Codeforces Beta Round #83 Div. 2 Only 8/24 0:00~2:00）

■A. Palindromic Times

問題

デジタル時計の時刻が与えられる（HH:MMの形式）．
その時刻以降で，時刻が回文になるものを求めよ．

解法

高々24x60回の計算で終わるので，逐一試す．

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

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

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

	int INF=1<<28;
	double EPS=1e-9;

	void run(){
		String[] ss=sc.next().split(":");
		int h=Integer.parseInt(ss[0]);
		int m=Integer.parseInt(ss[1]);
		for(;;){
			if(++m==60){
				m=0;
				if(++h==24){
					h=0;
				}
			}
			String s=String.format("%02d:%02d", h, m);
			if(new StringBuffer(s).reverse().toString().equals(s)){
				println(s);
				return;
			}
		}
	}

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

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

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

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

■C. Dorm Water Supply

問題・解法

ある有向グラフが与えられる．
頂点には，多くとも1つの入る/出る辺があり，辺には情報として容量が与えられる．
以下を満たす（頂点V，頂点U，容量C）を求めよ．

• Vには入る辺がない．
• Uには出る辺がない．
• Vから辺を辿ることで，Uに到着する．
• Cは，VからUに至る辺の容量で最小のもの．

問題を意訳すると以上のようになるため，あとは書くだけです．

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

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

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

	int INF=1<<28;
	double EPS=1e-9;

	int n, p;
	E[] es;
	int[] parent;
	LinkedList<E> answers;
	boolean[] visited;

	class E{
		int from, to, cap;

		E(int from, int to, int cap){
			this.from=from;
			this.to=to;
			this.cap=cap;
		}
	}

	void run(){
		n=sc.nextInt();
		p=sc.nextInt();
		es=new E[n];
		answers=new LinkedList<E>();
		parent=new int[n];
		fill(parent, -1);
		for(int i=0; i<n; i++){}
		for(int i=0; i<p; i++){
			int a=sc.nextInt()-1;
			int b=sc.nextInt()-1;
			int d=sc.nextInt();
			es[a]=new E(a, b, d);
			parent[b]=a;
		}
		solve();
	}

	void solve(){
		visited=new boolean[n];
		for(int i=0; i<n; i++){
			if(visited[i]){
				continue;
			}
			int k=i;
			boolean loop=false;
			for(; parent[k]>=0;){
				k=parent[k];
				if(k==i){
					loop=true;
					break;
				}
			}
			if(loop){
				continue;
			}
			if(es[k]!=null){
				visited[k]=true;
				dfs(es[k].to, k, es[k].cap);
			}
		}
		E[] anss=answers.toArray(new E[0]);
		sort(anss, new Comparator<E>(){
			@Override
			public int compare(E e1, E e2){
				return e1.from-e2.from;
			}
		});
		println(anss.length+"");
		for(E e : anss){
			println(e.from+" "+e.to+" "+e.cap);
		}
	}

	void dfs(int v, int tank, int diameter){
		visited[v]=true;
		if(es[v]==null){
			answers.add(new E(tank+1, v+1, diameter));
			return;
		}
		dfs(es[v].to, tank, min(diameter, es[v].cap));
	}

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

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

	void debug(Object... os){
		// System.err.println(Arrays.deepToString(os));
	}

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

■D. Basketball Team

問題

N人からなるチームを作りたい．
候補は全部でS人であり，Herr Wafaには仲間がK人いる．
S人からN人をランダムに選ぶとき，
Herr Wafaが少なくとも一人の仲間と一緒になる確率を求めよ．
N人を選べない（候補の人数が足りない）場合は-1とせよ．

解法

Herr Wafaがチームに選ばれなかった状態は省く．
(N, R)を二項係数（＝N個からR個を選ぶ組み合わせの総数）とする．
Herr Wafaがチームに選ばれたとして，残りのN-1人を選ぶ方法は(S-1, N-1)通り．
その内，仲間が一人も居ない場合は(S-1-K, N-1)通り．すなわち，
1-{(S-1-K, N-1)/(S-1, N-1)}
が答え．
左の項はもっと簡単に，
(S-N)(S-N-1)…(S-N-K+1)
-----------------------
(M-1)(M-2)…(M+K)
と表せるので，ループ一つで求められる．
但し，精度が落ちないように工夫して計算する必要がある（下記コード参照）．

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

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

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

	int INF=1<<28;
	double EPS=1e-9;

	int n, m, h;
	int[] s;

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

	void solve(){
		int sum=0;
		for(int i=0; i<m; i++){
			sum+=s[i];
		}
		if(sum<n){
			println("-1.0");
			return;
		}
		int k=s[h]-1;
		double ans=1;
		for(int i=0; i<k; i++){
			ans*=(double)(sum-n-i)/(sum-1-i);
		}
		println((1-ans)+"");
	}

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

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

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

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

■Result

oxoo- 2816pts. 78th
1562 -> 1631
次回でDiv.1に戻れるかも知れないがしかし…．