本棚の奥底にあった蟻本を取り出した．

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

作者: 秋葉拓哉,岩田陽一,北川宜稔
出版社/メーカー: マイナビ
発売日: 2012/01/28
メディア: 単行本（ソフトカバー）
購入: 25人クリック: 473回
この商品を含むブログ (36件) を見る

テンプレート

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REP2(i, st, ed) for (int i = st; i <= ed; i++)
using namespace std;

static const int inf = 1 << 28;

int main()
{
    return 0;
}

chaper 2

2-1 全探索問題

深さ優先探索01

部分和問題

数列${a_n}$から，要素をいくつか取り出して部分数列$b$を作る．入力$S$に対して，$b$の和が$S$となるような組み合わせは存在するか

アルゴリズム例

$i\leftarrow 0,s \leftarrow 0$

$dfs(index, sum):$

$i=n$ならば終了
部分和に要素$a[i]$を．．．
1. 含める$dfs(i+1,s+a[i])$
2. 含めない$dfs(i+1,s)$

bool dfs(int i, int sum)
{
    if (i == n)
        return sum == k;
    if (dfs(i + 1, sum))
        return true;
    if (dfs(i + 1, sum + a[i]))
        return true;
}

深さ優先n探索02

8近傍島数算出問題

大きさ$n\times m~$の庭があります．そこに雨が降り，水たまりが出来ました．ある水たまりに対し，8近傍に隣接した水たまりがある場合その水たまりは連結していると考えます．いくつの水たまりがあるかを出力せよ．

void dfs(int x, int y)
{
    if (map[x][y] == 0 ||
        x < 0 || y < 0 ||
        x > n || y > m)
        return;
    map[x][y] = 0;
    REP2(i, -1, 1)
    {
        REP2(j, -1, 1)
        {
            dfs(x - i, y - j);
        }
    }
}

幅優先探索01

迷路探索

$n\times m~$の迷路に対し，最短経路でスタートからゴールに到達したときのステップ数を出力せよ．入力は.を通路，#を壁，Sを開始地点，Gをゴール地点とする．

距離をd=infでリセット

$d(all)=\infty$
始点をd=0にして，キューに積む

$d(start)=0$

$Q.push(start)$
キューのつづく限り以下の処理をする
1. キューの先頭を取り出す
  
  $current = Q.pop()$
2. ゴールならば抜ける
3. 次の未探索かつ壁でない経路候補全てに以下の処理をする
  1. キューに積む
  2. d を更新する
  $d(next) \leftarrow d(current) + 1$

typedef pair<int, int> V;

int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};

int bfs()
{
    queue<V> que;
    REP(i, n)
    {
        REP(j, m)
        {
            d[i][j] = INF;
        }
    }
    que.push(V(stx, sty));
    d[stx][sty] = 0;

    while (!que.empty())
    {
        V cur = que.front();
        que.pop();
        if (cur.first == gox && cur.second == goy)
            break;
        REP(i, 4)
        {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if (0 <= nx && nx < n && 
                0 <= ny && ny < m &&
                mp[nx][ny] != '#' && d[nx][ny] == INF)
            {
                que.push(V(nx, ny));
                d[nx][ny] =
                     d[cur.first][cur.second] + 1;
            }
        }
    }
    return d[gox][goy];
}

2-2 貪欲法

貪欲法01

区間スケジューリング問題．

現在時間から選べるスケジュールのうち，最も早い時間に終わるものを選択すると良い．

void greedy()
{
    sort(_pair, _pair + n);

    int ans = 0, t = 0;
    REP(i, n)
    {
        if (t < _pair[i].second)
        {
            ans++;
            t = _pair[i].first;
        }
    }
    cout << ans << endl;
}

貪欲法02

実践例：

$n$個の点が数直線状にあり，その座標は$X_i,(i=1,2,...,n)$である．その点のうちいくつかを選び印をつけるとする．印をつけた点から$r$の範囲内にすべての点$X_i$を含めるためには，最低いくつの点に印をつける必要があるか

直感的な発想を実装すればOK

void greedy()
{
    sort(p, p + n);
    int i = 0, ans = 0;
    while (i < n)
    {
        int s = p[i++];
        while (i < n && p[i] <= s + r)
            i++;
        int m = p[i - 1];
        while (i < n && p[i] <= m + r)
            i++;
        ans++;
    }
    cout << ans << endl;
}

貪欲法03

辞書順最小

$n$文字からなる文字列$S$の先頭または末端から取り出して，末端に連結してできる$n$文字の文字列$T$を考える．$T$のうち辞書順で最小となるものを出力せよ．

基本，先頭と末端の辞書順を比べる．先頭と末端が同じ文字だった場合に，次に続く(先頭+1と末端-1)文字同士を比較して，辞書順で小さかった方の端の文字を出力すれば良い．for文で実装できるが終了条件に注意する．

void greedy()
{
    int a = 0, b = n - 1;
    bool left;
    while (a <= b)
    {
        for (int i = 0; a + i <= b; i++)
        {
            if (S[a + i] > S[b - i])
            {
                left = false;
                break;
            }
            else if (S[a + i] < S[b - i])
            {
                left = true;
                break;
            }
        }
        if (left)
            cout << S[a++];
        else
            cout << S[b--];
    }
    cout << endl;
}

貪欲法04

木こりは木を切りたい．切りたい長さは$L_1,L_2,...,L_n$であり，もとの長さはちょうどこの長さの和に等しい．板を切るためには板の長さ分のコストが掛かるとする．たとえば長さ$21$の板を$13$と$8$に分割した際にかかるコストは$21$である．コストが最小で木を切り分けたときのかかるコストはいくらか

$sum\leftarrow 0$
$\text{while}~~L.length()\geq2$
1. $\text{sort}(L, \leq)$
2. $m_1 = L.front(),m_2=L.front()$
3. $L.popFront()\times 2$
4. $sum\leftarrow sum+m_1+m_2$
5. $L.pushFront(m_1+m_2)$
$\text{return}~~sum$

vector<int> L;

void greedy()
{
    int ans = 0;
    while (L.size() >= 2)
    {
        sort(L.rbegin(), L.rend());
        int m1 = L.back();
        L.pop_back();
        int m2 = L.back();
        L.pop_back();
        ans += m1 + m2;
        L.push_back(m1 + m2);
    }
    cout << ans << endl;
}

進捗だめです

Notebook

🐜本の進捗(6/25)