pyてよn日記

一寸先は闇が人生

ABC006 - C: スフィンクスのなぞなぞ

AtCoder C++ 300点 C埋め 競プロ 競技プログラミング 全探索

全列挙の計算量を工夫して落とす問題．Otoshidama っぽさのある問題．

問題

f:id:pytwbf201830:20190217153856p:plain

思考過程

大人，老人，赤子の人数を i, j, k とすると，これらは以下の方程式を満たす．

  • i + j + k = N（人数の合計）
  • 2i + 3j + 4k = M（足の合計）

この条件からどれかを固定して全列挙すれば良いと考えた． 一番ループを少なく回せる赤子の人数，老人の人数の 2 重ループで全列挙しようと試みたが，最悪計算量が

O((105/4) * (105 - 105/4)/3)
= O(25000 * 75000/3) = O(25000 * 25000) = O(6 * 108)

程度となってしまい，TLE を上手く取り除けず，解けなかった．TLE に関しては下記の記事「WA を取るための自分的方針」を参考までに．

もう一工夫計算量を落とす必要がありそう．

解説

www.slideshare.net

正解は，上の方針に加え，老人の人数を固定するという条件を課して全列挙することだった．

老人の足の本数は 3 であるが，もし老人が 2 人（足 6 本）いたら， それらは大人と赤子一人ずつに分けることができる（2 + 4）．つまり，丁寧に見ていくと

  • 老人が 0 人：残りを考える．
  • 老人が 1 人：残りを考える．
  • 老人が 2 人：大人と赤子に 1 人ずつ分散させ，老人を 0 人にする．
  • 老人が 3 人：大人と赤子に 1 人ずつ分散させ，老人を 1 人にする．
  • 老人が 4 人：大人と赤子に 2 人ずつ分散させ，老人を 0 人にする．
  • 老人が 5 人：大人と赤子に 2 人ずつ分散させ，老人を 1 人にする．
  • 老人が 6 人：大人と赤子に 3 人ずつ分散させ，老人を 0 人にする．

のようなパターンになり，老人は 0 or 1 人調べれば良いことがわかる．これにより，最悪計算量は

O(105/4 * 2) = O(50000)

となり，この全列挙は十分通る．以下にソースコードを載せておく．

// ABC006_C
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    // input
    ll human, foot;
    cin >> human >> foot;

    // calculation
    if (human == 1) {
        if (foot == 2) {
            cout << 1 << " " << 0 << " " << 0 << "\n";
        } else if (foot == 3) {
            cout << 0 << " " << 1 << " " << 0 << "\n";
        } else if (foot == 4) {
            cout << 0 << " " << 0 << " " << 1 << "\n";
        } else {
            cout << -1 << " " << -1 << " " << -1 << "\n";
        }
    } else {
        if (foot < human*2 || human*4 < foot) {
            // (human, foot) = (2, 3) は足が足りない(3 < 2 * 2)
            // (human, foot) = (1, 5) は人が足りない(1 * 4 < 5)
            // 最低必要な人数，最大可能な人数で絞り込む
            cout << -1 << " " << -1 << " " << -1 << "\n";
        } else {
            ll max_baby = foot/4, k, foot_nokori;
            for (ll i = 0; i <= max_baby; ++i) {
                for (ll j = 0; j <= 1; ++j) {
                    k = human - i - j;
                    foot_nokori = (foot - 4*i - 3*j);
                    if (foot_nokori%2 == 0 && foot_nokori/2 == k) {
                        cout << k << " " << j << " " << i << "\n";
                        return 0;
                    }
                }
            }
            cout << -1 << " " << -1 << " " << -1 << "\n";
        }
    }
    return 0;
}

反省

これはちゃんと解けないといけない問題だった．この問題は，Otoshidama を一段階難しくした問題であると考えられるが，老人を固定できるという考え方が思い浮かばなかったのが悔しい．得た知見としては，

ある要素を一つ固定して for 文を回すことを考えるとき，和が倍数になることを考えることで削ることのできるパターンがある

ということである．全列挙を行うときに如何にして計算量を落とすかというのはこれからも常につきまとう問題であるので，この問題を心に留めておきたい．

全列挙を工夫して解く問題

本記事の問題の類題を紹介しておく．けんちょんさんの記事より引用．

計算量を落とす tips

今回の記事から計算量を落とすコツ，知見を得たら少しずつ書き留めていこうと思う．

  • ある要素を一つ固定して for 文を回すような全列挙を考えるとき，倍数，和の倍数を考えることで固定できるパターンがある <- New!!

なんか語呂が良くないけど自分がこれを読んで分かればよしとする．WA，TLE に関する知見のまとめはこちらをどうぞ．