斜め線が引かれた3x2の格子には合計で37の長方形が含まれる(上記問題文リンク先に図解)。
3x2よりも小さい格子は5つある(1x1, 2x1, 3x1, 1x2, 2x2)。これらの格子は各々次のような個数の長方形を含む。
1x1: 1
2x1: 4
3x1: 8
1x2: 4
2x2: 18
3x2に含まれる長方形の個数37と合わせると、3x2以下の格子についてそれぞれ長方形の個数を数えたものの総和は72であることがわかる。
47x43以下の全ての格子各々について含まれる長方形の個数の総和はいくつになるか。
やたら時間かかったし1分以内に計算終わらないし今回もダメな感じ。
この問題は見るからにわかるように斜めがすごく面倒くさい。縦横のカウントなんてあって無いようなものなので、斜めの長方形を数える方法が分かれば解ける。
長方形は対角の2点を決めてやれば残りの2点は定まるので、指定した2点から作成される長方形が領域内に収まるか否かを判定する関数をまずは作った。
あとは考えられる2点の組み合わせ全てについて長方形ができるかどうか判定していけばいい…のだけれどもちろん組み合わせが爆発するので少しだけ整理した。
m x nの格子に含まれる斜め長方形の個数が分かっていたとしよう。このとき、(m+1) x nの格子に含まれる斜め長方形の個数を求めるには、m+1行目に含まれる交点を頂点の一つとする斜め長方形の個数を数え上げて、m x nの格子に含まれる斜め長方形と足せばよい。
が、「m+1行目に含まれる交点を頂点の一つとする斜め長方形の個数を数え上げて」の部分だけでもまだまだ大量の組み合わせがあるので時間がかかる。
そこで問題をもう一段階スケールダウンして、m x nの格子の1行目に含まれる交点を頂点の一つとする長方形の個数をカウントする方法を考える。
m x nの格子について長方形のカウントができているとしよう。このとき、(m+1) x nの格子に含まれる長方形の個数をカウントするには、(m+1)行目に含まれる交点と、1行目に含まれる交点をそれぞれ1つづつ頂点として含む長方形の個数をカウントすればよい。そしてカウントしたものをm x nの格子に含まれる長方形の個数に足せば、(m+1) x nの格子に含まれる長方形の個数がわかる。
伸びた分に含まれる交点を調べるという点では一緒だが上端と下端の1行ずつのみ調べれば良いのでだいぶ組み合わせが減る。
減るには減るものの…と考えているうちにbrute forceでやってた計算が終わったので諦めた。
### 上端と下端の座標を指定し、長方形が作成できるか判定する関数 is.rectangle <- function(x1, y1, x2, y2, m, n){ x3 <- (y2 + x2 - y1 + x1) / 2 y3 <- (y1 - x1 + y2 + x2) / 2 x4 <- (y1 + x1 - y2 + x2) / 2 y4 <- (y1 + x1 + y2 - x2) / 2 if(## x3 != x1 && x4 != x1 && ## y3 != y1 && y4 != y1 && # 始点と異なる (y1 < y3 && y1 < y4) && sum(c(x3, y3, x4, y4) < 0) == 0 && # 領域内 sum(c(y3, y4) > m) == 0 && sum(c(x3, x4) > n) == 0 ) return(TRUE) FALSE } ### 斜めの長方形をカウント ## 上端と下端のみの組み合わせを調べる関数 rect.cnt.ud <- function(h, w){ m <- h*2; n <- w*2 tmp <- 0 for(y1 in 0:1){ for(y2 in (m-1):m){ for(x1 in 1:(n-1)){ if(y1 %% 2 != x1 %% 2) next for(x2 in 1:(n-1)){ if(y2 %% 2 != x2 %% 2) next tmp <- tmp + is.rectangle(x1, y1, x2, y2, m, n) }}}} tmp } ## 1行分だけカウント tilt.rec.slice.mat <- matrix(NA, ncol=43, nrow=47) tilt.rec.slice.mat[1,] <- 0:42 for(h in 2:47){ for(w in 1:43){ tilt.rec.slice.mat[h, w] <- tilt.rec.slice.mat[h-1, w] + rect.cnt.ud(h, w) # 新たに発生した組み合わせを足す } } ## 斜めの長方形をメモりつつ計算 ## メモ用行列 tilt.rec.mat <- matrix(NA, nrow=47, ncol=43) tilt.rec.mat[1,] <- 0:42 # 高さ1や tilt.rec.mat[,1] <- 0:46 # 幅1の枠内の長方形の個数は自明 tilt.rec.cnt <- function(h, w){ # height, width ## メモ済みならそれを返す if(!is.na(tilt.rec.mat[h, w])) return(tilt.rec.mat[h, w]) ## 1行分のカウントした値と ## 1行小さい四角の値を呼び出して足す tmp <- tilt.rec.slice.mat[h, w] + Recall(h-1, w) ## 計算した値はメモして返す (tilt.rec.mat[h, w] <<- tmp) } ## 縦横の長方形をカウントする関数 rect.cnt <- function(h, w) h*w*(h+1)*(w+1)/4 ## 縦横と斜めの長方形の和をメモる用行列 rect.mat <- matrix(NA, nrow=47, ncol=43) ## 縦横の長方形と斜めの長方形の和をメモってく for(h in 1:47){ for(w in 1:43){ rect.mat[h, w] <- rect.cnt(h, w) + tilt.rec.cnt(h,w) } } ## 47 * 43以下の全ての格子に含まれる長方形の和 sum(rect.mat)
