UTPC 2011(05/14 12:00~17:00)
久し振りの投稿．
■A プログラミングコンテスト
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class Main{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
int n, m;
void run(){
n=sc.nextInt();
m=sc.nextInt();
int max=0;
for(int j=0; j<n; j++){
int a=0;
for(int i=0; i<m; i++){
a+=sc.nextInt();
}
max=max(max, a);
}
println(""+max);
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
void print(String s){
System.out.print(s);
}
void println(String s){
System.out.println(s);
}
public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}
■B (iwi)
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class Main{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
void run(){
String s=sc.next();
int ans=0;
if(s.length()%2==1){
if(!Character.isLetter(s.charAt(s.length()/2))){
ans++;
}
}
boolean[][] check=new boolean[256][256];
check['i']['i']=true;
check['w']['w']=true;
check['('][')']=true;
check[')']['(']=true;
for(int i=0; i<s.length()/2; i++){
if(!check[s.charAt(i)][s.charAt(s.length()-1-i)]){
ans++;
}
}
println(""+ans);
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
void print(String s){
System.out.print(s);
}
void println(String s){
System.out.println(s);
}
public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}
■C [[iwi]]
全探索による解法．LCSのような解法もあるようです．
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class Main{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
void run(){
String ss=sc.next();
boolean[][] check=new boolean[256][256];
check['('][')']=true;
check[')']['(']=true;
check['{']['}']=true;
check['}']['{']=true;
check['['][']']=true;
check[']']['[']=true;
int k=ss.indexOf("iwi");
int m=k;
int n=ss.length()-(k+3);
String s=ss.substring(0, k);
String t=ss.substring(k+3, ss.length());
// debug(m, n);
// debug(s, t);
int max=0;
for(int sup1=0; sup1<1<<m; sup1++){
String s1="";
for(int i=0; i<m; i++){
if(((sup1>>i)&1)==1){
s1+=s.charAt(i);
}
}
for(int sup2=0; sup2<1<<n; sup2++){
if(Integer.bitCount(sup1)==Integer.bitCount(sup2)){
String s2="";
for(int j=0; j<n; j++){
if(((sup2>>j)&1)==1){
s2+=t.charAt(j);
}
}
boolean f=true;
for(int i=0; i<s1.length(); i++){
f&=check[s1.charAt(i)][s2.charAt(s2.length()-1-i)];
}
if(f){
// debug(s1, s2);
max=max(max, s1.length()+3+s2.length());
}
}
}
}
println(max+"");
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
void print(String s){
System.out.print(s);
}
void println(String s){
System.out.println(s);
}
public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}
■D 停止問題
BFSによる解法．
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class Main{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
int n, m;
char[][] cs;
void run(){
n=sc.nextInt();
m=sc.nextInt();
cs=new char[n][m];
for(int j=0; j<n; j++){
String s=sc.next();
for(int i=0; i<m; i++){
cs[j][i]=s.charAt(i);
}
}
int[] dx={0, 0, -1, 1};
int[] dy={-1, 1, 0, 0};
LinkedList<P> que=new LinkedList<P>();
boolean[][][][] visited=new boolean[m][n][16][4];
que.offer(new P(0, 0, 0, 3));
visited[0][0][0][3]=true;
for(; !que.isEmpty();){
P p=que.poll();
// debug(p.x, p.y, p.mem, p.dir);
if(cs[p.y][p.x]=='?'){
for(int i=0; i<4; i++){
P q=new P(p.x, p.y, p.mem, p.dir);
q.dir=i;
q.x=(q.x+dx[q.dir]+m)%m;
q.y=(q.y+dy[q.dir]+n)%n;
if(!visited[q.x][q.y][q.mem][q.dir]){
que.offer(q);
visited[q.x][q.y][q.mem][q.dir]=true;
}
}
continue;
}
P q=new P(p.x, p.y, p.mem, p.dir);
switch(cs[p.y][p.x]){
case '<':
q.dir=2;
break;
case '>':
q.dir=3;
break;
case '^':
q.dir=0;
break;
case 'v':
q.dir=1;
break;
case '_':
if(q.mem==0){
q.dir=3;
}else{
q.dir=2;
}
break;
case '|':
if(q.mem==0){
q.dir=1;
}else{
q.dir=0;
}
break;
case '.':
break;
case '@':
println("YES");
return;
case '+':
q.mem=(q.mem+1)%16;
break;
case '-':
q.mem=(q.mem+15)%16;
break;
}
if(Character.isDigit(cs[p.y][p.x])){
q.mem=cs[p.y][p.x]-'0';
}
q.x=(q.x+dx[q.dir]+m)%m;
q.y=(q.y+dy[q.dir]+n)%n;
if(!visited[q.x][q.y][q.mem][q.dir]){
que.offer(q);
visited[q.x][q.y][q.mem][q.dir]=true;
}
}
println("NO");
}
class P{
int x, y;
int mem;
int dir;
P(int x, int y, int mem, int dir){
this.x=x;
this.y=y;
this.mem=mem;
this.dir=dir;
}
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
void print(String s){
System.out.print(s);
}
void println(String s){
System.out.println(s);
}
public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}
■E ファーストアクセプタンス
System.arraycopyを何故か忘れていたため，競技中はWAでした．下は競技終了後のコード．ちなみに，bでソートすればいいので，aは関係ないです．
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class Main{
Scanner sc=new Scanner(System.in);
long INF=1L<<48;
double EPS=1e-9;
int n;
R[] rs;
void run(){
n=sc.nextInt();
rs=new R[n];
for(int i=0; i<n; i++){
int a=sc.nextInt();
int b=sc.nextInt();
rs[i]=new R(a, b);
}
sort(rs, new Comparator<R>(){
@Override
public int compare(R r1, R r2){
if(r1.b!=r2.b){
return r1.b-r2.b;
}else{
return r2.a-r1.a;
}
}
});
long[][] dp=new long[n+1][n+1];
fill(dp[0], INF);
dp[0][0]=0;
for(int j=1; j<=n; j++){
System.arraycopy(dp[j-1], 0, dp[j], 0, n+1);
for(int i=0; i<j; i++){
long t=dp[j-1][i]+rs[j-1].a;
if(t<=rs[j-1].b){
dp[j][i+1]=min(dp[j][i+1], t);
}
}
// debug(dp[j]);
}
for(int i=n; i>=0; i--){
if(dp[n][i]<INF){
println(i+"");
break;
}
}
}
class R{
int a, b;
R(int a, int b){
this.a=a;
this.b=b;
}
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
void print(String s){
System.out.print(s);
}
void println(String s){
System.out.println(s);
}
public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}
■Result
400pt. 77th
途中で離脱してしまったので，簡単な問題しか解けず残念．
Eは解法が合っていましたし，A~Dも1時間程度で解けていたので，わずかながらに成長しているようです．
それにしても，沢山の強豪がいますね．今年のICPCが心配です．
