[CSA] Round #3 Divisor Clique

Divisor Clique

https://csacademy.com/contest/beta-round-3/task/divisor_clique/

動的計画法と整数問題です。解けなかったので解説を読みました。

考え方

動的計画法

解説を読むと動的計画法を使うようです。数列 \( a \) の部分集合の任意の二つの要素 \( A \)、 \( B \) が \( A \mod B = 0\) または、\( B \mod A = 0 \) を満たすとします。このときの部分集合の最大数を求めます。

まず始めに、与えられた数列 \( a \) を昇順に整列させます。あとは動的計画法を使うようです。というか、公式の解説が理解できませんでした。

配列の最後から調べていく

動的計画法ではなく、整列させた数列の後ろから調べていく方法を考えてみました。まず始めに、 \( t = a _i\) とします。\( i \) は \( N – 1 \) から \( 0 \) まで数列の最後から調べていきます。 また、\( 0 \leq j < i \) を満たす \( j \) を \( i – 1 \) から \( 0 \) まで調べます。このとき、\( t \mod a_j = 0\) を満たすとき、\( t = a_j\) として更新します。この更新回数の最大値が解答となります。

ソースコード

動的計画法

配列の最後の要素から調べる

感想

なぜこのようにして解くことができるのかいまいち分かりませんでした。配列の最後から調べていく方法は、僕は証明ができていませんが、実践的な解法だと思います。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする