2011年9月25日日曜日

移転しました

http://d.hatena.ne.jp/todo314/
投稿者 時刻: 0 件のコメント:
ラベル:

2011年9月18日日曜日

Codeforces Beta Round #87 Div. 1 Only

Codeforces Beta Round #86 Div. 1 Only (9/16 0:00~2:00）

■A. Party

解法

グラフに注目したとき下のような列があったとする．
A1->A2->…->AN
この列の中の任意の2ノードは， 同じグループに属することができないため， 最低でもNグループ必要だと分かる．
このようなNの中で最大のものNmaxを見つければ， 任意の列は，長さが高々Nmaxなので， Nmax個のグループに高々1人で振り分けることが出来る．
結局，Nmaxが答え．
#86 Div. 1 A. Party

■B. Lawnmower

解法

ジグザグに進んでいくため，貪欲に求めることが出来る．
#86 Div. 1 B. Lawnmower

■Result

oo--- 1146pts. 256th
1700→1717
投稿者 時刻: 0 件のコメント:
ラベル:

2011年9月11日日曜日

Codeforces Beta Round #86 Div. 1 Only

Codeforces Beta Round #86 Div. 1 Only (9/9 0:00~2:00）

■A. A Grammar Lessons

問題

Petyaの作った言語は以下のBNFにより定義される．与えられた文字列がSentenceか判定せよ．

Sentence := Statement | AdjectiveM | AdjectiveF | NounM | NounF | VerbM | VerbF
Statement := (AdjectiveM* NounM VerbM*) | (AdjectiveF* NounF VerbF*)

AdjectiveM := "lios" | Alphabet AdjectiveM
AdjectiveF := "liala" | Alphabet AdjectiveF
NounM := "etr" | Alphabet NounM
NounF := "etra" | Alphabet NounF
VerbM := "initis" | Alphabet VerbM
VerbF := "inites" | Alphabet VerbF

Alphabet := "a"|"b"|"c"|…|"z"

解法

書くだけ．StatementのBNFをDFAにしてからコードにすると，機械的に解ける．
#86 Div. 1 A. A Grammar Lessons

■B. Petr#

問題

文字列s，sbegin，sendが与えられる．
以下を満たす文字列tの個数を求めよ．
  • tはsの部分文字列
  • sbeginはtのprefix
  • sendはtのsuffix

解法

sにおいて，sbeginおよびsendを検索して，インデックスの候補を列挙する．
sbegin，sendに関するインデックスks，keについて，
s[ks]からsbeginがあり，
s[ke]からsendがあり，
ks≦ke かつ ks+|sbegin|≦ke+|send|
ならば，
s[ks],…,s[ke],…,s[ke+|send|-1]
が条件を満たす文字列．
条件を満たす文字列を逐一生成すると，TLEするので，
ハッシュを計算し，重複要素を取り除くことで高速化．
#86 Div. 1 B. Petr#

■Result

o---- 254pts. 215th
1684->1700

投稿者 時刻: 0 件のコメント:
ラベル:

TopCoder SRM 517

TopCoder SRM 517 (9/11 1:00~3:00)

■CompositeSmash(Easy)

問題

ある数xをy≧2，z≧2，yz=xを満たす2つの数に分割する．
この分割操作を再帰的に繰り返す．
e.g., x=12ならば，(y,z)=(3,4) or (2,6)など．
1や素数は，それ以上分割できない．

初期値としてNが与えられる．
Nを任意の方法で分割していき， 全ての分割が終了するまでにtargetが出現するかを判定せよ．

解法

全探索．念の為メモ化もしたが，無くても通る様子．
SRM 517 Div. 1 Easy CompositeSmash

■Result

o-- +0/-0
191.33pts. 301th

■Rating

1645->1673
投稿者 時刻: 0 件のコメント:
ラベル:

2011年9月4日日曜日

Codeforces Beta Round #85 Div. 1 Only

Codeforces Beta Round #85 Div. 1 Only (9/4 21:00~23:00）

■A. Petya and Inequiations

問題

n,x,yが与えられる．
a12+a22+…+an2≥x
a1+a2+…+an≤y
を満たす正整数の列
a1,a2,…,an
を求めよ．なければ，-1を返せ．

解法

a1+a2+…+an
の最小値はn．次に，
a1+a2+…+an=y
としたとき，
a12+a22+…+an2
の最大値は，
ak=1 (1≤k≤n-1)
an=y-(n-1)
のとき，この値（=(n-1)+(y-(n-1))2）がx以上なら数列(ak)が答え．
#85 Div. 1 A. Petya and Inequiations

■B. Petya and Divisors

問題

2つの数列
x1,…,xn
y1,…,yn
が与えられる．
各(xi, yi)について，
xi mod k=0 かつ (∀j:i-yi≤j<i) xj mod k ≠ 0
なる正整数kの数を求めよ．

解法

xiの各約数di,kについて，
それがx1,…,xi-1の約数である最後のインデックスp[di,k]を記録しておく．
p[di,k]<i-yiなら条件を満たす．
その後，
p[di,k]=i
と更新．
#85 Div. 1 B. Petya and Divisors

■Result

o---- 484pts. 278th
1689 -> 1684

ドカーン．
投稿者 時刻: 0 件のコメント:
ラベル:

2011年9月3日土曜日

TopCoder SRM 513

TopCoder SRM 516(8/31 0:00~2:00)

敗北．

■NetworkXOneTimePad(Easy)

・解法

全探索．
Long.parseLong(str, 2)をLong.parseLong(str)と書いてしまい，終了数分前に直すはめになってしまった．

■Challenge Phase

TLEが狙えるかと思ったが撃墜失敗． むしろ，サンプルの弱さを考慮した撃墜を作っておくべきだった．

■Result

o-- +0/-1
50.0pts. 489th

■Rating

1727 -> 1645
捻挫+打撲．
投稿者 時刻: 0 件のコメント:
ラベル:

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かどうかを判定せよ．

解法

やるだけ．
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. 27th
1631 -> 1689
投稿者 時刻: 0 件のコメント:
ラベル:

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に戻れるかも知れないがしかし…．
投稿者 時刻: 0 件のコメント:
ラベル:
登録: コメント (Atom)