AtCoder Beginner Contest 115に参加しました

タイトルの通りABC 115に参加しました。競技プログラミングに参加するのは今回が初めてになります。

abc115.contest.atcoder.jp

↓の記事を参考に最低限のルールとC++の構文、標準ライブラリの関数を覚えての参戦です。

qiita.com

結果ですが、順位は1629/1927、A問題とB問題はAC、C問題はもう一歩で正答に至らず、D問題は愚直に再帰を回してTLEになりました。

うーん…ボロボロですね。

解けなかった問題は復習して、当面は「制限時間内に全問AC」を目標にしたいと思います。

というわけで、解説を見ながら解きなおしたCとDのAC済みコードを掲載します。

↓公式の解説

https://img.atcoder.jp/abc115/editorial.pdf

abc115.contest.atcoder.jp

昇順ソート後、K個ずつの組を考えてのリニアサーチです。 コンテスト中も「ソートしてサーチでいいのかな？」とか考えていたのですが、確信が持てず時間切れになってしまいました・・・。

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    int ans = 1000000010;

    int h[100010];
    for (int i = 0; i < N; i++) cin >> h[i];

    sort(h, h + N);
    
    for (int i = 0; i + K <= N; i++) {
        int delta = h[i + K - 1] - h[i];
        ans = min(ans, delta);
    }
    cout << ans << endl;
}

abc115.contest.atcoder.jp

漸化式を場合分けして再帰で解く解説通りのアプローチです。

#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
typedef long long ll;
 
ll a[60];
ll p[60];
 
ll f(ll N, ll X) {
    if (N == 0)
        if (X <= 0) return 0;
        else return 1;
    else if(X <= 1 + a[N-1]) return f(N-1, X-1);
    else return p[N-1] + 1 + f(N-1, X-2-a[N-1]);
}
 
int main() {
    ll N, X;
    cin >> N >> X;
 
    a[0] = 1;
    p[0] = 1;
    for (int i = 1; i < N; i++) {
        a[i] = a[i-1] * 2 + 3;
        p[i] = p[i-1] * 2 + 1;
    }
 
    cout << f(N, X) << endl;
}

結果はともかく、コンテスト自体はとても楽しかったです。 僕みたいに本職のプログラマではなく、 とくにアプリやサービスを作りたいわけではないけどプログラミングとアルゴリズムを勉強したい、 という方にはモチベーション維持にもいいと思います。