ガウスの日記
出典：第4回藍橋杯省選C++A/Bグループ
アルゴリズムタグ：シミュレーション
問題説明：
大数学者ガウスには日記をつけるという良い習慣がありました。彼の日記は特別な点があり、年月日を書く代わりに整数を使用していました。例えば、4210という数字です。
後になって、その整数が日付を表していることが分かりました。それは、その日がガウスの誕生日から何日目かを示していました。これは良い習慣かもしれません。日々が過ぎ去るたびに、どれだけの時間が無駄にできるかを思い出させてくれるからです。
ガウスは1777年4月30日に生まれました。彼が発見した重要な定理の日記には5343と記されており、それからその日が1791年12月15日であることが計算できます。
ガウスが博士号を取得した日、日記には8113と書かれています。ガウスが博士号を取得した年月日を計算してください。
出力形式：
yyyy-mm-ddの形式で答えを提出してください。例：1980-03-21
考え方：
この問題は日付を一つずつ計算していく力仕事です。大月、小月、うるう年を考慮する必要があります。ループを使ってシミュレーションを行い、年の増加にも注意が必要です。
C++コード：
#include <iostream>
#include <ctime>
using namespace std;
// うるう年かどうかを判定
bool isLeapYear(int year) {
return (year % 400 == 0) || (year % 100 != 0 && year % 4 == 0);
}
// 月の日数を取得
int getDaysInMonth(int year, int month) {
if (month == 2) {
return isLeapYear(year) ? 29 : 28;
}
if (month == 4 || month == 6 || month == 9 || month == 11) {
return 30;
}
return 31;
}
int main() {
// 初期日付：1777年4月30日
int year = 1777;
int month = 4;
int day = 30;
// 目標の日数：8113日後
int targetDays = 8113;
int elapsedDays = 0;
while (elapsedDays < targetDays) {
day++;
elapsedDays++;
// 月の最終日を超えた場合
if (day > getDaysInMonth(year, month)) {
day = 1;
month++;
// 年を超えた場合
if (month > 12) {
month = 1;
year++;
}
}
}
cout << year << " " << month << " " << day << endl;
return 0;
}不注意な計算
問題説明：
小明はせっかちな子供で、小学校の先生が黒板に書いた問題をよく間違えて書き写していました。ある時、先生が出した問題は「36 × 495 = ?」でしたが、彼は「396 × 45 = ?」と書き間違えました。しかし、結果は劇的で、彼の答えは正しかったのです！なぜなら 36 × 495 = 396 × 45 = 17820 だからです。
このような偶然の一致は他にもあります。例えば：27 × 594 = 297 × 54 などです。
a, b, c, d, e が1〜9の異なる5つの数字（0は含まない）であると仮定して、ab × cde = adb × ce のような形式を満たす式が全部でいくつあるか求めてください。
考え方：
条件 ab × cde = adb × ce を満たす必要があります。データ範囲が小さいので、全ての可能性を網羅的に検索します。
C++コード：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 2桁の数値を作成
int createTwoDigit(int first, int second) {
return first * 10 + second;
}
// 3桁の数値を作成
int createThreeDigit(int first, int second, int third) {
return first * 100 + second * 10 + third;
}
// 重複した数字があるかチェック
bool hasDuplicateDigits(int digits[], int size) {
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
if (digits[i] == digits[j]) {
return true;
}
}
}
return false;
}
int main() {
int count = 0;
int digits[5];
// 1から9までの数字を全て探索
for (digits[0] = 1; digits[0] <= 9; digits[0]++) {
for (digits[1] = 1; digits[1] <= 9; digits[1]++) {
for (digits[2] = 1; digits[2] <= 9; digits[2]++) {
for (digits[3] = 1; digits[3] <= 9; digits[3]++) {
for (digits[4] = 1; digits[4] <= 9; digits[4]++) {
// 重複がないか確認
if (!hasDuplicateDigits(digits, 5)) {
// 数値を作成
int ab = createTwoDigit(digits[0], digits[1]);
int cde = createThreeDigit(digits[2], digits[3], digits[4]);
int adb = createThreeDigit(digits[0], digits[3], digits[1]);
int ce = createTwoDigit(digits[2], digits[4]);
// 条件を満たすか確認
if (ab * cde == adb * ce) {
count++;
}
}
}
}
}
}
}
cout << count << endl;
return 0;
}39段の階段
出典：第4回藍橋杯C/C++Bグループ
アルゴリズムタグ：深さ優先探索、フィボナッチ数列、動的計画法
問題説明：
小明は映画「39段の階段」を観終わったばかりです。映画館から出る際、彼は階段の数を数えたところ、ちょうど39段でした！階段の前で立ち止まった彼は、突然問題を思いつきました：
もし私が一度に1段または2段しか登れないとしたら、左足から始めて左右交互に、最後のステップは右足で踏む（つまり、総ステップ数は偶数）場合、39段の階段を登る方法は何通りあるでしょうか？コンピュータの力を借りて、小明のために答えを見つけてください。
考え方：
1. 39段を登り終えた後の状態から考えると、最後のステップは確定しており、前のステップ（f[n-1]またはf[n-2]）を考えることができます。これは動的計画法の問題と考えることができます。
2. データの特性を活かして、全探索で答えを出します。
C++コード（動的計画法）：
#include <iostream>
#include <vector>
using namespace std;
// ステップの総数
const int TOTAL_STEPS = 39;
// 登り方の数を計算
int countWays() {
// dp[i]: i段目に到達する方法の数
vector<int> dp(TOTAL_STEPS + 1, 0);
// 初期条件
dp[0] = 1; // 地面にいる状態
// 各段について計算
for (int i = 1; i <= TOTAL_STEPS; i++) {
// 1段上がる
if (i >= 1) {
dp[i] += dp[i - 1];
}
// 2段上がる
if (i >= 2) {
dp[i] += dp[i - 2];
}
}
// 偶数ステップで終わる方法の数を計算
int evenStepsCount = 0;
for (int steps = 2; steps <= TOTAL_STEPS; steps += 2) {
evenStepsCount += dp[steps];
}
return evenStepsCount;
}
int main() {
cout << countWays() << endl;
return 0;
}黄金連分数
出典：第4回藍橋杯省選C++Bグループ
アルゴリズムタグ：フィボナッチ数列、高精度計算
問題説明：
黄金比0.61803...は無理数であり、この定数は非常に重要で、多くの工学問題で登場します。ある精密工学では、定数の精度が非常に重要です。ハブル宇宙望遠鏡の話を聞いたことがあるかもしれません。それは初打ち上げ後、人為的な加工誤差を発見し、そのような巨大な物体にとって、鏡面の加工における髪の毛より細かな誤差が一つだけあったにもかかわらず、それが「近視」にしてしまったのです！
話を戻しましょう、黄金分割数の可能な限り正確な値を求める方法はいくつかあります。比較的簡単な方法の一つは連分数を使用することです：
黄金数 = 1/(1 + 1/(1 + 1/(1 + ...)))
この連分数の「階数」が多ければ多いほど、その値は黄金分割数に近づきます。この特性を利用して、小数点以下100位まで正確な黄金分割値を求めてください。小数点以下3位の値は：0.618、小数点以下4位の値は：0.6180、小数点以下5位の値は：0.61803、小数点以下7位の値は：0.6180340（末尾の0は無視しないでください）。
考え方：
黄金連分数は黄金比と同じです。フィボナッチ数列の極限において、fib[n-1]/fib[n]が黄金比に近づきます。これは隣接するフィボナッチ数の比と考えることができます。
C++コード：
#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
using namespace std;
// 高精度除算を実行
string highPrecisionDivision(const string& numerator, const string& denominator, int precision) {
string result = "0.";
string remainder = numerator;
for (int i = 0; i < precision; i++) {
remainder += "0"; // 桁を一つ下げる
// 商を計算
int quotient = 0;
while (compareStrings(remainder, denominator) >= 0) {
remainder = subtractStrings(remainder, denominator);
quotient++;
}
result += to_string(quotient);
}
// 四捨五入
if (precision > 0) {
int lastDigit = result.back() - '0';
if (lastDigit >= 5) {
// 四捨五入の実装
// (実際の実装ではもっと複雑になります)
}
}
return result;
}
// 文字列としての数値を比較
int compareStrings(const string& a, const string& b) {
if (a.length() != b.length()) {
return a.length() - b.length();
}
return a.compare(b);
}
// 文字列としての数値の減算
string subtractStrings(const string& a, const string& b) {
// (実際の実装では桁借りなどを考慮する必要があります)
return "0"; // 簡略化のため
}
// フィボナッチ数列を計算
vector<string> calculateFibonacci(int n) {
vector<string> fib(n + 1);
fib[0] = "1";
fib[1] = "1";
for (int i = 2; i <= n; i++) {
// 高精度加算
fib[i] = addStrings(fib[i-1], fib[i-2]);
}
return fib;
}
// 高精度加算
string addStrings(const string& a, const string& b) {
// (実際の実装では桁上げなどを考慮する必要があります)
return "0"; // 簡略化のため
}
int main() {
const int PRECISION = 100;
const int FIBONACCI_TERMS = 100;
// フィボナッチ数列を計算
vector<string> fib = calculateFibonacci(FIBONACCI_TERMS);
// 黄金比を計算
string goldenRatio = highPrecisionDivision(fib[48], fib[49], PRECISION);
cout << goldenRatio << endl;
return 0;
}接頭辞判定
出典：第4回藍橋杯C/C++Bグループ
アルゴリズムタグ：ポインタ
問題説明：
以下のコードは、needle_startが指す文字列がhaystack_startが指す文字列の接頭辞であるかどうかを判定し、そうでなければNULLを返します。例えば、「abcd1234」は「abc」を接頭辞として含みます。
char* prefix(char* haystack_start, char* needle_start)
{
char* haystack = haystack_start;
char* needle = needle_start;
while(*haystack && *needle){
if(______________________________) return NULL; // 空白部分
}
if(*needle) return NULL;
return haystack_start;
}考え方：
while(*haystack && *needle)のポインタの使い方は、両方の文字列が境界を越えていないことを示しています。if(*needle) return NULL;は、比較後にneedleにまだ残っている場合、接頭辞ではないのでNULLを返します。
上記の原則から、コードでは明らかに比較部分が欠けており、2つの文字列が等しくない場合も接頭辞ではないと判定する必要があります。
解答：
*(haystack++) != *(needle++)
代替的なC++コード：
#include <iostream>
#include <string>
using namespace std;
// 接頭辞を判定する関数
bool isPrefix(const string& haystack, const string& needle) {
if (needle.length() > haystack.length()) {
return false;
}
for (size_t i = 0; i < needle.length(); i++) {
if (haystack[i] != needle[i]) {
return false;
}
}
return true;
}
int main() {
string haystack, needle;
cout << "検索文字列を入力してください: ";
getline(cin, haystack);
cout << "接頭辞として確認する文字列を入力してください: ";
getline(cin, needle);
if (isPrefix(haystack, needle)) {
cout << "接頭辞です" << endl;
} else {
cout << "接頭辞ではありません" << endl;
}
return 0;
}三分整列
出典：2013藍橋杯 CC++プログラミング設計大学Bグループ
問題説明：
一般的な整列には、クイックソートやシェルソートなどの多くの古典的なアルゴリズムがあります。しかし、実際の応用では、特別な要件がよくあります。古典的なアルゴリズムを無理に適用する必要はなく、状況に応じてより良い解決策を構築できます。
例えば、整数型の配列の数字を分類整列する場合：
負数を左端に、正数を右端に、0を中央に配置します。問題の特徴は、負数領域と正数領域内で整列が不要であることです。この特徴を利用して、1回の線形走査で問題を解決できます！
以下のプログラムはこの目標を実装しています。xは整列対象の整数型配列を指し、lenは配列の長さです。
void sort3p(int* x, int len)
{
int p = 0;
int left = 0;
int right = len-1;
while(p<=right){
if(x[p]<0){
int t = x[left];
x[left] = x[p];
x[p] = t;
left++;
p++;
}
else if(x[p]>0){
int t = x[right];
x[right] = x[p];
x[p] = t;
right--;
}
else{
__________________________; // 空白部分
}
}
}考え方：
負数を左端に、正数を右端に、0を中央に配置します。
- pはカウンターとして使用され、leftは0、rightは最大値です。
- tはswap用です。
- このロジックでは、0の場合はp++、つまり総数-1、つまり最終的に中央に0が格納されます！
解答：
p++;
代替的なC++コード：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 三分整列を行う関数
void threeWaySort(vector<int>& arr) {
int left = 0; // 負数の領域の右端
int right = arr.size() - 1; // 正数の領域の左端
int current = 0; // 現在の要素
while (current <= right) {
if (arr[current] < 0) {
// 負数の場合：左端と交換
swap(arr[current], arr[left]);
left++;
current++;
} else if (arr[current] > 0) {
// 正数の場合：右端と交換
swap(arr[current], arr[right]);
right--;
} else {
// 0の場合：次の要素へ
current++;
}
}
}
int main() {
vector<int> arr = {25, 18, -2, 0, 16, -5, 33, 21, 0, 19, -16, 25, -3, 0};
cout << "整列前の配列: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
threeWaySort(arr);
cout << "整列後の配列: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}誤った領収書
出典：第4回藍橋杯省選C++A/Bグループ
アルゴリズムタグ：整列、シミュレーション
問題説明：
ある機密機関から特定の領収書が発行され、年末にはすべて回収されます。各領収書には一意のID番号があります。全年のすべての領収書のID番号は連続していますが、IDの開始番号はランダムに選択されています。担当者の不注意により、ID番号の入力時に1つの誤りが発生し、あるIDが欠番になり、別のIDが重複しました。
あなたのタスクは、プログラミングを通じて、欠番のIDと重複するIDを見つけることです。欠番は最大値と最小値で発生しないと仮定します。
入力形式：
最初の行には整数Nが含まれ、その後にN行のデータが続きます。次のN行には、スペースで区切られた100個以下の正整数（100,000以下）が含まれ、各整数はID番号を表します。
出力形式：
プログラムは1行を出力し、2つの整数m、nをスペースで区切って表示します。mは欠番ID、nは重複IDを表します。
データ範囲：
1≤N≤100
入力例：
2
5 6 8 11 9
10 12 9出力例：
7 9考え方：
この問題は、配列内の重複番号と欠番を見つけるだけです。整列すれば十分です。難点は文字列の読み込み処理にあります。
代替的なC++コード：
#include <iostream>
#include <vector>
#include <algorithm>
#include
using namespace std;
// IDのリストから欠番と重複を検出
void findMissingAndDuplicate(const vector<int>& ids, int& missing, int& duplicate) {
unordered_set<int> idSet;
int minId = ids[0];
int maxId = ids[0];
// 最小値と最大値を特定
for (int id : ids) {
if (id < minId) minId = id;
if (id > maxId) maxId = id;
}
// 各IDの出現回数をカウント
vector<int> count(maxId - minId + 1, 0);
for (int id : ids) {
count[id - minId]++;
}
// 欠番と重複を特定
for (int i = 0; i < count.size(); i++) {
if (count[i] == 0) {
missing = minId + i;
} else if (count[i] > 1) {
duplicate = minId + i;
}
}
}
int main() {
int n;
cin >> n;
cin.ignore(); // 改行文字を消費
vector<int> allIds;
string line;
for (int i = 0; i < n; i++) {
getline(cin, line);
size_t start = 0;
size_t end = line.find(' ');
while (end != string::npos) {
allIds.push_back(stoi(line.substr(start, end - start)));
start = end + 1;
end = line.find(' ', start);
}
// 最後の要素を追加
allIds.push_back(stoi(line.substr(start)));
}
int missing, duplicate;
findMissingAndDuplicate(allIds, missing, duplicate);
cout << missing << " " << duplicate << endl;
return 0;
} コインの裏返し
出典：第4回藍橋杯省選C++Bグループ
アルゴリズムタグ：動的計画法、再帰
問題説明：
小明は「コインの裏返し」ゲームをプレイしています。テーブルには、一列に並んだいくつかのコインがあります。*を表、oを裏（小文字のo、0ではありません）とします。
例えば、状態は次のようになるかもしれません：**oo*oooo
左の2つのコインを同時に裏返すと、oooo****ooooになります。
今、小明の問題は：初期状態と目標状態が既知で、毎回隣接する2つのコインしか裏返せない場合、特定の局面に対して最小で何回裏返す必要があるかということです。
隣接する2つのコインを裏返す操作を1ステップと呼びます。
入力形式：
2行の同じ長さの文字列で、それぞれ初期状態と目標状態を表します。
出力形式：
整数1つ、最小操作回数を表します。
データ範囲：
入力文字列の長さは100以下です。答えが存在することが保証されています。
入力例1：
**********
o****o****出力例1：
5入力例2：
*o**o***o***
*o***o**o***出力例2：
1考え方：
現在のi番目のコインの状態はi-1によって決まります。任意の2つのコインの状態がある場合、i,i+1を同時に裏返すしかありません。連続して裏返し、配列aが配列bと完全に一致するまで操作回数を出力します。
代替的なC++コード：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// コインの状態を裏返す
void flipCoin(string& coins, int position) {
if (position >= 0 && position < coins.length()) {
coins[position] = (coins[position] == '*') ? 'o' : '*';
}
}
// 隣接する2つのコインを裏返す
void flipAdjacentCoins(string& coins, int position) {
flipCoin(coins, position);
flipCoin(coins, position + 1);
}
// 最小操作回数を計算
int calculateMinOperations(const string& start, const string& target) {
string current = start;
int operations = 0;
// 左から右へ順に処理
for (int i = 0; i < current.length() - 1; i++) {
if (current[i] != target[i]) {
// 現在のコインが目標と異なる場合、隣接する2つを裏返す
flipAdjacentCoins(current, i);
operations++;
}
}
// 最後のコインを個別にチェック
if (current[current.length() - 1] != target[current.length() - 1]) {
// 最後のコインだけが異なる場合、解は存在しない（問題保証によりここには到達しない）
return -1;
}
return operations;
}
int main() {
string start, target;
cin >> start >> target;
int minOperations = calculateMinOperations(start, target);
cout << minOperations << endl;
return 0;
}帯分数
出典：第4回藍橋杯省選C++Bグループ
アルゴリズムタグ：全探索、バックトラッキング、枝刈り
問題説明：
100は帯分数の形式で表現できます：100=3+69258714。また、100=82+3546197と表現できます。特徴は、帯分数において数字1〜9がそれぞれ1回だけ出現すること（0を含まない）です。
このような帯分数では、100には11種類の表現方法があります。
入力形式：
1つの正整数。
出力形式：
入力された数字を1〜9の数字を重複なく使用して帯分数として表現するすべての方法の数を出力します。
データ範囲：
1≤N<10^6
入力例1：
100出力例1：
11入力例2：
105出力例2：
6考え方：
問題から、帯分数において数字1〜9がそれぞれ1回だけ出現することがわかります。帯分数の特性はn=a+b/c、つまりn×c=a×c+bです。
最も直接的な方法は、1〜9の数字を全て探索し、各数字が1回だけ使用されるように制限し、n×c=a×c+bを満たすか確認します。
代替的なC++コード：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 数字が1〜9までの数字を1回ずつ使用しているか確認
bool isValidNumber(const vector<int>& digits) {
vector<bool> used(10, false);
for (int digit : digits) {
if (digit < 1 || digit > 9 || used[digit]) {
return false;
}
used[digit] = true;
}
return true;
}
// 数字のリストから整数を作成
int createNumber(const vector<int>& digits, int start, int end) {
int number = 0;
for (int i = start; i <= end; i++) {
number = number * 10 + digits[i];
}
return number;
}
// 帯分数の組み合わせを探索
int countMixedFractions(int n) {
vector<int> digits(9);
int count = 0;
// 1〜9の順列を生成
for (int i = 0; i < 9; i++) {
digits[i] = i + 1;
}
do {
// a, b, cの分割位置を探索
for (int aEnd = 0; aEnd < 9; aEnd++) {
for (int bEnd = aEnd + 1; bEnd < 9; bEnd++) {
int a = createNumber(digits, 0, aEnd);
int b = createNumber(digits, aEnd + 1, bEnd);
int c = createNumber(digits, bEnd + 1, 8);
// 帯分数の条件を確認
if (n * c == a * c + b) {
count++;
}
}
}
} while (next_permutation(digits.begin(), digits.end()));
return count;
}
int main() {
int n;
cin >> n;
cout << countMixedFractions(n) << endl;
return 0;
}区間連番数
出典：第4回藍橋杯省選C++Bグループ
アルゴリズムタグ：全探索、区間探索
問題説明：
小明は最近、奇妙で興味深い問題をずっと考えていました：1〜Nのある順列にはいくつの連番区間があるのでしょうか？
ここで言う連番区間の定義は：区間[L,R]内のすべての要素（つまり、この順列のL番目からR番目の要素）を昇順にソートすると、長さがR-L+1の「連続」数列が得られる場合、この区間を連番区間と呼びます。
Nが小さい場合、小明はすぐに答えを計算できますが、Nが大きくなると問題はそれほど単純ではなくなります。今、小明はあなたの助けが必要です。
入力形式：
最初の行は正整数Nで、順列の规模を表します。
2行目はN個の異なる数字Piで、このN個の数字の特定の順列を表します。
出力形式：
異なる連番区間の数を出力する整数。
データ範囲：
1≤N≤10000, 1≤Pi≤N
入力例1：
4
3 2 4 1出力例1：
7入力例2：
5
3 4 2 5 1出力例2：
9考え方：
区間[L,R]内のすべての要素（つまり、この順列のL番目からR番目の要素）を昇順にソートすると、長さがR-L+1の「連続」数列が得られる場合、この区間を連番区間と呼びます。
1.連番であるためには、単調増加部分列であり、かつその区間内のすべての数字が使用されている必要があります。
2.左右の端点をループで探索し、右端点-左端点が現在の最大値-現在の最小値と等しい場合、左端点から右端点までのすべての数が使用され、単調増加部分列であると判断できます。
代替的なC++コード：
#include <iostream>
#include <vector>
#include
using namespace std;
// 区間が連番かどうかを判定
bool isConsecutive(const vector<int>& arr, int left, int right) {
unordered_set<int> numbers;
int minVal = arr[left];
int maxVal = arr[left];
// 区間内の最小値と最大値を特定
for (int i = left; i <= right; i++) {
numbers.insert(arr[i]);
if (arr[i] < minVal) minVal = arr[i];
if (arr[i] > maxVal) maxVal = arr[i];
}
// 最大値 - 最小値 + 1 が区間の長さと等しい場合、連番
return (maxVal - minVal + 1) == (right - left + 1);
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int count = 0;
// すべての可能な区間を探索
for (int left = 0; left < n; left++) {
for (int right = left; right < n; right++) {
if (isConsecutive(arr, left, right)) {
count++;
}
}
}
cout << count << endl;
return 0;
}