108. 昨日と今日解いた問題（2022.04.24）

問題一覧

C - Coprime Set (Diff: 1151)
E - Multiplication 4 (Diff: 1607)
E - Lucky 7 Battle (Diff: 1609)

自分の解法など

C - Coprime Set

素数の積で数を構成しながら考えてみます。とりあえず $N=3$ で考えると、 $A = ( 2 \times 3, 3 \times 5, 5 \times 2)$ のような数列は条件を満たします。

ここから $N$ を増やしていくことを考えます。第 3 項までで全体の $\gcd$ が $1$ になることは確定しているので、任意の項と共通約数を持つように数列を構成することのみ考えればよいです。言い換えると、 $(2, 3, 5)$ のうちいずれか 2 つを約数に持つ数を追加していけばよいです。

ここで問題となるのが $1 \le A_i \le 10000$ という条件です。先程述べたような構成方法で第 $2500$ 項まで作れるのかが問題になります。これを証明するのは面倒なので、 $10000$ までの自然数で $(2, 3, 5)$ のうちいずれか 2 つを約数に持つ数がいくつあるのか、プログラムで算出してしまいます。すると、 $2666$ 個存在するので、問題なく構成できることが分かりました。

E - Multiplication 4

負の数が含まれていなければ、降順に取っていくのが明らかに最適です。負の数が含まれている場合でも偶数個選択で正にできるので、この方針で考えてみます。

まず、 $A$ を絶対値の大きな順に並べ直します。また、要素の正負が問題になってくるので対応する sign 配列も作っておくと便利です。

ここから $K$ 個順に取って、積が非負になればそれが答えです。以下、負になった場合を考えます。このとき、

$K$ から順に見て $1 \le i_1 \le K$ で $A_{i_1} \gt 0$ である要素と、 $K+1$ から順に見て $K+1 \le j_1 \le N$ で $A_{j_1} \le 0$ である要素を入れ替える
$K$ から順に見て $1 \le i_2 \le K$ で $A_{i_2} \lt 0$ である要素と、 $K+1$ から順に見て $K+1 \le j_2 \le N$ で $A_{j_2} \ge 0$ である要素を入れ替える

のどちらかを行えばよいことが分かります。この操作の狙いは、「積が負になってしまう原因である要素のうち絶対値が最小のものを追い出し、積を正にしてくれる要素のうち絶対値が最大のものを採用する」です。

どちらかのみ実行可能であればそれを行えばよいですが、どちらも実行可能であれば、 $\left| \frac{A_j}{A_i} \right|$ （採用要素の変更後、残る積の割合）が大きくなる方を行うのが最適です。2つ挙げた中で上の操作を行う場合を考えると、 $\frac{-A_{j_1}}{A_{i_1}} \gt \frac{A_{j_2}}{-A_{i_2}}$ が条件です。浮動小数点数を扱いたくないので、式変形して $A_{j_1}A_{i_2} \gt A_{j_2}A_{i_1}$ であることが条件と言い換えます。

以上の操作後、先頭から $K$ 項の積を取れば答えになります。

最後に例外処理として、両方の操作が実行不可能である場合はどうしても答えが負になるので、小さい方から $K$ 項の積が答えです。

E - Lucky 7 Battle

7の倍数であるかが重要なので、 $\pmod{7}$ で考えます。 $i$ までの要素をみたときの剰余が $a$ だった場合、 $i+1$ の要素で $b$ を採用したときに $10a + b \equiv 3a + b \pmod{7}$ となります。このように考慮すると、 $dp[N, 7]$ のような配列で状態を見ることができます。

$dp[i文字目まで見た, (i-1)文字目まで見たときの剰余] := (1:高橋くんの勝ち, 2:青木くんの勝ち)$

とすると、 $0 \le j \le 6$ について、

ターン目が高橋くんの手番
- $3j \equiv 0$ または $3j + S_N \equiv 0$ ならば、 $dp[N, j] = 1$
- それ以外ならば、 $dp[N, j] = 2$
ターン目が青木くんの手番
- $3j \not\equiv 0$ または $3j + S_N \not\equiv 0$ ならば、 $dp[N, j] = 2$
- それ以外ならば、 $dp[N, j] = 1$

とできます。ゴールから遡っていくことを考えると、 $N - 2 \ge i \ge 0$ について、

ターン目が高橋くんの手番
- $dp[i+1, 3j] = 1$ または $dp[i+1, 3j + S_i] = 1$ ならば、 $dp[i, j] = 1$
- それ以外ならば、 $dp[i, j] = 2$
ターン目が青木くんの手番
- $dp[i+1, 3j] = 2$ または $dp[i+1, 3j + S_i] = 2$ ならば、 $dp[i, j] = 2$
- それ以外ならば、 $dp[i, j] = 1$