LoginSignup
0

More than 1 year has passed since last update.

AIZU ONLINE JUDGEで問題を解いてみた

Last updated at Posted at 2022-07-18

競プロのサイト

AIZU ONLINE JUDGEというサイトの問題を解いていきます。

Insert Sort

1行目 入力数
2行目 入力

sample input
6
5 2 4 6 1 3
sample output
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6
code1.cpp
#include <iostream>
using namespace std;

void trace(int A[], int n) {
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << " ";
        cout << A[i];
    }
    cout << endl;
}

void InsertSort(int A[], int n) {
    for (int i = 0; i < n; i++) {
        int v = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > v) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = v;
        trace(A, n);
    }
}


int main() {
    int n;
    int N = 100;
    int A[N];

    cin >> n;
    for (int i = 0; i < n; i++) cin >> A[i];

    InsertSort(A, n);
    return 0;
}

Greatest Common Divisor

sample input
54 20
sample output
2

直感的に、最大公約数を求めてみる
どちらでも割り切れる最大の数を求める

code2_1.cpp

#include <iostream>
using namespace std;
int a, c;

int mmcm() {
    int result = 0;
    if (a > c) {
        for (int i = c; i >= 1; i--) {
            if (a % i == 0 && c % i == 0) return i;
        }
    } else if (a < c) {
        for (int i = a; i >= 1; i--) {
            if (a % i == 0 && c % i == 0) return i;
        }
    } else {
        result = a;
    }
    return result;
}

int main() {
    cin >> a >> c;
    int result;
    result = mmcm();
    cout << result << endl;
    return 0;
}

数が大きくなると、処理時間が長くなるので改良

ユークリッド互除法を用いてコードを書く

code2_2.cpp
#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int x, int y) {
    int r;
    if (x < y) swap(x, y);
    while (y > 0) {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

Prime Numbers

1行目 入力数
2行目以降 入力

sample input
7
1
2
3
4
5
6
7
sample output
4
code3.cpp
#include <iostream>

using namespace std;

int MAX = 10000;

int pm_bool(int p) {
    int r = 0;
    int i = 2;
    bool key = true;
    if (p <= 1) {
        return r;
    }
    while (key) {
        if (p % i == 0) {
            if (p == i) {
                r = 1;
            }
            key = false;
        }
        i++;
    }
    return r;
}

int main() {
    int n;
    int p[MAX];
    cin >> n;
    int result = 0;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        result = result + pm_bool(p[i]);
    }
    cout << result << endl;
    return 0;
}

Bubble Sort

sample input
5
5 3 2 4 1
sample output
1 2 3 4 5
8
code4.cpp
#include <iostream>
using namespace std;

int BubbleSort(int A[], int N) {
    int sw = 0;
    bool flag = 1;
    for (int i = 0; flag; i++) {
        flag = 0;
        for (int j = N - 1; j >= i + 1; j--) {
            if (A[j] < A[j - 1]) {
                swap(A[j], A[j -1]);
                flag = 1;
                sw++;
            }
        }
    }
    return sw;
}

int main() {
    int A[100], N, sw;

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    sw = BubbleSort(A, N);
    for (int i = 0; i < N; i++) {
        if (i) cout << " ";
        cout << A[i];
    }
    cout << endl;
    cout << sw << endl;

    return 0;

    return 0;
}

続きはこちら

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0