GCJ QRから一夜明けて

今日は大体のんびりしていました。
Google Code Jam 2014 Qualification Roundは90点満点で通過!
219位でした。このタイミングなので解説を。

A問題は、1~16のカードを4*4に並べることを2回行う。
その時に、毎回列を指定し、一致するカードが1つに絞れるならそれを出力し、
2つ以上であればBad magician!を出力し、1つもなければVolunteer cheeted!を出力する。
候補が1個あればそれを入れておき、2個以上になった瞬間にBad magicianとすればよい。


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

public class Main {

public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../GoogleCodeJam2014/io/A-small-attempt0.in"));
PrintWriter pw = new PrintWriter(new FileWriter("../GoogleCodeJam2014/io/output.txt"));
int n = Integer.parseInt(input.readLine());

for(int i = 0 ; i < n ; i++){
int[][] cp = new int[4][4];
int start = Integer.parseInt(input.readLine());
for(int j = 0 ; j < 4 ; j++){
String[] st = input.readLine().split(" ");
for(int k = 0 ; k < 4 ; k++){
cp[j][k] = Integer.parseInt(st[k]);
}
}
int goal = Integer.parseInt(input.readLine());
int[][] cp2 = new int[4][4];
for(int j = 0 ; j < 4 ; j++){
String[] st = input.readLine().split(" ");
for(int k = 0 ; k < 4 ; k++){
cp2[j][k] = Integer.parseInt(st[k]);
}
}
pw.print("Case #"+(i+1)+": "+isOk(cp,cp2,start,goal));
pw.println();
pw.flush();
}
input.close();
pw.close();
}

public static String isOk(int[][] cp,int[][] cp2,int start,int goal){
int[] st = new int[4];
int[] en = new int[4];
for(int i = 0 ; i < 4 ; i++){
st[i] = cp[start-1][i];
}
for(int i = 0 ; i < 4 ; i++){
en[i] = cp2[goal-1][i];
}
int answer = 0;
int count = 0;
for(int i = 0 ; i < 4 ; i++){
for(int j = 0 ; j < 4 ; j++){
if(st[i] == en[j]){
count++;
answer = st[i];
}
}
}
if(count > 1){
return "Bad magician!";
}else if(count == 1){
return answer+"";
}else{
return "Volunteer cheated!";
}
}
}


B問題は、流行っていたクッキークリッカーの問題。
はじめのクッキーは0枚で、毎秒2枚焼きあがる。
ここでクッキーがC枚を超えたところで、クッキー工場が建てられる。
クッキー工場を立てるとクッキーの毎秒生産がF枚向上する。
所持クッキーがX枚に到達する最短時間を求めよ。

ある程度決め打ちしてもいいが、
1つずつ工場を買って(最初は0)X枚に到達するときの時間が
更新できなくなった時点で処理を終えれば良い。


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

public class Main {

public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../GoogleCodeJam2014/io/B-large.in"));
PrintWriter pw = new PrintWriter(new FileWriter("../GoogleCodeJam2014/io/output.txt"));
int n = Integer.parseInt(input.readLine());
for(int i = 0 ; i < n ; i++){
String[] st = input.readLine().split(" ");
double C = Double.parseDouble(st[0]);
double F = Double.parseDouble(st[1]);
double X = Double.parseDouble(st[2]);
pw.print("Case #"+(i+1)+": "+cookie(C,F,X));
pw.println();
pw.flush();
}
input.close();
pw.close();
}

public static double cookie(double C, double F, double X){
double pers = 2;
double mintime = X/pers;
double nowtime = 0;
while(true){
nowtime += C/pers;
pers += F;
double newtime = nowtime + X/pers;
if(newtime < mintime){
mintime = newtime;
}else{
break;
}
}
return mintime;
}
}


C問題は、一番時間がかかりました。
R*Cの2次元空間に、M個の爆弾を配置したい。
この時、地雷出ないところをクリックしたとき、一発で全部が埋まるような配置
(要するにクリックすると周囲8マスに爆弾が無ければオートで開く)が可能であれば
その配置を出し、不可能であればImpossibleを返せ。

R=C=4,M=5など、正方形で地雷が1個多い時に例外処理が必要なところで、
結構ハマりました。

要するに

....
....
....
.*** のような僻地を作ってはいけない。

....
....
..**
**** などはok。

R=C=4,M=5ではこうする必要がある。
...*
...*
...*
..**


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

public class Main {
static PrintWriter pw;
public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../GoogleCodeJam2014/io/C-large.in"));
pw = new PrintWriter(new FileWriter("../GoogleCodeJam2014/io/output.txt"));
int n = Integer.parseInt(input.readLine());
for(int i = 0 ; i < n ; i++){
String[] st = input.readLine().split(" ");
int R = Integer.parseInt(st[0]);
int C = Integer.parseInt(st[1]);
int M = Integer.parseInt(st[2]);
pw.println("Case #"+(i+1)+":");
if(M == 0){
for(int j = 0 ; j < R ; j++){
for(int k = 0 ; k < C ; k++){
if(j == 0 && k == 0){
pw.print("c");
}else{
pw.print(".");
}
}
pw.println();
}
}else if(R >= 4 && R == C && M == R-1){
StringBuilder[] sb = new StringBuilder[R];
for(int j = 0 ; j < R ; j++){
sb[j] = new StringBuilder();
for(int k = 0 ; k < C ; k++){
if(j == 0 && k == 0){
sb[j].append("c");
}else{
sb[j].append(".");
}
}
}
for(int j = R-R/2 ; j < R ; j++){
sb[j].setCharAt(R-1, '*');
}
for(int j = R-R/2 ; j < R ; j++){
sb[R-1].setCharAt(j, '*');
}
if(R % 2 != 0){
sb[R-1].setCharAt(R-R/2-1, '*');
}
for(int j = 0 ; j < sb.length ; j++){
pw.println(sb[j]);
}
}else{
mine(R,C,M);
}
pw.flush();
}
input.close();
pw.close();
}

public static void mine(int R,int C,int M){
Queue q = new LinkedList();
BL first = new BL(R,C);
q.add(first);
boolean existed = false;
while(!q.isEmpty()){
BL tbl = q.poll();

if(tbl.mc == M){
if(isok(R,C,tbl.br,R*C-M)){
for(int j = 0 ; j < R ; j++){
for(int k = 0 ; k < C ; k++){
if(j == 0 && k == 0){
pw.print("c");
}else{
if(tbl.br[j][k]){
pw.print("*");
}else{
pw.print(".");
}
}
}
pw.println();
}
existed = true;
break;
}
}else{
/*System.out.println(tbl.x+","+tbl.y+","+tbl.muki+","+tbl.mc);
for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
if(!tbl.br[i][j]){
System.out.print(".");
}else{
System.out.print("x");
}
}
System.out.println();
}
System.out.println();*/
int x = tbl.x;
int y = tbl.y;
int muki = tbl.muki;
if(muki == 0){
if(!isEdge(R,C,x,y-1)){
BL make = new BL(R,C);
make.mc = tbl.mc+1;
for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
make.br[i][j] = tbl.br[i][j];
}
}
make.br[y-1][x] = true;
make.x = x;
make.y = y-1;
make.muki = 2;
make.refered = true;
q.add(make);
}
if(!isEdge(R,C,x-1,y)){
BL make = new BL(R,C);
make.mc = tbl.mc+1;
for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
make.br[i][j] = tbl.br[i][j];
}
}
make.br[y][x-1] = true;
make.x = x-1;
make.y = y;
make.muki = 1;
make.refered = true;
q.add(make);
}
}else if(muki == 1){
if(!isEdge(R,C,x-1,y)){
BL make = new BL(R,C);
make.mc = tbl.mc+1;
for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
make.br[i][j] = tbl.br[i][j];
}
}
if(make.br[y][x-1]){
make.mc--;
}else{
make.refered = true;
make.br[y][x-1] = true;
}
make.x = x-1;
make.y = y;
make.muki = 1;
q.add(make);
}else{
if(!isEdge(R,C,C-1,y-1) && tbl.refered){
BL make = new BL(R,C);
for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
make.br[i][j] = tbl.br[i][j];
}
}
make.mc = tbl.mc+1;
if(make.br[y-1][C-1])make.mc--;
make.x = C-1;
make.y = y-1;
make.muki = 1;
make.br[y-1][C-1] = true;
make.refered = false;
q.add(make);

make = new BL(R,C);
for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
make.br[i][j] = tbl.br[i][j];
}
}
make.mc = tbl.mc+1;
if(make.br[y-1][C-1])make.mc--;
make.br[y-1][C-1] = true;
make.refered = false;
make.x = C-1;
make.y = y-1;
make.muki = 2;
q.add(make);
}
}
}else if(muki == 2){
if(!isEdge(R,C,x,y-1)){
BL make = new BL(R,C);
make.mc = tbl.mc+1;
for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
make.br[i][j] = tbl.br[i][j];
}
}
if(make.br[y-1][x]){
make.mc--;
}else{
make.br[y-1][x] = true;
make.refered = true;
}
make.x = x;
make.y = y-1;
make.muki = 2;
q.add(make);
}else{
if(!isEdge(R,C,x-1,R-1) && tbl.refered){
BL make = new BL(R,C);
for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
make.br[i][j] = tbl.br[i][j];
}
}
make.mc = tbl.mc+1;
if(make.br[R-1][x-1])make.mc--;
make.br[R-1][x-1] = true;
make.x = x-1;
make.y = R-1;
make.muki = 1;
make.refered = false;
q.add(make);

make = new BL(R,C);
for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
make.br[i][j] = tbl.br[i][j];
}
}
make.mc = tbl.mc+1;
if(make.br[R-1][x-1])make.mc--;
make.br[R-1][x-1] = true;
make.x = x-1;
make.y = R-1;
make.muki = 2;
make.refered = false;
q.add(make);
}
}
}
}
}
if(!existed){
pw.println("Impossible");
}
}
public static boolean isEdge(int R,int C,int x,int y){
if(x < 0 || y < 0 || x == C || y == R)return true;
return false;
}

public static boolean isok(int R,int C,boolean[][] br,int rest){
if(br[0][0])return false;
Queue q = new LinkedList();
q.add(0+","+0);
rest--;
/*for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
if(!br[i][j]){
System.out.print(".");
}else{
System.out.print("x");
}
}
System.out.println();
}
System.out.println(rest);*/
boolean[][] searched = new boolean[R][C];
searched[0][0] = true;
int[] dx = {-1,0,1,-1,1,-1,0,1};
int[] dy = {-1,-1,-1,0,0,1,1,1};
while(!q.isEmpty()){
String[] st = q.poll().split(",");
int x = Integer.parseInt(st[0]);
int y = Integer.parseInt(st[1]);
boolean ok = true;
for(int i = 0 ; i < dx.length ; i++){
if(!isEdge(R,C,x+dx[i],y+dy[i])){
if(br[y+dy[i]][x+dx[i]]){
ok = false;
break;
}
}
}
if(ok){
for(int i = 0 ; i < dx.length ; i++){
if(!isEdge(R,C,x+dx[i],y+dy[i]) && !searched[y+dy[i]][x+dx[i]]){
searched[y+dy[i]][x+dx[i]] = true;
rest--;
q.add((x+dx[i])+","+(y+dy[i]));
}
}
/*for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
if(searched[i][j]){
System.out.print(".");
}else{
System.out.print("x");
}
}
System.out.println();
}
System.out.println();*/
}
}
if(rest == 0)return true;
return false;
}
}

class BL{
boolean[][] br;
int mc = 1;
int x;
int y;
int muki = 0;//1 is yoko 2 is tate
boolean refered;
BL(int R,int C){
br = new boolean[R][C];
y = R-1;
x = C-1;
br[y][x] = true;
}
}


D問題は、例年に比べて簡単でした。
勝てないおもりの時は、Kenが持ってるおもりの一番重い奴よりちょっと小さめに宣言し
(そうするとKenは一番重いおもりで勝ちに行く)
勝てる場合はKenが持ってる一番重い奴より重く宣言する
(そうするとKenは一番軽いおもりを選択する)と、全部勝てるので勝ち数が一番多くなる。


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

public class Main {

public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../GoogleCodeJam2014/io/D-large.in"));
PrintWriter pw = new PrintWriter(new FileWriter("../GoogleCodeJam2014/io/output.txt"));
int n = Integer.parseInt(input.readLine());
for(int i = 0 ; i < n ; i++){
int bk = Integer.parseInt(input.readLine());
String[] st = input.readLine().split(" ");
String[] st2 = input.readLine().split(" ");
double[] naomi = new double[bk];
double[] ken = new double[bk];
for(int j = 0 ; j < bk ; j++){
naomi[j] = Double.parseDouble(st[j]);
ken[j] = Double.parseDouble(st2[j]);
}
Arrays.sort(naomi);
Arrays.sort(ken);
pw.print("Case #"+(i+1)+": "+naoken(naomi,ken,bk));
pw.println();
pw.flush();
}
input.close();
pw.close();
}

public static String naoken(double[] naomi,double[] ken,int length){
int windex = length-1;
int lindex = 0;
int wincount = 0;
for(int i = length-1 ; i >= 0 ; i--){
if(naomi[i] > ken[windex]){
lindex++;
wincount++;
}else{
windex--;
}
}
windex = length-1;
lindex = 0;
int dwincount = 0;
for(int i = 0 ; i < length ; i++){
if(naomi[i] < ken[lindex]){
windex--;
}else{
lindex++;
dwincount++;
}
}
return dwincount+" "+wincount;
}
}


お昼はなか卯で食べる。
f0019846_10271257.jpg


夜はピザでも食ってました。
f0019846_10285220.png

  by ddrer-yossi | 2014-04-13 23:26 | 日常生活 | Comments(0)

<< Code-Strike予選とか Google Code Jam... >>

SEM SKIN - DESIGN by SEM EXE