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回の計算で終わるので，逐一試す．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class A{  
10.     Scanner sc=new Scanner(System.in);  
11.   
12.     int INF=1<<28;  
13.     double EPS=1e-9;  
14.   
15.     void run(){  
16.         String[] ss=sc.next().split(":");  
17.         int h=Integer.parseInt(ss[0]);  
18.         int m=Integer.parseInt(ss[1]);  
19.         for(;;){  
20.             if(++m==60){  
21.                 m=0;  
22.                 if(++h==24){  
23.                     h=0;  
24.                 }  
25.             }  
26.             String s=String.format("%02d:%02d", h, m);  
27.             if(new StringBuffer(s).reverse().toString().equals(s)){  
28.                 println(s);  
29.                 return;  
30.             }  
31.         }  
32.     }  
33.   
34.     void println(String s){  
35.         System.out.println(s);  
36.     }  
37.   
38.     void print(String s){  
39.         System.out.print(s);  
40.     }  
41.   
42.     void debug(Object... os){  
43.         System.err.println(Arrays.deepToString(os));  
44.     }  
45.   
46.     public static void main(String[] args){  
47.         new A().run();  
48.     }  
49. }  

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に至る辺の容量で最小のもの．

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class C{  
10.     Scanner sc=new Scanner(System.in);  
11.   
12.     int INF=1<<28;  
13.     double EPS=1e-9;  
14.   
15.     int n, p;  
16.     E[] es;  
17.     int[] parent;  
18.     LinkedList<E> answers;  
19.     boolean[] visited;  
20.   
21.     class E{  
22.         int from, to, cap;  
23.   
24.         E(int from, int to, int cap){  
25.             this.from=from;  
26.             this.to=to;  
27.             this.cap=cap;  
28.         }  
29.     }  
30.   
31.     void run(){  
32.         n=sc.nextInt();  
33.         p=sc.nextInt();  
34.         es=new E[n];  
35.         answers=new LinkedList<E>();  
36.         parent=new int[n];  
37.         fill(parent, -1);  
38.         for(int i=0; i<n; i++){}  
39.         for(int i=0; i<p; i++){  
40.             int a=sc.nextInt()-1;  
41.             int b=sc.nextInt()-1;  
42.             int d=sc.nextInt();  
43.             es[a]=new E(a, b, d);  
44.             parent[b]=a;  
45.         }  
46.         solve();  
47.     }  
48.   
49.     void solve(){  
50.         visited=new boolean[n];  
51.         for(int i=0; i<n; i++){  
52.             if(visited[i]){  
53.                 continue;  
54.             }  
55.             int k=i;  
56.             boolean loop=false;  
57.             for(; parent[k]>=0;){  
58.                 k=parent[k];  
59.                 if(k==i){  
60.                     loop=true;  
61.                     break;  
62.                 }  
63.             }  
64.             if(loop){  
65.                 continue;  
66.             }  
67.             if(es[k]!=null){  
68.                 visited[k]=true;  
69.                 dfs(es[k].to, k, es[k].cap);  
70.             }  
71.         }  
72.         E[] anss=answers.toArray(new E[0]);  
73.         sort(anss, new Comparator<E>(){  
74.             @Override  
75.             public int compare(E e1, E e2){  
76.                 return e1.from-e2.from;  
77.             }  
78.         });  
79.         println(anss.length+"");  
80.         for(E e : anss){  
81.             println(e.from+" "+e.to+" "+e.cap);  
82.         }  
83.     }  
84.   
85.     void dfs(int v, int tank, int diameter){  
86.         visited[v]=true;  
87.         if(es[v]==null){  
88.             answers.add(new E(tank+1, v+1, diameter));  
89.             return;  
90.         }  
91.         dfs(es[v].to, tank, min(diameter, es[v].cap));  
92.     }  
93.   
94.     void println(String s){  
95.         System.out.println(s);  
96.     }  
97.   
98.     void print(String s){  
99.         System.out.print(s);  
100.     }  
101.   
102.     void debug(Object... os){  
103.         // System.err.println(Arrays.deepToString(os));  
104.     }  
105.   
106.     public static void main(String[] args){  
107.         new C().run();  
108.     }  
109. }  

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)
と表せるので，ループ一つで求められる．
但し，精度が落ちないように工夫して計算する必要がある（下記コード参照）．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class D{  
10.     Scanner sc=new Scanner(System.in);  
11.   
12.     int INF=1<<28;  
13.     double EPS=1e-9;  
14.   
15.     int n, m, h;  
16.     int[] s;  
17.   
18.     void run(){  
19.         n=sc.nextInt();  
20.         m=sc.nextInt();  
21.         h=sc.nextInt()-1;  
22.         s=new int[m];  
23.         for(int i=0; i<m; i++){  
24.             s[i]=sc.nextInt();  
25.         }  
26.         solve();  
27.     }  
28.   
29.     void solve(){  
30.         int sum=0;  
31.         for(int i=0; i<m; i++){  
32.             sum+=s[i];  
33.         }  
34.         if(sum<n){  
35.             println("-1.0");  
36.             return;  
37.         }  
38.         int k=s[h]-1;  
39.         double ans=1;  
40.         for(int i=0; i<k; i++){  
41.             ans*=(double)(sum-n-i)/(sum-1-i);  
42.         }  
43.         println((1-ans)+"");  
44.     }  
45.   
46.     void println(String s){  
47.         System.out.println(s);  
48.     }  
49.   
50.     void print(String s){  
51.         System.out.print(s);  
52.     }  
53.   
54.     void debug(Object... os){  
55.         System.err.println(Arrays.deepToString(os));  
56.     }  
57.   
58.     public static void main(String[] args){  
59.         new D().run();  
60.     }  
61. }  

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に戻れるかも知れないがしかし…．