SRM467 DIV2 - Mostly Sourceless

ox- 942 -> 932
あんまり下がらなかった。こういうときにバシッと解いていればrateがガッと上昇したのに……

Practice Roomで一応500,1000も解きました。

250 - ShorterSuperSum

n,kの最大が14なので問題文そのまま再帰で書けばおしまい。

public class ShorterSuperSum {
    public int calculate(int k, int n) {
        return calc(k, n);
    }
    public int calc(int k, int n){
        if(k==0) return n;
        int b = 0;
        for(int i=1; i<=n; i++){
            b += calc(k-1, i);
        }
        return b;
    }
}

こういうのは素直に書いたらどうせTLEすんだろ！！！１１と思い込み、別の解答探そうとして時間ロスしました。あほすぎる。
みんなが瞬殺してるのを見てあわてて素直に書きました。

Dr.Wesleyは時刻t(bestTime <= t <= worstTimeの範囲から一様に選ばれる実数)に教室に到着すると仮定します。
Johnは時刻0に教室に着き、博士をwaitTime分待ってからwalkTime分散歩に出かけます。
散歩から戻ってきたとき、まだ博士が到着していなかったらまたwaitTime分待ってからwalkTime分散歩に出かけるの繰り返し。
ただし、t + lateTime以降に来たやつは教室から締め出されます。
Johnが遅刻して博士に締め出される確率を求める問題。

bestArrivalからworstArrival-1まで1ずつ見ていって、締め出される場合の合計/(worstArrival - bestArrival)で求められる？
条件がなにやらややこしいだけにテストケースが親切だったので、こっちむりやり直したらあっちが通らないの連続で時間切れ。
以下はPracticeで赤い方々のコードを参考にしｔ……というかほぼ写しになってしまったコード。

public class LateProfessor {
    public double getProbability(int waitTime, int walkTime, int lateTime, int bestArrival, int worstArrival) {
        int deny = 0;
        int awaye = waitTime + walkTime;
        if(walkTime < lateTime) return 0.0;
        if(bestArrival == worstArrival) {
            int tmp = bestArrival % awaye;
            if( waitTime < tmp && tmp <= awaye - lateTime ) return 1.0;
            else return 0.0;
        }
        for(int i=bestArrival; i<worstArrival; i++){
            int tmp = i % awaye;
            if( waitTime <= tmp && tmp < awaye - lateTime ) deny++;
        }
        double div = (worstArrival - bestArrival);
        double ret = (double)deny / div;
        return ret ;
    }
}

だいぶ悩んだけど(bestArrival == worstArrival)のときと順繰りに見ていくときで遅刻する条件の不等号が変わるのが未だに理解できません。要復習。
しかし正解率14.77%って……

1000 - MazeOnFire

$ < な……なんなんですか？ここ、どこですか？なんで私焼かれてるんですか？

マス目で構成された迷宮があります。
マス目は「炎{F}」と「壁{#}」と「何もない場所{.}」と「$さん{$}」を含みます。1マスにどれか1つしか入りません。
$さんは1ターンのうちに上下左右の隣接したマスのどれか1つに逃げることができます。ただし壁は越えられません。
炎は1ターンのうちに上下左右の隣接したマスすべてに燃え広がります。ただし壁は火を通しません。
$さんが生き延びることのできる最大ターン数を返せよな！って問題。いつまで経っても死なない場合は-1を返します。

TopCoderでプログラムしてみた。第455回(直後放送 SRM467) - 2010/04/16 11:30開始 - ニコニコ生放送
こっそり応援していた↑の放送中、最後の方で紹介されてた方法で解いてみました。

$さんも炎と同じような感じで、上下左右に分裂することにします。炎と重なった$さんは燃えて消滅します。
こうすれば分裂したうちのどれかは必ず最良の方向に移動していることになるので、$さんが全滅したターンが答えになります。

public class MazeOnFire {
    public int maximumTurns(String[] m) {
        int turn = 0;
        char[][] maze = new char[m.length][];
        for(int i=0; i<m.length; i++) maze[i] = m[i].toCharArray();
        char[][] next = new char[m.length][m[0].length()];
        for(int i=0; i<m.length; i++)
            for(int j=0; j<m[0].length(); j++)
                next[i][j] = maze[i][j];

        while(turn++ < 2501){
            for(int i=0; i<maze.length; i++) {
                for(int j=0; j<maze[0].length; j++) {
                    if(maze[i][j]=='$'){
                        if(i-1 > -1 && next[i-1][j]=='.') next[i-1][j]='$';
                        if(i+1 < maze.length && next[i+1][j]=='.') next[i+1][j]='$';
                        if(j-1 > -1 && next[i][j-1]=='.') next[i][j-1]='$';
                        if(j+1 < maze[0].length && next[i][j+1]=='.') next[i][j+1]='$';
                    }
                    if(maze[i][j]=='F'){
                        if(i-1 > -1 && next[i-1][j]!='#') next[i-1][j]='F';
                        if(i+1 < maze.length && next[i+1][j]!='#') next[i+1][j]='F';
                        if(j-1 > -1 && next[i][j-1]!='#') next[i][j-1]='F';
                        if(j+1 < maze[0].length && next[i][j+1]!='#') next[i][j+1]='F';
                    }
                }
            }
            if(isDied(next)) return turn;
            for(int i=0; i<m.length; i++)
                for(int j=0; j<m[0].length(); j++)
                    maze[i][j] = next[i][j];
        }
        return -1;
    }

    public boolean isDied(char[][] cs){
        int a=0;
        for(int i=0; i<cs.length; i++)
            for(int j=0; j<cs[0].length; j++)
                if(cs[i][j]=='$') a++;
        return a==0;
    }
}

最初ループ回数250くらいでよくね？とsubmitしたら答えが1000越えのケースから叩き落とされて絶望した。
どういうケースで最も遅くなるのかぱっと分からなかったので、適当に大きくとっときました。

来週の火曜日もがんばる。

250 - ShorterSuperSum

500 - LateProfessor

1000 - MazeOnFire