数え上げはそこそこ得意だと思っていたのに、解けなくて解説を見たので。
問題リンク
問題概要
R×Cのマス目に好きな順番でコマを1マスに1つずつ置いていく。いくつかのマスには最初からコマが置かれている。
コマが置かれたマスが長方形をなす回数を最大化するようなコマの置き方は何通りか。
解法
後半部分のみを解説します。
長方形を
- 上に伸ばす
- 下に伸ばす
- 左に伸ばす
- 右に伸ばす
操作を考えると、これらはそれぞれ回数が決まっていて、かつそれぞれの操作の際に長方形の縦もしくは横の長さの階乗が組み合わせ総数にかかります。
ここで一旦上下と左右をそれぞれ同一視すると
- 縦に伸ばす
- 横に伸ばす
の2パターンになります。当然回数は決まっています。
例えば、上2回・下1回・左1回・右3回の時は
縦3回・横4回になるので
[-][-][-][-][-][-][-]
や
[-][-][-][-][-][-][-]
などのパターンが考えられます。
ここで各操作にかかる係数はその時点での長方形の縦・横幅のみに依存する
(ここがポイントで、今は縦・横の操作の回数という観点でのみ考えているので、「上の操作ばっかりではみ出す」みたいなことは考えなくて良い)
ので、状態数がせいぜいR×CのDPで計算可能です。
最後に、縦と横の操作にそれぞれ上下・左右を割り当てます。
[-][-][-][-][-][-][-]
のパターンからは例えば
[-][-][-][-][-][-][-]
のような割り当てが可能ですが、
この割り当ては上下と左右で独立、かつ全てのパターンについて同じ式
(「縦の回数」個から「上の回数」個を選ぶ組み合わせ数と、「横の回数」個から「左の回数」個を選ぶ組み合わせ数の積)
なので、単純に掛けてしまえば良いです。
まとめると
- 上方向と下方向(左方向と右方向)の遷移は同じ式なので、同一視してみると状態としては単純に横幅と縦幅だけを考えていることになる。
- 横幅と縦幅だけを状態として見る場合、DPがO(RC)で出来る。
- その後上下・左右をそれぞれ分離する。全パターンに対し同じ係数を掛けているので、結局全体にそれを掛ければ良い。
となる。
提出
https://atcoder.jp/contests/joisc2013-day2/submissions/23933535
感想
途中の操作をあえて抽象化する(上下・左右を同一視する)のが難しい。
