競プロで数学が絡む多くの問題は、立式して、命題の同値言い換えでうまく解くことができる。
いわれた通りに立式
これが一番見えやすいものである。複雑な関数でなければ数学の知見がそのまま使える。というか、解いてる本人の数学力によっては複雑な関数でも使えちゃう場合がある。
例 ABC112 - D(400)
この問題で、自然数k, sをおくと
a_1+a_2+a_3+...+a_N = M = k * s
とかける。
そして、kを最大公約数だと考えて、これを最大化するのが目標。これをもってして式を見直すと、
a_1+1_2+...+a_N = k * s = k(b_1+b_2+..+b_N)
でb_nという自然数列で書ける。つまり
b_1+b_2+...+b_N = s
となる。
ここで、sを最小化すれば、kが最大になると気付く。sの最小条件はb_1=b_2=...=b_N=1の時であり、その時はs=Nである。
つまり、この問題はsがN以上であるという条件を満たした下で最大のkの求めるという課題である。これは約数列挙で簡単にできる。
a_1+a_2+a_3+...+a_N = M = k * s
とかける。
そして、kを最大公約数だと考えて、これを最大化するのが目標。これをもってして式を見直すと、
a_1+1_2+...+a_N = k * s = k(b_1+b_2+..+b_N)
でb_nという自然数列で書ける。つまり
b_1+b_2+...+b_N = s
となる。
ここで、sを最小化すれば、kが最大になると気付く。sの最小条件はb_1=b_2=...=b_N=1の時であり、その時はs=Nである。
つまり、この問題はsがN以上であるという条件を満たした下で最大のkの求めるという課題である。これは約数列挙で簡単にできる。
例 天下一プロコン2019 - D(600)
三角形を作れるという条件をうまく立式化したい。三角不等式という三角形の成立条件を表す有名な絶対不等式があり、三辺をa, b, cとすると、
|a + b| > c ⋀ |a - b| < c
を(a, b, c) = (b ,c ,a)と置換してできる変数群において成立する。{ここで、問題設定で
a + b + c = T(定数)}
といえる。このことを利用すると、△不等式を
|T - c| = T - c > c つまり c < T/2
とわかる。同様にa < T/2, b < T/2であるとわかる。この時、不等式|a - b| < cは必ず成り立つことがわかる(実験すれば分ける)
つまりこの問題は、
{a < T/2 ⋀ b < T/2 ⋀c < T/2
を満たすa, b, cを作れる振り分け方}を求めたい。確率論でよくある余事象の手法を使うと
U - {a >= T/2 ∨ b >= T/2 ∨ c >= T/2}
を計算すればいいとわかる。
ベンズを書いて、包除原理で考えると、
A := a >= T/2, B := b >= T/2,C := c >= T/2 とすれば、U - A - B - C + (A ⋀ B) + (B ⋀ C) + (C ⋀ A) - (A ⋀ B ⋀ C)とわかる。
(A ⋀ B ⋀ C) = 0であり、(A ⋀ B)は他の2つと同じ値となり、Tが奇数の時は0, 偶数の時は動的計画法でA = B = T/2になる場合の数を計算できる。Aは、動的計画法で
dp[i][j]:=i番目の数まで足して和がjの場合の数
dp[i][j] += dp[i - 1][j] * 2(採用しない場合、B or Cに振り分けるで2通り)
dp[i][j] += dp[i - 1][j - ar[i]];(採用する場合)
と解ける。(A >= T/2 の時、B, C <= T/2である)
|a + b| > c ⋀ |a - b| < c
を(a, b, c) = (b ,c ,a)と置換してできる変数群において成立する。{ここで、問題設定で
a + b + c = T(定数)}
といえる。このことを利用すると、△不等式を
|T - c| = T - c > c つまり c < T/2
とわかる。同様にa < T/2, b < T/2であるとわかる。この時、不等式|a - b| < cは必ず成り立つことがわかる(実験すれば分ける)
つまりこの問題は、
{a < T/2 ⋀ b < T/2 ⋀c < T/2
を満たすa, b, cを作れる振り分け方}を求めたい。確率論でよくある余事象の手法を使うと
U - {a >= T/2 ∨ b >= T/2 ∨ c >= T/2}
を計算すればいいとわかる。
ベンズを書いて、包除原理で考えると、
A := a >= T/2, B := b >= T/2,C := c >= T/2 とすれば、U - A - B - C + (A ⋀ B) + (B ⋀ C) + (C ⋀ A) - (A ⋀ B ⋀ C)とわかる。
(A ⋀ B ⋀ C) = 0であり、(A ⋀ B)は他の2つと同じ値となり、Tが奇数の時は0, 偶数の時は動的計画法でA = B = T/2になる場合の数を計算できる。Aは、動的計画法で
dp[i][j]:=i番目の数まで足して和がjの場合の数
dp[i][j] += dp[i - 1][j] * 2(採用しない場合、B or Cに振り分けるで2通り)
dp[i][j] += dp[i - 1][j - ar[i]];(採用する場合)
と解ける。(A >= T/2 の時、B, C <= T/2である)
よって、動的計画法でそれぞれの集合に該当したものを計算し、足し引きすれば解ける。