GCJの問題をRで解いてみた - ぬいぐるみライフ？

少し前に、Rの勉強をするべくGCJの問題をRで解いてみました。

問題概要

Online Round 1A: Problem A. Minimum Scalar Product

二つのn次元ベクトルv1、v2が与えられる。
ベクトルの各要素は整数である。
v1とv2のそれぞれについて要素を並び替え、v1とv2の内積を計算した結果をPとするとき、Pの最小値を求めよ。

問題の原文はこちら。

入力

入力のフォーマットは以下の通り。まず最初に整数Tがひとつ与えられます。

T: テストケース数(入力データセット数)

次に、各テストケースごとに以下の入力が与えられます。

n
x1 x2 ... xn
y1 y2 ... yn

n: ベクトルv1, v2の要素数(次元)
x1, x2, ..., xn: ベクトルv1の各要素の値(整数)
y1, y2, ..., yn: ベクトルv2の各要素の値(整数)

出力

出力のフォーマットは以下の通り。各テストケースについて以下の出力を行います。

Case #X: Y

X: テストケースの番号(1,2,...,T)
Y: 内積の最小値

入力の値の範囲

入力データファイルはSmall datasetとLarge datasetの二種類があります。

Small dataset

 T = 1000
 1 ≤ n ≤ 8
 -1000 ≤ xi, yi ≤ 1000

Large dataset

 T = 10
 100 ≤ n ≤ 800
 -100000 ≤ xi, yi ≤ 100000

Large datasetだとベクトルの要素数が最大800まであるため、要素の順列をとって内積をひとつひとつ計算するプログラムを書くと800! ≒ 7.7 * 10^1976で計算量が爆発します。

ソース

v1とv2の各要素をそれぞれ昇順・降順にソートして内積をとった値が求める最小値となるので*1、それを計算して終了です。

lines <- 0
file <- "A-large.in"

solve <- function() {
    n <- scan(file, skip=lines, nmax=1)
    lines <<- lines + 1
    v1 <- scan(file, skip=lines, nmax=n)
    lines <<- lines + 1
    v2 <- scan(file, skip=lines, nmax=n)
    lines <<- lines + 1

    sum(sort(v1) * sort(v2,decreasing=T))
}

t <- scan(file, skip=lines, nmax=1)
lines <- lines + 1

out <- matrix(0, t, 3)
for (a in 1:t) {
    out[a,] <- c("Case", sprintf("#%d:", a), solve())
}

write(t(out), "A.out", ncolumns=3)