Codeforces Beta Round #86 Div. 1 Only (9/16 0:00~2:00）
■A. Party
解法
グラフに注目したとき下のような列があったとする．■B. Lawnmower
解法
ジグザグに進んでいくため，貪欲に求めることが出来る．■Result
oo--- 1146pts. 256thCodeforces Beta Round #86 Div. 1 Only (9/9 0:00~2:00）
■A. A Grammar Lessons
問題
Petyaの作った言語は以下のBNFにより定義される．与えられた文字列がSentenceか判定せよ．解法
書くだけ．StatementのBNFをDFAにしてからコードにすると，機械的に解ける．■B. Petr#
問題
文字列s，sbegin，sendが与えられる．解法
sにおいて，sbeginおよびsendを検索して，インデックスの候補を列挙する．■Result
o---- 254pts. 215thCodeforces Beta Round #85 Div. 1 Only (9/4 21:00~23:00）
■A. Petya and Inequiations
問題
n,x,yが与えられる．解法
a1+a2+…+an■B. Petya and Divisors
問題
2つの数列解法
xiの各約数di,kについて，■Result
o---- 484pts. 278thCodeforces Beta Round #84 Div. 2 Only 8/30 1:00~3:00）
■A. Nearly Lucky Number
問題
Lucky Digitを，4または7として定義する．解法
やるだけ．
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である文字列のことである．解法
abcdabcd…
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の個数が固定ならば，
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の非循環無向グラフ（＝全域木）が与えられる．解法
例えば，グラフが以下のようなものだったとする．
ここで，点線になっている辺は，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 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. 27thCodeforces 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
問題・解法
ある有向グラフが与えられる．
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人からなるチームを作りたい．解法
Herr Wafaがチームに選ばれなかった状態は省く．
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. 78thCodeforces Beta Round #69 (Div. 2 Only)
Div. 1復帰が目標でした．A. Panoramixs Prediction
値が小さいので愚直に一つずつ試行．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;
int m, n;
void run(){
m=sc.nextInt();
n=sc.nextInt();
boolean f=true;
for(int i=m+1; i<n; i++){
f&=!isP(i);
}
f&=isP(n);
println(f?"YES":"NO");
}
boolean isP(int n){
for(int i=2; i*i<=n; i++){
if(n%i==0){
return false;
}
}
return n!=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 A().run();
}
}
B. Depression
%12を忘れないように気をつけるだけ．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(){
String[] ss=sc.next().split(":");
double h=Integer.parseInt(ss[0]);
double m=Integer.parseInt(ss[1]);
h=(h%12)/12.0*360;
m=m/60.0*360;
h=(h+m/12)%360;
println(h+" "+m);
}
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. Heroes
全探索で解くことが出来るが，ちょっとしたミスをしたためSystem Test落ち．下は修正版．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, a, b, c;
int[] p, q;
HashMap<String, Integer> map;
void run(){
int m=7;
map=new HashMap<String, Integer>();
map.put("Anka", 0);
map.put("Chapay", 1);
map.put("Cleo", 2);
map.put("Troll", 3);
map.put("Dracul", 4);
map.put("Snowy", 5);
map.put("Hexadecimal", 6);
n=sc.nextInt();
p=new int[n];
q=new int[n];
for(int i=0; i<n; i++){
p[i]=map.get(sc.next());
sc.next();
q[i]=map.get(sc.next());
}
a=sc.nextInt();
b=sc.nextInt();
c=sc.nextInt();
long dmin=1L<<32;
int lmax=0;
for(int k=1; k<1<<m; k++){
for(int j=1; j<1<<m; j++){
int i=((1<<m)-1)&~(k^j);
if((k^j)==(k|j)&&i>0){
int x=a/Integer.bitCount(i);
int y=b/Integer.bitCount(j);
int z=c/Integer.bitCount(k);
int d=max(abs(x-y), max(abs(y-z), abs(z-x)));
int l=0;
for(int e=0; e<n; e++){
if(((k>>p[e])&1)!=0&&((k>>q[e])&1)!=0)
l++;
else if(((j>>p[e])&1)!=0&&((j>>q[e])&1)!=0)
l++;
else if(((i>>p[e])&1)!=0&&((i>>q[e])&1)!=0)
l++;
}
if(d<dmin){
dmin=d;
lmax=l;
}else if(d==dmin){
lmax=max(lmax, l);
}
}
}
}
println(dmin+" "+lmax);
}
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. Falling Anvils
x2+√px+q=0は，p≧4qならば実解が存在する．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 t;
double a, b;
void run(){
t=sc.nextInt();
for(int i=0; i<t; i++){
a=sc.nextInt();
b=sc.nextInt();
double area;
if(4*b<a+EPS){
area=2*b*(a-b);
}else{
area=a*(b+a/8);
}
if(abs(b)<EPS){
println("1");
}else if(abs(a)<EPS){
println("0.5");
}else{
println(area/(2*a*b)+"");
}
}
}
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();
}
}
ooxo- 2726p 46位コンテストが随分ご無沙汰だったので参加してきました．
Codeforces Round #61 (Div. 2)
A. Petya and Java
面倒だったので，BigIntegerを使って読み込み．実は，入力は必ず正の数なので，負の方向へのチェックは必要ありませんでした…．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(){
BigInteger b=sc.nextBigInteger();
long[] s={-128, -32768, -2147483648, -9223372036854775808L};
long[] e={127, 32767, 2147483647, 9223372036854775807L};
String[] ss={"byte", "short", "int", "long"};
for(int i=0; i<4; i++){
if(b.compareTo(new BigInteger(s[i]+""))>=0
&&b.compareTo(new BigInteger(e[i]+""))<=0){
println(ss[i]);
return;
}
}
println("BigInteger");
}
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. Petya and Countryside
全探索すればOK．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;
int n;
int[] a;
void run(){
n=sc.nextInt();
a=new int[n];
for(int i=0; i<n; i++){
a[i]=sc.nextInt();
}
int max=0;
for(int j=0; j<n; j++){
int s=1;
for(int i=j-1; i>=0; i--){
if(a[i]<=a[i+1]){
s++;
}else{
break;
}
}
for(int i=j+1; i<n; i++){
if(a[i-1]>=a[i]){
s++;
}else{
break;
}
}
max=max(max, s);
}
println(max+"");
}
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. Petya and File System
書けば通ると思いましたが，落ちてしまいました．D. Petya and His Friends
私が考えたのは以下のやり方．| a1 | a2 | a3 | a4 | … | an |
| 2 | 2 | 2 | 2 | … | |
| 3 | 3 | 3 | … | 3 | |
| 5 | 5 | 5 | … | 5 | |
| 7 | 7 | 7 | … | 7 |
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;
void run(){
int n=sc.nextInt();
if(n==2){
println("-1");
return;
}
BigInteger[] bis=new BigInteger[n];
for(int i=0; i<n; i++){
bis[i]=BigInteger.ONE;
}
int max=1000;
int p=0;
int[] prime=new int[max];
boolean[] isPrime=new boolean[max+1];
Arrays.fill(isPrime, true);
isPrime[0]=isPrime[1]=false;
for(int i=2; i<=max; i++){
if(isPrime[i]){
prime[p++]=i;
for(int j=2*i; j<=max; j+=i){
isPrime[j]=false;
}
}
}
for(int j=0; j<n; j++){
BigInteger bi=new BigInteger(prime[j]+"");
for(int i=0; i<n-1; i++){
bis[(j+i)%n]=bis[(j+i)%n].multiply(bi);
}
}
for(int i=0; i<n; i++){
if(bis[i].toString().length()>100){
println("-1");
return;
}
}
for(int i=0; i<n; i++){
println(bis[i]+"");
}
}
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();
}
}
ooxo- 3226p 68位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);
void run(){
int a=sc.nextInt();
int b=sc.nextInt();
int n=sc.nextInt();
if(a*b>0){
a=Math.abs(a);
b=Math.abs(b);
for(int x=1;; x++){
int c=a*(int)Math.pow(x, n);
if(c==b){
println(""+x);
break;
}else if(c>b){
println("No solution");
break;
}
}
}else if(a*b<0){
if(n%2==0){
println("No solution");
return;
}
a=Math.abs(a);
b=Math.abs(b);
for(int x=1;; x++){
int c=a*(int)Math.pow(x, n);
if(c==b){
println("-"+x);
break;
}else if(c>b){
println("No solution");
break;
}
}
}else{
if(a==0&&b==0){
println("1");
}else if(a==0){
println("No solution");
}else{
println("0");
}
}
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new A().run();
}
}
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 n;
R[] rs;
double EPS=1e-6;
void run(){
n=sc.nextInt();
rs=new R[n];
for(int i=0; i<n; i++){
R r=new R();
r.x=sc.nextInt();
r.y=sc.nextInt();
r.t=sc.nextInt();
r.p=sc.nextDouble();
rs[i]=r;
}
Arrays.sort(rs, new Comparator<R>(){
@Override
public int compare(R r1, R r2){
return r2.t-r1.t;
}
});
for(int j=0; j<n; j++){
R r=rs[j];
r.E+=r.p;
for(int i=j+1; i<n; i++){
R s=rs[i];
double d=Math.sqrt((r.x-s.x)*(r.x-s.x)+(r.y-s.y)*(r.y-s.y));
if(d<r.t-s.t+EPS){
s.E=Math.max(s.E, r.E);
}
}
}
double ans=0;
for(R r : rs){
ans=Math.max(ans, r.E);
}
println(""+ans);
}
class R{
int x, y, t;
double p;
double E;
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new C().run();
}
}
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 n, m;
int[] x, y;
int[] rod;
void run(){
n=sc.nextInt();
m=sc.nextInt();
x=new int[n];
y=new int[n];
rod=new int[m];
for(int i=0; i<n; i++){
x[i]=sc.nextInt();
y[i]=sc.nextInt();
}
for(int i=0; i<m; i++)
rod[i]=sc.nextInt();
boolean f1=true;
boolean f2=true;
int[] ans1=new int[n];
boolean[] selected=new boolean[m];
Arrays.fill(ans1, -1);
Arrays.fill(selected, false);
for(int k=0; k<n; k+=2){
// k-1,k,k+1
int x1=x[(k-1+n)%n];
int y1=y[(k-1+n)%n];
int x2=x[k];
int y2=y[k];
int x3=x[k+1];
int y3=y[k+1];
int len1=(int)Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
int len2=(int)Math.sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));
boolean f=false;
for(int i=0; i<m; i++){
if(!selected[i]&&len1+len2==rod[i]){
selected[i]=true;
ans1[k]=i+1;
f=true;
break;
}
}
if(!f){
f1=false;
break;
}
}
int[] ans2=new int[n];
Arrays.fill(ans2, -1);
Arrays.fill(selected, false);
for(int k=1; k<n; k+=2){
// k-1,k,k+1
int x1=x[k-1];
int y1=y[k-1];
int x2=x[k];
int y2=y[k];
int x3=x[(k+1)%n];
int y3=y[(k+1)%n];
int len1=(int)Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
int len2=(int)Math.sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));
boolean f=false;
for(int i=0; i<m; i++){
if(!selected[i]&&len1+len2==rod[i]){
selected[i]=true;
ans2[k]=i+1;
f=true;
break;
}
}
if(!f){
f2=false;
break;
}
}
if(f1||f2){
println("YES");
if(f1){
for(int i=0; i<n; i++)
print(ans1[i]+" ");
println("");
}
else if(f2){
for(int i=0; i<n; i++)
print(ans2[i]+" ");
println("");
}
}else{
println("NO");
}
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new A().run();
}
}
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 n;
int[] a;
int[] fav;
void run(){
n=sc.nextInt();
a=new int[n];
fav=new int[n];
for(int i=0; i<n; i++)
a[i]=sc.nextInt()-1;
for(int i=0; i<n; i++)
fav[i]=sc.nextInt();
V[] vs=new V[n];
for(int i=0; i<n; i++)
vs[i]=new V(i);
boolean[][] added=new boolean[n][n];
for(int j=0; j<n; j++){
for(int i=0; i<n; i++){
if((Math.abs(j-i)==fav[i]||Math.abs(j-i)==fav[j])&&!added[j][i]){
added[j][i]=true;
vs[i].add(vs[j]);
}
}
}
scc(vs);
parent=new int[n];
rank=new int[n];
for(int i=0; i<n; i++)
makeSet(i);
for(int j=0; j<n; j++)
for(int i=0; i<n; i++)
if(vs[i].comp==vs[j].comp)
union(i, j);
for(int i=0; i<n; i++){
if(!sameComponents(i, a[i])){
println("NO");
return;
}
}
println("YES");
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new B().run();
}
// Union-Find
int[] parent;
int[] rank;
void makeSet(int x){
parent[x]=x;
rank[x]=0;
}
void union(int x, int y){
link(findSet(x), findSet(y));
}
boolean sameComponents(int x, int y){
return findSet(x)==findSet(y);
}
void link(int x, int y){
if(rank[x]>rank[y]){
parent[y]=x;
}else{
parent[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
int findSet(int x){
if(parent[x]!=x)
parent[x]=findSet(parent[x]);
return parent[x];
}
// Strongly Connected Components
int m;
V[] us;
int scc(V[] vs){
m=vs.length;
us=new V[m];
for(V v : vs)
if(!v.visit)
dfs(v);
for(V v : vs)
v.visit=false;
for(V u : us)
if(!u.visit)
dfsrev(u, m++);
return m;
}
void dfs(V v){
v.visit=true;
for(V u : v.fs)
if(!u.visit)
dfs(u);
us[--m]=v;
}
void dfsrev(V v, int k){
v.visit=true;
for(V u : v.rs)
if(!u.visit)
dfsrev(u, k);
v.comp=k;
}
// 頂点
static class V{
// 接続している頂点
LinkedList<V> fs=new LinkedList<V>();
// 接続されている頂点
LinkedList<V> rs=new LinkedList<V>();
boolean visit;
int comp;
int id;
V(int id){
this.id=id;
}
void add(V to){
fs.add(to);
to.rs.add(this);
}
}
}
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);
void run(){
int n=sc.nextInt();
int[] cnt=new int[3001];
for(int i=2; i<=3000; i++){
cnt[i]+=cnt[i-1]+(isAP(i)?1:0);
}
println(""+cnt[n]);
}
boolean isAP(int n){
int d=-1, e=-1;
int m=n;
for(int i=2; i<n; i++){
if(m%i==0){
if(e!=-1){
return false;
}else if(d!=-1){
e=i;
}else{
d=i;
}
while(m%i==0)
m/=i;
}
}
return e!=-1;
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new A().run();
}
}
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);
void run(){
char[]cs =sc.nextLine().toCharArray();
int cnt=0;
int stack=0;
for(char c:cs){
if(c=='(')
stack++;
else{
if(stack==0)
cnt++;
else
stack--;
}
}
cnt+=stack;
int length=cs.length-cnt;
println(""+length);
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new B().run();
}
}
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 n, m, a, b, c;
char[][] map;
void run(){
n=sc.nextInt();
m=sc.nextInt();
a=sc.nextInt();
b=sc.nextInt();
c=sc.nextInt();
map=new char[n][m];
if((m*n)%2!=0){
println("IMPOSSIBLE");
return;
}
if(n%2==0&&m%2==0){
for(int j=0; j<n; j+=2){
for(int i=0; i<m; i+=2){
if(c>0){
c--;
char s=getDifferent(new int[]{i, i+1, i, i+1},
new int[]{j, j, j+1, j+1});
map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;
}else if(a>=2){
char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});
map[j][i]=map[j][i+1]=s;
char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});
map[j+1][i]=map[j+1][i+1]=t;
a-=2;
}else if(b>=2){
char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});
map[j][i]=map[j+1][i]=s;
char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});
map[j][i+1]=map[j+1][i+1]=t;
b-=2;
}else{
println("IMPOSSIBLE");
return;
}
}
}
}
if(m%2==1){
for(int j=0; j<n; j+=2){
for(int i=0; i<m-1; i+=2){
if(c>0){
c--;
char s=getDifferent(new int[]{i, i+1, i, i+1},
new int[]{j, j, j+1, j+1});
map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;
}else if(a>=2){
char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});
map[j][i]=map[j][i+1]=s;
char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});
map[j+1][i]=map[j+1][i+1]=t;
a-=2;
}else if(b>=2){
char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});
map[j][i]=map[j+1][i]=s;
char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});
map[j][i+1]=map[j+1][i+1]=t;
b-=2;
}else{
println("IMPOSSIBLE");
return;
}
}
}
for(int j=0; j<n; j+=2){
if(b>0){
char s=getDifferent(new int[]{m-1, m-1}, new int[]{j, j+1});
map[j][m-1]=map[j+1][m-1]=s;
b--;
}else{
println("IMPOSSIBLE");
return;
}
}
}
if(n%2==1){
for(int j=0; j<n-1; j+=2){
for(int i=0; i<m; i+=2){
if(c>0){
c--;
char s=getDifferent(new int[]{i, i+1, i, i+1},
new int[]{j, j, j+1, j+1});
map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;
}else if(b>=2){
char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});
map[j][i]=map[j+1][i]=s;
char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});
map[j][i+1]=map[j+1][i+1]=t;
b-=2;
}else if(a>=2){
char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});
map[j][i]=map[j][i+1]=s;
char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});
map[j+1][i]=map[j+1][i+1]=t;
a-=2;
}else{
println("IMPOSSIBLE");
return;
}
}
}
for(int i=0; i<m; i+=2){
if(a>0){
char s=getDifferent(new int[]{i, i+1}, new int[]{n-1, n-1});
map[n-1][i]=map[n-1][i+1]=s;
a--;
}else{
println("IMPOSSIBLE");
return;
}
}
}
for(int j=0;j<n;j++){
for(int i=0;i<m;i++){
System.out.print(map[j][i]);
}
println("");
}
}
char getDifferent(int[] xs, int[] ys){
boolean[] exist=new boolean[256];
for(int i=0; i<xs.length; i++){
int x=xs[i];
int y=ys[i];
if(x>0)
exist[map[y][x-1]]=true;
if(x<m-1)
exist[map[y][x+1]]=true;
if(y>0)
exist[map[y-1][x]]=true;
if(y<n-1)
exist[map[y+1][x]]=true;
}
for(int i=0; i<exist.length; i++)
if(!exist[i]&&Character.isLowerCase(i))
return (char)i;
return 'E';
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new C().run();
}
}
import java.util.Scanner;
public class A{
Scanner sc=new Scanner(System.in);
int n;
int[] a, b, c;
public void run(){
n=sc.nextInt();
a=new int[n];
b=new int[n];
c=new int[n];
for(int i=0; i<n; i++){
a[i]=sc.nextInt();
b[i]=sc.nextInt();
c[i]=sc.nextInt();
}
int cost1=0;
boolean[] visited=new boolean[n];
visited[0]=true;
int p=b[0];
for(int k=1; k<n; k++){
for(int i=0; i<n; i++){
if(visited[i])
continue;
if(a[i]==p){
p=b[i];
visited[i]=true;
break;
}else if(b[i]==p){
cost1+=c[i];
p=a[i];
visited[i]=true;
break;
}
}
}
int cost=0;
for(int x : c)
cost+=x;
int cost2=cost-cost1;
println(""+Math.min(cost1, cost2));
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new A().run();
}
}
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;
public class B{
Scanner sc=new Scanner(System.in);
int m, n;
HashMap<String, R> map=new HashMap<String, R>();
int[] ps={25, 18, 15, 12, 10, 8, 6, 4, 2, 1};
public void run(){
m=sc.nextInt();
for(int i=0; i<m; i++){
n=sc.nextInt();
for(int k=0; k<n; k++){
String s=sc.next();
if(!map.containsKey(s))
map.put(s, new R(s));
R r=map.get(s);
if(k<ps.length)
r.score+=ps[k];
r.rank[k]++;
}
}
R[] rs=map.values().toArray(new R[0]);
Arrays.sort(rs, new Comparator<R>(){
@Override
public int compare(R r1, R r2){
if(r1.score!=r2.score)
return r2.score-r1.score;
for(int i=0; i<50; i++)
if(r1.rank[i]!=r2.rank[i])
return r2.rank[i]-r1.rank[i];
return 0;
}
});
println(rs[0].name);
Arrays.sort(rs, new Comparator<R>(){
@Override
public int compare(R r1, R r2){
if(r1.rank[0]!=r2.rank[0])
return r2.rank[0]-r1.rank[0];
if(r1.score!=r2.score)
return r2.score-r1.score;
for(int i=1; i<50; i++){
if(r1.rank[i]!=r2.rank[i])
return r2.rank[i]-r1.rank[i];
}
return 0;
}
});
println(rs[0].name);
}
final class R{
int score=0;
int[] rank=new int[50];
String name;
R(String name){
this.name=name;
}
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new B().run();
}
}
import java.util.Scanner;
public class C{
Scanner sc=new Scanner(System.in);
int n;
long j;
public void run(){
n=sc.nextInt();
j=sc.nextLong();
int[] mx=new int[2*n];
int[] my=new int[2*n];
mx[0]=sc.nextInt();
my[0]=sc.nextInt();
int[] ax=new int[n];
int[] ay=new int[n];
for(int i=0; i<n; i++){
ax[i]=sc.nextInt();
ay[i]=sc.nextInt();
}
for(int i=1; i<2*n; i++){
mx[i]=2*ax[(i-1)%n]-mx[i-1];
my[i]=2*ay[(i-1)%n]-my[i-1];
}
int k=(int)(j%(2*n));
println(mx[k]+" "+my[k]);
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new C().run();
}
}
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);
void run(){
String s=sc.nextLine();
int n=s.length();
int ans=0;
for(int len=1; len<n; len++){
for(int i=0; i+len<=n; i++){
String t=s.substring(i, i+len);
if(s.indexOf(t, i+1)!=-1){
ans=len;
break;
}
}
}
println(ans+"");
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new A().run();
}
}
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);
void run(){
int t=sc.nextInt();
for(int i=0; i<t; i++){
int n=sc.nextInt();
println(""+max(0, n-2));
}
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
public static void main(String[] args){
new B().run();
}
}
import java.util.*;
public class A{
Scanner sc=new Scanner(System.in);
HashMap<String, Integer> map=new HashMap<String, Integer>();
Team[] teams;
void run(){
int n=sc.nextInt();
sc.nextLine();
teams=new Team[n];
for(int i=0; i<n; i++){
String s=sc.nextLine();
map.put(s, i);
teams[i]=new Team();
teams[i].name=s;
}
for(int i=0; i<n*(n-1)/2; i++){
String[] s=sc.nextLine().split(" ");
String[] team=s[0].split("-");
String[] score=s[1].split(":");
int t1=map.get(team[0]);
int t2=map.get(team[1]);
int s1=Integer.parseInt(score[0]);
int s2=Integer.parseInt(score[1]);
if(s1>s2){
teams[t1].point+=3;
}else if(s1<s2){
teams[t2].point+=3;
}else{
teams[t1].point+=1;
teams[t2].point+=1;
}
teams[t1].diff+=s1-s2;
teams[t2].diff+=s2-s1;
teams[t1].goal+=s1;
teams[t2].goal+=s2;
}
Arrays.sort(teams, new java.util.Comparator<Object>(){
@Override
public int compare(Object o1, Object o2){
Team t1=(Team)o1;
Team t2=(Team)o2;
if(t1.point!=t2.point)
return t2.point-t1.point;
if(t1.diff!=t2.diff)
return t2.diff-t1.diff;
return t2.goal-t1.goal;
}
});
String[] s=new String[n/2];
for(int i=0;i<n/2;i++)
s[i]=teams[i].name;
Arrays.sort(s);
for(int i=0;i<n/2;i++)
System.out.println(s[i]);
}
class Team{
String name;
int point;
int diff;
int goal;
}
public static void main(String[] args){
Locale.setDefault(Locale.US);
new A().run();
}
}
今回はCodeforcesへの参加方法について．
■登録方法
http://www.codeforces.com/registerにアクセス．
■コンテストの登録
近々コンテストがある場合は， トップページhttp://www.codeforces.com/に| → Pay attention Registration is running Codeforces Beta Round #18 (Div. 2 Only) 119:34:50 Register now » |
■コンテストの流れ
Registerした状態で開始時刻になると，色々とダイアログが出て，コンテストが開始されます．import java.util.*;
public class A{
void exe(){
LinkedList<Integer> list=new LinkedList<Integer>();
for(int i=2; i<=1000; i++)
if(isPrime(i))
list.add(i);
Object[] primes=list.toArray();
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
int cnt=0;
for(int c=2; c<=n; c++){
if(!isPrime(c))
continue;
for(int i=0; i<primes.length-1; i++){
int p1=(Integer)primes[i];
int p2=(Integer)primes[i+1];
if(c==1+p1+p2){
cnt++;
}
}
}
if(cnt>=k)
System.out.println("YES");
else
System.out.println("NO");
}
boolean isPrime(int n){
if(n<=1)
return false;
if(n==2)
return true;
if(n%2==0)
return false;
int m=(int)Math.sqrt(n)+1;
for(int i=3; i<=m; i+=2)
if(n%i==0)
return false;
return true;
}
public static void main(String[] args){
Locale.setDefault(Locale.US);
new A().exe();
}
}
import java.util.*;
public class B{
int n, m;
int[] q, a, b, c;
void exe(){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
q=new int[n];
for(int i=0; i<n; i++)
q[i]=sc.nextInt();
m=sc.nextInt();
a=new int[m];
b=new int[m];
c=new int[m];
for(int i=0; i<m; i++){
a[i]=sc.nextInt();
b[i]=sc.nextInt();
c[i]=sc.nextInt();
}
int max=0;
for(int i=0; i<n; i++){
if(q[i]>q[max])
max=i;
}
int cost=0;
for(int i=0; i<n; i++){
if(i==max)
continue;
int minj=-1;
for(int j=0; j<m; j++){
if(b[j]-1==i){
if(minj==-1||c[j]<c[minj]){
minj=j;
}
}
}
if(minj==-1){
System.out.println("-1");
return;
}
cost+=c[minj];
}
System.out.println(""+cost);
}
public static void main(String[] args){
Locale.setDefault(Locale.US);
new B().exe();
}
}
