Codeforces初参戦

今日はIETFの英文仕様を読む作業をしつつ、資料を作成していました。
夜はDDR StrikeでDP中心プレー。割と頑張れたような気がするけど、負荷はゆるゆる。

5ボールカスケード454回
6x,4 4,6x 8往復
エクサボールで4ボールファウンテンを200回とかそんなの。

んで、プログラミングの方はCodeforcesに初参戦。
まあ、GCJJの前段階な練習にもなる感じでした。
というわけで、入出力の仕様に苦戦するのは当然の結果でした。

1問目は、バスの乗客が乗り降り、先に降りてから乗るというルールで、人数が最大になる値を返すプログラム。

import java.util.*;

public class Test {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int stops = input.nextInt();
int oriru[] = new int[stops];
int noru[] = new int[stops];

for(int i= 0 ; i < stops ; i++){
oriru[i] = input.nextInt();
noru[i] = input.nextInt();
}

System.out.println(minimumPassenger(stops,oriru,noru));
}

public static int minimumPassenger(int c,int a[],int b[]){
int num = 0;
int maxnum = 0;
for(int i = 0 ; i < c ; i++){
num -= a[i];
num += b[i];
maxnum = Math.max(maxnum,num);
}
return maxnum;
}
}

こんなのはもう、3分で片付けたかった。仕様に苦戦とか。

2問目は、狼と豚がいる。狼は隣接している豚1匹だけ食べる。最大何匹食べられるかという問題。
ちなみに全く根拠はないのですが、マス目が狼の場合、上、左、右、下の順に調べて行って、豚であった瞬間カウントして豚を消すという作業をしていました。なんとなく左上から右下に向かっていけばいいんじゃないという。結果Acceptedだったわけですが、腑に落ちないですね。

import java.util.*;

public class Test {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int row = input.nextInt();
int col = input.nextInt();
String line = "";
input.nextLine();
char[][] map = new char[row][col];
//String[] st = new String[row];
for(int i = 0 ; i < row ; i++){
line = input.nextLine();
//System.out.println(line.charAt(2));
for(int j = 0 ; j < col ; j++){
map[i][j] = line.charAt(j);
}
//System.out.println(st[i]);
}

System.out.print(pigEaten(row,col,map));

}

public static int pigEaten(int row, int col, char[][] map){
int count = 0;
for(int i = 0 ; i < row ; i++){
for(int j = 0 ; j < col ; j++){
if(map[i][j] == 'W'){
if(isField(row,col,i-1,j) && map[i-1][j] =='P'){
map[i-1][j] = '#';
map[i][j] = '#';
count++;
continue;
}
if(isField(row,col,i,j-1) && map[i][j-1] =='P'){
map[i][j-1] = '#';
map[i][j] = '#';
count++;
continue;
}
if(isField(row,col,i,j+1) && map[i][j+1] =='P'){
map[i][j+1] = '#';
map[i][j] = '#';
count++;
continue;
}
if(isField(row,col,i+1,j) && map[i+1][j] =='P'){
map[i+1][j] = '#';
map[i][j] = '#';
count++;
continue;
}
}
}
}
return count;
}


public static boolean isField(int row,int col,int i,int j){
if(i < 0 || j < 0 || i == row || j == col){
return false;
}
return true;
}
}


コードも汚いです。C問題は、多分木において、親子関係にあるものは同じグループに所属させてはならないという条件で、最小何グループできるかという問題。
例えば、2の上司は1、3の上司も1の場合、1と2、1と3は一緒にしてはならないので、
結果的に1と2,3の2グループとなる。

これ、本番中は色々と錯綜していましたが、気づけば超簡単な問題でした。
我ながら本番終了後に綺麗な解答を思いついたものだなと。

グループの最小数 = 木の深さ になるということに気づけばおしまいでした。
それで書いた答案がこれ。

import java.util.*;

public class Test {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int employee = input.nextInt();
input.nextLine();
int[] subemp = new int[employee+1];
for(int i = 1 ; i < subemp.length ; i++){
subemp[i] = input.nextInt();
}
System.out.println(isGroup(employee,subemp));


}

public static int isGroup(int employee,int[] subemp){
int count = 0;
for(int i = 1 ; i < employee+1 ; i++){
int n = subemp[i];
int tmpcount = 1;
while(n != -1){
n = subemp[n];
tmpcount++;
}
count = Math.max(count,tmpcount);
}
return count;
}
}

ちなみにmain関数部分が入力読み込みで、isGroupが問題の関数部分です。
美しい解が思いつくとやみつきになるので、競技プログラミングはやめられない。

D,Eは問題を見て諦めました。まあ、初回で○○---だったのでまずまずでしょう。

  by ddrer-yossi | 2011-09-15 23:16 | 日常生活 | Comments(0)

<< ゲーセン廃人 資料作成にとりかかる >>

SEM SKIN - DESIGN by SEM EXE