#4 - 文系出身エンジニアが競プロをやる

今日からは先日購入した以下の書籍を読み進めつつ問題を解きます。

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』

そのため、今回使うコンテストサイトは AOJです。

AIZU ONLINE JUDGE: Programming Challenge

PCの言語設定が英語なためか、URLに言語パラメータを渡しても日本語になってくれない問題があったりはしますが進めます。（どうやら問題の言語設定は別のところで見落としてたみたいです…）

ALDS1_1_D: Maximum Profit

問題文

FX取引では、異なる国の通貨を交換することで為替差の利益を得ることができます。例えば、１ドル100円の時に 1000ドル買い、価格変動により 1ドル 108円になった時に売ると、(108円 − 100円) × 1000ドル = 8000円の利益を得ることができます。

ある通貨について、時刻 t における価格 Rt (t=0,1,2,,,n−1)が入力として与えられるので、価格の差 Rj−Ri (ただし、j>i とする) の最大値を求めてください。

入力

最初の行に整数 n が与えられます。続く n 行に整数 Rt (t=0,1,2,,,n−1) が順番に与えられます。

出力

最大値を１行に出力してください。

制約

・2≤n≤200,000
・1≤Rt≤109

コード

#include <iostream>
#include <algorithm>

using namespace std;
static const int MAX = 200000;

int main() {
    int n, r[MAX];
    cin >> n;

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

    int maxv = MAX * -10000;
    int minv = r[0];

    for (int i = 1; i < n; i++) {
        maxv = max(maxv, r[i] - minv);
        minv = min(minv, r[i]);
    }

    cout << maxv << endl;
    return 0;
}

かなり苦戦しました。書籍では「導入問題」と銘打ってあるものの価格差に対する認識が朧げで解説を読みつつ（ほぼ写経）実装しました。

maxvへ挿入する値の小ささが足りないと、パスしなかったのが辛かった。

ALDS1_1_A: Insertion Sort

挿入ソートの問題です。この前段で安定ソート（Stable Sort）の説明があります。

こちらは、問題文に記載された擬似コードを参照しつつ進めました。
出力形式が厄介でしたが、問題自体は比較的簡単でした。

擬似コード

1 insertionSort(A, N) // N個の要素を含む0-オリジンの配列A
2   for i が 1 から N-1 まで
3     v = A[i]
4     j = i - 1
5     while j >= 0 かつ A[j] > v
6       A[j+1] = A[j]
7       j--
8     A[j+1] = v

問題

N 個の要素を含む数列 A を昇順に並び替える挿入ソートのプログラムを作成してください。上の疑似コードに従いアルゴリズムを実装してください。アルゴリズムの動作を確認するため、各計算ステップでの配列（入力直後の並びと、各 i の処理が終了した直後の並び）を出力してください。

入力

入力の最初の行に、数列の長さを表す整数 N が与えられます。2 行目に、N 個の整数が空白区切りで与えられます。

出力

出力は N 行からなります。挿入ソートの各計算ステップでの途中結果を 1 行に出力してください。配列の要素は１つの空白で区切って出力してください。最後の要素の後の空白など、余計な空白や改行を含めると Presentation Error となりますので注意してください。

制約

・1 ≤ N ≤ 100
・0 ≤ A の要素 ≤ 1,000

コード

#include <iostream>
#include <algorithm>

using namespace std;
static const int MAX = 1000;

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

int main() {
    int n, a[MAX];
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];
    trace(a, n);
    int k;
    for (int i = 1; i < n; i++) {
        k = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > k) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = k;
        trace(a, n);
    }
    return 0;
}

trace関数の実装とtraceの位置が結構肝で、ハマりました…。
入出力の例をしっかりと頭に入れないとダメですね。
また最初手元の実行環境では、 printfを使って書いていましたがAOJの環境では、#include <stdio> してなかったのでfailしてました。辛い…

ostream / std::endl

今まで模倣的に endlを書いてましたが、気になったので調べてみました。

改行を出力し、バッファをフラッシュする。
C++のストリームには行バッファリングの機能がないため、行バッファリングの模倣としてendlが多用される。

endl - cpprefjp C++日本語リファレンス

なるほどなあ…🤔

おわりに

社内のSlackに競プロチャンネルを作成したりしてました。
身近にやってる人いると、励みになったりモチベーション上がりそう。

週末のコンテストに向けて過去問を解いたり、アルゴリズムの勉強したりしていくぞ！