BottomCoder SRM 376 div2
| points | result | time |
|---|---|---|
| 250 | AC | 3.5m |
| 500 | AC | 13m |
| 1000 | WA | ? |
実装ゲーが多かったような。
250
文字列documentの連続する!,?について、?がひとつでも含まれていれば?一つにまとめ、それ以外は!一つにまとめるものとするとき、できあがる文字列を答えよ。
'?'の数、'!'の数をそれぞれ数えて、それ以外の文字が出たときにまとめる処理をする。最後に処理させるために、'?','!'以外の文字をあらかじめ加えておいて、あとで消している。
public class PunctuationCleaner { public String clearExcess(String document) { StringBuilder sb = new StringBuilder(); int q = 0; int e = 0; document += " "; for(int i = 0;i < document.length();i++){ char c = document.charAt(i); if(c == '?'){ q++; }else if(c == '!'){ e++; }else{ if(q+e > 0){ if(q > 0){ sb.append('?'); }else{ sb.append('!'); } e = q = 0; } sb.append(c); } } sb.deleteCharAt(sb.length()-1); return sb.toString(); } }
500
線路が'-','|','+','S', また線路でない箇所'.'のいずれかでかかれたマップ(<=10*10)が与えられる。それぞれ、左右方向、上下方向、上下左右に行ける線路を表している。マップ上の文字'S'からfuelステップだけ、隣り合う線路上を移動できるとき、行けるマスの総数を求めよ。
'S'は実質'+'と同じ。BFSでたどる。'+','-'から横に行けるマスは'+'か'-'でないといけないし、'+','|'から縦に行けるマスは'+'か'|'でないといけない。
各マスに、そのマスにたどり着いたときの最大の残り燃料+1(:=maxfuel)を割り当てるようにする('S'のところはfuel+1)と、1以上のところが該当するマスとなって都合が良い。また、あるマスを見るときに残っている燃料がmaxfuel以下ならそれ以上探索する必要がない。
こういうのテンプレ化して速く書けるようにしようかしら。
import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; public class Trainyard { public int reachableSquares(String[] layout, int fuel) { int n = layout.length; int m = layout[0].length(); char[][] l = new char[n][m]; int sr=0, sc=0; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ l[i][j] = layout[i].charAt(j); if(l[i][j] == 'S'){ sr = i; sc = j; } } } Queue<Integer> q = new LinkedList<Integer>(); q.add(sr*m+sc); int[] mf = new int[n*m]; mf[sr*m+sc] = fuel+1; int[] dr = {1, -1, 0, 0}; int[] dc = {0, 0, 1, -1}; while(!q.isEmpty()){ int cur = q.poll(); int r = cur / m; int c = cur % m; int inf = 0, sup = 0; if(l[r][c] == '+' || l[r][c] == 'S'){ inf = 0; sup = 4; }else if(l[r][c] == '-'){ inf = 2; sup = 4; }else if(l[r][c] == '|'){ inf = 0; sup = 2; } for(int i = inf;i < sup;i++){ int nr = r + dr[i]; int nc = c + dc[i]; if(nr >= 0 && nr < n && nc >= 0 && nc < m && mf[nr*m+nc] < mf[cur]-1){ if(i <= 1 && (l[nr][nc] == '|' || l[nr][nc] == '+')){ mf[nr*m+nc] = mf[cur] - 1; q.add(nr*m+nc); }else if(i >= 2 && (l[nr][nc] == '-' || l[nr][nc] == '+')){ mf[nr*m+nc] = mf[cur] - 1; q.add(nr*m+nc); } } } } int ct = 0; for(int i = 0;i < n*m;i++){ if(mf[i] > 0)ct++; } return ct; } }
1000
4x4のボードの上にPornがいくつか乗っている。0ポイントの状態から、次のいずれかの操作を任意回行った時のポイントの最大値を求めよ。ただしPornの移動先は空いていないといけないし盤外には移動できない。
- Pornを一つ選び、縦に隣接している別のPorn1個を飛び越えて2ポイント得る。飛び越えられたPornは死ぬ。
- Pornを一つ選び横に1マス移動させて1ポイント失う。
再帰ゲー。Pornのあるなしで状態数が2^16通りしかないので、各状態につきとりうる最大ポイントを定めれば、その状態にきたときに最大ポイント以下ならばそれ以降は探索しなくてよくなる。
また、最小で0ポイント、最大でも15個飛び越えて30ポイントまでしかえられないので、-30ポイント以下になったら強制的に探索を打ち切って良い。
最初何をトチ狂ったか各Pornにポイントがあるものと勘違いした上に上下左右に飛び越えられるのかと思ってた。問題文は正しく理解しましょう。
import java.util.Arrays; public class JollyJumpers { boolean[][] p = new boolean[4][4]; int[] max = new int[1<<16]; int point; public int maxScore(String[] layout) { for(int i = 0;i < 4;i++){ for(int j = 0;j < 4;j++){ char c = layout[i].charAt(j); p[i][j] = c == '#'; } } Arrays.fill(max, Integer.MIN_VALUE); point = 0; rec(); int mx = 0; for(int i = 0;i < 1<<16;i++){ mx = Math.max(mx, max[i]); } return mx; } int enc() { int x = 0; for(int i = 0;i < 4;i++){ for(int j = 0;j < 4;j++){ x = x * 2 + (p[i][j] ? 1 : 0); } } return x; } void rec() { int e = enc(); if(point <= max[e] || point <= -30){ return; } max[e] = point; if(Integer.bitCount(e) <= 1)return; for(int i = 0;i < 4;i++){ for(int j = 0;j < 4;j++){ if(p[i][j]){ // move for(int k = -1;k <= 1;k+=2){ int nr = i; int nc = j+k; if(nc >= 0 && nc < 4 && !p[nr][nc]){ point--; p[nr][nc] = true; p[i][j] = false; rec(); point++; p[i][j] = true; p[nr][nc] = false; } } // jump for(int k = -1;k <= 1;k+=2){ int nr = i+k*2; int nc = j; if(nr >= 0 && nr < 4 && p[i+k][j] && !p[nr][nc]){ point += 2; p[nr][nc] = true; p[i+k][j] = false; p[i][j] = false; rec(); point -= 2; p[i][j] = true; p[i+k][j] = true; p[nr][nc] = false; } } } } } } void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }
