裏 RjpWiki

Julia ときどき R, Python によるコンピュータプログラム,コンピュータ・サイエンス,統計学

◯はぴったり☓は無し

2017年06月01日 | ブログラミング

◯はぴったり☓は無し


締め切りが 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);
    }

}





コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

PVアクセスランキング にほんブログ村

PVアクセスランキング にほんブログ村