【メモ】灰色部門が茶色になるために勉強用アルゴリズム

つい先日、AtCoderのコンテストに初参加しました。過去問を解くのは当たり前なのですが、解き方の種類をある程度知っておかないと、まず発想として解き方が思い浮かばない場合もあるのでよく出る、たまに出ると言われるアルゴリズムをまとめてみました。

C++で解いた方が良いってよく言われますが、高校時代に一番初めに触ったプログラミング言語がC言語だったので、なんとなくC言語から離れられないです（笑）

基本的に
・アルゴリズム
・例題
・解答

というような構成で続いています。目指せ茶色！！！

:::note warn
・例題はあくまで例なので、本番には関係ありません。
:::

## 1. 階乗
階乗は、1からnまでの全ての自然数の積を計算します。nの階乗は、n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1と表されます。

```c
int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}
```
<details><summary>例題</summary>

**問題**: 整数 $N$ が与えられます。 $N$ の階乗を計算してください。

**制約**: 

$1 \leq N \leq 10$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>

int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", factorial(n));
    return 0;
}
```

</details>

## 2. 基数変換
基数変換は、ある数を一つの基数から別の基数に変換するプロセスです。例えば、10進数から2進数への変換などがあります。

```c
#include <stdio.h>

void to_binary(int n) {
    if (n / 2 != 0) {
        to_binary(n / 2);
    }
    printf("%d", n % 2);
}
```
<details><summary>例題</summary>

**問題**: 10進数の数 $N$ が与えられます。 $N$ を2進数に変換してください。

**制約**: 

$1 \leq N \leq 10^5$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>

void to_binary(int n) {
    if (n > 1) {
        to_binary(n / 2);
    }
    printf("%d", n % 2);
}

int main() {
    int n;
    scanf("%d", &n);
    to_binary(n);
    printf("\n");
    return 0;
}
```

</details>

## 3. 文字列の回文判定
回文は、前から読んでも後ろから読んでも同じになる文字列のことを指します。

```c
#include <string.h>

int is_palindrome(char *str) {
    int len = strlen(str);
    for (int i = 0; i < len / 2; i++) {
        if (str[i] != str[len - i - 1]) {
            return 0;
        }
    }
    return 1;
}
```
<details><summary>例題</summary>

**問題**: 文字列 $S$ が与えられます。 $S$ が回文であるかどうかを判定してください。

**制約**: 

$S$の長さは$1 \leq |S| \leq 10^5$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>
#include <string.h>

int is_palindrome(char *s) {
    int len = strlen(s);
    for (int i = 0; i < len / 2; i++) {
        if (s[i] != s[len - 1 - i]) {
            return 0;
        }
    }
    return 1;
}

int main() {
    char s[100];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = '\0';  // 改行文字を削除
    printf("%d\n", is_palindrome(s));
    return 0;
}

```

</details>

## 4. 最大公約数・最小公倍数
最大公約数(GCD)は、2つの数の共通の約数の中で最大のものを指します。最小公倍数(LCM)は、2つの数の共通の倍数の中で最小のものを指します。

```c
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
```
<details><summary>例題</summary>

**問題**: 2つの整数 $A$ と $B$ が与えられます。$A$ と $B$ の最大公約数と最小公倍数を計算してください。

**制約**: 

$1 \leq A,B \leq 10^5$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    printf("gcd: %d, lcm: %d\n", gcd(a, b), lcm(a, b));
    return 0;
}
```

</details>

## 5. 線形全探索
線形全探索は、全ての要素を一つずつ調べて目的の要素を見つけ出す方法です。

```c
#include <stdio.h>

int linear_search(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

int main() {
    int n, x;
    scanf("%d %d", &n, &x);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    printf("%d\n", linear_search(arr, n, x));
    return 0;
}
```
<details><summary>例題</summary>

**問題**: 2つの整数 $A$ と $B$ が与えられます。$A$ と $B$ の最大公約数と最小公倍数を計算してください。

**制約**: 

$1 \leq A,B \leq 10^5$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>

void cumulative_sum(int arr[], int n) {
    int sum[n];
    sum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        sum[i] = sum[i - 1] + arr[i];
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", sum[i]);
    }
    printf("\n");
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    cumulative_sum(arr, n);
    return 0;
}
```

</details>

## 6. 累積和
累積和は、配列の各要素に対して、その要素までの要素の和を計算したものです。これにより、配列の任意の範囲の合計を効率的に計算することができます。

```c
#include <stdio.h>

void cumulative_sum(int arr[], int n) {
    int sum[n];
    sum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        sum[i] = sum[i - 1] + arr[i];
    }
    // sum[i] は arr[0] から arr[i] までの合計になります
}
```
<details><summary>例題</summary>

**問題**: $N$ 個の整数 $a_1,a_2,...,a_N$ が与えられます。各 $i$ につい、$a_1+a_2+...+a_i$ を計算してください。

**制約**: 

$1 \leq N \leq 10^5$
$-10^9 \leq a_i \leq 10^9$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>

void cumulative_sum(int arr[], int n) {
    int sum[n];
    sum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        sum[i] = sum[i - 1] + arr[i];
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", sum[i]);
    }
    printf("\n");
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    cumulative_sum(arr, n);
    return 0;
}
```

</details>

## 7. 平方数判定
平方数は、ある整数の2乗で表される数です。平方数を判定する一つの方法は、数の平方根を取り、それが整数であるかどうかを確認することです。

```c
#include <math.h>

int is_square(int n) {
    int root = sqrt(n);
    return root * root == n;
}
```
<details><summary>例題</summary>

**問題**: 整数 $N$ が与えられます。 $N$ が平方数であるかどうかを判定してください。

**制約**: 

$1 \leq N \leq 10^9$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>
#include <math.h>

int is_square(int n) {
    int root = sqrt(n);
    return root * root == n;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", is_square(n));
    return 0;
}
```

</details>

## 8. 素数判定
素数は、1と自分自身以外に約数を持たない正の整数です。素数を判定する一つの方法は、2からその数の平方根までの全ての数で割り切れるかどうかを確認することです。

```c
#include <stdio.h>
#include <math.h>

int is_prime(int n) {
    if (n <= 1) {
        return 0;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", is_prime(n));
    return 0;
}
```
<details><summary>例題</summary>

**問題**: 整数 $N$ が与えられます。 $N$ が素数であるかどうかを判定してください。

**制約**: 

$1 \leq N \leq 10^5$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>

void print_divisors(int n) {
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            printf("%d ", i);
            if (i != n / i) {
                printf("%d ", n / i);
            }
        }
    }
    printf("\n");
}

int main() {
    int n;
    scanf("%d", &n);
    print_divisors(n);
    return 0;
}
```

</details>

## 9. 約数列挙
ある数の約数を全て列挙するには、1からその数までの全ての数で割り切れるかどうかを確認します。

```c
#include <stdio.h>

void print_divisors(int n) {
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            printf("%d ", i);
        }
    }
    printf("\n");
}
```
<details><summary>例題</summary>

**問題**: 整数 $N$ が与えられます。 $N$ の約数を全て列挙してください。

**制約**: 

$1 \leq N \leq 10^5$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>

void print_divisors(int n) {
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            printf("%d ", i);
            if (i != n / i) {
                printf("%d ", n / i);
            }
        }
    }
    printf("\n");
}

int main() {
    int n = 12;
    print_divisors(n);
    return 0;
}

```

</details>

## 10. 二分探索
二分探索は、ソートされた配列に対して、目的の値を効率的に見つけるアルゴリズムです。配列の中央の値と目的の値を比較し、目的の値が中央の値より小さければ左半分を、大きければ右半分を探索します。

```c
#include <stdio.h>

int binary_search(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) {
            return mid;
        }
        if (arr[mid] > x) {
            return binary_search(arr, l, mid - 1, x);
        }
        return binary_search(arr, mid + 1, r, x);
    }
    return -1;
}
```
<details><summary>例題</summary>

**問題**: $N$ 個のソートされた整数  $a_1,a_2,...,a_N$ が与えられます。整数 $x$ が配列に存在するかどうかを判定してください。

**制約**: 

$1 \leq N \leq 10^5$
$1 \leq a_i \leq 10^9$
$1 \leq x \leq 10^9$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>

int binary_search(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) {
            return mid;
        }
        if (arr[mid] > x) {
            return binary_search(arr, l, mid - 1, x);
        }
        return binary_search(arr, mid + 1, r, x);
    }
    return -1;
}

int main() {
    int n, x;
    scanf("%d %d", &n, &x);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    printf("%d\n", binary_search(arr, 0, n - 1, x));
    return 0;
}
```

</details>

## 11. 順列全探索
順列全探索は、ある集合の全ての順列（並べ方）を生成し、それぞれに対して何らかの操作を行うアルゴリズムです。

```c
#include <stdio.h>

void permutation(int *data, int start, int end) {
    if (start == end) {
        for (int i = 0; i <= end; i++) {
            printf("%d ", data[i]);
        }
        printf("\n");
    } else {
        for (int i = start; i <= end; i++) {
            int temp = data[start];
            data[start] = data[i];
            data[i] = temp;

            permutation(data, start + 1, end);

            temp = data[start];
            data[start] = data[i];
            data[i] = temp;
        }
    }
}
```
<details><summary>例題</summary>

**問題**: $N$ 個の整数  $a_1,a_2,...,a_N$ が与えられます。これらの整数の全ての順列を生成してください。

**制約**: 

$1 \leq N \leq 8$
$1 \leq a_i \leq 10^5$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void permute(int arr[], int l, int r) {
   if (l == r) {
        for (int i = 0; i <= r; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    } else {
        for (int i = l; i <= r; i++) {
            swap(&arr[l], &arr[i]);
            permute(arr, l + 1, r);
            swap(&arr[l], &arr[i]); // backtrack
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    permute(arr, 0, n - 1);
    return 0;
}
```

</details>

## 12. bit全探索
bit全探索は、ある集合の全ての部分集合を生成し、それぞれに対して何らかの操作を行うアルゴリズムです。これは、各要素が集合に含まれるかどうかを表すビット列を全て試すことで実現します。

```c
#include <stdio.h>

void bit_search(int n) {
    for (int bit = 0; bit < (1<<n); ++bit) {
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) {
                printf("%d ", i);
            }
        }
        printf("\n");
    }
}
```
<details><summary>例題</summary>

**問題**: $N$ 個の整数  $a_1,a_2,...,a_N$ が与えられます。これらの整数の全ての部分集合を生成してください。

**制約**: 

$1 \leq N \leq 20$
$1 \leq a_i \leq 10^5$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>

void print_subset(int arr[], int n, int bit) {
    for (int i = 0; i < n; i++) {
        if (bit & (1 << i)) {
            printf("%d ", arr[i]);
        }
    }
    printf("\n");
}

void bit_search(int arr[], int n) {
    for (int bit = 0; bit < (1 << n); bit++) {
        print_subset(arr, n, bit);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    bit_search(arr, n);
    return 0;
}
```

</details>

## 13. 幅優先探索(BFS)
幅優先探索は、グラフや木の探索アルゴリズムの一つで、始点から近い順にノードを探索します。キューを用いて実装します。

```c
#include <stdio.h>

#define MAX_QUEUE_SIZE 100

typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;

void enqueue(Queue *q, int element) {
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = element;
}

int dequeue(Queue *q) {
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}

int is_empty(Queue *q) {
    return q->front == q->rear;
}

void bfs(int graph[][MAX_QUEUE_SIZE], int start, int n) {
    int visited[MAX_QUEUE_SIZE] = {0};
    Queue q = {0};

    enqueue(&q, start);
    visited[start] = 1;

    while (!is_empty(&q)) {
        int current = dequeue(&q);
        printf("%d ", current);

        for (int i = 0; i < n; i++) {
            if (graph[current][i] && !visited[i]) {
                enqueue(&q, i);
               visited[i] = 1;
            }
        }
    }
}
```
<details><summary>例題</summary>

**問題**: $N$ 個のノードと $M$ 本の無向辺があるグラフが与えられます。ノード1から各ノードへの最短経路を探してください。

**制約**: 

$2 \leq N \leq 20$
$1 \leq M \leq 10^5$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int front, rear, size;
    unsigned capacity;
    int* array;
} Queue;

Queue* createQueue(unsigned capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
}

int isFull(Queue* queue) { return (queue->size == queue->capacity); }

int isEmpty(Queue* queue) { return (queue->size == 0); }

void enqueue(Queue* queue, int item) {
    if (isFull(queue)) {
        return;
    }
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
}

int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        return -1;
    }
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

void bfs(int graph[][MAX_SIZE], int start, int n) {
    int visited[n];
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }

    Queue* queue = createQueue(n);
    enqueue(queue, start);
    visited[start] = 1;

    while (!isEmpty(queue)) {
        int node = dequeue(queue);
        printf("%d ", node);

        for (int i = 0; i < n; i++) {
            if (graph[node][i] && !visited[i]) {
                enqueue(queue, i);
                visited[i] = 1;
            }
        }
    }
    printf("\n");
}

int main() {
    int n;
    scanf("%d", &n);
    int graph[MAX_SIZE][MAX_SIZE];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    bfs(graph, 0, n);
    return 0;
}
```

</details>

## 14. 深さ優先探索(DFS)
深さ優先探索もグラフや木の探索アルゴリズムの一つで、あるノードから遠くのノードを優先的に探索します。再帰を用いて実装することが一般的です。

```c
#include <stdio.h>

#define MAX_SIZE 100

void dfs(int graph[][MAX_SIZE], int visited[], int node, int n) {
    visited[node] = 1;
    printf("%d ", node);

    for (int i = 0; i < n; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(graph, visited, i, n);
        }
    }
}
```
<details><summary>例題</summary>

**問題**: $N$ 個のノードと $M$ 本の無向辺があるグラフが与えられます。ノード1から始めて全てのノードを訪れる経路を探してください。
**制約**: 

$2 \leq N \leq 20$
$1 \leq M \leq 10^5$

</details>

<details><summary>解答</summary>

```c
#include <stdio.h>

#define MAX_SIZE 100

void dfs(int graph[][MAX_SIZE], int start, int visited[], int n) {
    visited[start] = 1;
    printf("%d ", start);

    for (int i = 0; i < n; i++) {
        if (graph[start][i] && !visited[i]) {
            dfs(graph, i, visited, n);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int graph[MAX_SIZE][MAX_SIZE];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    int visited[MAX_SIZE] = {0};
    dfs(graph, 0, visited, n);
    printf("\n");
    return 0;
}
```

</details>