タグ:Google Code Jam ( 6 ) タグの人気記事

 

母の日とか姉と飲むとか、GCJR1C

今日は母の日ということで、JETSTREAM PRIMEを贈りました。
私も自分用に買いましたが。
f0019846_15133774.jpg


朝はCross beats!
雨の音が虹を呼ぶMasterで100%ULT
f0019846_16515113.png


お昼は久しぶりに姉と母で集合してランチを食べる。
f0019846_1514073.jpg


f0019846_1514890.jpg


f0019846_151417100.jpg


f0019846_15142787.jpg


f0019846_15143892.jpg


ちょっと贅沢な感じでした。

その後は家で過ごす、が、午後3時に室温が30度となっていた。
f0019846_15164948.jpg


メギツネMasterをイベント前になんとか解禁。初見フルコン。
f0019846_16523327.png


Google Code Jam前にゲーセンへ。

AGEHA(A) フルコン
f0019846_15174798.jpg


Recollection(A) フルコン
f0019846_1518765.jpg


Scripted Connection A mix(A)easy
f0019846_15182822.jpg


その後はGoogle Code Jam R1Cへ。

A問題のPart elfは、両親のエルフ率の1/2を受け継ぐ。
今p/qエルフのとき、何世代前に100%エルフがいたか、その最小値を求める問題。

Smallでは愚直に約分してから、何世代目なのかを求め、分子を徐々に減らして世代を求める。

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("../GoogleCodeJam2014R1A/io/A-small-attempt3.in"));
pw = new PrintWriter(new FileWriter("../GoogleCodeJam2014R1A/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int k = 0 ; k < T ; k++){
String[] s = input.readLine().split("\\/");
long l1 = Long.parseLong(s[0]);
long l2 = Long.parseLong(s[1]);
for(int i = 2 ; i <= l1 ; i++){
if(l1 % i == 0 && l2 % i == 0){
l1 /= i;
l2 /= i;
i--;
}
}
int count = 0;
long nums = l2;
boolean isok = true;
while(nums != 1){
if(nums % 2 != 0){
isok = false;
break;
}else{
nums /= 2;
count++;
}
}
if(!isok){
pw.println("Case #"+(k+1)+": impossible");
}else{
if(l1*2 >= l2){
pw.println("Case #"+(k+1)+": 1");
}else{
l1 -= 1;
if(l1 == 0){
pw.println("Case #"+(k+1)+": "+count);
}else{
System.out.println(l1+","+l2+","+count+","+isok);
while(l1 != 1){
l1 /= 2;
count--;
}
if(!isok){
pw.println("Case #"+(k+1)+": impossible");
}else{
pw.println("Case #"+(k+1)+": "+count);
}
}
}
}
pw.flush();
}
input.close();
pw.close();
}
}


Largeは、約数の計算方法をユークリッド互除法で求めた上で、同じようにやる。

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("../GoogleCodeJam2014R1A/io/A-large.in"));
pw = new PrintWriter(new FileWriter("../GoogleCodeJam2014R1A/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int k = 0 ; k < T ; k++){
String[] s = input.readLine().split("\\/");
long l1 = Long.parseLong(s[0]);
long l2 = Long.parseLong(s[1]);
long num = euclid(l1,l2);
/*for(int i = 2 ; i <= l1 ; i++){
if(l1 % i == 0 && l2 % i == 0){
l1 /= i;
l2 /= i;
i--;
}
}*/
l1 /= num;
l2 /= num;
int count = 0;
long nums = l2;
boolean isok = true;
while(nums != 1){
//System.out.println(nums);
if(nums % 2 != 0){
isok = false;
break;
}else{
nums /= 2;
count++;
}
}
if(!isok){
pw.println("Case #"+(k+1)+": impossible");
}else{
if(l1*2 >= l2){
pw.println("Case #"+(k+1)+": 1");
}else{
l1 -= 1;
if(l1 == 0){
pw.println("Case #"+(k+1)+": "+count);
}else{
System.out.println(l1+","+l2+","+count+","+isok);
while(l1 != 1){
l1 /= 2;
count--;
//System.out.println(nums);
}
if(!isok){
pw.println("Case #"+(k+1)+": impossible");
}else{
pw.println("Case #"+(k+1)+": "+count);
}
}
}
}
pw.flush();
}
input.close();
pw.close();
}

public static long euclid(long a, long b) {
long r = a % b;
while (r > 0) {
a = b;
b = r;
r = a % b;
}
return b;
}
}


B問題は、問題文の理解とサンプルケースがどうしても合わないので飛ばす。
C問題は、マス目が与えられている時、Kマス以上の包含関係を持つには、
いくつ石を置く必要があるかという問題。

Smallだけ通そうと必死でしたが、通りませんでした。
結果は2614位。R1落ちです。

その後は姉と話があるということで若干飲みに行きました。
f0019846_15313249.jpg


1時間程度なので飲んでしゃべる程度。食べ物も頼まず、1ドリンク。
2014年だけに2014円。
f0019846_1532088.jpg

  by ddrer-yossi | 2014-05-11 23:12 | 日常生活

Google Code Jam 2014 R1A

今日はGCJR1Aに参戦。

A問題は、コンセントがあって、スイッチをオンオフにして、後のコンセントに一致するまでの
最短回数を求める問題。
Smallは制約がしょぼいので、全探索でいけそうということでそれでやる。
意外に時間がかかった。


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("../GoogleCodeJam2014R1A/io/A-small-attempt0.in"));
pw = new PrintWriter(new FileWriter("../GoogleCodeJam2014R1A/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int k = 0 ; k < T ; k++){
String[] s = input.readLine().split(" ");
int N = Integer.parseInt(s[0]);
int L = Integer.parseInt(s[1]);
String[] out = new String[N];
String[] dev = new String[N];
s = input.readLine().split(" ");
for(int i = 0 ; i < N ; i++){
out[i] = s[i];
}
s = input.readLine().split(" ");
for(int i = 0 ; i < N ; i++){
dev[i] = s[i];
}
int index = 0;
int min = Integer.MAX_VALUE;
while(true){
String st = Integer.toBinaryString(index);
if(st.length() > L)break;

boolean[] devices = new boolean[N];

int zeroinsert = L-st.length();
String newst = "";
for(int i = 0 ; i < zeroinsert ; i++){
newst += "0";
}
newst += st;

StringBuilder[] sb = new StringBuilder[N];
for(int i = 0 ; i < N ; i++){
sb[i] = new StringBuilder();
sb[i].append(out[i]);
}
int onecount = 0;
for(int i = 0 ; i < L ; i++){
if(newst.charAt(i) == '1'){
onecount++;
for(int j = 0 ; j < N ; j++){
if(sb[j].charAt(i) == '0'){
sb[j].setCharAt(i, '1');
}else{
sb[j].setCharAt(i, '0');
}
}
}
}
int count = 0;
for(int i = 0 ; i < N ; i++){
for(int j = 0 ; j < N ; j++){
if(sb[i].toString().equals(dev[j])){
count++;
break;
}
}
}
if(count == N)min = Math.min(min,onecount);
index++;
}
if(min == Integer.MAX_VALUE){
pw.println("Case #"+(k+1)+": NOT POSSIBLE");
}else{
pw.println("Case #"+(k+1)+": "+min);
}
pw.flush();
}
input.close();
pw.close();
}
}


Largeは思いつかなかったが、コンセントを一箇所固定して、
そのスイッチの動かし方をしたら他がきっちり一致するかどうかを調べて、
最短回数となるパターンを出力すれば良い。

たとえば
01 11 10
11 00 10

なら、01-11を固定すると最初だけスイッチを入れる仕組みになる。
この変更点を加えた上で、残りのコンセントで一致させられるかどうかを見る。
O(n^2)で可能。

その後はB問題へ、
木構造のグラフが与えられて、幾つかの頂点を削除して二分木を作るとき、
最少何個の頂点を削除すれば二分木ができるかという問題。

Smallは制約が小さいので全探索でいけそうと思ったが、バグが取れないのか通せず。
結果は8点で2532位。これは厳しい。

その後は某所で親を連れて皿うどんを食べに行きました。
f0019846_052352.jpg


その後はゲーセン。
Into The Sunlight(H) フルコン
f0019846_081244.jpg


夜は串焼きを食べに行きました。食べ放題かつ飲み放題!
f0019846_065444.jpg


f0019846_0775.jpg


f0019846_072511.jpg


TCO R1C パラレルですが、Arenaの不具合があったので、参加を取りやめました。

後は初めて例のアレを行いました。

  by ddrer-yossi | 2014-04-26 23:23 | Beatmania

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 | 日常生活

Google Code Jam 2014 Qualification Round、TCOR1A

今日はGoogle Code Jam 2014 Qualification Round.
朝8時に起きて、挑みました。

A、Bはすんなり。Cは面倒そうなので、Dから始めて、
大体2時間でここまで終える。
Cは例外処理が多く、相当苦戦を強いられた。
終わってみれば6時間経っていた。

夜はゲーセンに少し行った上で、つけ麺を食べに行きました。鳥系。
f0019846_1111847.jpg


夜はTCO R1Aに参加。

easyは、文字列Sと数値Lが与えられて、
L字選択してソートして、後の文字を消去する動作を行った時、
辞書順で一番前に来る文字列を生成せよという問題。

後ろから全部試せば良い。そうすると辞書順最善になる。

import java.util.Arrays;

public class EllysSortingTrimmer {

public String getMin(String S, int L) {
int length = S.length();
String s = S;
for(int i = length-L ; i >= 0 ; i--){
String bef = s.substring(0,i);
String sub = s.substring(i,i+L);
char[] c = sub.toCharArray();
Arrays.sort(c);
s = bef+new String(c);
}
return s;
}

}


mediumも文字列問題。
文字列Lと最長距離Dが与えられるとき、
Lの文字列をソートしてできる辞書順最小の文字列を答えよ。
ただし、ソートにおける各文字は元の位置からD文字以下しか移動できない。
結局どれを動かすのが最善になるのか考えて頭痛くなってやめました。

思いつくのが遅かったので結局ぐだぐだな順位に。1248->1228

  by ddrer-yossi | 2014-04-12 23:31 | TopCoder

僕と仕事とOB会。 GCJ Round2

今日は朝仕事で、MySQLとPHPのバージョン更新を行いました。
が、依存関係がどうこうと言われ、解決できませんでした。
ちなみにWindows環境ではなく、CentOSです。

お昼は唐揚げ弁当。
f0019846_1473326.jpg


帰宅前に一旦ゲーセンへ。

f0019846_1464229.jpg


裏表が93%。

帰宅後はOB会のため渋谷へ。
公開できる写真が限られていますがこんな感じです。

f0019846_1513025.jpg


f0019846_1514233.jpg


某社の方といろいろなお話ができて、有意義な時間を過ごせました。
が、あまり話しすぎて、GCJに走って帰宅して微妙に間に合わなかったのは宜しくなかったです。

取り敢えずA問題を読んでみるも、文章長すぎてテンパッて無理だと悟ってBへ。
これはSmallとLarge通せばワンチャンあるんじゃないかという希望で
コーディングを行いましたが、結局Smallすら通せず。
でもこれ、適当に左上から並べていっても大丈夫だよね・・・という。
後にこれは、ランダムを使っても良いということが。

まあ、できていないのでソースは上げないことにします。
ということで提出すらできず。僕の今年のGoogle Code Jamは、ここで終わりました。

  by ddrer-yossi | 2012-05-26 23:45 | 日常生活

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