GCJ 2016 Round 1C Problem C. Fashion Police
本番出てたら解けなかったかな。
https://code.google.com/codejam/contest/4314486/dashboard#s=p2
問題
J 種類のジャケット、P 種類のパンツ、 S 種類のシャツを持っている。この街では、以前に着た服の組合せ (i,j,k) をもう一度着ると捕まる。さらに(*,j,k),(i,*,k),(i,j,*) の形の組み合わせを K 日より多く着てしまった場合も捕まる。
この街で捕まらずに過ごせるのは最大で何日間だろうか。
- 1≦J≦P≦S≦10
- 1≦K≦10
解法
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 通りのパターンは下図のような方法で構成できる。
上界が A×B×K なので、これが最大。
GCJ Round 1C Problem C. Fashion Police
問題設定が面白い。