Hatena::Grouptopcoder

kitayutaのTopCoderの何か

2011-11-13

TopCoder SRM 523 Div1

18:05

結果

<Challenge Succeeded> <215.83> <Unopened> +50*1 -25*1 Total: 240.83pt 1294→1396

Highest更新らしい!!

250 CountingSeries

簡単…なはずが、コーナーケースに当たって落ちる。こわい。

提出したコード(落ちる):

//include等省略
class CountingSeries {
    public:
        long long countThem(long long a, long long b, long long c, long long d, long long upperBound) {
            ll cnt=(upperBound-a)/b+1;
            while(c<=upperBound){
                if((c-a)%b==0&&(c-a)/b>=0);
                else cnt++;
                if(d==1) break;
                c*=d;
            }
            return cnt;
        }
};

落ちた原因は、upperBound<aの時に適切な処理をしていなかった点。

//include等省略
class CountingSeries {
    public:
        long long countThem(long long a, long long b, long long c, long long d, long long upperBound) {
            ll cnt;
            if(upperBound-a>=0) cnt=(upperBound-a)/b+1;  //修正点
            else cnt=0;
            while(c<=upperBound){
                if((c-a)%b==0&&(c-a)/b>=0);
                else cnt++;
                if(d==1) break;
                c*=d;
            }
            return cnt;
        }
};

500 BricksN

DP(メモ化再帰)をした。dp[一番下のブロックの幅][一番下のブロックの高さ]として、求める答えはdp[w][1]。これを求める過程として、ある長さの連続するブロックは何通りに敷き詰められるかをDPして求めておいたりする(dp2)。

オーバーフローに注意するべきかもしれない。

DPに慣れてきていい傾向。あと初めてMedium通した。

//include等省略
const ll MOD = 1000000007;
ll dp[51][51];
ll dp2[51];
ll solve(int wid,int hei,int k,int h){
    if(wid<1 || hei>h) return 1;
    if(dp[wid][hei]==-1){
        ll ret=0;
        for(int i=0;i<=wid;i++){
            ret+=(((dp2[i]*solve(i,hei+1,k,h))%MOD)*solve(wid-i-1,hei,k,h))%MOD;
            ret%=MOD;
        }
        dp[wid][hei]=ret;
    }
    return dp[wid][hei];
}
class BricksN {
    public:
        int countStructures(int w, int h, int k) {
            dp2[0]=1;
            for(int i=1;i<=w;i++){
                dp2[i]=0;
                for(int j=1;j<=min(i,k);j++){
                    dp2[i]+=dp2[i-j];
                    dp2[i]%=MOD;
                }
            }
            for(int i=1;i<=w;i++){
                for(int j=1;j<=h;j++){
                    dp[i][j]=-1;
                }
            }
            return solve(w,1,k,h);
        }
};

Challenge Phase

  • 上の500のコードにおける "ret+=(dp2[i]*solve(i,hei+1,k,h))%MOD)*solve(wid-i-1,hei,k,h))%MOD;" を "ret+=(dp2[i]*solve(i,hei+1,k,h)*solve(wid-i-1,hei,k,h))%MOD;" とかやって明らかにオーバーフローしてるコードを落とす。
  • 250が落とされる。
  • 250の落とされ方をなんとなく把握して、適当に人のをchallengeしたらミス。焦ってはいけない…

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/kita_yuta/20111113