Codeforces Beta Round #84 Div. 2 Only

Codeforces Beta Round #84 Div. 2 Only 8/30 1:00~3:00）

■A. Nearly Lucky Number

問題

Lucky Digitを，4または7として定義する．
Lucky Numberは，Lucky Digitのみで表現される（10進）数のことである．
Nearly Lucky Numberとは，ある数に含まれるLucky Digitの個数が，Lucky Numberである数のことである．
与えられた数が，Nearly Lucky Numberかどうかを判定せよ．

解法

やるだけ．

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.         long n=sc.nextLong();  
17.         int c=0;  
18.         for(; n>0; n/=10){  
19.             if(n%10==4||n%10==7){  
20.                 c++;  
21.             }  
22.         }  
23.         boolean f=c>0;  
24.         for(; c>0; c/=10){  
25.             f&=c%10==4||c%10==7;  
26.         }  
27.         println(f?"YES":"NO");  
28.     }  
29.   
30.     void println(String s){  
31.         System.out.println(s);  
32.     }  
33.   
34.     void print(String s){  
35.         System.out.print(s);  
36.     }  
37.   
38.     void debug(Object... os){  
39.         System.err.println(Arrays.deepToString(os));  
40.     }  
41.   
42.     public static void main(String[] args){  
43.         new A().run();  
44.     }  
45. }  

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(){
		long n=sc.nextLong();
		int c=0;
		for(; n>0; n/=10){
			if(n%10==4||n%10==7){
				c++;
			}
		}
		boolean f=c>0;
		for(; c>0; c/=10){
			f&=c%10==4||c%10==7;
		}
		println(f?"YES":"NO");
	}

	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();
	}
}

■B. Lucky String

問題

Lucky Stringとは， ある文字列において出現するアルファベットのインデックスをアルファベット毎に分類・ソートしたときに， 隣り合うインデックスの差がLucky Numberである文字列のことである．
長さnのLucky Stringの内，辞書式順で最も早いものを出力せよ．

解法

abcdabcd…
↑これをn文字出力するだけ．

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 B{  
10.     Scanner sc=new Scanner(System.in);  
11.   
12.     int INF=1<<28;  
13.     double EPS=1e-9;  
14.   
15.     void run(){  
16.         int n=sc.nextInt();  
17.         StringBuffer sb=new StringBuffer("");  
18.         for(int i=0; i<n;){  
19.             for(char c='a'; c<='d'&&i<n; c++, i++){  
20.                 sb.append(c);  
21.             }  
22.         }  
23.         println(sb.toString());  
24.     }  
25.   
26.     void println(String s){  
27.         System.out.println(s);  
28.     }  
29.   
30.     void print(String s){  
31.         System.out.print(s);  
32.     }  
33.   
34.     void debug(Object... os){  
35.         System.err.println(Arrays.deepToString(os));  
36.     }  
37.   
38.     public static void main(String[] args){  
39.         new B().run();  
40.     }  
41. }  

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

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

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

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

	void run(){
		int n=sc.nextInt();
		StringBuffer sb=new StringBuffer("");
		for(int i=0; i<n;){
			for(char c='a'; c<='d'&&i<n; c++, i++){
				sb.append(c);
			}
		}
		println(sb.toString());
	}

	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 B().run();
	}
}

■C. Lucky Sum of Digits

問題

各桁の総和がnとなる最小のLucky Numberを求めよ．

解法

4の個数と，7の個数が固定ならば，
44…4477…77
という形のLucky Numberが最小であることは明らか．
次に，4の個数をa，7の個数をbとすると，
4a+7b=n
が成立する．
（例えば28で考えれば分かるが） 上の条件を満たす(a, b)の中で，bが最大ものが最小のLucky Numberとなることは明らか．
従って，aを0から逐次増やしていき， (n-4a) mod 7=0となればそこで計算を終了すればいい．
そのようなaが見つからずにループが終了したときは，条件を満たすLucky Numberは存在しない．

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;  
16.   
17.     void run(){  
18.         n=sc.nextInt();  
19.         for(int a=0; n-4*a>=0; a++){  
20.             if((n-4*a)%7==0){  
21.                 int b=(n-4*a)/7;  
22.                 StringBuffer sb=new StringBuffer();  
23.                 for(int i=0; i<a; i++){  
24.                     sb.append('4');  
25.                 }  
26.                 for(int i=0; i<b; i++){  
27.                     sb.append('7');  
28.                 }  
29.                 println(sb.toString());  
30.                 return;  
31.             }  
32.         }  
33.         println("-1");  
34.     }  
35.   
36.     void println(String s){  
37.         System.out.println(s);  
38.     }  
39.   
40.     void print(String s){  
41.         System.out.print(s);  
42.     }  
43.   
44.     void debug(Object... os){  
45.         System.err.println(Arrays.deepToString(os));  
46.     }  
47.   
48.     public static void main(String[] args){  
49.         new C().run();  
50.     }  
51. }  

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;

	void run(){
		n=sc.nextInt();
		for(int a=0; n-4*a>=0; a++){
			if((n-4*a)%7==0){
				int b=(n-4*a)/7;
				StringBuffer sb=new StringBuffer();
				for(int i=0; i<a; i++){
					sb.append('4');
				}
				for(int i=0; i<b; i++){
					sb.append('7');
				}
				println(sb.toString());
				return;
			}
		}
		println("-1");
	}

	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();
	}
}

■E. Lucky Tree

問題

ノード数n，辺の数n-1の非循環無向グラフ（＝全域木）が与えられる．
各辺には，重みがついている．
次の条件を満たす3つ組(i,j,k)の数を求めよ．

• iからjの経路にはLucky Numberを重みとして持つ辺が少なくとも1つある．
• iからkの経路にはLucky Numberを重みとして持つ辺が少なくとも1つある．

解法

例えば，グラフが以下のようなものだったとする．
ここで，点線になっている辺は，Lucky Numberの重みを持つ．
ポイントは，上の条件を満たさない3つ組みを求める方が簡単だということ．
例えば，グループ1に注目してみる．
グループ1から選んだ3ノードより構成される3つ組み (v₁,v₂,v₃)は，決して上の条件を満たさない．
また，グループ1から2ノード（v₁,v₂とする）を選び， グループ1以外の任意の1ノード（uとする）を選んだとき，
(v₁,v₂,u)，(v₁,u,v₂)
も上の条件を満たさない．
つまり，あるグループkがmノードから構成されているとすれば，
m(m-1)(m-2)+2m(m-1)(n-m)
が，グループkのノードを2つ以上含みかつ上の条件を満たさ「ない」3つ組みの総数となる．
全てのグループについて上式の和を計算したものをsumとする．
最後に，nノードから3つ選ぶ順列の総数はn(n-1)(n-2)であるから，
n(n-1)(n-2)-sumが答えとなる．
さて，どうやってグラフ構造をグループに分け，そのグループのノード数を計算するだが， これについては，Union-Findを用いるのがスマートだと思われる．

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 E{  
10.     Scanner sc=new Scanner(System.in);  
11.   
12.     int INF=1<<28;  
13.     double EPS=1e-9;  
14.   
15.     int n;  
16.   
17.     void run(){  
18.         n=sc.nextInt();  
19.         make(n);  
20.   
21.         for(int i=0; i<n-1; i++){  
22.             int u=sc.nextInt()-1;  
23.             int v=sc.nextInt()-1;  
24.             int w=sc.nextInt();  
25.             if(!isLucky(w)){  
26.                 union(u, v);  
27.             }  
28.         }  
29.   
30.         debug(p);  
31.   
32.         long ans=0;  
33.         for(int i=0; i<n; i++){  
34.             long s=size(i);  
35.             if(p[i]>=0){  
36.                 continue;  
37.             }  
38.             if(s>=3){  
39.                 ans+=s*(s-1)*(s-2);  
40.             }  
41.             if(s>=2){  
42.                 ans+=s*(s-1)*(n-s)*2;  
43.             }  
44.         }  
45.   
46.         // debug(n*(n-1)*(n-2));  
47.         // debug(ans);  
48.         ans=(long)n*(n-1)*(n-2)-ans;  
49.         println(ans+"");  
50.     }  
51.   
52.     boolean isLucky(int n){  
53.         for(; n>0; n/=10){  
54.             if(n%10!=4&&n%10!=7){  
55.                 return false;  
56.             }  
57.         }  
58.         return true;  
59.     }  
60.   
61.     int[] p;  
62.   
63.     void make(int n){  
64.         p=new int[n];  
65.         fill(p, -1);  
66.     }  
67.   
68.     int find(int x){  
69.         return p[x]<0?x:(p[x]=find(p[x]));  
70.     }  
71.   
72.     boolean union(int x, int y){  
73.         x=find(x);  
74.         y=find(y);  
75.         if(x!=y){  
76.             if(p[y]<p[x]){  
77.                 int t=x;  
78.                 x=y;  
79.                 y=t;  
80.             }  
81.             p[x]+=p[y];  
82.             p[y]=x;  
83.         }  
84.         return x!=y;  
85.     }  
86.   
87.     int size(int x){  
88.         return -p[find(x)];  
89.     }  
90.   
91.     void println(String s){  
92.         System.out.println(s);  
93.     }  
94.   
95.     void print(String s){  
96.         System.out.print(s);  
97.     }  
98.   
99.     void debug(Object... os){  
100.         System.err.println(Arrays.deepToString(os));  
101.     }  
102.   
103.     public static void main(String[] args){  
104.         new E().run();  
105.     }  
106. }  

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

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

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

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

	int n;

	void run(){
		n=sc.nextInt();
		make(n);

		for(int i=0; i<n-1; i++){
			int u=sc.nextInt()-1;
			int v=sc.nextInt()-1;
			int w=sc.nextInt();
			if(!isLucky(w)){
				union(u, v);
			}
		}

		debug(p);

		long ans=0;
		for(int i=0; i<n; i++){
			long s=size(i);
			if(p[i]>=0){
				continue;
			}
			if(s>=3){
				ans+=s*(s-1)*(s-2);
			}
			if(s>=2){
				ans+=s*(s-1)*(n-s)*2;
			}
		}

		// debug(n*(n-1)*(n-2));
		// debug(ans);
		ans=(long)n*(n-1)*(n-2)-ans;
		println(ans+"");
	}

	boolean isLucky(int n){
		for(; n>0; n/=10){
			if(n%10!=4&&n%10!=7){
				return false;
			}
		}
		return true;
	}

	int[] p;

	void make(int n){
		p=new int[n];
		fill(p, -1);
	}

	int find(int x){
		return p[x]<0?x:(p[x]=find(p[x]));
	}

	boolean union(int x, int y){
		x=find(x);
		y=find(y);
		if(x!=y){
			if(p[y]<p[x]){
				int t=x;
				x=y;
				y=t;
			}
			p[x]+=p[y];
			p[y]=x;
		}
		return x!=y;
	}

	int size(int x){
		return -p[find(x)];
	}

	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 E().run();
	}
}

■Result

ooo-o 4068pts. 27th
1631 -> 1689