競プロ典型90問 065

RGB Balls 2（★7）

問題

kyopro_educational_90/problem/065.jpg at main · E869120/kyopro_educational_90

問題概要

赤青緑のボールの組み合わせが何通りか答える

この記事では

3種類のボールの状態を整理するやり方を紹介します。

この問題の解答の後半で難しい計算を行う必要があります。この記事はこの計算についてはやりません。この計算の分野は単独の分野として確立していて、いろいろな解説ページがあります。

3次元で考える

情報を整理するために3次元をイメージします。

Kを設定

赤の個数 + 青の個数 + 緑の個数としてKが与えられます。そのKを立体上に表現します。

右はKのところで切り取った三角形です。

Xのラインを設定

X、つまり赤と緑の合計の最大値を表現します。左の図で、右の面の点線のところからBの方向に切り取った面がXになります。このXの面と三角形が交わるところは赤の実線で表現します。右の図の赤線の読み方は、赤線より右下は赤と緑の合計がXを超えるので不適となり、赤線上、または赤線より左上が許される状態になります。

Xのところで切断すると次のようになっています。

XYZのラインを表現

右の三角形の3つの赤線で囲まれた部分より外は不適になります。

赤の個数を設定

当然、用意されている個数を超えることは出来ないので、そのラインを表現します。右の図で赤の線より右上は用意された個数を超えた状態です。

赤青緑の個数を設定

青と緑にも同様のことをします。

赤の最低値を調べる

情報がそろったのでそれぞれの取りうる最低値、最高値を調べます。まずは赤の最低値です。これはKとY(青と緑の最高値)から求まります。K-Yです。

赤の最高値を調べる

ここは難しいところです。

• 赤の個数
• Z
• X

のすべてを満たす必要があります。

PがX(赤と緑の最大値)とZ(赤と青の最大値)を両方満たす赤の最大値です。この値はKから青の最低値を引いて(Q)そこから緑の最低値を引いた値(P)です。

以上より

• Pでの赤の値
• 与えられた赤の個数

の低い方が赤の最大値になります。

青と緑も同様に計算します。

解なしのパターン

XやYZが極端に低い場合はK個選ぶことができない解なしになります。

• Xより左上
• Yより右上
• Zより下

を同時に満たすことは出来ません。

さいごに

ここまで整理することはこの問題を解く上で必ず必要ということではありませんが、状況整理に迷う人の助けになればと思い書いてみました。