精進5日目：ABC006-C スフィンクスのなぞなぞ

数学パズルとはこのことか？

atcoder.jp

考え方1

N 人全員が老人だった場合の足の本数と M の差分を取り、「M のほうが大きければ、その差分だけ老人を減らして赤ちゃんを増やす」、「M のほうが小さければ、その差分だけ大人を減らして老人を増やす」という方法で解けます。

老人減らして赤ちゃんを増やすパターン

すこし物騒ですが、老人の本数が真ん中であることを利用した解き方ですかね。

Python3 で実装したコード

N, M = map(int, input().split())

ans = [0, 0, 0]

if (M < N*2) or (N*4 < M):

    ans = [-1, -1, -1]

else:

    x = M - 3*N

    ans[1] = N

    if x > 0:

        # 3 の倍数で足りないから、4の倍数を増やして全体を増やす

        ans[1] -= x

        ans[2] += x

    elif x < 0:

        # 3の倍数で超えてるから、2の倍数を増やして全体を減らす

        ans[1] += x

        ans[0] -= x

print(*ans)

考え方2

公式解説にもありましたが、老人が2人以上の偶数人いる場合は脚が6の倍数となるので、大人とこどもに振り分けることができます。つまりこのとき、老人は0人で良い。

老人が奇数人いる場合は上記偶数のケースを加味すると、実質1人のときだけ考えればよいです。

つまり、老人0人と1人の場合に対して、大人と赤ちゃんの人数を全探索すれば問題を解けます。

python3 で実装したコード

N, M = map(int, input().split())

adult = -1

elder = -1

baby = -1

if M%2 == 0:

    for i in range(N+1):

        if (2*i + 4*(N-i)) == M:

            adult = i

            elder = 0

            baby = N - i

            break

else:

    N -= 1

    M -= 3

    for i in range(N+1):

        if (2*i + 4*(N-i)) == M:

            adult = i

            elder = 1

            baby = N - i

            break

print(adult, elder, baby)

 

なんか、むだが多そうだけどまぁいいか。

むすび

数学パズルって、おもしろいですね（解けるとは言ってない）。最近力技ばかりだった気がするので、良い刺激になりました。