DP練。八段大敗北

今日は朝からDP八段の練習のため、ラスストを家でひたすら。
DP練。八段大敗北_f0019846_603296.jpg


お昼はスタミナタンメンのつけ麺を食べに行く。
DP練。八段大敗北_f0019846_61620.jpg


その後はゲーセン。

RUGGED ASH(A) フルコン
DP練。八段大敗北_f0019846_613447.jpg


CaptivAte~誓い~(DPH)ノマゲ
DP練。八段大敗北_f0019846_621259.jpg


からのDP八段ですが、30連敗を決めました。苦しい。
DP練。八段大敗北_f0019846_63457.jpg


気晴らしのポップン。
For east nightbird (H) PERFECT
DP練。八段大敗北_f0019846_634847.jpg


Mynarco(H) PERFECT
DP練。八段大敗北_f0019846_641363.jpg


帰宅後はAtCoder Regular Contest #019に参加。

A問題は、特定文字を変換して数値化するだけ。実際は文字列出力だけでよい。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String rs = br.readLine();
String st = "";
for(int i = 0 ; i < rs.length(); i++){
if(rs.charAt(i) == 'O' || rs.charAt(i) == 'D'){
st += "0";
}else if(rs.charAt(i) == 'I'){
st += "1";
}else if(rs.charAt(i) == 'Z'){
st += "2";
}else if(rs.charAt(i) == 'S'){
st += "5";
}else if(rs.charAt(i) == 'B'){
st += "8";
}else{
st += rs.charAt(i);
}
}
System.out.println(st);
}
}


B問題は、文字列の長さな偶数のとき、最初と最後を調べて一箇所だけ文字が違う
(ABCCBD であればAD BB CCと調べる)となると、
回文になる可能性が2つでてくるので、文字列の長さ*25 - 2する必要がある。
そうでないときは文字列の長さ*25でよい。
文字列の長さが奇数のときは、
全部一致する場合は (文字列の長さ-1)*25(これは真ん中の文字を何にしても回文になるが、
その他の文字を何にしても回文でなくなる)
一箇所だけ不一致であれば文字列の長さ*25 - 2 (これは文字列の長さが偶数のときと同じ)
それ以外は 文字列の長さ*25(いずれにせよ回文にならない)で良い。

回文の条件を考えると、全部調べる必要がなくなります。全部調べると間に合いませんがね。


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String rs = br.readLine();
if(rs.length() % 2 == 1){
int count = 0;
for(int i = 0 ; i < rs.length()/2; i++){
if(rs.charAt(i) != rs.charAt(rs.length()-i-1))count++;
}
if(count == 0){
System.out.println((rs.length()-1)*25);
}else if(count == 1){
System.out.println(rs.length()*25-2);
}else{
System.out.println(rs.length()*25);
}
}else{
int count = 0;
for(int i = 0 ; i < rs.length()/2; i++){
if(rs.charAt(i) != rs.charAt(rs.length()-i-1))count++;
}
if(count == 1){
System.out.println(rs.length()*25-2);
}else{
System.out.println(rs.length()*25);
}
}
}
}


C問題は、戦闘をK回以内に抑えつつ、祠のCに到達して最短で魔王を倒すような
道筋を考えて、最短ターンを出力する問題。
Cまでにかかった戦闘回数とターン数としてDP、
祠から魔王を倒す道筋で戦闘回数とターン数をDPし、
それぞれの組み合わせで戦闘回数がKを超えず、ターン数が最も小さくなるものを選べば良さそう。

解けなかったTLEするコードがありますが、これは全部考えてしまったからです。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] rs = br.readLine().split(" ");
int R = Integer.parseInt(rs[0]);
int C = Integer.parseInt(rs[1]);
int K = Integer.parseInt(rs[2]);
String[] map = new String[R];
int stx = -1;
int sty = -1;
int[][] minimumturn = new int[R][C];
int[][] minimumend = new int[R][C];

int[][] maxattackturn = new int[R][C];
int[][] maxattackend = new int[R][C];

int[] xplus = {-1,0,1,0};
int[] yplus = {0,-1,0,1};

for(int i = 0 ; i < R ; i++){
for(int j = 0 ; j < C ; j++){
minimumturn[i][j] = Integer.MAX_VALUE;
minimumend[i][j] = Integer.MAX_VALUE;
}
}

for(int i = 0 ; i < R ; i++){
map[i] = br.readLine();
for(int j = 0 ; j < C ; j++){
if(map[i].charAt(j) == 'S'){
sty = i;
stx = j;
maxattackturn[sty][stx] = K;
break;
}
}
}

Queue q = new LinkedList();
int goalturn = Integer.MAX_VALUE;
q.add(stx+","+sty+","+0+","+0+","+K+","+"2148438647");//x,y,sword,turn,attack;
while(!q.isEmpty()){
String[] st =q.poll().split(",");
int xnum = Integer.parseInt(st[0]);
int ynum = Integer.parseInt(st[1]);
int sword = Integer.parseInt(st[2]);
int turn = Integer.parseInt(st[3]);
int attack = Integer.parseInt(st[4]);
String attacked = st[5];
if(turn > goalturn)continue;
for(int i = 0 ; i < 4 ; i++){
if(iswallOrTree(map,xnum+xplus[i],ynum+yplus[i],R,C)){
if(sword == 0){
if(turn+1 >= minimumturn[ynum+yplus[i]][xnum+xplus[i]] && attack <= maxattackturn[ynum+yplus[i]][xnum+xplus[i]])continue;
if(map[ynum+yplus[i]].charAt(xnum+xplus[i]) == 'E'){
boolean fight = true;
if(attacked.length() != 2){
String[] fighter = attacked.split("-");
for(int j = 0 ; j < fighter.length/2 ; j++){
if((ynum+yplus[i]) == Integer.parseInt(fighter[j*2+2]) && (xnum+xplus[i]) == Integer.parseInt(fighter[j*2+1])){
fight = false;
break;
}
}
}
if(fight){
if(attack > 0){
if(turn+1 < minimumturn[ynum+yplus[i]][xnum+xplus[i]]){
minimumturn[ynum+yplus[i]][xnum+xplus[i]] = turn+1;
}
if(attack-1 > maxattackturn[ynum+yplus[i]][xnum+xplus[i]]){
maxattackturn[ynum+yplus[i]][xnum+xplus[i]] = attack-1;
}
q.add((xnum+xplus[i])+","+(ynum+yplus[i])+","+sword+","+(turn+1)+","+(attack-1)+","+(attacked+"-"+(xnum+xplus[i])+"-"+(ynum+yplus[i])));
}
}else{
q.add((xnum+xplus[i])+","+(ynum+yplus[i])+","+sword+","+(turn+1)+","+(attack)+","+attacked);
}
}else if(map[ynum+yplus[i]].charAt(xnum+xplus[i]) == 'C'){
if(turn+1 < minimumturn[ynum+yplus[i]][xnum+xplus[i]]){
minimumturn[ynum+yplus[i]][xnum+xplus[i]] = turn+1;
}
if(attack > maxattackturn[ynum+yplus[i]][xnum+xplus[i]]){
maxattackturn[ynum+yplus[i]][xnum+xplus[i]] = attack;
}
q.add((xnum+xplus[i])+","+(ynum+yplus[i])+","+1+","+(turn+1)+","+(attack)+","+attacked);
}else{
if(turn+1 < minimumturn[ynum+yplus[i]][xnum+xplus[i]]){
minimumturn[ynum+yplus[i]][xnum+xplus[i]] = turn+1;
}
if(attack > maxattackturn[ynum+yplus[i]][xnum+xplus[i]]){
maxattackturn[ynum+yplus[i]][xnum+xplus[i]] = attack;
}
q.add((xnum+xplus[i])+","+(ynum+yplus[i])+","+sword+","+(turn+1)+","+(attack)+","+attacked);
}
}else{
if(turn+1 >= minimumend[ynum+yplus[i]][xnum+xplus[i]] && attack <= maxattackend[ynum+yplus[i]][xnum+xplus[i]])continue;
if(map[ynum+yplus[i]].charAt(xnum+xplus[i]) == 'E'){
boolean fight = true;
if(attacked.length() != 2){
String[] fighter = attacked.split("-");
for(int j = 0 ; j < fighter.length/2 ; j++){
if((ynum+yplus[i]) == Integer.parseInt(fighter[j*2+2]) && (xnum+xplus[i]) == Integer.parseInt(fighter[j*2+1])){
fight = false;
break;
}
}
}

if(fight){
if(attack > 0){
if(turn+1 < minimumend[ynum+yplus[i]][xnum+xplus[i]]){
minimumend[ynum+yplus[i]][xnum+xplus[i]] = turn+1;
}
if(attack-1 > maxattackend[ynum+yplus[i]][xnum+xplus[i]]){
maxattackend[ynum+yplus[i]][xnum+xplus[i]] = attack-1;
}
q.add((xnum+xplus[i])+","+(ynum+yplus[i])+","+sword+","+(turn+1)+","+(attack-1)+","+(attacked+"-"+(xnum+xplus[i])+"-"+(ynum+yplus[i])));
}
}else{
q.add((xnum+xplus[i])+","+(ynum+yplus[i])+","+sword+","+(turn+1)+","+(attack)+","+attacked);
}
}else if(map[ynum+yplus[i]].charAt(xnum+xplus[i]) == 'C'){
if(turn+1 < minimumend[ynum+yplus[i]][xnum+xplus[i]]){
minimumend[ynum+yplus[i]][xnum+xplus[i]] = turn+1;
}
if(attack > maxattackend[ynum+yplus[i]][xnum+xplus[i]]){
maxattackend[ynum+yplus[i]][xnum+xplus[i]] = attack;
}
q.add((xnum+xplus[i])+","+(ynum+yplus[i])+","+1+","+(turn+1)+","+(attack)+","+attacked);
}else if(map[ynum+yplus[i]].charAt(xnum+xplus[i]) == 'G'){
goalturn = Math.min(goalturn, turn+1);
}else{
if(turn+1 < minimumend[ynum+yplus[i]][xnum+xplus[i]]){
minimumend[ynum+yplus[i]][xnum+xplus[i]] = turn+1;
}
if(attack > maxattackend[ynum+yplus[i]][xnum+xplus[i]]){
maxattackend[ynum+yplus[i]][xnum+xplus[i]] = attack;
}
q.add((xnum+xplus[i])+","+(ynum+yplus[i])+","+sword+","+(turn+1)+","+(attack)+","+attacked);
}
}
}
}
}
if(goalturn == Integer.MAX_VALUE){
System.out.println(-1);
}else{
System.out.println(goalturn);
}
}

static boolean iswallOrTree(String[] map,int x,int y,int R,int C){
if(x < 0 || y < 0 || x == C || y == R || map[y].charAt(x) == 'T')return false;
return true;
}
}


家でのBPはクリア圏内なんだけどなーって泣きそうになっている。
DP練。八段大敗北_f0019846_645987.jpg

  by ddrer-yossi | 2014-03-15 23:11 | Beatmania

<< DP八段取得! Codefor... 焼肉と家庭用DJTの解禁作業 >>

SEM SKIN - DESIGN by SEM EXE