グリッド上での数え上げを数える手法を紹介する。
何点か固定
これはグリッド上に任意にコマを配置して、そのすべての配置パターンについてうんぬん数え上げるとタイプに多い。
一見つかみどころがなさそうだけど、数か所固定して数え上げればうまく網羅できる場合が多い。
一見つかみどころがなさそうだけど、数か所固定して数え上げればうまく網羅できる場合が多い。
例 ABC127 - E(500)
すべて数え上げろだなんて、突拍子もない話である。しかし、上記のことを頭の中で意識しておこう。
まずこの問題はx,yは独立して考えてよい。そして、x軸上の距離d((X_i) - (X_i+1) == d)の時、どれほどのパターンがあるかを考える。
全パターンを網羅するには、K - 2このコマを残ったN * M - 2か所に配置すればよい。これはcomb(N * M - 2, K - 2)である。
また、y軸は独立して考えるので、dを固定すると、
d * (N - d) * M ^ 2と全部のパターン数が出る。
内訳としては 長さ＊1行あたりの数＊固定する二つのコマをどの行におくかの二乗 である。
あとはこれを1からM - 1まで足し合わせばよい。
y軸もx軸とほぼ同じで、x,y軸の計算結果を足してからcomb(N * M - 2, K - 2)をかければAC。(2019/5/26)
まずこの問題はx,yは独立して考えてよい。そして、x軸上の距離d((X_i) - (X_i+1) == d)の時、どれほどのパターンがあるかを考える。
全パターンを網羅するには、K - 2このコマを残ったN * M - 2か所に配置すればよい。これはcomb(N * M - 2, K - 2)である。
また、y軸は独立して考えるので、dを固定すると、
d * (N - d) * M ^ 2と全部のパターン数が出る。
内訳としては 長さ＊1行あたりの数＊固定する二つのコマをどの行におくかの二乗 である。
あとはこれを1からM - 1まで足し合わせばよい。
y軸もx軸とほぼ同じで、x,y軸の計算結果を足してからcomb(N * M - 2, K - 2)をかければAC。(2019/5/26)
