2 つの時刻の間の時間数の筆算で,0 ~ 9 の全てが現れる計算は何通りあるか
例
16時27分
- 5時38分
==========
10時49分
0x 時とか 0y 分のような zero fill の 0 は除く
また,0 時 zz 分も除く
プログラム1
以下の AWK(GAWK) プログラムが 4 秒ほどで,一番速かった。
#!/usr/local/bin/gawk -f
BEGIN {
for (h1 = 1; h1 < 24; h1++) {
for (m1 = 0; m1 < 60; m1++) {
t1 = h1*60+m1
for (h2 = 1; h2 <= h1; h2++) {
for (m2 = 0; m2 < 60; m2++) {
t2 = h2*60+m2
if (t2 > t1) break
diff = t1-t2
m3 = diff%60
h3 = int(diff/60)
tbl(h1)
tbl(h2)
if (h3 > 0) tbl(h3)
tbl(m1)
tbl(m2)
tbl(m3)
if (length(digits) == 10) {
# print h1, m1, h2, m2, h3, m3
count++
}
delete digits
}
}
}
}
print "ans =", count
}
function tbl(d, d1) {
d1 = int(d/10)
if (d1 > 0) digits[d1]
digits[d%10]
}
文字列を使って以下のようにしたものは 7 秒強かかる。
#!/usr/local/bin/gawk -f
BEGIN {
for (h1 = 1; h1 < 24; h1++) {
for (m1 = 0; m1 < 60; m1++) {
t1 = h1*60+m1
for (h2 = 1; h2 <= h1; h2++) {
for (m2 = 0; m2 < 60; m2++) {
t2 = h2*60+m2
if (t2 > t1) break
diff = t1-t2
m3 = diff%60
h3 = int(diff/60)
hm = m1 m2 m3 h1 h2
if (h3 > 0) hm = hm h3
split(hm, a, "")
for (i in a) digits[a[i]]
if (length(digits) == 10) {
# print h1, m1, h2, m2, h3, m3
count++
}
delete digits
}
}
}
}
print "ans =", count
}
最初のプログラムを R で描き直すと,25 秒もかかる。ほぼ 6 倍ということだ。
tbl = function(d, digits) {
d1 = d %/% 10
if (d1 > 0) digits[d1+1] = TRUE
digits[d %% 10+1] = TRUE
return(digits)
}
count = 0
for (h1 in 1:23) {
for (m1 in 0:59) {
t1 = h1*60+m1
for (h2 in 1:h1) {
for (m2 in 0:59) {
t2 = h2*60+m2
if (t1 < t2) break
diff = t1-t2
m3 = diff %% 60
h3 = diff %/% 60
digits = logical(10)
digits = tbl(h1, digits)
digits = tbl(h2, digits)
if (h3 > 0) digits = tbl(h3, digits)
digits = tbl(m1, digits)
digits = tbl(m2, digits)
digits = tbl(m3, digits)
if (sum(digits) == 10) {
# cat(h1, m1, h2, m2, h3, m3, "\n")
count = count+1
}
}
}
}
}
cat("ans =", count, "\n")
R で定石のベクトル演算を使って書いてみたら,260 秒もかかるとんでもないプログラムになった。最短 AWK プログラムのほぼ 65 倍ということだ。
a = expand.grid(1:23, 0:59, 1:23, 0:59)
t1 = a[,1]*60+a[,2]
t2 = a[,3]*60+a[,4]
diff = t1 - t2
flag = diff > 0
a$diff1 = diff %/% 60
a$diff2 = diff %% 60
a = a[flag,]
func = function(d) {
d2 = d%%10
d1 = d%/%10
d1[d1 == 0] = NA
return(length(table(c(d1, d2))))
}
count = 0
apply(a, 1, function(x) {
if (x[5] == 0) x = x[-5]
if (func(x) == 10) {
# cat(h1, m1, h2, m2, h3, m3, "\n")
count+1 ->> count
}
})
cat("ans =", count, "\n")
解答は,以下の 48 通りということである。
16時27分 - 5時38分 = 10時49分
16時27分 - 5時39分 = 10時48分
16時27分 - 5時48分 = 10時39分
16時27分 - 5時49分 = 10時38分
16時27分 - 10時38分 = 5時49分
16時27分 - 10時39分 = 5時48分
16時27分 - 10時48分 = 5時39分
16時27分 - 10時49分 = 5時38分
18時25分 - 7時36分 = 10時49分
18時25分 - 7時39分 = 10時46分
18時25分 - 7時46分 = 10時39分
18時25分 - 7時49分 = 10時36分
18時25分 - 10時36分 = 7時49分
18時25分 - 10時39分 = 7時46分
18時25分 - 10時46分 = 7時39分
18時25分 - 10時49分 = 7時36分
20時47分 - 3時48分 = 16時59分
20時47分 - 3時49分 = 16時58分
20時47分 - 3時58分 = 16時49分
20時47分 - 3時59分 = 16時48分
20時47分 - 6時48分 = 13時59分
20時47分 - 6時49分 = 13時58分
20時47分 - 6時58分 = 13時49分
20時47分 - 6時59分 = 13時48分
20時47分 - 13時48分 = 6時59分
20時47分 - 13時49分 = 6時58分
20時47分 - 13時58分 = 6時49分
20時47分 - 13時59分 = 6時48分
20時47分 - 16時48分 = 3時59分
20時47分 - 16時49分 = 3時58分
20時47分 - 16時58分 = 3時49分
20時47分 - 16時59分 = 3時48分
20時57分 - 4時18分 = 16時39分
20時57分 - 4時19分 = 16時38分
20時57分 - 4時38分 = 16時19分
20時57分 - 4時39分 = 16時18分
20時57分 - 6時18分 = 14時39分
20時57分 - 6時19分 = 14時38分
20時57分 - 6時38分 = 14時19分
20時57分 - 6時39分 = 14時18分
20時57分 - 14時18分 = 6時39分
20時57分 - 14時19分 = 6時38分
20時57分 - 14時38分 = 6時19分
20時57分 - 14時39分 = 6時18分
20時57分 - 16時18分 = 4時39分
20時57分 - 16時19分 = 4時38分
20時57分 - 16時38分 = 4時19分
20時57分 - 16時39分 = 4時18分
※コメント投稿者のブログIDはブログ作成者のみに通知されます