きままにものづくり

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

SRM653Div1Easy

問題

様々な国から来たN人が一列に並んでいる。その内の何人かにどこの国から来たのかを聞いた。同じ国から来た人は隣合っている。
現状の調査結果を表す配列Aが与えられる。この結果から、全ての解答を一意に予測できるか求めよ。

解法

Coding is fun: SRM 653 DIV1 Easy - CountryGroupHard
ここの解答を使用した。

i番目の要素に注目し、それより前の要素jを使用して[j,i]の部分配列を考える。この配列の中の0以外の要素の全てが len = (j - i + 1)に等しい場合、その部分配列は一意に決まる。その結果をdp[i]に保存する。複数のjで条件を満たす場合、dp[i]の値は1より大きくなり、[0,i]での予測できる解答は複数あることを示す。問題は[0,N]で、解答が一意に定まるかどうかを問いているので、dp[N]が1かどうかを調べれば良い。

計算量

 O(N^2)

コード