PKU JudgeOnline
TopCoderの方で詰まったので気分転換にPku JudgeOnlineの方に移る．こっちはときやすそうな問題を選んで解いていったのですんなりいった．
- 解いた問題
以下ソース
Pku3173
出力をみて，規則性を予測しろという問題は初めて見た気がする．まあ，すぐにわかる類のやつなので問題なし．
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int s = sc.nextInt();
show(n,s);
}
static void show(int n,int s){
int arr[] = new int[n];
arr[0] = s;
for(int i=1;i<arr.length;i++){
arr[i] = arr[i-1]+i;
}
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length;j++){
int val = arr[j]+i;
val = val - 9 * ((val-1)/9);
if(j<i)System.out.print(" ");
else System.out.print(val);
System.out.print(" ");
}
System.out.println();
}
System.out.println();
}
}
Pku3176
単なるDP
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[][] = new int[n][n];
for(int i=0;i<arr.length;i++){
for(int j=0;j<=i;j++){
arr[i][j] = sc.nextInt();
}
}
int memo[][] = new int[n][n];
memo[0][0] = arr[0][0];
for(int i=0;i<n-1;i++){
for(int j=0;j<=i;j++){
int cp = memo[i][j];
memo[i+1][j] = Math.max(memo[i+1][j],arr[i+1][j]+cp);
memo[i+1][j+1] = Math.max(memo[i+1][j+1],arr[i+1][j+1]+cp);
}
}
int max = 0;
for(int i=0;i<memo.length;i++){
max = Math.max(memo[n-1][i],max);
}
System.out.println(max);
}
}
Pku3183
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
int start = 0;
while(start<arr.length){
int st = isUp(start, arr);
System.out.println(st+1);
int down = isDown(st, arr);
start = down+1;
}
}
static int isDown(int start,int arr[]){
for(int i=start;i<arr.length-1;i++){
if(arr[i]<=arr[i+1]){
return i;
}
}
return arr.length-1;
}
static int isUp(int start,int arr[]){
for(int i=start;i<arr.length-1;i++){
if(arr[i]>=arr[i+1]){
return i;
}
}
return arr.length-1;
}
}
Pku3194
flood fill
package pku3194;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true){
int n = sc.nextInt();
if(n==0)break;
int arr[][] = new int[n][n];
for(int i=1;i<n;i++){
for(int j=0;j<n;j++){
int x = sc.nextInt();
int y = sc.nextInt();
arr[x-1][y-1] = i;
}
}
Set<Integer> used = new HashSet<Integer>();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int val = arr[i][j];
if(used.contains(val))continue;
if(val<0)continue;
used.add(val);
fill(i,j,val,arr);
}
}
boolean flag = true;
l:for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int val = arr[i][j];
if(val>=0){
flag = false;
break l;
}
}
}
if(flag){
System.out.println("good");
}else{
System.out.println("wrong");
}
}
}
static int dx[] ={1,-1,0,0};
static int dy[] ={0,0,1,-1};
static void fill(int x,int y,int val,int arr[][]){
arr[x][y] = -1;
for(int i=0;i<dx.length;i++){
try{
int nx = x + dx[i];
int ny = y + dy[i];
if(arr[nx][ny]==val){
fill(nx,ny,val,arr);
}
}catch (Exception e) {
// TODO: handle exception
}
}
}
}
Pku3201
Little Quilt なる言語のインタプリタを書けという問題．でQuiltのクラスを書いたところで思ったのがJavaにeval欲しいよねと，eval("sew(turn(sew(B,turn(B))),A)")とかで答えが返ってくれば一瞬なのにと思った．まあ，なくてもこの構文解析はそんなに大変ではない．
入力がどうも１行に複数の命令が来ているっぽくそこではまった．(turn(A);B;みたいな)
import java.util.Scanner;
class Quilt{
private char arr[][];
private final static char Aarr[][] = {{'/','/'},{'/','+'}};
private final static char Barr[][] = {{'-','-'},{'-','-'}};
public final static Quilt A = new Quilt(Aarr);
public final static Quilt B = new Quilt(Barr);
public Quilt(char arr[][]){
this.arr = arr;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for(char a[]:arr){
for(char c:a){
sb.append(c);
}
sb.append('\n');
}
return sb.toString();
}
public int getWidth(){
return arr[0].length;
}
public int getHeight(){
return arr.length;
}
private static char trance(char c){
switch (c) {
case '|':
return '-';
case '-':
return '|';
case '\\':
return '/';
case '/':
return '\\';
default:
return c;
}
}
public static Quilt turn(Quilt q){
char rotate[][] = new char[q.getWidth()][q.getHeight()];
for(int i=0;i<q.getWidth();i++){
for(int j=0;j<q.getHeight();j++){
rotate[i][j] = trance(q.arr[q.getHeight()-1-j][i]);
}
}
return new Quilt(rotate);
}
public static Quilt sew(Quilt a, Quilt b) throws Exception{
if(a.getHeight() != b.getHeight()){
throw new Exception();
}
char concat[][] = new char[a.getHeight()][a.getWidth() + b.getWidth()];
for(int i=0;i<a.getHeight();i++){
for(int j=0;j<a.getWidth();j++){
concat[i][j] = a.arr[i][j];
}
}
for(int i=0;i<a.getHeight();i++){
for(int j=0;j<b.getWidth();j++){
concat[i][j+a.getWidth()] = b.arr[i][j];
}
}
return new Quilt(concat);
}
}
class Evaluator{
private static Quilt es(String str) throws Exception{
Quilt a = eval2(str);
//skip ,
if(str.charAt(index)!=',')throw new Exception();
index++;
Quilt b = eval2(str);
// skip )
if(str.charAt(index)!=')')throw new Exception();
index++;
return Quilt.sew(a, b);
}
private static Quilt et(String str) throws Exception{
Quilt q = eval2(str);
// skip )
if(str.charAt(index)!=')')throw new Exception();
index++;
return Quilt.turn(q);
}
private static Quilt eval2(String str) throws Exception{
switch (str.charAt(index)) {
case 'A':
index++;
return Quilt.A;
case 'B':
index++;
return Quilt.B;
case 's':
//skip s(
if(str.charAt(index+1)!='(')throw new Exception();
index +=2;
return es(str);
case 't':
//skip t(
if(str.charAt(index+1)!='(')throw new Exception();
index +=2;
return et(str);
default:
break;
}
return null;
}
private static int index;
public static Quilt eval(String str) throws Exception{
str = str.replace(" ", "");
str = str.replace("sew", "s");
str = str.replace("turn", "t");
index = 0;
Quilt res = eval2(str);
if(str.charAt(index)!=';')throw new Exception();
return res;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = "";
int cnt = 1;
while(sc.hasNext()){
String line = sc.next();
str += line;
}
String arr[] = str.split(";");
for(String s:arr){
System.out.printf("Quilt %d:\n",cnt++);
try{
System.out.print(Evaluator.eval(s+";"));
}catch (Exception e) {
System.out.println("error");
}
}
}
}
