きままにものづくり

日々の気付いたことなんかを書いてます。

SRM594Div1Easy

問題

N個の惑星の相対サイズAとM個の惑星の相対サイズBが与えられる。各要素は中心からの距離が近い順に並べられている。相対サイズとはある基準に対して何倍であるかを示す値である。AとBそれぞれの中では基準は同一であるが、AとBで同じ基準であるとは限らない。
この時の最小の惑星の数を求めよ。

解法

最長共通部分列で答えが導ける。
基準を同じにするためにAとBそれぞれから一要素だけ選択し、その要素を選択していない方のすべての要素にかける。

計算量

 O((NM)^2)

コード

広告を非表示にする