Zenn
Open27

プロコン奮闘記

C++
競技プログラミング
AtCoder
Tomoki OtaTomoki Ota

概要

アルゴリズムをしなさすぎて忘れてたので、やり直すことに。

目標

とりあえずAtCoder 緑を目指す。

Tomoki OtaTomoki Ota

まずはAOJの ALDS1をやり直していきます。
その前に昔はgcc使ってたけど、m2 maxのmacbook proに変えると、clangになっていた。
m2 Macにgccの開発環境の構築していきます。

Tomoki OtaTomoki Ota

開発環境構築しなくても、普通にg++ hoge.cppでいけました。

Tomoki OtaTomoki Ota

1問目 Insertion Sort(挿入ソート)

アルゴリズムじゃなくて、出力の形式で詰まった笑
テストケースだと思ってたのが、自分のoutputだった。。。

ALDS1_1_A
#include <iostream>
using namespace std;

void insertionSort(int n, int a[]) {   
    for (int i = 0; i < n; i++) {
        int j = i - 1;
        int v = a[i];
        while (j >= 0 && a[j] > v) {
            a[j+1] = a[j];
            a[j] = v;
            j--;
        }
        a[j+1] = v;
        for (int j = 0; j < n;j++) {
            cout << a[j] << ((j == n-1) ? "": " ");
        }
        cout << endl;
    }
}

int main() {
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    insertionSort(N, A);
    return 0;
}

流石にブランクあっても、10分くらいで終わると思ってたから悔しい

Tomoki OtaTomoki Ota

2問目Bubble Sort (バブルソート)

バブルソートは簡単。

#include <iostream>
using namespace std;

void bubbleSort(int n, int a[]) {
    int count = 0;
    for (int i = 0;i < n; i++) {
        for (int j = n-1; j >= i; j--) {
            if (a[j-1] > a[j]) {
                int temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
                count++;
            }
        }
    }

    for (int i = 0;i < n;i++) {
        cout << a[i] << ((i == n-1) ? "" : " ");
    }
    cout << endl;
    cout << count << endl;
}

int main()
{
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    bubbleSort(N, A);
    return 0;
}
Tomoki OtaTomoki Ota

3問目 Selection Sort(選択ソート)

朝にやると頭が回ってすぐ終わる。
これも簡単。

#include <iostream>
using namespace std;

void selectionSort(int n, int a[]) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        int minj = n-1;
        for (int j = n-1; j >= i; j--){
            if (a[j] <= a[minj]) {
                minj = j;
            }
        }
        if(minj != i) {
            int temp = a[minj];
            a[minj] = a[i];
            a[i] = temp;
            count++;
        }
    }

    for (int i = 0;i < n;i++) {
        cout << a[i] << ((i == n-1) ? "" : " ");
    }
    cout << endl;
    cout << count << endl;
}
int main()
{
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    selectionSort(N, A);
    return 0;
}
Tomoki OtaTomoki Ota

4問目 Queue

一発で成功。

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


int main () {
    int n, q;
    string a;
    int b;
    int fin_time = 0;

    cin >> n >> q;
    queue<string> name;
    queue<int> time;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        name.push(a);
        time.push(b);
    }
    
    int count = 0;
    while(!name.empty()) {
        if (time.front() > q) {
            count += q;
            fin_time += q;
            a = name.front();
            b = time.front()-q;
            name.pop();
            time.pop();
            name.push(a);
            time.push(b);
        } else {
            fin_time += time.front();
            cout << name.front() << " " << fin_time << endl;
            time.pop();
            name.pop();
        }
    }
    return 0;
}
Tomoki OtaTomoki Ota

わざわざQueue2つ以下のようにしなくても、 queue<pair<string,int> > que;でいいのか。

queue<string> name;
queue<int> time;
Tomoki OtaTomoki Ota

5問目 LinearSearch(線形探索)

番兵の考え方を学ばなければならない。

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

int main() {
    int n, q;
    cin >> n;
    int S[n];

    for (int i = 0; i < n; i++) {
        cin >> S[i];
    }

    cin >> q;
    int T[q];

    for (int i = 0; i < q; i++) {
        cin >> T[i];
    }

    int count = 0;
    for (int i = 0; i < q; i++) {
        for (int j = 0; j < n; j++) {
            if (S[j] == T[i]) {
                count++;
                break;
            }
        }
    }
    cout << count << endl;

    return 0;
}
Tomoki OtaTomoki Ota

6問目 Graph

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

int main() {
    int n, u, k, v;
    cin >> n;
    int A[n][n];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            A[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        cin >> u >> k;
        for (int j = 0; j < k; j++) {
            cin >> v;
            A[u - 1][v - 1] = 1;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << A[i][j] << ((j == n - 1) ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}
Tomoki OtaTomoki Ota

7問目 DFS (深さ優先探索)

スタックと回帰の２通りがある。
回帰を使う方がコードは短くなるが、オーバーフローになる可能性がある。
あと、C++で２重配列を引数にするときは要注意。グローバル変数にした方が簡単。

#include <iostream>
using namespace std;

int n, t = 0;
bool A[100][100];
bool fin[100];
int d[100];
int f[100];

void dfs(int u) {
    t++;
    d[u] = t;
    fin[u] = t;
    for (int i = 0; i < n; i++) {
        if (!fin[i] && A[u][i]) {
            dfs(i);
        }
    }
    t++;
    f[u] = t;
}
int main() {
    int u, k, v;
    cin >> n;

    for (int i = 0; i < n; i++) {
        fin[i] = false;
        for (int j = 0; j < n; j++) {
            A[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        cin >> u >> k;
        for (int j = 0; j < k; j++) {
            cin >> v;
            A[u - 1][v - 1] = 1;
        }
    }

    for (int i = 0; i < n; i++) {
        if (!fin[i]) {
            dfs(i);
        }
    }

    for(int i = 0; i < n; i++) {
        cout << i+1 << " " << d[i] << " " << f[i] << endl;
    }

    return 0;
}
Tomoki OtaTomoki Ota

8問目 BFS (幅優先探索)

BFSはスタックを使う。

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

int main() {
    int u, k, v;
    int n = 0;
    int A[100][100];
    bool fin[100];
    int d[100];
    queue<int> que;
    cin >> n;

    for (int i = 0; i < n; i++) {
        fin[i] = false;
        for (int j = 0; j < n; j++) {
            A[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        cin >> u >> k;
        for (int j = 0; j < k; j++) {
            cin >> v;
            A[u - 1][v - 1] = 1;
        }
    }

    que.push(0);

    for (int i = 0; i < n; i++) {
        d[i] = -1;
    }

    d[0] = 0;
    int l = 0;
    while (!que.empty()) {
        for (int i = 0; i < n; i++) {
            if (A[que.front()][i] && d[i] == -1) {
                que.push(i);
                d[i] = d[que.front()] + 1;
            }
        }
        fin[que.front()] = true;
        que.pop();
    }

    for (int i = 0; i < n; i++) {
        cout << i + 1 << " " << d[i] << endl;
    }

    return 0;
}
Tomoki OtaTomoki Ota

アルゴリズムは問題なかったのに以下のようなエラーが出て詰まってしまった。

$ g++ a.cpp
a.cpp:10:18: warning: result of comparison against a string literal is unspecified (use an explicit string comparison function instead) [-Wstring-compare]
        if (b[i] == "1") {
                 ^  ~~~
a.cpp:10:18: error: comparison between pointer and integer ('std::basic_string<char>::value_type' (aka 'char') and 'const char *')
        if (b[i] == "1") {
            ~~~~ ^  ~~~
Tomoki OtaTomoki Ota

9問目 Merge Sort (マージソート)

計算量はO(nlogn)。

#include <climits>
#include <iostream>

using namespace std;

int num = 0;

void merge(int a[], int l, int m, int r) {
    int a1[m - l], a2[r - m];
    for (int i = 0; i < m - l; i++) {
        a1[i] = a[i + l];
    }
    for (int i = 0; i < r - m; i++) {
        a2[i] = a[i + m];
    }
    a1[m - l] = INT_MAX;
    a2[r - m] = INT_MAX;

    int p = 0;
    int q = 0;
    for (int i = l; i < r; i++) {
        if (a1[p] <= a2[q]) {
            a[i] = a1[p];
            num++;
            p++;
        } else {
            a[i] = a2[q];
            num++;
            q++;
        }
    }
}

void mergeSort(int a[], int left, int right) {
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid, right);
        merge(a, left, mid, right);
    }
}
int main() {
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    mergeSort(A, 0, N);

    for (int i = 0; i < N; i++) {
        cout << A[i] << (i == N - 1 ? "" : " ");
    }
    cout << endl;

    cout << num << endl;

    return 0;
}
Tomoki OtaTomoki Ota
  • Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）
    1,2番は解けた。3は問題文の意味が一見よく分からなかったので4番目を解こうとしたらハマった。
    自分の実行環境だと普通に高速で答えが出るのに、なぜかatcoderの環境ではTLEになった。
Tomoki OtaTomoki Ota

これ使わないとTLEになるっぽい。てか使ったらめちゃくちゃ簡単やった。
ただの数学の問題。

Tomoki OtaTomoki Ota
  • 今回のコンテストABC291の反省
    要素の重複を探すときは配列/リストから探すと、1回あたり配列/リストの長さに比例する時間がかかり、全体で Θ(N ^2 ) となりTLEとなる。setなどを用いることで 1回あたり O(logN) 時間、全体で O(NlogN) 時間となる。
    https://atcoder.jp/contests/abc291/editorial/5837
Tomoki OtaTomoki Ota

動的計画法

まずはよくあるコインの最小枚数問題を解いていく.
DPL_1_A Coin Changing Problem
c_1, ・・・c_m ( c_1 < ・・・<c_m ) のm種類のコインでn円を払うときの最小枚数を求める。

  • 貪欲法 : 一番大きいコインから割っていく → 最適解が出せない時がある(eg. n=18, c=[1, 2, 6, 9, 15]のとき、貪欲法だと[15, 2, 1]の3枚だが、正解は[9,9]の2枚。)
Tomoki OtaTomoki Ota

今週挑戦するコンテスト (2023/4/1)

C問題までクリア
素数のD問題でつまづく。
惜しいとこまで解けてたけどタイムオーバ
ABC296

Tomoki OtaTomoki Ota

欲張り法

クラスカル法

最小全域木（クラスカル法とUnionFind）
ネットワークにおいて、枝の総長が最も短いスパニングツリーを最小全域木、最小木と呼ぶ。

アルゴリズム

  1. 枝を長さの短い順にソートする。最も短い枝をa_{0} とする。この時、 T = (a{0}), k = 1とする。
  2. Tが閉路担っていなければ、Tにa_{k}を追加する。そうでなければ、スキップする。
  3. Tがスパニングツリーになれば終わり。なっていなければ k = k + 1をして、ステップ2に戻る。

動的計画法

分岐限定法

ナップザック問題

ナップザック問題は貪欲法で解答が求まる。
ナップザック問題はNP困難である。