きっかけ

　就職して、スキルアップのためにと思いプログラミングコンテストに参加しています。今回はその１つである「AtCoder Beginner Contest (ABC) 037」に参加してみました。

　自分の肌で感じた難易度としては

問題	難易度
A	易
B	やや易
C	やや難
D	難

という感じでした。Dは時間内に終えることができませんでした。。。しかしなんとか終了後１時間ほどで正解できました。ちかれた。。。。
一応手元の環境で動くものができても、TLE(実行時間制限超過)などへの対処を考えるのが難しかったです。

なお、使用言語はC++です。

　自分の解法

[ABC#037 コンテストページ]http://abc037.contest.atcoder.jp/
問題はこちら。問題概要はこのページの問題の要約です。

A問題

問題概要

１個A円の饅頭とB円の饅頭がある。C円持っている状態で、なるべく多くの個数の饅頭を買うとする。買うことのできる最大の個数を出力せよ。ただし２種類を同じ個数買う必要もなく、また買わない種類の饅頭があっても良い。

入力として、整数A,B,Cが空白区切で与えられる。
出力として、買うことのできる最大の個数を与えよ。

解法

　これはA,Bのうち小さいほうでCを割れば良いですね。

提出コード

q1.cpp

#include <iostream>
using namespace std;

int main(){
    int A,B,C;
    cin >> A >> B >> C;

    if(A<B)
        cout << C/A << endl;
    else
        cout << C/B << endl;  

    return 0;
}

無論業務で使うならばコメントアウトは徹底しないといけませんね。。。しかし競技なのでご愛嬌を・・・・

B問題

問題概要

要素が全て０である数列{$a_n$}がある。$Q$個のクエリが与えられて、そのクエリごとに以下の処理を実行する。
- 数列の左から$L_i$番目から$R_i$番目の要素を$T_i$にかえる。
このとき最終的な数列の要素がどうなっているか出力しなさい。

入力として、１行目に数列の長さ$N$とクエリの数$Q$が与えられる。
$i+1$行目には$i$番目のクエリ$Q_i$が与えられる。クエリは、
$L_i$ $R_i$ $T_i$
のように１行で空白区切で与えられる。なお、数列の先頭のインデックスは1となっている。

出力として、最終的な配列の要素を、１行１要素で出力する。

解法

$N$,$Q$の範囲が
$1 \leq Q \leq 100$
$1 \leq N \leq 100$
となっているので、forループを使って$L$番目から$R$番目に１つ１つ代入していっても、代入回数は最大$10^4$回で、計算量は問題ないと言えるとみて、愚直にクエリ通り実行していきます。。

提出コード

q2.cpp

#include <iostream>
using namespace std;

int main(){
    int N,Q;
    cin >> N >> Q;
    int l,r,t;
    int a[N];

    for(int i=0;i<N;i++)
        a[i] = 0;  //全要素を0にリセット

    for(int i=0;i<Q;i++){
        cin >> l >> r >> t;
        for(int j=l-1;j<r;j++)  //左からl番目からr番目までにtを代入していく
            a[j] = t;
    }

    for(int i=0;i<N;i++)
        cout << a[i] << endl; //１行１要素で出力

    return 0;
}

C問題

問題概要

長さが$N$の数列{$a_n$}と、自然数$K$が与えられる。数列{$a_n$}中の、長さ$K$の連続する部分列全てに含まれる数の総和を求めよ。

入力は、１行目に整数$N$,$K$が与えられ、２行目に数列の各項　$a_1,a_2,a_3,...,a_N$が与えられる。
出力は、総和を１行で出力する。

解法

まず、愚直に総和を計算するプログラムを書いてみた。

総和 = $\sum_{i=0}^{K-1} a_i +\sum_{i=1}^{K} a_i +\sum_{i=2}^{K+1} a_i + ... + \sum_{i=N-K}^{N-1} a_i $

q3.cpp(数列を記録し和を求める部分のみ)

    for(int i=0;i<N;i++){
        cin >> a[i];  // 数列の入力を受け付ける
    }
    long long ans =0;  // 総和の大きさがわからないのでとりあえずlong long
    for(int i=0;i<N-K+1;i++){
        for(int j=i;j<i+K;j++){
            ans += a[j]; // 愚直に足していく
        }
    }

結果、案の定TLEwwwwwwww
今回の変数の範囲は$1\leq K \leq N \leq 10^5、1\leq a_i \leq 10^8$ですから、$O(N^2)$オーダーのこの方法だと間に合わないみたいです。そこで、少し見方を変えて、何番目の項はいくつの部分列に含まれているかを計算します。

	$a_0$	$a_1$	$a_2$	...	$a_{K-1}$	$a_K$	...	$a_{N-2}$	$a_{N-1}$	$a_{N}$
0番目から始まる部分列	◯	◯	◯	...	◯
１番目から始まる部分列		◯	◯	...	◯	◯
２番目から始まる部分列			◯	...	◯	◯	・.
				...	・.	・.	・.
$N-K-2$番目から始まる部分列				...	・.	・.	・.	◯
$N-K-1$番目から始まる部分列				...		・.	・.	◯	◯
$N-K$番目から始まる部分列				...				◯	◯	◯

と、こんな感じに◯が平行四辺形型に並ぶので、上の場合なら$a_0 \times 1 + a_1 \times 2 + a_2 \times 3 + ... + a_{N-2} \times 3 + a_{N-1} \times 2 + a_N \times 1$を計算すれば良いでしょう。
しかも、この方法なら、各$a_i$を読み込むごとに、その$a_i$がいくつの部分列に含まれるかを計算すれば良いので、数列として記憶する必要がありません。

注意したいのは、この◯の並び方が

◯	◯	◯	◯		...
◯	◯	◯	◯	◯	...
	・.	・.	・.	・.	・.
		◯	◯	◯	...	◯
			◯	◯	...	◯	◯

のように横長になる（$K-1 \leq N-K$）か、

◯	◯	◯			...
◯	◯	◯	◯		...
	・.	・.	・.	・.	・.
			◯	◯	...	◯
				◯	...	◯	◯

のように縦長になる（$K-1 > N-K$）のかですね。

q3.cpp(総和を求める部分のみ)

for(int i=0;i<N;i++){
        cin >> v;
        if(2*K > N+1){  //横長の平行四辺形となる場合
            if(i <= N-K){
                ans += v*(i+1);
            }else if(i <= K-1){
                ans += v*(N-K+1);
            }else{
                ans += v*((N-K+1)-(i-K+1));
            }
        }else{  //縦長の平行四辺形となる場合
            if(i <= K-1){
                ans += v*(i+1);
            }else if(i <= N-K){
                ans += v*K;
            }else{
                ans += v*((N-K+1)-(i-K+1));
            }
        }
    }

ふう。

D問題

　問題概要

$H \times W$のグリッドがあり、各グリッドには整数が書かれている。
今、どこか好きなグリッドからスタートし、上下左右に隣接しているいずれかのグリッドに好きなだけ移動することを考える。
ただし、今自分がいるグリッドに書いてある整数より大きな整数の書いてあるグリッドにしか移動できない。

このとき、移動の仕方の総数を$10^9+7$で割ったあまりを求めなさい。ただし、「はじめのグリッドから移動しない」という方法も１通りとして数える。

解法

たとえば入力例の

2 3
1 4 5
2 4 9

を例にとってみると、

1	4	5
2	4	9

(0,0)
(0,1)
(0,2)
(1,0)
(1,1)
(1,2)
(0,0)→(0,1)
(0,0)→(0,1)→(0,2)
(0,0)→(0,1)→(0,2)→(1,2)
(0,1)→(0,2)
(0,1)→(0,2)→(1,2)
(0,2)→(1,2)
(0,0)→(1,0)
(0,0)→(1,0)→(1,1)
(0,0)→(1,0)→(1,1)→(1,2)
(1,0)→(1,1)
(1,0)→(1,0)→(1,1)
(1,0)→(1,1)

の18通りあることに。。。ふえぇ。。。

こういうの見ると、つい幅優先探索を使いたくなるけど、ここでは深さ優先探索っぽいことをやってみます。

グリッド$(i,j)$からスタートする場合の移動の仕方を$W(i,j)$と書くことにします。
すると、たとえば(0,0)からスタートする移動の仕方は、
(i) (0,0)から移動せず終了 (1通り)
(ii) 次に右のグリッド(0,1)に移動する場合の移動の仕方 ( $W(0,1)$通り )
(iii) 次に下のグリッド(1,0)に移動する場合の移動の仕方 ( $W(1,0)$通り )
の３つに場合分けできるので、

$W(0,0) = W(0,1)+ W(1,0) + 1$　　・・・(4.1)

という式に展開できます。
(4.1)式の右辺の$W(0,1)$は、

(i) (0,1)から移動せず終了
(ii) 次に右のグリッド(0,2)に移動する場合の移動の仕方 ( $W(0,2)$通り )
(iii) 次に下のグリッド(1,1)に移動する場合の移動の仕方 ( $W(1,1)$通り )
(iv) 次に左のグリッド(0,0)に移動する場合の移動の仕方 ( $W(0,0)$通り )

の４つに場合分けしますが、問題のルール上(iii),(iv)のような移動は不可能なので

$W(0,1) = W(0,2) + 1$　　・・・(4.2)

のように展開できます。
要するに、隣接してるグリッドのうち、自分のグリッドより大きい数が書いてあるグリッドについてのみ、
そのグリッドからスタートした場合の移動の仕方を足していけば良いのですね。

このように再帰的に展開していけば、全てのグリッドについて、そのグリッドからスタートする場合の移動の仕方を計算できます。

実装の方法としては、はじめに全てのグリッドの$W(i,j)$を-1に設定し、main関数部で全てのグリッドの$W(i,j)$の値が-1でなくなるまで以下の計算を繰り返すことになります。

q4.cpp(核心部のみ)

int Map::calcWay(int x,int y){
    if(way[x][y] != -1)   // すでにW(x,y)を計算してある場合
        return way[x][y];
    bool ismax = true;  //そのグリッドに、隣接するどのグリッドよりも大きい数が書いてあるかどうか
    int res=0;
    if(x>0){
        if(map[x-1][y] > map[x][y]){
            res += calcWay(x-1,y);  res %= DIVISOR; ismax = false;
        }
    }
    if(x<height-1){
        if(map[x+1][y] > map[x][y]){
            res += calcWay(x+1,y);  res %= DIVISOR; ismax = false;
        }
    }
    if(y>0){
        if(map[x][y-1] > map[x][y]){
            res += calcWay(x,y-1);  res %= DIVISOR; ismax = false;
        }
    }
    if(y < width-1){
        if(map[x][y+1] > map[x][y]){
            res += calcWay(x,y+1);  res %= DIVISOR; ismax = false;

        }
    }

    res++;


    if(ismax){
        way[x][y] = 1;  //隣接するどのグリッドよりも数が大きい場合W(x,y)は1
        ans += 1;
        ans %= DIVISOR;
        return 1;

    }else{
        way[x][y] = res;
        ans += res;
        ans %= DIVISOR;
        return res;
    }   
}

感想

　ちょっと時間かかりすぎちゃったかなぁ。あとはもっと効率のいい方法あるんじゃないかってこの記事を書きながら思いました。
次は時間内に全部ときたい。

追記

16/5/7 誤字があったので訂正しました。