1 C/C++の基礎知識

1.1 無限大の定義（INF）

整数型の無限大を表す定数の定義方法：

const int INF = 0x3f3f3f3f;

1.2 scanf関数の使い方

一般的なデータ型のscanfフォーマット指定子：

データ型	フォーマット指定子
int	%d
long long	%lld
float	%f
double	%lf
char	%c
文字列（char配列）	%s

1.3 実用的な出力フォーマット

1.3.1 %md

%mdは、int型変数がm桁に満たない場合にm桁で右寄せ出力します。上位桁はスペースで埋められます。変数が既にm桁を超えている場合は、そのまま出力されます。

例：

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

int main() {
    int num1 = 123, num2 = 1234567;
    printf("%5d\n", num1);
    printf("%5d\n", num2);
    return 0;
}

出力結果：

  123
1234567

1.3.2 %0md

変数がm桁に満たない場合、上位桁を0で埋めます。

例：

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

int main() {
    int num1 = 123, num2 = 1234567;
    printf("%05d\n", num1);
    printf("%05d\n", num2);
    return 0;
}

出力結果：

00123
1234567

1.3.3 %.mf

浮動小数点数をm桁の小数部で出力します。四捨六入五成双のルールが適用されます。

例：

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

int main() {
    double value = 12.3456;
    printf("%.0f\n", value);
    printf("%.1f\n", value);
    printf("%.2f\n", value);
    printf("%.3f\n", value);
    printf("%.4f\n", value);
    return 0;
}

出力結果：

12
12.3
12.35
12.346
12.3456

1.4 typedefの使用

long long型を簡略化して定義する例：

typedef long long LL;

1.5 よく使われる数学関数

1.5.1 fabs(double x)

double型変数の絶対値を計算します。

1.5.2 floor(double x), ceil(double x)

それぞれdouble型変数の切り捨てと切り上げを行います。戻り値はdouble型です。

1.5.3 pow(double r, double p)

rのp乗を計算します。両方の引数はdouble型である必要があります。

1.5.4 sqrt(double x)

double型変数の平方根を計算します。

1.5.5 log(double x)

自然対数（底e）の対数を計算します。

注意：C言語には任意の底の対数を直接計算する関数がないため、底の変換公式を使用する必要があります。

log_a(b) = log_e(b) / log_e(a)

1.5.6 round(double x)

double型変数xを四捨五入します。戻り値もdouble型なので、整数型に変換する必要があります。

注：コード中でif(n)はif(n!=0)と同じ意味、if(!n)はif(n==0)と同じ意味です。

1.6 breakとcontinue文

break：必要な場面でループを直接終了します。

continue：条件が満たされた場合にcontinueを実行すると、それ以降の処理をスキップし、次のループ反復に進みます。

1.7 配列の注意点

サイズsizeの1次元配列を定義した場合、アクセスできるのはインデックス0からsize-1までの要素です。例えば、int a[10]ではa[0], a[1], ..., a[9]にアクセスできますが、a[10]にはアクセスできません。

1.8 memset関数

配列の全要素に同じ値を設定する関数：

memset(配列名, 値, sizeof(配列名));

配列の全要素を0に設定する例：

memset(配列名, 0, sizeof(配列名));

1次元配列と2次元配列の両方に適用できます。

1.9 strlen()関数

文字配列内の最初の\0までの文字数を取得します。

strlen(文字配列);

2 アルゴリズム入門

2.1 シミュレーション

シミュレーションとは、問題の記述に従ってそのままコードを書く手法で、特定のアルゴリズムをあまり必要とせず、問題の記述に基づいてコーディング能力を試すものです。

2.1.1 コラッツの予測（3n+1問題）

#include <iostream>
using namespace std;

int main() {
    int number, count = 0;
    cin >> number;
    
    while (number != 1) {
        if (number % 2 == 0)
            number = number / 2;
        else
            number = (3 * number + 1) / 2;
        count++;
    }
    
    cout << count << endl;
    return 0;
}

2.1.2 学校別得点集計

#include <iostream>
using namespace std;

const int MAX_SCHOOLS = 100010;
int schoolScores[MAX_SCHOOLS] = {0};

int main() {
    int numEntries, schoolId, score;
    cin >> numEntries;
    
    for (int i = 0; i < numEntries; i++) {
        cin >> schoolId >> score;
        schoolScores[schoolId] += score;
    }
    
    int topSchool = 1, maxScore = -1;
    for (int i = 1; i <= numEntries; i++) {
        if (schoolScores[i] > maxScore) {
            maxScore = schoolScores[i];
            topSchool = i;
        }
    }
    
    cout << topSchool << " " << maxScore << endl;
    return 0;
}

2.2 要素の検索

2.2.1 配列内の要素検索

#include <iostream>
using namespace std;

const int MAX_SIZE = 210;
int arr[MAX_SIZE];

int main() {
    int size, target;
    while (cin >> size) {
        for (int i = 0; i < size; i++) {
            cin >> arr[i];
        }
        
        cin >> target;
        int position;
        for (position = 0; position < size; position++) {
            if (arr[position] == target) {
                cout << position << endl;
                break;
            }
        }
        
        if (position == size) {
            cout << -1 << endl;
        }
    }
    return 0;
}

2.3 図形の出力

2.3.1 正方形パターンの出力

#include <iostream>
using namespace std;

int main() {
    int width, height;
    char symbol;
    cin >> width >> symbol;
    
    height = (width % 2 == 1) ? width / 2 + 1 : width / 2;
    
    // 上辺の出力
    for (int i = 0; i < width; i++) {
        cout << symbol;
    }
    cout << endl;
    
    // 中間部分の出力
    for (int i = 1; i < height - 1; i++) {
        cout << symbol;
        for (int j = 0; j < width - 2; j++) {
            cout << " ";
        }
        cout << symbol << endl;
    }
    
    // 下辺の出力（高さが1より大きい場合のみ）
    if (height > 1) {
        for (int i = 0; i < width; i++) {
            cout << symbol;
        }
        cout << endl;
    }
    
    return 0;
}

2.4 日付処理

2.4.1 日付間の差分計算

#include <iostream>
using namespace std;

int monthDays[13][2] = {
    {0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30},
    {31, 31}, {30, 30}, {31, 31}, {31, 31}, {30, 30},
    {31, 31}, {30, 30}, {31, 31}
};

bool isLeapYear(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

int main() {
    int date1, date2;
    while (cin >> date1 >> date2) {
        if (date1 > date2) {
            int temp = date1;
            date1 = date2;
            date2 = temp;
        }
        
        int y1 = date1 / 10000, m1 = date1 % 10000 / 100, d1 = date1 % 100;
        int y2 = date2 / 10000, m2 = date2 % 10000 / 100, d2 = date2 % 100;
        
        int daysDiff = 1;
        while (y1 < y2 || m1 < m2 || d1 < d2) {
            d1++;
            if (d1 == monthDays[m1][isLeapYear(y1)] + 1) {
                m1++;
                d1 = 1;
            }
            if (m1 == 13) {
                y1++;
                m1 = 1;
            }
            daysDiff++;
        }
        
        cout << daysDiff << endl;
    }
    return 0;
}

2.5 基数変換

2.5.1 基数変換のテンプレート

P進数の数xをQ進数に変換するには、2段階のプロセスが必要です。

（1）P進数xを10進数yに変換

int y = 0, product = 1;
while (x != 0) {
    y = y + (x % 10) * product;
    x = x / 10;
    product = product * P;
}

（2）10進数yをQ進数zに変換

int z[40], digitCount = 0;
do {
    z[digitCount++] = y % Q;
    y = y / Q;
} while (y != 0);

2.5.2 D進数でのA+B

#include <iostream>
using namespace std;

int main() {
    int a, b, base;
    cin >> a >> b >> base;
    
    int sum = a + b;
    int result[31], numDigits = 0;
    
    do {
        result[numDigits++] = sum % base;
        sum /= base;
    } while (sum != 0);
    
    for (int i = numDigits - 1; i >= 0; i--) {
        cout << result[i];
    }
    
    return 0;
}

2.6 文字列処理

2.6.1 回文判定

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

const int MAX_LENGTH = 256;

bool isPalindrome(char str[]) {
    int len = strlen(str);
    for (int i = 0; i < len / 2; i++) {
        if (str[i] != str[len - 1 - i]) {
            return false;
        }
    }
    return true;
}

int main() {
    char inputStr[MAX_LENGTH];
    while (cin.getline(inputStr, MAX_LENGTH)) {
        if (isPalindrome(inputStr)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

3 基本的なアルゴリズム

3.1 ソート

ソート問題では、通常C++のsort関数を使用します。ソート問題の一般的な解決手順：

3.1.1 関連する構造体の定義

ソート問題では、通常、個人の多くの情報（名前、試験番号、スコア、順位など）が与えられます。これらの情報を格納するために構造体配列を使用できます。例：

struct Student {
    char name[10];    // 名前
    char id[10];      // 試験番号
    int score;        // スコア
    int rank;         // 順位
} students[100010];

3.1.2 比較関数の作成

sortを使用してソートする際には、ソートルールを実装するcmp関数を提供する必要があります。例えば、以下の要件：すべての学生をスコアの降順でソートし、スコアが同じ場合は名前の辞書順で昇順にソートします。

実際のソートルールは次のように記述できます：

1. 2人の学生のスコアが異なる場合、スコアが高い学生を前に配置
2. そうでない場合、辞書順で小さい名前の学生を前に配置

対応するcmp関数：

bool compareStudents(Student a, Student b) {
    if (a.score != b.score)
        return a.score > b.score;
    else
        return strcmp(a.name, b.name) < 0;
}

注：strcmp(str1, str2)は、str1の辞書順がstr2より小さい場合は負数、等しい場合は0、大きい場合は正数を返します。

3.1.3 順位の実装

多くのソート問題では、ソート後に各個人の順位を計算する必要があります。一般的なルールは：スコアが異なる場合は順位も異なり、スコアが同じ場合は同じ順位で、その順位を占有します。例えば、5人の学生のスコアが90、88、88、88、86の場合、順位は1、2、2、2、5となります。

実装方法：

まず、配列の最初の個人の順位を1とします。次に、残りの個人を走査します。現在の個人のスコアが前の個人のスコアと等しい場合、現在の個人の順位は前の個人の順位と同じになります。そうでない場合、現在の個人の順位は配列のインデックス+1になります。

students[0].rank = 1;
for (int i = 1; i < n; i++) {
    if (students[i].score == students[i-1].score) {
        students[i].rank = students[i-1].rank;
    } else {
        students[i].rank = i + 1;
    }
}