Google Code Jam 2017 Qualification Round

今日はGoogle Code Jam Qualification Round。
しかし、完全に失念してしまい、取り掛かったのは開始3時間後から。
記載しているソースコードですが、当日中ではなく、この記事は5/1に書いたものになります。

A問題は、パンケーキの表が+、裏が-で、新しい機械は連続したn枚をいっぺんに裏返せる。
このとき、解法があれば最小回数を出力し、なければIMPOSSIBLEを出力せよ。

やり方としては左から裏返っていなければ裏返していき、途中でできなくなったらIMPOSSIBLEにする。

<pre>
import java.io.*;

public class A {
static PrintWriter pw;
public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../GoogleCodeJam2017/io/A-large.in"));
pw = new PrintWriter(new FileWriter("../GoogleCodeJam2017/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int i = 0 ; i < T ; i++){
String[] strs = input.readLine().split(" ");
String s = strs[0];
int K = Integer.parseInt(strs[1]);
int result = 0;
int[] number = new int[s.length()];
for(int j = 0 ; j < s.length() ; j++){
if(s.charAt(j) == '+')number[j] = 1;
}
for(int j = 0 ; j < s.length() ; j++){
if(number[j] == 0){
if(j <= s.length() - K){
for(int k = j ; k < j + K ; k++){
if(number[k] == 0){
number[k] = 1;
}else{
number[k] = 0;
}
}
result++;
}else{
result = -1;
break;
}
}
/*for(int k = 0 ; k < s.length() ; k++){
System.out.print(number[k]);
}
System.out.println();*/
}
if(result == -1){
pw.println("Case #"+(i+1)+": IMPOSSIBLE");
}else{
pw.println("Case #"+(i+1)+": "+ result);
}
}
pw.flush();
input.close();
pw.close();
}
}

</pre>

きづけば単純だが、一番コードの書き直しを行った問題であった。方針ブレブレ。

B問題は、整数Nが与えられるとき、各桁が昇順になっている最大値を求めよという問題。
0先行や、桁が1つ落ちる時に再帰的に桁を戻っていけばよい。

<pre>
import java.io.*;

public class B {
static PrintWriter pw;
public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../GoogleCodeJam2017/io/B-large.in"));
pw = new PrintWriter(new FileWriter("../GoogleCodeJam2017/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int i = 0 ; i < T ; i++){
String s = input.readLine();
int[] num = new int[s.length()];
for(int j = 0 ; j < s.length(); j++){
num[j] = Character.digit(s.charAt(j), 10);
}

for(int j = 0 ; j < s.length() - 1 ; j++){
if(num[j] > num[j + 1]){
if(j == 0){
if(num[j] == 1){
num[j] = 0;
for(int k = j + 1 ; k < s.length() ; k++)num[k] = 9;
break;
}else{
num[j]--;
for(int k = j + 1 ; k < s.length() ; k++)num[k] = 9;
break;
}
}else{
num[j]--;
for(int k = j + 1 ; k < s.length() ; k++){
num[k] = 9;
}
j -= 2;
}
}
}

String res = "";
for(int j = 0 ; j < num.length ; j++){
if(j == 0 && num[j] == 0)continue;
res += num[j];
}
pw.println("Case #"+(i+1)+": "+res);
}
pw.flush();
input.close();
pw.close();
}
public static String addnine(int n){
String s = "";
for(int i = 0 ; i < n ; i++){
s += "9";
}
return s;
}
}

</pre>

C問題は、文章の意味を理解するのに最も時間がかかりました。
そして一番頑張ったかも。
Bath roomの区切りがあるが、人はなるべく隣に人がいない状況を好んでシャワー室を選択するとき、
K人目を埋めた時の左右の最大空きマス数を求めよという問題でした。
何か一つの場合を適当にやってみると、木構造のように分岐していくので計算で求めていく。
わかっちゃえば計算式はとても簡潔なんだけど、一番時間がかかりましたね。

<pre>
import java.io.*;

public class C {
static PrintWriter pw;
public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../GoogleCodeJam2017/io/C-large.in"));
pw = new PrintWriter(new FileWriter("../GoogleCodeJam2017/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int i = 0 ; i < T ; i++){
String[] s = input.readLine().split(" ");
long N = Long.parseLong(s[0]);
long K = Long.parseLong(s[1]);
int pow = 0;
long sum = 0;
while(true){
long getter = (long)Math.pow(2, pow);
long zenkaiamari = (long)((N - getter) % (sum + 1));
long zenkainum = (N - sum - 1) / (sum + 1);
N -= getter;
sum += getter;
System.out.println(sum);
if(K <= getter){
if(K <= zenkaiamari){
pw.println("Case #"+(i+1)+": "+ ((zenkainum + 1) / 2 + (zenkainum + 1) % 2) +" "+ (zenkainum + 1) / 2);
}else{
pw.println("Case #"+(i+1)+": "+ (zenkainum / 2 + zenkainum % 2) +" "+ zenkainum / 2);
}
break;
}else{
K -= getter;
}
pow++;
}
}
pw.flush();
input.close();
pw.close();
}
}
</pre>

D問題は明らかに面倒そうなのでやらず。65点の2438位で通過です。
久々に頭を使ったし、良い問題だなと思いました。


1問残して一段落ついたところでゲーセンへ。
ハンガリー舞曲 第5番 ~ Hungarian Dances No.5 ~ HARDを99.1% フルコン S
Google Code Jam 2017 Qualification Round_f0019846_20182538.jpg
プライド革命 WHを99.1%
Google Code Jam 2017 Qualification Round_f0019846_20192360.jpg
Strange Flow WHを98.2% フルコン S
Google Code Jam 2017 Qualification Round_f0019846_20195309.jpg
REVへ。Hi UNLIMITEDをCool2の99% ULT フルコン。これ、等速なんですよね…。
Google Code Jam 2017 Qualification Round_f0019846_20201645.jpg
最終的に42840まで伸ばしました。
Google Code Jam 2017 Qualification Round_f0019846_20204463.jpg
ポケモンGOも。6占領。
Google Code Jam 2017 Qualification Round_f0019846_20205290.jpg

  by ddrer-yossi | 2017-04-08 20:16 | reflec beat

<< 早く退勤しつつ、リフレク、RE... Hi詰めとよろしいおにく >>

SEM SKIN - DESIGN by SEM EXE