最近、ルームメイトが華為のソフトウェア筆記試験に参加しました。問題を手に入れた後、私も試しにやってみましたが、問題 2 は非常に巧妙でしたので、ブログに記録しておきます。
問題の説明#
ドライバーの小王は倉庫に行って荷物を運びます。倉庫の管理者は事前に荷物をパッケージ化し、一列に並べました。パッケージは 1 から番号が付けられています。各パッケージには M={M1, M2, ..., Mn} という形で荷物が入っています。トラックは一度に最大で K 個の荷物を運ぶことができます。小王は最大の力を発揮するために、一度に K の倍数の荷物を選んで分割して運びたいと考えています。倉庫の管理者は管理を容易にするため、小王に連続した番号のパッケージを選択するように要求しています。例えば、1、2、3 番のパッケージを選択することができますが、2、4、6 番のパッケージを選択することはできません。K の倍数の荷物を運ぶ場合、小王が選択できる方法は何通りあるかを計算してください。
入力の説明#
パッケージの数 N とトラックが一度に運ぶことのできる最大の荷物数 K
各パッケージに入っている荷物の数：M1, M2, M3, M4, ...
入力は 2 行で、以下の形式です：
N K
MI M2 M3 M4 ...
N と K の値の範囲は [1, 100000] です。
各パッケージに入っている荷物の数の範囲も [1, 100000] です。
分析#
連続したシーケンスの問題なので、スライディングウィンドウを使用することを考えましたが、分析の結果、使用できないことがわかりました。
スライディングウィンドウの一般的な方法は、まずウィンドウを拡大し、ある条件が満たされなくなった場合にウィンドウを縮小することです。しかし、この問題では、局所的な条件によってウィンドウを縮小する必要があるわけではありません。つまり、現在のウィンドウが K の倍数でないために、ウィンドウをさらに拡大しても K の倍数にならないことを保証することはできません。
次に、区間の合計を動的計画法を使用して求め、各区間が条件を満たしているかどうかを判断することを考えました。経験から、これが正しい方法であることがわかりましたが、動的計画法には区間和を示す 2 次元配列が必要であり、そのための空間計算量は O (N^2) です。また、この 2 次元配列を走査する必要があり、そのための時間計算量も O (N^2) です。N の値が [1,100000] の範囲である場合、このような計算量は受け入れられません。
列挙をするのでしょうか？空間計算量は低くなりますが、動的計画法よりも時間計算量がはるかに高くなり、さらに受け入れられません。
行き詰まったら解答を見ることにしました。いくつかの解答を見て、この解答は O (n+k) の時間計算量の解法を提供しており、大いに示唆を受けました。
この解法の基本的なアイデアは次のとおりです：
- 荷物 0 から荷物 j までの和と荷物 0 から荷物 i までの和の差を取ると、その差は荷物 i から荷物 j までの和になります。もし差が k で割り切れる場合、つまり荷物 0 から荷物 j までの和を k で割った余りが荷物 0 から荷物 i までの和を k で割った余りと等しい場合、その区間は条件を満たします。
この結論は数学的に次のように表されます：
(Sum[j]-Sum[i])%k=0 => Sum[j] = n*k + Sum[i] => Sum[j]%k = Sum[i]%k
- 複数の位置 a、b、c... が Sum [a]% k=Sum [b]% k=Sum [c]% k=... を満たす場合、位置の数を t とすると、これらの位置から任意の 2 つの位置を選ぶことで条件を満たす区間を構成することができます。したがって、この場合の条件を満たす区間の数は C (t,2) です。
C (t,2) は数学の組み合わせの式であり、展開すると t*(t-1)/2 になります。
具体的な手順は以下の通りです：
-
長さ n の配列 M を使用して倉庫の荷物数を保存し、入力が完了したら長さ n の配列 Sum を開き、Sum [i] が M [0]+M [1]+...+M [i] を表すようにします。この時点で、Sum [j]-Sum [i] は荷物 i から荷物 j までの区間の総数を表します。
-
長さ k の配列 count を作成し、Sum 配列を走査し、任意の 0 から n のインデックス x に対して、count [Sum [x]% k]+=1 を実行します。
-
count 配列を走査し、任意の 0 から k のインデックス y に対して、count [y]>1 の場合、result = result + C (count [y],2) とします。最後に result を返します。
実際のコード表現では、M と Sum 配列を省略し、入力時に count を操作することができます。これにより、n 個の入力を処理するだけで、長さ k の配列を走査する時間計算量が O (n+k) になり、また長さ k の count 配列のみを使用するため、空間計算量が O (k) になり、この問題の最適解です。
コード#
私の Golang のコードは以下の通りです：
package main
import "fmt"
func main() {
var (
n, k int
tmp int
current int
count []int
result int
)
fmt.Scanln(&n, &k)
count = make([]int, k)
// 荷物リストを入力し、リアルタイムで累積する
for i := 0; i < n; i++ {
fmt.Scan(&tmp)
current = (current + tmp) % k
count[current] += 1
}
for _, v := range count {
if v > 1 {
result += v * (v - 1) / 2
}
}
fmt.Println(result)
}