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}$ で求められます。