GCJ 2016 Round 1C Problem C. Fashion Police

本番出てたら解けなかったかな。

J 種類のジャケット、P 種類のパンツ、 S 種類のシャツを持っている。この街では、以前に着た服の組合せ (i,j,k) をもう一度着ると捕まる。さらに(*,j,k),(i,*,k),(i,j,*) の形の組み合わせを K 日より多く着てしまった場合も捕まる。

この街で捕まらずに過ごせるのは最大で何日間だろうか。

J,P,S という名前は対称性が悪いので A,B,C と呼び直すことにする。C<K のときは全パターン着れるので無視する。

(i,j,*) の形のパターンは高々 A×B×K 通りしかないはずである。つまり解は高々 A×B×K である。

(*,j,k) や (i,*,k) でも解の上界は与えることはできるが、A≦B≦C という制約があるため (i,j,*) が最もいい上界を与える。

さらに A×B×K 通りのパターンは下図のような方法で構成できる。

f:id:pekempey:20160508222213p:plain

上界が A×B×K なので、これが最大。

問題設定が面白い。