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かどうかを判定せよ．
解法
やるだけ．
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文字出力するだけ．
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は存在しない．
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つ組み (v1,v2,v3)は，決して上の条件を満たさない．
また，グループ1から2ノード（v1,v2とする）を選び， グループ1以外の任意の1ノード（uとする）を選んだとき，
(v1,v2,u)，(v1,u,v2)
も上の条件を満たさない．
つまり，あるグループ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を用いるのがスマートだと思われる．
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. 27th1631 -> 1689
0 件のコメント:
コメントを投稿