平面直行座標上で原点を含む3点(座標の係数はいずれも正の整数)から直角三角形を作図する。
座標の各係数が0以上50以下のとき直角三角形はいくつできるか、という問題。
こういう組み合わせが簡単に列挙できる問題は全てのパターンをベクトルとして列挙してしまって一度に計算すると簡単。
5秒かかった。準備を丁寧にやったら半分になるかもしれない。面倒なのでやらない。
何も考えずに書くとこうなる。
limit <- 50 count <- 0 for(i in 0:limit){ for(j in 0:limit){ P <- c(i, j) if(all.equal(P, c(0,0))==TRUE) next for(n in 0:limit){ for(m in 0:limit){ Q <- c(n, m) if(all.equal(Q, c(0,0))==TRUE) next if(all.equal(P, Q)==TRUE) next OP <- sum(P^2) OQ <- sum(Q^2) PQ <- sum((P-Q)^2) set <- sort(c(OP, OQ, PQ),T) if(set[1] == sum(set[2:3])) count <- count + 1 }}}} count/2
2時間以内には終わるけどあまり賢い方法ではない。少し余分な計算をしているがそこを削っても半分になる程度。
組み合わせを全部ベクトルにするとこうなる
limit <- 50 i <- rep(0:limit) j <- rep(i, each=limit+1) n <- rep(j, each=limit+1) m <- rep(n, each=limit+1) n <- rep(n, limit+1) j <- rep(j, (limit+1)^2) i <- rep(i, (limit+1)^3) OP <- i^2 + j^2 OQ <- n^2 + m^2 PQ <- (i-n)^2 + (j-m)^2 count <- 0 for(k in 1:((limit+1)^4)){ if(i[k]==0 && j[k]==0 || n[k]==0 && m[k]==0 || i[k]==n[k] && j[k]==m[k]) next set <- sort(c(OP[k], OQ[k], PQ[k]),T) if(set[1] == sum(set[2:3])) count <- count + 1 }
ただ組み合わせは700万近いのでこれでも時間がかかる。
そこで、for文のところをベクトル同士の演算に変えてしまう。これだと5秒で回る。
(sum(c(OP==(OQ+PQ)|OQ==(OP+PQ)|PQ==(OP+OQ)))- sum(i==0 & j==0 | n==0 & m==0 | i==n & j==m))/2
あまり綺麗には見えないし、ちょっと組み合わせが増えたら通用しなくなってしまうのが難点だけど。