SRM697D1Easy DivisibleSetDiv1
ゴリ押しで通したけど想定解難しい
問題概要(原文)
$N$ 要素の数列 $B \; (\; 1 \leq B_i \leq 10)$ が与えられる．以下の制約を満たす数列 $A$ はあるか？
- $A_i > 1$
- $A_i$ は互いに相異なる
- $A_{i}^{B_{i}}$ は $\prod_{x \in A \; \setminus \; \{ A_{i} \} }x$ を満たす
考察
$B$ は昇順としても一般性は失わない．さらにこの問題は以下の制約を満たす数列 $C$ があるか判定せよと言い換えてもよい．
- $C_i \geq 1$
- $C_i$ は互いに相異なる
- $C_{i}(B_{i}+1) \geq \sum_{j = 0}^{N - 1} C_{j}$
これはどういうことかというと， $A_{i} = p_{0}^{q_{0}} p_{1}^{q_{1}} \ldots p_{m}^{q_{m}}$ とする． まず $A_i$ が $2$ のべき についてのみ考えてよいことを示す．
$A_{i}$ が ある素数 $p$ の冪乗で表される数でなくてはならない，という制約を加えたときに，条件を満たすもの数列 $A=\{ a_{0}, a_{1}, \ldots , a_{N - 1} \}$があったとする．ここで $a_{i} = p^{C_{i}}$ で表されるとする． もともとの問題と，先ほど述べた問題の答えが一致しなくてはならない．
さらに，素数 $p$ ごとに問題を分解することができるので，適当な素数 $p$ についてのみ考えればよくなる．
さて，条件を満たす数列 $C$ が存在するか判定したい気持ちになった． $\sum_{j = 0}^{N-1} C_{j} = X$ とおこう．
$C_{i} = \left \lceil \frac{X}{B_{i} + 1} \right \rceil$ としたときに， $X \geq \sum_{ j = 0 }^{N - 1} C_{j}$ となれば，条件を満たす．
$X$ を適当な数まで全探索すればよい．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class DivisibleSetDiv1
{
public string isPossible(int[] b)
{
var n = b.Length;
Array.Sort(b);
for (int i = n; i <= 114514; i++)
{
var s = new HashSet<int>();
var sum = 0;
foreach (var x in b)
{
var k = (i + x) / (x + 1);
while (!s.Add(k)) k++;
sum += k;
if (sum > i) break;
}
if (sum <= i)
{
Debug.WriteLine(i);
return "Possible";
}
}
return "Impossible";
}
}
コメント
- これは結構好き
