活動日誌'19 No.012

投稿者 NOSS | 2019-07-05

こんにちは、NOSSです。
今日は再帰について講習会を行いました。

講習会

再帰について講習をしました。最初は難しいと思いますが、再帰が書けると使えるアルゴリズムの幅が広がるのでぜひ習得しましょう。

参考にしたサイト

詳しく解説されているので、読むと理解が深まると思います

コンテスト

今日は再帰を使う問題を中心に集めました。

解説

B問題

問題リンク:https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_5_A

それぞれの整数について選ぶか選ばないかの2通りなので、選び方の総数は $2^n$ 通りになります。
$n \le 20$ より、最大でも $2^{20} \cong 10^6$ 程度なので全探索が可能です。

各整数について使う、使わないを再帰で分岐します。

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> A;

// k種類の整数を使ってちょうどxをつくる通りを求める
int solve(int k, int x){
    if(k==0){  // 終了条件
        if(x==0) return 1;
        else return 0;
    }
    int cnt = 0;  // 何通りあるか

    cnt += solve(k-1, x);  // A[k-1]を使わない通り

    cnt += solve(k-1, x-A[k-1]);  // A[k-1]を使う通り

    return cnt;
}

int main() {
    while(cin >> n){
        A.resize(n);
        for(int i=0;i<n;i++){
            cin >> A[i];
        }
        int m;
        cin >> m;
        for(int i=0;i<m;i++){
            int x;
            cin >> x;
            if(solve(n,x) >= 1){  // 1通り以上ある
                cout << "yes" << endl;
            }
            else{
                cout << "no" << endl;
            }
        }
    }
    return 0;
}

C問題

問題リンク:https://onlinejudge.u-aizu.ac.jp/problems/1160

島を見つけたら、塗りつぶしの要領でその島全体を沈めます。こうすることで1つの島を複数数えることを防げます。

#include <iostream>
using namespace std;

int h, w, field[55][55];

// field[i][j]付近の島を塗りつぶす関数
void dfs(int i, int j){
    field[i][j] = 0;  // その位置の島を塗りつぶす

    // 周囲を探索
    for(int di= -1; di <= 1; di++){
        for(int dj= -1; dj <= 1; dj++){
            int ni = i + di, nj = j + dj;  // 次に見る位置
            if(ni < 0 || ni >= h) continue;  // 配列の範囲外なら無視
            if(nj < 0 || nj >= w) continue;
            if(field[ni][nj] == 1){  // 島を発見
                dfs(ni, nj);  // その周辺を塗りつぶす
            }
        }
    }
}

int main() {
    while(cin >> w >> h, w){
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                cin >> field[i][j];
            }
        }
        int ans = 0;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(field[i][j] == 1){  // 島を発見
                    dfs(i,j);  // 塗りつぶす
                    ans++;  // カウントする
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

コメント

来週はICPCですね。がんばりましょう。

あと、今週末もAtCoder Beginner Contest 133があります。