GoogleCodeJam Qualification Roundとcodeforces #115

今日は朝8時から待ちに待ったGoogle Code JamのQualification Roundです。
なんと今日はGoogle Code Jam + codeforces + AtCoderという
プログラミングコンテストの日です。
忘れちゃいけないのは今日が情報処理試験の前日だということ。
ひどいものです(えっ

Google Code Jamは見た感じAもBもCも解けそうだったので解いていった。
しかしAは得点が高そうだったのでB→C→Aの順番で。
実際はAが一番簡単でした。

予選通過したかどうか判明したのは翌日の15日ですが、
取り敢えず o oo oo -- の60ptsで792位通過でした。

A問題

暗号の対応関係を見るだけ。問題文にもヒントがあることを見落とさないように。
1文字だけテストケースと問題文じゃわからない対応関係があるので、それだけ
残りの文字から判明させる。

非常につまらないソースですが。

import java.util.*;
import java.io.*;

public class Test {

public void dor() throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/A-small-attempt0.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int n = input.nextInt();
input.nextLine();
for(int i = 0 ; i < n ; i++){
String s = input.nextLine();
pw.println("Case #"+(i+1)+": "+num(s));
}
input.close();
pw.flush();
pw.close();
}

public static String num(String s){
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < s.length() ; i++){
if(s.charAt(i) == ' '){
sb.append(' ');
}else if(s.charAt(i) == 'a'){
sb.append('y');
}else if(s.charAt(i) == 'b'){
sb.append('h');
}else if(s.charAt(i) == 'c'){
sb.append('e');
}else if(s.charAt(i) == 'd'){
sb.append('s');
}else if(s.charAt(i) == 'e'){
sb.append('o');
}else if(s.charAt(i) == 'f'){
sb.append('c');
}else if(s.charAt(i) == 'g'){
sb.append('v');
}else if(s.charAt(i) == 'h'){
sb.append('x');
}else if(s.charAt(i) == 'i'){
sb.append('d');
}else if(s.charAt(i) == 'j'){
sb.append('u');
}else if(s.charAt(i) == 'k'){
sb.append('i');
}else if(s.charAt(i) == 'l'){
sb.append('g');
}else if(s.charAt(i) == 'm'){
sb.append('l');
}else if(s.charAt(i) == 'n'){
sb.append('b');
}else if(s.charAt(i) == 'o'){
sb.append('k');
}else if(s.charAt(i) == 'p'){
sb.append('r');
}else if(s.charAt(i) == 'q'){
sb.append('z');
}else if(s.charAt(i) == 'r'){
sb.append('t');
}else if(s.charAt(i) == 's'){
sb.append('n');
}else if(s.charAt(i) == 't'){
sb.append('w');
}else if(s.charAt(i) == 'u'){
sb.append('j');
}else if(s.charAt(i) == 'v'){
sb.append('p');
}else if(s.charAt(i) == 'w'){
sb.append('f');
}else if(s.charAt(i) == 'x'){
sb.append('m');
}else if(s.charAt(i) == 'y'){
sb.append('a');
}else if(s.charAt(i) == 'z'){
sb.append('q');
}
}
return sb.toString();
}

public static void main(String[] args) throws Exception{
(new Test()).dor();
}


}

B問題
3人の審判がいる。3人の出すスコアは似通っていて0-10である。
2点以上の差があれば驚くべきスコアとなる。2点より差が大きくなることはない。
基準点pと演者の人数Nと驚くべきスコアの数Sと演者の得点a[0]・・・a[N-1]が与えられていて、
基準点p以上のスコアを出した審判が存在する演者の最大値を答えなさい。

重要なのは4通りに分類すること。

・そもそもの平均点がp以上である
・平均点はpより1低いけど、驚くべきスコアがなくてもp以上を出す審判がいる
・驚くべきスコアを使わないとp点以上に行かない
・そもそも無理

import java.util.*;
import java.io.*;

public class Test {

public void dor() throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/B-small-attempt0.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int n = input.nextInt();
for(int i = 0 ; i < n ; i++){
int N = input.nextInt();
int S = input.nextInt();
int P = input.nextInt();
int[] person = new int[N];
for(int j = 0 ; j < N ; j++){
person[j] = input.nextInt();
}
pw.println("Case #"+(i+1)+": "+num(N,S,P,person));
}
input.close();
pw.flush();
pw.close();
}

public static int num(int N,int S,int P,int[] person){
Arrays.sort(person);
int mone = 0;
//int mtwo = 0;
int oks = 0;
int preoks = 0;
for(int i = 0 ; i < person.length ; i++){
if(person[i]/3 == 0){
if(P == 2){
if(person[i] == 2)mone++;
}else if(P == 1){
if(person[i] >= 1){
preoks++;
}
}else if(P == 0){
preoks++;
}
}else if(person[i]/3 >= P || (person[i]/3 >= P-1 && person[i] % 3 == 1) || (person[i]/3 >= P-1 && person[i] % 3 == 2)){
oks = person.length-i;
break;
}else if(person[i]/3 >= P-1){
mone++;
}else if(person[i]/3 >= P-2 && person[i] % 3 == 2){
mone++;
}
}
oks += preoks;
if(S <= mone){
oks += S;
}else{
oks += mone;
}
return oks;
}

public static void main(String[] args) throws Exception{
(new Test()).dor();
}


}

C問題 リサイクル数の定義 たとえば12345と34512はリサイクル数。
前からn文字を後ろにくっつけた数をリサイクル数の組と表現する。
この組の数がAからBの範囲内で何組あるか答える。

1,数字を前から順番に調べていく
2,その数字の先頭を後ろにつけるという作業をもとの数字に戻るまで行う
3,この数字がA以上B以下に収まっていて、かつ今調べている数字より大きな数であれば組として加える

たとえば 1234と3412の例

1234,2341 1234, 3412 1234, 4123は組である
3412,4123は組であるが、3412,1234 3412,2341は上記に重複するのでダメ。
ということ。3つ目の条件が超重要である。

boolean型の配列を用意してわざわざやっていましたが、
3つ目の条件を使えばこれは不要です。

import java.util.*;
import java.io.*;

public class Test {

public void dor() throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/C-small-attempt0.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int n = input.nextInt();
for(int i = 0 ; i < n ; i++){
int A = input.nextInt();
int B = input.nextInt();
boolean[] ispaired = new boolean[B+1];
pw.println("Case #"+(i+1)+": "+num(A,B,ispaired));
}
input.close();
pw.flush();
pw.close();
}

public static int num(int A,int B,boolean[] ispaired){
int count = 0;
for(int i = A ; i <= B ; i++){
StringBuilder sb = new StringBuilder(i+"");
boolean same = false;
ispaired[i] = true;
while(!same){
sb.append(sb.charAt(0));
sb.deleteCharAt(0);
if(Integer.parseInt(sb.toString()) == i){
same = true;
}else if(A <= Integer.parseInt(sb.toString()) && Integer.parseInt(sb.toString()) <= B && sb.charAt(0) != '0' && !ispaired[Integer.parseInt(sb.toString())]){
count++;
}
}
}
return count;
}

public static void main(String[] args) throws Exception{
(new Test()).dor();
}
}


その後はcodeforcesへ。

A問題 数字の文字列を3つに分類して、最高値になるようにせよ。
ただし、先頭が0は認めず、かつ1000000以下になるものとする。
区切り用のfor文を二重に回してO(n^2)オーダで可能。
nが30しかないので、総当りで問題ない。


import java.util.Scanner;

public class Test {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
String s = input.nextLine();
System.out.println(maximum(s));


}

public static int maximum(String s){
if(s.length() <= 2)return -1;
int maximum = -1;
for(int i = 1 ; i < s.length()-1 ; i++){
for(int j = 2 ; j < s.length(); j++){
if(i >= 8 || j-i >= 8 || s.length()-j >= 8 || i >= j)continue;
String first = s.substring(0,i);
String second = s.substring(i,j);
String third = s.substring(j,s.length());
//System.out.println(i+","+j);
if((first.charAt(0) == '0' && first.length() >= 2) || (second.charAt(0) == '0' && second.length() >= 2) || (third.charAt(0) == '0' && third.length() >= 2))continue;
int firstnum = Integer.parseInt(first);
int secondnum = Integer.parseInt(second);
int thirdnum = Integer.parseInt(third);
if(firstnum > 1000000 || secondnum > 1000000 || thirdnum > 1000000)continue;
int tmp = firstnum+secondnum+thirdnum;
//System.out.println(firstnum+","+secondnum+","+thirdnum);
maximum = Math.max(tmp, maximum);
}
}
return maximum;
}
}

B問題
名前と得点が与えられている。
その得点が
上位50%以下ならnoob
上位20%以下~50%より大きいならrandom
上位10%以下~20%より大きいならaverage
上位1%以下~10%より大きいならhardcore
上位1%より大きいならpro

名前とスコアは同一人物で複数個あることもあり、
それらに関しては一番大きいスコアを取る。
まずはこれの判定が必要。
pairを使いたくなかったので、名前とスコアにそれぞれArrayListで動的に配列を用意した。
それらについて調べて、スコアが負けていたらカウントするといった方式です。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Test {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
//input.nextLine();
ArrayList list = new ArrayList();
ArrayList score = new ArrayList();
for(int i = 0 ; i < n ; i++){
String name = input.next();
int sc = input.nextInt();
if(list.contains(name)){
int tscore = score.get(list.indexOf(name));
tscore = Math.max(tscore,sc);
score.remove(list.indexOf(name));
score.add(list.indexOf(name),tscore);
}else{
list.add(name);
score.add(sc);
}
}
maximum(list,score);


}

public static void maximum(ArrayList list,ArrayList score){
int size = list.size();
System.out.println(size);
for(int i = 0 ; i < list.size(); i++){
int noob = 0;
for(int j = 0 ; j < list.size() ; j++){
if(score.get(i) < score.get(j))noob++;
}
double lost = ((double)noob/(double)size)*100;
if(lost > 50){
System.out.println(list.get(i)+" "+"noob");
}else if(lost <= 50 && lost > 20){
System.out.println(list.get(i)+" "+"random");
}else if(lost <= 20 && lost > 10){
System.out.println(list.get(i)+" "+"average");
}else if(lost <= 10 && lost > 1){
System.out.println(list.get(i)+" "+"hardcore");
}else{
System.out.println(list.get(i)+" "+"pro");
}
}
}
}


C問題は問題文をちゃんと把握していなかったか、wrong answer 3でした。
あ、今でも理由はわかっていません。

n点のブロックがm個あるというのがいくつかあって
ボーナスポイントがnターン後に増えるといった仕様。
ブロックの取り方によってスコアの最大値が変わるので、そのなかの最大値を返せ。

ターン数のほうが多い時は、
序盤スコアが低いのを取っていって、
終盤スコアが高いの取るだけじゃないかと思っているのですが。

ブロックの方が多い場合は、ターンが終わる時に
低いブロックだけ残るように取るといった具合だと思っています。

終了後はご飯を食べてAtCoderに参戦!とおもったのですが、
サーバーが落ちてしまい、結局コンテストなしとなりました。
記念すべき1回でした。
開始時に集中するアクセスの分散などを適切に行わないと厳しそうです。

その後は午後の参考書をようやく読み始める。こんなんで受かるのかすら怪しいです。
4時ぐらいまで粘って寝る。

  by ddrer-yossi | 2012-04-14 23:34 | codeforces

<< 情報処理試験 過去問解いていたら寝ていた >>

SEM SKIN - DESIGN by SEM EXE