2010年7月11日日曜日

Codeforces Beta Round #23

Codeforces Beta Round #23(7/9 0:00~2:00)

■A. You're Given a String...

□問題
文字列が与えられる.文字列中に2回以上現れる部分文字列の内,最大の長さを求めよ.

□解法
文字列の長さが100以下なので書くだけ.

□コード
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();
}
}

■B. Party

□問題
N人がパーティにやってきた.最初に友達が0人の人が省かれる.次に現在いるパーティ内での友達が1人の人が省かれる,次に現在いるパーティ内での友達が2人の人が省かれる,…最後に現在いるパーティ内での友達がN-1人の人が省かれる.最後まで残った人の数が最大のものを求める.

□解法
問題の趣旨が掴めない….
→しかし,結構な人数の人が提出している.
→よく分からないけど,実は答え全部1なんじゃね?
→提出,WA,あわわわわ.
→試しに,N=3で手書きシミュレートしてみよう.
→なるほど,2人以上が残ることは出来ないなぁ.
→N=4で(ry
→最大2人残った.
→あぁ,N>=2の時は最大N-2人残るのか(N<2の時は0人).
→提出,AC.

□コード
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();
}

}

C,D,Eは解けませんでした….

■Result
○○×××

■Rating
1554 -> 1633

CDEのどれかを解くことが出来れば安定して上昇すると思われます.

0 件のコメント: