16/08/24

paiza

勢いで登録してみた

取り敢えず下から1つずつランクを上げていくことにした。
平均レートが高い問題を選んだせいか、やるだけ(でも少ししんどい)問題にやたら当たった。
ランクAの問題で判断ミスにより手間取り結果時間5分オーバーでランクアップならず。

twitterで軽く検索した所、ランクSでもABCのC,D問題ぐらいなので十分視野範囲内っぽい。
とはいえサイトの性質上ネタバレ厳禁なので、競プロみたいに解法身に着けていくサイトではなさそう。
モチベーションがどうしても落ちた時とかで気まぐれに埋めていくのが良さそう？

AOJ

AOJ0203を解いた。動的計画法の応用というイメージ。
メモ化再帰しか使ったことが無いので、漸化式で解くやつも何時かやってみたい。

折角なのでへたれコードを貼ってみる

#include <iostream>
#include <sstream>
#include <cstdlib>
#include <cstdio>
using namespace std;
 
#define NONE 0
#define TREE 1
#define JUMP 2
 
int dp[17][17];
int area_state[17][17];
int h,w;
 
int solve(int y, int x){
 
    if (dp[y][x] != -1)
        return dp[y][x];
    if (x == 0 || x == w+1){
        dp[y][x] = 0;
        return 0;
    }   
    if (y == h || y == h+1){
        dp[y][x] = 1;
        return 1;
    }
 
    if (area_state[y][x] == TREE){
        return 0;
 
    }else if (area_state[y][x] == JUMP){
        dp[y][x] = (solve(y+2, x));
        return dp[y][x];
 
    }else if (area_state[y][x] == NONE){
        if(y == h-1){
            dp[y][x] = 1;
            return 1;
        }
        int left = 0;
        int right = 0;
 
        if(area_state[y+1][x-1] != JUMP){
            left = solve(y+1,x-1);
        }
        if(area_state[y+1][x+1] != JUMP){
            right =  solve(y+1,x+1);
        }
        dp[y][x] =  left + solve(y+1,x) + right;
        return dp[y][x];
    }
}
 
 
int main() {
    while (cin >> w >> h && w&&h ){ 
        fill( dp[0], dp[17], -1);
        fill( area_state[0], area_state[17], 0);
 
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                int zone;
                cin >> zone;
                area_state[i][j+1] = zone;
            }
        }
 
        int ans = 0;
        for(int i = 1; i < w+1; i++){
            ans += solve(0,i);
        }
         
        cout << ans << endl;
    }
    return 0;
}