[ABC006] C – スフィンクスのなぞなぞ

---

ディープラーニングの訓練中暇なので、AtCoderの過去問解いてみることにしました。どこまで解けるかはわかりませんが、ABCのC問題、D問題中心に解いてみます。全部書くのはきついので自分が面白いなと感じた問題をピックアップしていきます。

最初に取り上げるのはABC006のC問題「スフィンクスのなぞなぞ」です。一見、再帰やメモ化を匂わせるような問題ですが、実はそれを使わなくてもスマートに解ける面白い問題です。

問題文

新学期に向けて新たな気持ちで通学しているあなたの前に、スフィンクスが立ちふさがっています。
このスフィンクスは「なぞなぞ」を出すことで有名で、このなぞなぞに答えられない場合、留年します。

なぞなぞは以下のとおりです。
「この街には人間が N 人いる。人間は、大人、老人、赤ちゃんの 3 通りだ。
この街にいる人間の、足の数の合計は M 本で、大人の足は 2 本、老人の足は 3 本、赤ちゃんの足は 4 本と仮定した場合、存在する人間の組み合わせとしてあり得るものを 1 つ答えよ。」

新学期早々留年したくないあなたは、このなぞなぞに正解する必要があります。
なぞなぞの答えとなる「この街に存在する人間の組み合わせ」を 1 つ出力してください。
もし、そのような組み合わせが存在しない場合は-1 -1 -1と出力してください。

https://beta.atcoder.jp/contests/abc006/tasks/abc006_3

条件

• $1\leq N \leq 10^5$, $1\leq M \leq 5\times 10^5$
• 大人、老人、赤ちゃんの人数は0人以上の整数
• 部分点あり（詳細は省略）

連立方程式で解く

部分点無視していきなり満点解答でいきます。まず、NとMが大きすぎるのでforループで貪欲に解くのはダメです。$10^{10}$クラスになりおそらくオーバーします。

まず大人の人数をa, 老人の人数をb, 赤ちゃんの人数をcとしましょう。連立方程式で整理します。

　　$2a+3b+4c=M $
　　$ a+b+c=N$

連立方程式を解くには最低でも変数分の式が必要なので、これは一意に解を求めることができません。逆に言えばこの場合は式が2本だったら解けます（ここポイント）。

今これは数学の問題ではないので、足りなそうな値はforループで与えてしまえばいいのです。ループが速そうなのでcを与えるものとしましょう。今、仮に与えたcを$c^*$とします。

　　$2a+3b=M-4c^* $
　　$ a+b=N-c^*$

これは変数2個、式2本の連立方程式なので一意に解を求めることができます。数学的にaとbを解いていきましょう。下の式を2倍して上の式から引くと、

　　$ b=M-2N-2c^* $

これを代入して、

　　$ a=-M+3N+c^* $

と求められます。あとはforループで回せば終わりですね。

コード

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var vals = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var N = vals[0];
            var M = vals[1];

            //連立方程式を解く
            //a=大人、b=老人、c=子どもとして、
            // 2a+3b+4c=M
            // a+b+c=N
            //c=c*として与えられたら、
            // a = -M + 3N + c*
            // b = M - 2N - 2c*
            //で計算できる
            for(var child = 0; child <= Math.Min(N, M/4); child++)
            {
                var adult = -M + 3 * N + child;
                var silver = M - 2 * N - 2 * child;
                if(adult >= 0 && silver >= 0)
                {
                    Console.WriteLine($"{adult} {silver} {child}");
                    return;
                }
            }
            Console.WriteLine("-1 -1 -1");
        }
    }
}

今回の場合は連立方程式の解が小数にならないので小数のチェックは不要です。0以上の制約だけ見ればいいです。

以上です。解法の1つですが連立方程式で整理するとエレガントに解けますね。

---

---

Shikoan's ML Blogの中の人が運営しているサークル「じゅ～しぃ～すくりぷと」の本のご案内

---