At Coder Beginner Contest 037

[TakefumiYamamura]

http://abc037.contest.atcoder.jp/

[TakefumiYamamura]

C - 総和

Time limit : 2sec / Memory limit : 256MB

問題文

長さ N の数列 {ai} と1 以上 N 以下の整数 K が与えられます。 この数列には長さ K の連続する部分列が N−K+1 個あります。これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。

制約

1≤K≤N≤105 0≤ai≤108 ai は整数である。

note

普通にやるとO(n*2) 累積和を使えば良い。 まず1~x番目の和となる s[x] を求める。　これはn回の操作でも止まるのでO(n) よって長さkの部分列は先頭がi+1番目の場合 s[i+k] -s[i]でもとまる。 したがって全体の計算量はn+n-kよりO(n)となる

Computation is O(n*2) in greedy method. I should use cumulative sum. Firstly I seek s[x] which is the sum between 1-th and x-th variable. This manipulation takes O(n) Secondly, I can find the sum of the sequence which length is k by the calculation s[i+k] - s[i]. Therefore I can find the asnswer in O(n) .

#include <iostream>

using namespace std;
#define ll long long

int main(){
    int n, k;
    int a[10000010];
    ll s[10000010];
    s[0] = 0;
    ll sum = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        s[i] = a[i] + s[i-1];
    }
    for (int i = 0; i + k <= n ; ++i)
    {
        sum += s[i+k] - s[i];
    }
    cout << sum << endl;
}

[TakefumiYamamura]

D - 経路

Time limit : 2sec / Memory limit : 256MB

問題文

H*W のマス目があり、それぞれのマスには整数が書かれています。 i 行 j 列に書かれている数は aij です。

あなたはこのグリッドの中の好きなマスから好きなだけ動きます(最初のマスから動かなくてもかまいません)。 今いるマスの上下左右に隣接しているマスのうち、今いるマスより大きな整数が書かれたマスに移動することができます。

ありうる移動経路の個数を109+7で割った余りを求めてください。

制約

1≤H,W≤1,000 1≤aij≤109

note

It is a good problem to learn recursion and dynamic problems

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;

int h, w;
int a[1001][10001];
int f[1001][10001];
const int MOD = 1e9 + 7;
ll ans = 0;

bool check_limit(int i, int j){
    if(i >= h || i < 0) return false;
    if(j >= w || j < 0) return false;
    return true;
}

int dp(int i, int j){
    if(f[i][j] != 0){
        return f[i][j];
    }
    ll tmp = 0;
    if(check_limit(i, j+1) && a[i][j+1] > a[i][j]){
        tmp += dp(i, j+1); 
    }
    if(check_limit(i+1, j) && a[i+1][j] > a[i][j]){
        tmp += dp(i+1, j); 
    }
    if(check_limit(i, j-1) && a[i][j-1] > a[i][j]){
        tmp += dp(i, j-1); 
    }
    if(check_limit(i-1, j) && a[i-1][j] > a[i][j]){
        tmp += dp(i-1, j); 
    }
    f[i][j] = (tmp + 1) % MOD;
    return f[i][j];
}

int main(){
    cin >> h >> w;
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            cin >> a[i][j];
            f[i][j] = 0;
        }
    }
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            ans += dp(i, j);
            ans %= MOD;
        }
    }

    cout << ans % MOD << endl;
    return 0;
}