🦁

【ABC260】「C - Changing Jewels」のメモ

2022/07/18に公開

AtCoder

競プロ

tech

概要

AtCoder Beginner Contest 260のC問題を解けなかったので、解説を見て得られた知見などを書いてみます。

コンテスト中に書いたコード

コンテスト中にコードは書けませんでした。愚直に書いてもTLEになる気がしたのですが、今思えばそれでも試しに書いてみるべきだったかもしれません。

解説を見て

解説ではDPを使った方法と、再帰関数を使った方法のそれぞれが紹介されていました。
DPは現状身に付けていないですが、再帰関数を使った方法なら理解できるのでそちらで見てみます。
といっても、ベースケース（レベル 1 の青い宝石の個数を計算なしで求められるケース）の考察以外は、そのまま問題文をコードにするだけなのですが…

以下は書いたコードです。

#include <bits/stdc++.h>
using namespace std;

long long calc(int n, bool is_red, int x, int y) {
    if(n == 1) {
        return is_red ? 0 : 1;
    }

    if(is_red) {
        return calc(n - 1, true, x, y) + calc(n, false, x, y) * x;
    } else {
        return calc(n - 1, true, x, y) + calc(n - 1, false, x, y) * y;
    }
}

int main() {
    int n, x, y;
    cin >> n >> x >> y;

    cout << calc(n, true, x, y) << endl;
}

以前、以下のような記事を書いたことがあります。

この記事で言いたかったのは、再帰関数は「今実装しようとしている関数は、既に実装済みであるかのように考える」ことでいい感じに実装できるということです。
上記は模範解答に倣ってcalcというわかりにくい名前になっていますが、この関数は今持っている宝石のレベルと色を指定すると、それによって得ることができる青い宝石の数を返す関数です。
（解説の通り、nはlevelにしてxとyはグローバル変数にしたほうがわかりやすいですね…）

レベルが1の場合は計算なしで個数が求められるため、これがベースケース（再帰の終了条件）となります。
それ以外の場合、この関数は「既に実装済みである」ので、得られる宝石をcalc関数に渡せばレベル1の青い宝石の個数が求められるので、それをそのまま足し合わせれば実装完了です。
なんでこれでうまくいくのかと突っ込んで訊かれるとうまく答えられないのですが、再帰関数ってそういうものだとパターンとして覚えればいいと思います。

教訓

再帰関数自体はたまに使いますが、競プロでこんなに素直に再帰関数で実装できる問題が出るとは思ってなかったです。そういうケースもあると覚えておきます。
しかし、再帰的な構造を持っていると気づけなかったのは悔しいですね。わかったようなことを書いていますが、再帰についてあんまりわかっていないのかもしれません。

一応ヒントはあって、条件に「n は 2 以上」という制約がついています。ならばnが1ならどうなるのか？そこが再帰関数のベースケースになるのでは？と発想できたらよかったですね。

素直な再帰関数で解ける問題もある
上記に気づけるように、再帰関数にもっと慣れる必要がある
「n は 2 以上」みたいな制約がついていたら、再帰関数かもと考えてみる

概要

コンテスト中に書いたコード

解説を見て

教訓

Discussion