タイピング大会とCodeforces #253

今日は朝から社員大会のため直帰。
お昼はフォーラムの近場でラーメンを食べる。
f0019846_6284155.jpg


その後はTopCoderを犠牲にして、パーティーに参加。
そしてタイピング大会は出場し、優勝しておきました。
昔とった杵柄ですな(えっ
景品お菓子だったし、リアルに要らない奴や…。金くれ金!

最後まで参加していましたが、結局抽選は当たらず。
どうでもいい同期があたっていたのでクソゲーかと思った。

帰宅前にゲーセン少々。

Flip Flap SPECIAL 97.1%
f0019846_6303364.jpg


その後はCodeforcesに参加。元気だね私…。

A問題は、単純に使われている文字の種類を数え上げるだけ。
小文字しか使われないのでその辺だけ考えれば良い。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
boolean[] set = new boolean[26];
for(int i = 0 ; i < s.length(); i++){
if(s.charAt(i) >= 97 && s.charAt(i) <= 122){
set[s.charAt(i) - 97] = true;
}
}
int count = 0;
for(int i = 0 ; i < set.length ; i++){
if(set[i])count++;
}
System.out.println(count);
}


}


B問題は、2nの部分文字列が、2回繰り返しになるようにする追加アルファベット数を求める問題。


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
int k = Integer.parseInt(br.readLine());
for(int i = 0 ; i < k ; i++){
s += "*";
}
int maxc = 0;
for(int i = 0 ; i < s.length() ; i++){
for(int j = i ; j < (s.length()-i)/2 + i ; j++){
int pre = j - i + 1;
boolean isok = true;
for(int l = i ; l < j ; l++){
if(s.charAt(l) == s.charAt(l+pre) || s.charAt(l+pre) == '*' || s.charAt(pre) == '*'){

}else{
isok = false;
break;
}
}
if(isok){
maxc = Math.max(maxc, pre);
}
}
}
System.out.println(maxc*2);
}


}

始点と終点をキメて総当りでOK。200程度なのでO(n^3)は(200^3)で間に合う。

C問題は、色のヒントもしくは数字のヒントをもらって、すべてのカードを一意に識別できる
最短を求める問題。今考えたけど実は総当りでいけるんじゃないかと。
それだけじゃダメですが。

D問題は、質問に答えてくれる確率が人によって与えられているので、
Andreyは聞くか聞かないか選べる。
その時に答えを返してくれる最大の確率を求めよという問題。


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] s = br.readLine().split(" ");
double[] nums = new double[n];
for(int i = 0 ; i < n ; i++){
nums[i] = Double.parseDouble(s[i]);
}
Arrays.sort(nums);
if(nums[n-1] >= 0.5){
System.out.println(nums[n-1]);
}else{
int index = 0;
while(index < n){
if(nums[index] < 0.5){
index++;
}else{
break;
}
}
double sumper = 0;
for(int k = 0 ; k < index ; k++){
for(int l = k ; l < index ; l++){
double sumper2 = 0;
for(int i = k ; i <= l ; i++){
double tmpsum = 1;
for(int j = k ; j <= l ; j++){
if(j == i){
tmpsum *= nums[j];
}else{
tmpsum *= (1-nums[j]);
}
}
sumper2 += tmpsum;
sumper = Math.max(sumper, sumper2);
}
}
}
System.out.println(sumper);
}
}


}


nが100程度なのでO(n^4)は1000万程度でいける。
ちなみにどれかの確率が0.5以上なら、掛けあわせで0.5より大きくなることはない
(0.5*0.5+0.5*0.5が最大)のでその値を出力する(テストケース1)
ソートして0.5より大きくなる最初のインデックスを見つける。
後はある範囲からある範囲に対して聞いて、ある範囲まで聞いてくれなくて、どこかで聞いてくれる
という計算をしたときの、最大となる確率を求めていく。

1589 -> 1725(34th、部屋内1位)でついに念願のDiv1に。これからやらなくなりそうですね…。
明日はサッカーがあるので早めに寝ます(2時半過ぎ。

  by ddrer-yossi | 2014-06-19 23:27 | codeforces | Comments(0)

<< 譲り合いの精神を活かしたギリシャ戦 リフレクガチ勢かな? >>

SEM SKIN - DESIGN by SEM EXE