TopCoder SRM651 div2 (unrated)

今日は昼ごろにゲーセンに向かう。
ケーキセット EXHAUSTをクリア。
TopCoder SRM651 div2 (unrated)_f0019846_1573032.jpg


Air Reading Powerは、95.1%でAAA+到達。取れるとは思わなかったので嬉しかった。
TopCoder SRM651 div2 (unrated)_f0019846_1581224.jpg


the keelは初見96.5% フルコン
TopCoder SRM651 div2 (unrated)_f0019846_1583821.jpg


ケンタッキーがやすかったのでケンタッキーチキンを食べることに。
その後は店探しやプレゼント探しに難航しつつ、夜はNEXT FRONTIERをがんばる。
なんとかULTつけたときには、Fail1個でした。そりゃないわ…。
TopCoder SRM651 div2 (unrated)_f0019846_20341.jpg


夜は数カ月ぶりにディアブロをやりました。新作のやつですが、
新作をほとんど経験できるところはなかったです。
ダイヤモンドとか増えてましたけどね。

TopCoderはeasyでは
.とSと#のマップがあり、Sはロボットのスタート、.は空き場所、#は障害物で、
ロボットをULRDで上下左右に動かすとき、
ロボットが障害物にぶつかればそのまま動かない、
マップの場外にロボットが行けば、ロボットが死ぬというときに、
動作後にロボットが生きているか死んでいるか判定せよという問題。

× if(board[sty+obsy[0]].charAt(stx+obsx[0]) != '.')
○ if(board[sty+obsy[0]].charAt(stx+obsx[0]) != '#')

この部分の書き方ミスで落としてしまったが、
終了間際に気づいて直した。が、システムで送信できないことに気づき、
そこでUnratedだということに気づいた。つらい。


public class RobotOnMoonEasy {

public String isSafeCommand(String[] board, String S) {
int stx = 0;
int sty = 0;
for(int i = 0 ; i < board.length ; i++){
for(int j = 0 ; j < board[i].length(); j++){
if(board[i].charAt(j) == 'S'){
stx = j;
sty = i;
break;
}
}
}
for(int i = 0 ; i < S.length(); i++){

int[] obsx = {0,-1,1,0};
int[] obsy = {-1,0,0,1};

if(S.charAt(i) == 'U'){
if(isDead(stx+obsx[0],sty+obsy[0],board))return "Dead";
if(board[sty+obsy[0]].charAt(stx+obsx[0]) != '#'){
stx += obsx[0];
sty += obsy[0];
}
}else if(S.charAt(i) == 'L'){
if(isDead(stx+obsx[1],sty+obsy[1],board))return "Dead";
if(board[sty+obsy[1]].charAt(stx+obsx[1]) != '#'){
stx += obsx[1];
sty += obsy[1];
}
}else if(S.charAt(i) == 'R'){
if(isDead(stx+obsx[2],sty+obsy[2],board))return "Dead";
if(board[sty+obsy[2]].charAt(stx+obsx[2]) != '#'){
stx += obsx[2];
sty += obsy[2];
}
}else if(S.charAt(i) == 'D'){
if(isDead(stx+obsx[3],sty+obsy[3],board))return "Dead";
if(board[sty+obsy[3]].charAt(stx+obsx[3]) != '#'){
stx += obsx[3];
sty += obsy[3];
}
}
}
return "Alive";
}

public boolean isDead(int x,int y,String[] board){
if(x < 0 || y < 0 || x == board[0].length() || y == board.length)return true;
return false;
}

}


mediumは、両親がいて、プレゼントの価値がValueで与えられているとき、
プレゼントの価値の合計が等しく、かつ個数も等しくなるような分け方が
可能かどうか判定せよという問題。

最初はどうすればいいかわからなかったが、
実は片方だけ判定すればよく、
そして、 [現在の価値][現在の個数][現在のインデックス]でDPすると、
うまい具合に調べられることがわかった。値はboolean型で、
可能かどうかだけ判断してあげればよい。
気付けばこの問題はmedよりはやい。


import java.util.Arrays;

public class FoxAndSouvenirTheNext {

public String ableToSplit(int[] value) {
if(value.length % 2 != 0)return "Impossible";
Arrays.sort(value);
int valuesum = 0;
for(int i = 0 ; i < value.length ; i++){
valuesum += value[i];
}
if(valuesum % 2 != 0)return "Impossible";
valuesum /= 2;
int pres = value.length / 2;
boolean[][][] DP = new boolean[pres + 1][valuesum + 1][value.length + 1];
DP[0][0][0] = true;
for(int i = 0 ; i < DP.length ; i++){
for(int j = 0 ; j < DP[0].length ; j++){
for(int k = 0 ; k < DP[0][0].length - 1 ; k++){
if(DP[i][j][k]){
if(j + value[k] <= valuesum && (i + 1) <= pres){
DP[i + 1][j + value[k]][k + 1] = true;
}
DP[i][j][k + 1] = true;
}
}
}
}
if(DP[pres][valuesum][value.length])return "Possible";
return "Impossible";
}
}


ソートしてますが、ソートしなくても大丈夫な気がします。

hardは、マップが与えられていて、
隣り合う行か列にあれば、隣接した町にいる扱いになる時、
K匹の狐が隣り合う感じになる組み合わせが何通りあるか求める問題。
要するに一筆書きで何通りになるかという話であるが、難しかった。

何度も言いますがunratedなので…。

  by ddrer-yossi | 2015-02-28 23:56 | TopCoder

<< ぼんやりと過ごす1日 記念すべき1年 >>

SEM SKIN - DESIGN by SEM EXE