Google Code Jam 2013 Qualification Round

朝9時スタートということですが、10分ほど遅れて開始。

A問題。素直にタテ・ヨコ・ナナメの勝敗判定をやるだけ。
一瞬勝敗シミュレートかと思って焦ったが、違った。


import java.util.*;
import java.io.*;
import java.math.BigDecimal;

public class Test {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/A-large.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int n = input.nextInt();
for(int i = 0 ; i < n ; i++){
String[] s = new String[4];
for(int j = 0 ; j < 4 ; j++){
s[j] = input.next();
}
pw.print("Case #"+(i+1)+": "+win(s));
pw.println();
}
input.close();
pw.flush();
pw.close();
}

public static String win(String[] s){
for(int i = 0 ; i < 4 ; i++){
int Tcount = 0;
int Ocount = 0;
int Xcount = 0;
for(int j = 0 ; j < 4 ; j++){
if(s[i].charAt(j) == 'X'){
Xcount++;
}else if(s[i].charAt(j) == 'O'){
Ocount++;
}else if(s[i].charAt(j) == 'T'){
Tcount++;
}
}
if(Xcount == 4 || (Xcount == 3 && Tcount == 1))return "X won";
if(Ocount == 4 || (Ocount == 3 && Tcount == 1))return "O won";
}

for(int i = 0 ; i < 4 ; i++){
int Tcount = 0;
int Ocount = 0;
int Xcount = 0;
for(int j = 0 ; j < 4 ; j++){
if(s[j].charAt(i) == 'X'){
Xcount++;
}else if(s[j].charAt(i) == 'O'){
Ocount++;
}else if(s[j].charAt(i) == 'T'){
Tcount++;
}
}
if(Xcount == 4 || (Xcount == 3 && Tcount == 1))return "X won";
if(Ocount == 4 || (Ocount == 3 && Tcount == 1))return "O won";
}

int Tcount = 0;
int Ocount = 0;
int Xcount = 0;
for(int i = 0 ; i < 4 ; i++){
if(s[i].charAt(i) == 'X'){
Xcount++;
}else if(s[i].charAt(i) == 'O'){
Ocount++;
}else if(s[i].charAt(i) == 'T'){
Tcount++;
}
if(Xcount == 4 || (Xcount == 3 && Tcount == 1))return "X won";
if(Ocount == 4 || (Ocount == 3 && Tcount == 1))return "O won";
}

Tcount = 0;
Ocount = 0;
Xcount = 0;
for(int i = 0 ; i < 4 ; i++){
if(s[i].charAt(3-i) == 'X'){
Xcount++;
}else if(s[i].charAt(3-i) == 'O'){
Ocount++;
}else if(s[i].charAt(3-i) == 'T'){
Tcount++;
}
if(Xcount == 4 || (Xcount == 3 && Tcount == 1))return "X won";
if(Ocount == 4 || (Ocount == 3 && Tcount == 1))return "O won";
}
int counter = 0;
for(int i = 0 ; i < 4 ; i++){
for(int j = 0 ; j < 4 ; j++){
if(s[i].charAt(j) != '.'){
counter++;
}
}
}
if(counter == 16){
return "Draw";
}else{
return "Game has not completed";
}
}

}


B問題。まっすぐに進む芝刈り機があって、ある芝の形にできるかどうかという問題。
上下左右のどこかしらにある位置より低い芝がなければ作れるので、全位置に関して調べれば良い。


import java.util.*;
import java.io.*;
import java.math.BigDecimal;

public class Test {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/B-large.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int n = input.nextInt();
for(int i = 0 ; i < n ; i++){
int row = input.nextInt();
int col = input.nextInt();
int[][] rawn = new int [row][col];
for(int j = 0 ; j < row ; j++){
for(int k = 0 ; k < col ; k++){
rawn[j][k] = input.nextInt();
}
}
pw.print("Case #"+(i+1)+": "+win(row,col,rawn));
pw.println();
}
input.close();
pw.flush();
pw.close();
}

public static String win(int row,int col,int[][] rawn){
boolean[] isnum = new boolean[100];
for(int i = 0 ; i < row ; i++){
for(int j = 0 ; j < col ; j++){
isnum[rawn[i][j]-1] = true;
}
}
for(int i = 0 ; i < isnum.length ; i++){
if(isnum[i]){
for(int j = 0 ; j < row ; j++){
for(int k = 0 ; k < col ; k++){
if(rawn[j][k] == (i+1)){
if(!hantei(j,k,rawn,(i+1),row,col))return "NO";
}
}
}
}
}
return "YES";
}

public static boolean hantei(int j,int k,int[][] rawn,int len,int row,int col){
boolean rok = true;
boolean cok = true;
for(int i = 0 ; i < col ; i++){
if(rawn[j][i] > len){
rok = false;
break;
}
}

for(int i = 0 ; i < row ; i++){
if(rawn[i][k] > len){
cok = false;
break;
}
}
if(rok || cok){
return true;
}else{
return false;
}
}

}


C問題は、二乗して回文になり、かつ二乗前の数値も回文である数の個数を
AからBの範囲で求めるという問題。

ここのlargeまではすんなり求まり、large-2でどうするかというところで、
歯医者に行く時間になったので、中断して歯医者へ。

歯の型を取ってもらって終了。
ゲーセンには1クレだけ行く。route 80sでフルコンできずに苦しんだ。

帰宅後はC-large2を考える。
出力してみて法則を見つけたので、これらの数値だけ調べればいいんじゃないかと思う。
ただし、0,1,2に関してすべて調べると、3^50となり、残念ながら無理。
さらに法則を見て、0のときと1のときをそれぞれ分けて再帰的に数を作って、出力させたものを、
食わせるという手法で戦った。この処理自体は8分近くかかったが、
large-2には影響しないので、後はこの出力を配列に読み込ませて、large-2で使うだけでした。


import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class Test {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/C-large-2.in"));
Scanner input2 = new Scanner(new FileReader("./iothings/output50.txt"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
ArrayList lst = new ArrayList();

/*lst.add(new BigInteger("1"));
lst.add(new BigInteger("2"));
lst.add(new BigInteger("3"));
for(int i = 2 ; i <= 50 ; i++){
goesone(i,"",lst);
goestwo(i,"",lst);
}
pw.println(lst.size());
for(int i = 0 ; i < lst.size(); i++){
pw.println(lst.get(i));
}*/

int listnum = input2.nextInt();
for(int i = 0 ; i < listnum ; i++){
lst.add(new BigInteger(input2.next()));
}
int n = input.nextInt();
for(int i = 0 ; i < n ; i++){
BigInteger A = new BigInteger(input.next());
BigInteger B = new BigInteger(input.next());
pw.print("Case #"+(i+1)+": "+win(A,B,lst));
pw.println();
}
input.close();
pw.flush();
pw.close();
}

public static int win(BigInteger A,BigInteger B,ArrayList lst){
int sum = 0;
for(int i = 0 ; i < lst.size(); i++){
BigInteger Cc = lst.get(i).multiply(lst.get(i));
if(Cc.compareTo(A) >= 0 && Cc.compareTo(B) <= 0){
sum++;
}else{
if(Cc.toString().length() > B.toString().length())break;
}
}
return sum;
}

public static void goesone(int length,String s,ArrayList lst){
if(s.length() == 0 && length % 2 == 1){
for(int i = 0 ; i <= 2 ; i++){
goesone(length,i+"",lst);
}
}else{
for(int i = 0 ; i <= 1 ; i++){
StringBuilder sb = new StringBuilder(s);
sb.insert(0, i);
sb.insert(sb.length(), i);
//System.out.println(sb);
if(sb.length() == length){
if(sb.charAt(0) != '0'){
BigInteger moto = new BigInteger(sb.toString());
BigInteger bs = moto.multiply(moto);
StringBuilder sb2 = new StringBuilder(bs.toString());
StringBuilder sb3 = new StringBuilder(bs.toString()).reverse();
if(sb2.toString().equals(sb3.toString()))lst.add(moto);
}
}else{
goesone(length,sb.toString(),lst);
}
}
}
}

public static void goestwo(int length,String s,ArrayList lst){
if(s.length() == 0 && length % 2 == 1){
for(int i = 0 ; i <= 1 ; i++){
goestwo(length,i+"",lst);
}
}else{
StringBuilder sb = new StringBuilder(s);
if(sb.length() == length-2){
sb.insert(0, 2);
sb.insert(sb.length(), 2);

BigInteger moto = new BigInteger(sb.toString());
BigInteger bs = moto.multiply(moto);
StringBuilder sb2 = new StringBuilder(bs.toString());
StringBuilder sb3 = new StringBuilder(bs.toString()).reverse();
if(sb2.toString().equals(sb3.toString()))lst.add(moto);
}else{
sb.insert(0, 0);
sb.insert(sb.length(), 0);
goestwo(length,sb.toString(),lst);
}
}
}
}


D問題も考えてましたが、時間内に解けないので、諦めてゲーセンへ。

route 80sフルコンから。

Google Code Jam 2013 Qualification Round_f0019846_1634425.jpg


mosaic難ついた。
Google Code Jam 2013 Qualification Round_f0019846_1635618.jpg


ついでにギガデリも!
Google Code Jam 2013 Qualification Round_f0019846_16352863.jpg


白壁灰も!
Google Code Jam 2013 Qualification Round_f0019846_16362337.jpg


締めはポップンで。
Google Code Jam 2013 Qualification Round_f0019846_16364284.jpg




1,1
2,4
3,9
11,121
22,484
101,10201
111,12321
121,14641
202,40804
212,44944
1001,1002001
1111,1234321
2002,4008004
10001,100020001
10101,102030201
10201,104060401
11011,121242121
11111,123454321
11211,125686521
20002,400080004
20102,404090404
100001,10000200001
101101,10221412201
110011,12102420121
111111,12345654321
200002,40000800004
1000001,1000002000001
1001001,1002003002001
1002001,1004006004001
1010101,1020304030201
1011101,1022325232201
1012101,1024348434201
1100011,1210024200121
1101011,1212225222121
1102011,1214428244121
1110111,1232346432321
1111111,1234567654321
2000002,4000008000004
2001002,4004009004004
10000001,100000020000001
10011001,100220141022001
10100101,102012040210201
10111101,102234363432201
11000011,121000242000121
11011011,121242363242121
11100111,123212464212321
11111111,123456787654321
20000002,400000080000004
100000001,10000000200000001
100010001,10002000300020001
100020001,10004000600040001
100101001,10020210401202001
100111001,10022212521222001
100121001,10024214841242001
101000101,10201020402010201
101010101,10203040504030201
101020101,10205060806050201
101101101,10221432623412201
101111101,10223454745432201
110000011,12100002420000121
110010011,12102202520220121
110020011,12104402820440121
110101011,12122232623222121
110111011,12124434743442121
111000111,12321024642012321
111010111,12323244744232321
111101111,12343456865434321
111111111,12345678987654321
200000002,40000000800000004
200010002,40004000900040004
1000000001,1000000002000000001
1000110001,1000220014100220001
1001001001,1002003004003002001
1001111001,1002223236323222001
1010000101,1020100204020010201
1010110101,1020322416142230201
1011001101,1022123226223212201
1011111101,1022345658565432201
1100000011,1210000024200000121
1100110011,1210242036302420121
1101001011,1212203226223022121
1101111011,1212445458545442121
1110000111,1232100246420012321
1110110111,1232344458544432321
1111001111,1234323468643234321
2000000002,4000000008000000004

  by ddrer-yossi | 2013-04-13 23:05 | Beatmania

<< 友人と池袋ラウンドワンへ。 TopCoder SRM 57... >>

SEM SKIN - DESIGN by SEM EXE