Google Code Jam 2013 R1A

朝10時からということで参戦。目標1000位以内。
得点からしてCから行けるかなと思いきや、結構難読でテンパる。
結局10分さらっと読んですぐできなさそうと見て、Aに入る。これは大きなロス。

A問題は、最初の半径rの白塗り円が与えられていて、そこから外側に半径r+1の黒円、
更に外にr+2の白円という順番で繰り返し塗っていく。
ペンキがk与えられていたら、いくつの黒円が描けるかという問題。
kがミリリットルとか書いてあったので、cm^3からcm^2に変換するのどうやるのかなとか
考えてしまいましたが、問題文に書いてあって、1ミリリットルは1πcm^2として計算するということ。
時間中にはできませんでしたが、等差数列を求めて、適正な値を二分探索してあげると、
すぐに終わります。1から順に計算していっても終わりません。
MAXの適正値決めるの難しいんだけどね。オーバーフローしてはいけないので。


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

public class Test2 {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/A-large-practice.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int num = input.nextInt();
http://foo.com;
for(int i = 0 ; i < num ; i++){
long r = input.nextLong();
long t = input.nextLong();
pw.print("Case #"+(i+1)+": "+radius(r,t));
pw.println();
pw.flush();
}
input.close();
pw.close();
}

public static long radius(long r,long t){
long min = 0;
long max = Math.min(Long.MAX_VALUE/r,1000000000);
long mid = (min+max)/2;
while(min <= max){
long ts = (r*2+1)*mid+2*mid*(mid-1);
if(ts == t){
return mid;
}else if(ts < t){
min = mid+1;
}else if(ts > t){
max = mid-1;
}
mid = (min+max)/2;
}
return mid;
}
}


B問題は、smallしか通りませんでした。内容としては、
最大体力がE与えられていて、日ごとにR回復する。
日にちごとのレジャーの楽しさがN個与えられていて、
楽しさを最大値を求める問題。

例えば E = 5 R = 3 N = 5 {2,5,1,1,8}の場合、
2*2+5*4+1*0+1*0+8*5となります。

その日以降で一番楽しい日を探して、その日までに回復しきっちゃうのであれば、
全部使ってしまい、回復し切らないなら回復しきる部分まで使い切るという方法で解けます。
smallまでは・・・。


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

public class Test {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/B-small-attempt0.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int num = input.nextInt();
for(int i = 0 ; i < num ; i++){
int E = input.nextInt();
int R = input.nextInt();
int N = input.nextInt();
int[] vi = new int[N];
for(int j = 0 ; j < N ; j++){
vi[j] = input.nextInt();
}
pw.print("Case #"+(i+1)+": "+radius(E,R,N,vi));
pw.println();
pw.flush();
}
input.close();
pw.close();
}

public static long radius(int E,int R,int N,int[] vi){
if(R >= E){
long sum = 0;
for(int i = 0 ; i < vi.length ; i++){
sum += vi[i];
}
return sum * E;
}else{
long sum = 0;
int ME = E;
for(int i = 0 ; i < vi.length ; i++){
int vnum = vi[i];
int count = E;
boolean last = true;
for(int j = i+1 ; j < vi.length ; j++){
count += R;
if(count >= ME*2 || vnum < vi[j]){
last = false;
break;
}
}
if(count >= ME*2 || last){
sum += E*vnum;
E = 0;
}else if(count > ME){
sum += (count-ME)*vnum;
E -= (count-ME);
}
E += R;
}
return sum;
}
}
}


C問題は、数が幾つか与えられていて、
それがどういう因数で構成されているかを予測する問題です。
Smallは、セット的にありえる可能性が決まっているので大体うまくいくのですが、
largeは割と運なところがあるかもしれません。


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

public class Test {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/C-small-1-attempt0.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int T = input.nextInt();
int R = input.nextInt();
int N = input.nextInt();
int M = input.nextInt();
int K = input.nextInt();
pw.println("Case #1:");
for(int i = 0 ; i < R ; i++){
int[] vi = new int[K];
for(int j = 0 ; j < vi.length ; j++){
vi[j] = input.nextInt();
}
pw.println(radius(N,M,K,vi));
pw.flush();
}
input.close();
pw.close();
}

public static String radius(int N,int M,int K,int[] vi){
int[] counter = new int[4];//2 3 4 5
for(int i = 0 ; i < vi.length ; i++){
int ni = 0;
int san = 0;
int yon = 0;
int go = 0;
while(vi[i] != 1){
if(vi[i] % 4 == 0){
yon++;
vi[i] /= 4;
}else if(vi[i] % 3 == 0){
san++;
vi[i] /= 3;
}else if(vi[i] % 5 == 0){
go++;
vi[i] /= 5;
}else if(vi[i] % 2 == 0){
ni++;
vi[i] /= 2;
}
}
if(ni > counter[0])counter[0] = ni;
if(san > counter[1])counter[1] = san;
if(yon > counter[2])counter[2] = yon;
if(go > counter[3])counter[3] = go;
}
String st = "";
while(counter[0] != 0){
st += "2";
counter[0]--;
}
while(counter[1] != 0){
st += "3";
counter[1]--;
}
while(counter[2] != 0){
st += "4";
counter[2]--;
}
while(counter[3] != 0){
st += "5";
counter[3]--;
}
if(st.length() == N){
return st;
}else{
for(int i = st.length(); i < N ; i++){
st += "2";
}
return st;
}
}
}


33点の1677位。
A問題のlargeを慎重にやっていれば抜けられただけにもったいない。
R1B、R1Cの通過に賭けましょう。

その後は麻雀。こういうの決まると楽しい。
Google Code Jam 2013 R1A_f0019846_11363830.png


夜はゲーセンへ。とりあえず脳直システムが解禁されていたので。
Google Code Jam 2013 R1A_f0019846_1131374.jpg


後はマジアカやっておくかーということで賢者に。
Google Code Jam 2013 R1A_f0019846_11325718.jpg


頑張ればミス20切れるかなー・・・?
Google Code Jam 2013 R1A_f0019846_11335158.jpg


今度はリフレクへ。
朧とwaxing and wandingをフルコン。
Google Code Jam 2013 R1A_f0019846_11342577.jpg


Google Code Jam 2013 R1A_f0019846_11345372.jpg


GAIAはなかなかむずかしい。
Google Code Jam 2013 R1A_f0019846_11352093.jpg


今日から地元ゲーセンでくじが始まっていたので、今日買っておくかーということで、
時間外手数料払ってお金を下ろして、10枚分のパセリを購入しました。
うち5枚を引いてみたが、1枚景品、4枚お菓子という結果に。まあ、そりゃあそうだよね・・・。

麻雀(3-1-4-2-1)

  by ddrer-yossi | 2013-04-27 23:14 | 日常生活

<< また一等を引いてしまった。 SRM忘れる。数え役満発動。 >>

SEM SKIN - DESIGN by SEM EXE