Base64で反転
締め切りが 2016/11/22 10:00 AM なので,その 1 分後に投稿されるように予約
設問
A-Zとa-zの52文字から構成される、長さが 3n の文字列があります。
これをASCIIコードからBase64にエンコードし、左右反転します。
さらにBase64からデコードしたときに、元の文字列と同じになるもののうち、
元の文字列に含まれる文字が n 種類のものがいくつあるかを出力してください。
例えば、n = 1 のとき、「TQU」という文字列はエンコードすると「VFFV」となり、
左右反転してデコードすると「TQU」に戻ります。
ただ、この場合は「T」「Q」「U」という3種類の文字を使用しています。
同様に、「DQQ」「fYY」は2種類の文字を使用しています。
n = 1 のときは「UUU」の1つだけですので、1を出力します。
なお、n は5以下の整数とします。
【入出力サンプル】
標準入力
1
標準出力
1
===================
R で書いたら, n = 5 のときに制限時間オーバー
f = function(N) {
tbl = c(LETTERS, letters)
int.tbl = sapply(tbl, utf8ToInt)
tbl1 = c("a", "A", "b", "B", "d", "D", "e", "E", "f", "F", "h", "H", "i", "I", "j", "J", "L", "M",
"N", "P", "Q", "R", "T", "U", "V", "X", "Y", "Z")
tbl2 = c("Q", "U", "Y")
tbl3 = c("P", "Q", "R", "S", "T", "U", "V", "X", "Y", "Z")
a0 = as.matrix(expand.grid(tbl1, tbl2, tbl3))
a = as.matrix(expand.grid(sapply(tbl1, utf8ToInt), sapply(tbl2, utf8ToInt), sapply(tbl3, utf8ToInt)))
intToBin = matrix(0L, 8, max(int.tbl))
for (i in int.tbl) {
intToBin[, i] = as.integer(intToBits(i))[8:1]
}
intToBin2 = matrix(0L, 6, 52)
for (i in 1:52) {
intToBin2[, i] = as.integer(intToBits(i - 1))[6:1]
}
# アルファベット3文字の組の2進表現(3バイト;24ビット) 24×140608 (=52^3)
b = rbind(intToBin[, a[, 1]], intToBin[, a[, 2]], intToBin[, a[, 3]])
# エンコーディングされたアルファベット4文字(6ビット)の組として読む
w = 2^(5:0)
z1 = w %*% b[1:6, ] # 0 ~ 51 ならアルファベットに変換される
z2 = w %*% b[7:12, ]
z3 = w %*% b[13:18, ]
z4 = w %*% b[19:24, ]
valid = (52 > z2) & (52 > z3) & (52 > z4) # z1 はチェック無用
z1 = z1[valid]
z2 = z2[valid]
z3 = z3[valid]
z4 = z4[valid]
a = a0[valid, ] # アルファベット3文字の組 82800×3
w1 = intToBin2[, z1 + 1] # 4文字の組からデコードしてアルファベット3文字の組を作る
w2 = intToBin2[, z2 + 1]
w3 = intToBin2[, z3 + 1]
w4 = intToBin2[, z4 + 1]
y = rbind(w4, w3, w2, w1)
w8 = 2^(0:7)
range = int.tbl # sapply(tbl, utf8ToInt)
y1 = w8 %*% y[8:1, ]
y2 = w8 %*% y[16:9, ]
y3 = w8 %*% y[24:17, ]
valid2 = (y1 %in% range) & (y2 %in% range) & (y3 %in% range)
s1 = sapply(y1[valid2], intToUtf8)
s2 = sapply(y2[valid2], intToUtf8)
s3 = sapply(y3[valid2], intToUtf8)
final = cbind(a[valid2, ], s1, s2, s3) # 右3列は,左3列と逆順のエンコード文字列を生成する
# たとえば,"AQQ" は "QVFR" となり,"DUP" は "RFVQ" となる
flag = rowSums(final[, 1:3] == final[, 4:6]) == 3
sym = final[flag, 1:3]
rev = final[!flag, ]
n = nrow(final)
n.sym = nrow(sym)
result = 0
unique2 = function(x) length(.Internal(unique(x, FALSE, FALSE, NA)))
if (N == 1) { # 1 ==> 1
f = apply(sym, 1, function(x) length(table(x)) == 1)
result = sum(f)
} else if (N == 2) { # 2 ==> 2
f = apply(final, 1, function(x) length(table(x)) == 2)
result = sum(f)
} else if (N == 3) { # 3 ==> 127
for (i in 1:n) {
if (unique2(final[i, ]) > 3)
next
for (j in 1:n.sym) {
result = result + (unique2(c(final[i, ], sym[j, ])) == 3)
}
}
} else if (N == 4) { # 4 ==> 1536
for (i1 in 1:n) {
if (unique2(final[i1, ]) > 4)
next
for (i2 in i1:n) {
result = result + (unique2(c(final[i1, ], final[i2, ])) == 4) * ifelse(i1 == i2, 1, 2)
}
}
} else if (N == 5) { # 5 ==> 52500
f = 5 >= apply(final, 1, function(x) length(unique(x)))
final = final[f, ]
n = nrow(final)
for (i1 in 1:n) {
if (unique2(final[i1, ]) > 5)
next
for (i2 in i1:n) {
part2 = c(final[i1, ], final[i2, ])
if (unique2(part2) > 5)
next
for (j in 1:n.sym) {
result = result + (unique2(c(part2, sym[j, ])) == 5) * ifelse(i1 == i2, 1, 2)
}
}
}
}
cat(result)
}
f(1) # 1
f(2) # 2
f(3) # 127
f(4) # 1536
f(5) # 52500
最新の画像[もっと見る]
-
算額(その2059) 42分前
-
算額(その2057) 4時間前
-
算額(その2056) 19時間前
-
算額(その2055) 19時間前
-
算額(その2054) 1日前
-
算額(その2053) 1日前
-
算額(その2052) 1日前
-
算額(その2051) 1日前
-
算額(その2051) 1日前
-
算額(その2050) 2日前
※コメント投稿者のブログIDはブログ作成者のみに通知されます