第5回藍橋杯 C++ B級プログラミングコンテスト問題解説

1. ビールと飲料の購入

解法: 全探索(ブルートフォース)
ビール(1缶2.3元)と飲料(1缶1.9元)の合計金額が82.3元。ビールの本数が飲料より少ない条件で計算します。浮動小数点計算の誤差を避けるため、10倍して整数で処理します。

#include <iostream>
using namespace std;

int main() {
    for (int beer = 0; beer <= 823 / 23; ++beer) {
        for (int soft = beer + 1; soft * 19 + beer * 23 <= 823; ++soft) {
            if (beer * 23 + soft * 19 == 823) {
                cout << beer << endl;
            }
        }
    }
    return 0;
}

2. 面切りの回数

解法: 漸化式
対折回数 $n$ に対して、面の本数 $f(n)$ は $f(n) = 2 \times f(n-1) - 1$ となります。$f(0)=2$ から計算します。

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

int main() {
    int noodles = 2;
    for (int i = 0; i < 10; ++i) {
        noodles = noodles * 2 - 1;
    }
    cout << noodles << endl;
    return 0;
}

3. 李白の酒飲み歩き

解法: 深さ優先探索 (DFS)
酒の量を状態として保持し、店(酒が2倍)と花(酒が1減る)を再帰的に選択します。合計15ステップ(店5回、花10回)で最後の酒が0になるパターンを探します。

#include <iostream>
using namespace std;

int total_ways = 0;
void solve(int shops, int flowers, int sake, int step) {
    if (shops > 5 || flowers > 10 || sake < 0) return;
    if (step == 15) {
        if (shops == 5 && flowers == 10 && sake == 0) total_ways++;
        return;
    }
    solve(shops + 1, flowers, sake * 2, step + 1);
    solve(shops, flowers + 1, sake - 1, step + 1);
}

4. 史豊収(Shi Fengshou)乗算アルゴリズム

解法: 文字列比較による繰り上がり判定
問題のコードは、多倍長乗算における7倍の計算シミュレーションです。不足している部分は、辞書順比較の結果に基づいて進位(キャリー)を決定するロジックです。

// 補完コード部分
if (r < 0) return i + 1;

5. フラクタル図形の描画

解法: 再帰的描画
ランク $N$ の三角形を描くために、3つの $N-1$ ランクの三角形を適切なオフセット位置に配置します。空白行のパディング処理が重要です。

// 補完コード部分
f(a, rank - 1, row, col + half_width);

6. 不思議な分数

解法: GCDによる等価判定
分子 $a, c$ と分母 $b, d$ について、$\frac{a}{b} \times \frac{c}{d} = \frac{10a+c}{10b+d}$ を満たす組み合わせを探します。最大公約数(GCD)を用いて約分した後の値で比較します。

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
// 判断ロジック:
if ((a * c) * (10 * b + d) == (10 * a + c) * (b * d)) count++;

7. 六角形の数値埋め

解法: 全順列探索
1から12までの数値を順列として並べ、六角形の各辺の合計が等しくなるものを探します。固定された値(1, 8, 3)を制約条件に含めます。

8. 蟻の感冒(風邪)

解法: 物理シミュレーションの簡略化
衝突は単なる方向転換であるため、蟻を「通り抜ける」と解釈して計算します。感冒にかかった蟻より左側で右向きに移動している蟻、および右側で左向きに移動している蟻をカウントします。

9. 地宮取宝(宝探し)

解法: 動的計画法 (DP)
状態を dp[i][j][k][v](位置 $(i,j)$、個数 $k$、最大値 $v$)として定義します。選択する場合としない場合の遷移を足し合わせます。

10. 子供たちの並び替え

解法: 樹状配列(Binary Indexed Tree)
ある子供を所定の位置に置くまでに必要な交換回数は、その子供より前にいて身長が高い人数と、後ろにいて身長が低い人数の和です。各子供の不満度は交換回数 $k$ に対して $\sum_{i=1}^k i = \frac{k(k+1)}{2}$ で求められます。

タグ: C++ 算法 動的計画法 再帰 データ構造

7月29日 17:12 投稿