ABC011: C - 123引き算 - pyてよn日記

問題
考察過程
解法
- 貪欲法を用いた解法
- 動的計画法を用いた解法（FIXME）
終わりに

　シミュレーション系の問題．愚直解しか思いつかずタイムアップ．正直この問題は解けないといけない問題だと思う．

問題

ABC011: C - 123引き算

f:id:pytwbf201830:20190312180140p:plain

考察過程

　まず，「-1, -2, -3 の 3 つの分岐がある DFS の典型だな．余裕やん．」と考えそれを実装したが TLE．よくよく考えると，3 通りの分岐がある操作を 100 回繰り返すと状態の数は $3^{100}$ 通りなのでこれは当然無理．

　念の為 DFS で書いた愚直解のコードを以下に示しておく（愚直解を書くことも大事なことだと思うので）．WA は出ず，AC と TLE のみだったので恐らく愚直解としては正しいと思われる．

▶︎愚直解のソースコードを展開

#include <iostream>
using namespace std;
using ll = long long;

ll A, B, C, D;

bool dfs (ll start, ll depth) {
    if (start == B || start == C || start == D) {
        return false;
    }

    if (start <= 0 || depth == 100) {
        if (start == 0) {
            return true;
        } else {
            return false;
        }
    }

    bool ret1 = dfs(start-1, depth+1);
    bool ret2 = dfs(start-2, depth+1);
    bool ret3 = dfs(start-3, depth+1);

    return (ret1 || ret2 || ret3);
}

int main() {
    // input(sunippets: inpv, inpn, inps)
    cin >> A >> B >> C >> D;

    bool flag = dfs(A, 0);
    if (flag) {
        cout << "YES" << "\n";
    } else {
        cout << "NO" << "\n";
    }

    return 0;
}

　結局分からずタイムアップ．

解法

AtCoder Beginner Contest 011 解説 from AtCoder Inc.

www.slideshare.net

　解説には，二つの解法があった．

貪欲法を用いた解法
動的計画法を用いた解法（FIXME，いずれ更新する予定）

　現状 DP は分からないので貪欲法による解法のみ紹介．

貪欲法を用いた解法

　この解法は直感的で分かりやすい．正直，手元で実験をしてこの解法を思いつけないとだめだなと思った．

　出来る限り大きい数（3, 2, 1 の順）を N から NG 数と一致しないように引いていき，この操作を 100 回行った後に N が 0 以下であれば YES を出力．途中 NG 数を避けられなかったり，操作終了後 N が正のだったら NO を出力する．コードを以下に示す．

#include <iostream>
using namespace std;
using ll = long long;

int main() {
    // input(sunippets: inpv, inpn, inps)
    ll N, B, C, D;
    cin >> N >> B >> C >> D;

    if (N == B || N == C || N == D) {
        cout << "NO" << "\n";
    } else {
        ll n;
        for (ll i = 0; i < 100; ++i) {
            if (N-3 != B && N-3 != C && N-3 != D) N -= 3;
            else if (N-2 != B && N-2 != C && N-2 != D) N -= 2;
            else if (N-1 != B && N-1 != C && N-1 != D) N -= 1;
            else {
                cout << "NO" << "\n";
                return 0;
            }
            if (N <= 0) break;
        }

        if (N <= 0) {
            cout << "YES" << "\n";
        } else {
            cout << "NO" << "\n";
        }
    }

    return 0;
}