◯はぴったり☓は無し
締め切りが 2017/06/01 10:00 AM なので，その 1 分後に投稿されるように予約
【概要】
26×26のマス目に、◯と☓が配置されています。
数 n を指定します。マス目に沿った矩形のうち、◯をちょうど n 個含み、☓を含まない矩形として、最大となる矩形の面積を求めて下さい。
例えば、下図の場合、緑に塗られた部分が最大面積の矩形の例になります。
【入出力】
入力は、
2 Ip,Ni,Wl,Sl,Ih Cr,Lv,Pu,Uf,Hd
のようになっています。空白区切りで順に、n、◯のマスの座標、☓のマスの座標です。
一つ一つの座標はコンマで区切って並べられています。
座標は、x座標とy座標が区切り文字なしで並べられています。
（上記の入力が上図に対応しています）
出力は、
220
のように出力してください。
10進数で最大の面積を出力して下さい。
ただし、◯をちょうど n 個含み、☓を含まない矩形を作れない場合は
-
を出力して下さい。
【例】
入力
2 Ip,Ni,Wl,Sl,Ih Cr,Lv,Pu,Uf,Hd
出力
220
入力
7 Fl,Mi,Jl,Fp,Aq,Bm,Hn,Gz,Su,Fs Ul,Ko,Se,Xx,Jr,Xa,Wn,Jj,Hw,Zb
出力
-
入力
2 Xm,Po,Kl,Dv,Ri,Zc,Lz,Yz,Ev,Ay Nh,Bc,Vc,Ok,Hm,Lw,Hz,Rv,Mv
出力
184
【補足】
• 不正な入力に対処する必要はありません。
• マス目に沿った矩形のみを考えます。つまり、傾いた矩形のことは考えません。
• x 座標は大文字のアルファベット、y座標は小文字のアルファベットです。
• ◯の数、☓の数 は、いずれも 20 個を超えることはありません。
---------------------------------
素直に書いてみる。さいわいなことに，R では行列操作が容易である。
実行時間も，予想に反して十分に速い。
f = function(s) {
g = function(s) {
s = unlist(strsplit(gsub(",", "", s), ""))
s = matrix(sapply(s, function(S) utf8ToInt(S) %% 32), byrow=TRUE, ncol=2)
s
}
tbl.o = tbl.x = matrix(0, 26, 26)
s = unlist(strsplit(s, " "))
n = as.integer(s[1])
tbl.o[g(s[2])] = 1 # "o", 転置してもしなくても同じ結果になる
tbl.x[g(s[3])] = 1 # "x", 転置してもしなくても同じ結果になる
Max = 0
for (iBegin in 1:25) {
for (jBegin in 1:25) {
for (iEnd in iBegin:26) {
for (jEnd in jBegin:26) {
Matrix =
if (sum(tbl.x[iBegin:iEnd, jBegin:jEnd]) != 0) {
break
} else if (sum(tbl.o[iBegin:iEnd, jBegin:jEnd]) == n) {
Max = max(Max, (iEnd-iBegin+1)*(jEnd-jBegin+1))
}
}
}
}
}
cat(ifelse(Max == 0, "-", Max))
}
if (0) {
f("1 Bb Ab,Ba,Cb,Bc") # 1
f("5 Oh,Be,Af,In,Eg,Rl Aa") # 650
f("2 Ky,Zd,Yi,Av,Tk,Lz,Jk,Vx,Ga,Um,Ho Yr,Wc,Cb,Tf,Io,Bk,Yh,Yl,Bp,Qf,Ur") # 198
f("1 Le,Dq,Qa,Qs,Sl,Xa,Nf,Qb,Ur,Sc,Ei,Mq Kw,Qe,Rv,Ry,Ih,Aq,Jb,Px,Yx,Lu,Kq,Qm") # 154
f("3 Bl,Aq,Vl,Iu,Iy,Om,Te,Js,Fu,Xj,Kr,Ja,Nm He,Ki,Yu,Mr,Ua,Vw,Ha,Xy,Bv,Tp,Lw,Jr,Th") # 147
f("0 Zy,Ze,Va,Yn,Hb,Cv,Co,Kh,Ml,Wh,Zr,Vh,Mm,Vj Hc,Pw,Ne,Iu,Jt,If,Wm,Dy,Uc,Lx,Xs,Sa,Hv,Ao") # 136
f("2 Dn,Ve,Cf,Rh,Jg,Na,Bh,Ad,Xz,To,Fw,Ml,Bp,Vd,Go Py,Ol,Px,Qc,Bg,Ss,Vm,Xr,Eh,Kz,Dr,Kc,Tb,Vu,Ov") # 154
f("4 Mg,Qb,Ae,Wo,Fg,Ke,Zx,Na,Us,Ky,Zm,Mi,Ls,Py,Ye,Ya Ux,Kj,Fo,Jw,Ug,Mt,Aw,Tb,El,Oo,Rv,Ri,Zd,Am,Bu,Il") # 126
f("3 Ti,Oq,Wy,Dz,Xb,Ys,Mk,Ym,Ae,Ii,Wu,Ol,Ta,Mm,Eq,Vs,Cg Sa,Ub,Vf,Wv,Zf,No,Up,Zo,Ws,Bb,Uy,Yn,Xv,Yh,Ob,Zu,Gt") # 190
f("1 Tv,Sg,Js,Lb,Mu,Sz,Za,Pl,It,Bs,Cl,Bf,Ik,Du,Te,Gc,Ge,Ub Kh,Mb,La,Dz,Wa,Jg,Ra,Ca,Rm,Yo,Um,Uz,Lo,Zn,We,Bb,Vv,Gw") # 104
f("2 Pn,We,Au,Wz,Nc,Jr,Rr,Og,Yd,Sk,Zn,Fj,Ds,Nw,Rd,Sj,Zm,Ll,Mt Dx,Bt,Xo,Tg,Iv,Kp,Oa,Av,Ve,Yx,Nb,Ku,Vr,Wl,Gr,Gf,Md,Sd,Uy") # 126
f("9 Lv,Nd,Jw,Ps,Br,Dg,Vq,Xs,Pj,Nw,Mn,Ce,Te,Ss,Mv,Tu,Rk,Xb Eo,Gg,Nz,Mo,Wp,Pk,Jn,Os,No,Ey,Vz,Uf,Xk,Pd,Iy,Lo,Zd,Pg,Gl,Nx") # -
} else {
f(readLines(file("stdin", "r")))
}
======================================================
awk で書くと，長くなるし，とても時間が掛かる
{
f($0) # コンソールから文字列を入力し，関数を呼ぶ
}
function charToInt(s) {
return index("ABCDEFGHIJKLMNOPQRSTUVWXYZ", toupper(s))
}
function g(s, mark, k, t, i) {
gsub(",", "", s)
k = split(s, t, "")
for (i = 1; i < k; i += 2) {
tbl[charToInt(t[i]), charToInt(t[i+1])] = mark
}
}
function f(S, i, j, n, Max, iBegin, jBegin, iEnd, jEnd, xs, os, area) {
for (i = 1; i
for (j = 1; j
tbl[i, j] = "."
}
}
split(S, s, " ")
n = s[1]
g(s[2], "o")
g(s[3], "x")
Max = 0
for (iBegin = 1; 25 >= iBegin; iBegin++) {
for (jBegin = 1; 25 >= jBegin; jBegin++) {
for (iEnd = iBegin; 26 >= iEnd; iEnd++) {
for (jEnd = jBegin; 26 >= jEnd
xs = os = 0
for (i = iBegin; iEnd >= i; i++) {
for (j = jBegin; jEnd >= j; j++) {
if (tbl[i, j] == "o") {
os++
if (os > n) break
}
else if (tbl[i, j] == "x") {
xs = 1
break
}
}
if (xs == 1 || os > n) break
}
if (xs == 1 || os > n) break
else if (os == n) {
area = (iEnd-iBegin+1)*(jEnd-jBegin+1)
Max = area > Max ? area : Max
}
}
}
}
}
print Max == 0 ? "-" : Max
}
======================================================
Java で書くと，計算時間は速いが，プログラムは長いまま
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
String line;
line = cin.nextLine(); // コンソールから文字列を入力し，
f(line); // 関数を呼ぶ
}
static String[][] g(String s, String[][] tbl, String mark) {
int k, i;
char[] t;
s = s.replace(",", "");
t = s.toCharArray();
k = t.length;
for (i = 0; i < k; i += 2) {
tbl[t[i] % 32 - 1][t[i + 1] % 32 - 1] = mark;
}
return tbl;
}
static void f(String S) {
int i, j, n, Max, iBegin, jBegin, iEnd, jEnd, xs, os, area;
String[] s;
String[][] tbl = new String[26][26];
for (i = 0; i < 26; i++) {
for (j = 0; j < 26; j++) {
tbl[i][j] = ".";
}
}
s = S.split(" ");
n = Integer.parseInt(s[0]);
tbl = g(s[1], tbl, "o");
tbl = g(s[2], tbl, "x");
Max = 0;
for (iBegin = 0; iBegin < 25; iBegin++) {
for (jBegin = 0; jBegin < 25; jBegin++) {
for (iEnd = iBegin; iEnd < 26; iEnd++) {
for (jEnd = jBegin; jEnd < 26; jEnd++) {
xs = os = 0;
for (i = iBegin; iEnd >= i; i++) {
for (j = jBegin; jEnd >= j; j++) {
if (tbl[i][j] == "o") {
os++;
if (os > n)
break;
} else if (tbl[i][j] == "x") {
xs = 1;
break;
}
}
if (xs == 1 || os > n)
break;
}
if (xs == 1 || os > n)
break;
else if (os == n) {
area = (iEnd - iBegin + 1) * (jEnd - jBegin + 1);
Max = area > Max ? area : Max;
}
}
}
}
}
System.out.println(Max == 0 ? "-" : Max);
}
}
