Google Code Jam 2013 Qual

長く苦しい戦いだった…….ソースを載せます.

A (LOLCODE)

一番苦労した.言語の公式サイトにつながらないし,WebArchiveからSpecificationを探してきて頑張って書いた.特に超不便な連想配列しか用意されていない点や,文字列の i 番目にアクセスすることができない点は辛かった.後者は特にどうしようもなかったので Python で input を改行区切りに変換するスクリプトを書くことで対処した.

HAI 1.3
  I HAS A CSN ITZ A NUMBR
  GIMMEH CSN

  I HAS A CURCS ITZ 0
  IM IN YR LOOP UPPIN YR CURCS WILE DIFFRINT CURCS AN BIGGR OF CURCS AN CSN
    I HAS A BRD ITZ A BUKKIT
    I HAS A ROW ITZ 0
    I HAS A COL ITZ 0
    IM IN YR RDLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
      COL R 0
      I HAS A LNE ITZ A BUKKIT
      IM IN YR RDLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
        LNE HAS A SRS COL
        GIMMEH LNE'Z SRS COL
      IM OUTTA YR RDLPC
      BRD HAS A SRS ROW ITZ LNE
    IM OUTTA YR RDLPR

    VISIBLE "Case #" AN SUM OF 1 AN CURCS AN ": "!
    I HAS A DTRMND ITZ FAIL

    ROW R 0
    IM IN YR RLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
      I HAS A XC ITZ 0
      I HAS A OC ITZ 0
      I HAS A TC ITZ 0
      COL R 0
      IM IN YR RLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
        I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS COL, WTF?
          OMG "X", XC R SUM OF 1 AN XC, GTFO
          OMG "O", OC R SUM OF 1 AN OC, GTFO
          OMG "T", TC R SUM OF 1 AN TC, GTFO
        OIC
      IM OUTTA YR RLPC
      NOT DTRMND, O RLY?
        YA RLY, BOTH OF BOTH SAEM XC AN BIGGR OF XC AN 3 AN BOTH SAEM SUM OF XC AN TC AN 4, O RLY?
          YA RLY, VISIBLE "X won", DTRMND R WIN
          MEBBE BOTH OF BOTH SAEM OC AN BIGGR OF OC AN 3 AN BOTH SAEM SUM OF OC AN TC AN 4
            VISIBLE "O won", DTRMND R WIN
          OIC
      OIC
    IM OUTTA YR RLPR

    COL R 0
    IM IN YR CLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
      I HAS A XC ITZ 0
      I HAS A OC ITZ 0
      I HAS A TC ITZ 0
      ROW R 0
      IM IN YR CLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
        I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS COL, WTF?
          OMG "X", XC R SUM OF 1 AN XC, GTFO
          OMG "O", OC R SUM OF 1 AN OC, GTFO
          OMG "T", TC R SUM OF 1 AN TC, GTFO
        OIC
      IM OUTTA YR CLPR
      NOT DTRMND, O RLY?
        YA RLY, BOTH OF BOTH SAEM XC AN BIGGR OF XC AN 3 AN BOTH SAEM SUM OF XC AN TC AN 4, O RLY?
          YA RLY, VISIBLE "X won", DTRMND R WIN
          MEBBE BOTH OF BOTH SAEM OC AN BIGGR OF OC AN 3 AN BOTH SAEM SUM OF OC AN TC AN 4
            VISIBLE "O won", DTRMND R WIN
          OIC
      OIC
    IM OUTTA YR CLPC

    I HAS A XCDA ITZ 0
    I HAS A OCDA ITZ 0
    I HAS A TCDA ITZ 0
    ROW R 0
    IM IN YR DIAGA UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
      I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS ROW, WTF?
        OMG "X", XCDA R SUM OF 1 AN XCDA, GTFO
        OMG "O", OCDA R SUM OF 1 AN OCDA, GTFO
        OMG "T", TCDA R SUM OF 1 AN TCDA, GTFO
      OIC
    IM OUTTA YR DIAGA
    NOT DTRMND, O RLY?
      YA RLY, BOTH OF BOTH SAEM XCDA AN BIGGR OF XCDA AN 3 AN BOTH SAEM SUM OF XCDA AN TCDA AN 4, O RLY?
        YA RLY, VISIBLE "X won", DTRMND R WIN
        MEBBE BOTH OF BOTH SAEM OCDA AN BIGGR OF OCDA AN 3 AN BOTH SAEM SUM OF OCDA AN TCDA AN 4
          VISIBLE "O won", DTRMND R WIN
        OIC
    OIC

    I HAS A XCDB ITZ 0
    I HAS A OCDB ITZ 0
    I HAS A TCDB ITZ 0
    COL R 0
    IM IN YR DIAGB UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
      I HAS A TML ITZ BRD'Z SRS COL, TML'Z SRS DIFF OF 3 AN COL, WTF?
        OMG "X", XCDB R SUM OF 1 AN XCDB, GTFO
        OMG "O", OCDB R SUM OF 1 AN OCDB, GTFO
        OMG "T", TCDB R SUM OF 1 AN TCDB, GTFO
      OIC
    IM OUTTA YR DIAGB
    NOT DTRMND, O RLY?
      YA RLY, BOTH OF BOTH SAEM XCDB AN BIGGR OF XCDB AN 3 AN BOTH SAEM SUM OF XCDB AN TCDB AN 4, O RLY?
        YA RLY, VISIBLE "X won", DTRMND R WIN
        MEBBE BOTH OF BOTH SAEM OCDB AN BIGGR OF OCDB AN 3 AN BOTH SAEM SUM OF OCDB AN TCDB AN 4
          VISIBLE "O won", DTRMND R WIN
        OIC
    OIC

    I HAS A DC ITZ 0
    ROW R 0
    IM IN YR DCNTLR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
      COL R 0
      IM IN YR DCNTLC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
        I HAS A TML ITZ BRD'Z SRS ROW, BOTH SAEM TML'Z SRS COL AN ".", O RLY?
          YA RLY, DC R SUM OF 1 AN DC
        OIC
      IM OUTTA YR DCNTLC
    IM OUTTA YR DCNTLR
    BOTH OF NOT DTRMND AN BOTH SAEM DC AN 0, O RLY?
      YA RLY, VISIBLE "Draw", DTRMND R WIN
    OIC

    NOT DTRMND, O RLY?
      YA RLY, VISIBLE "Game has not completed"
    OIC
  IM OUTTA YR LOOP
KTHXBYE

B (LOLCOCDE)

内容的にも慣れ的にも明らかに A より楽だった.

HAI 1.3
  I HAS A CSN ITZ A NUMBR
  GIMMEH CSN

  I HAS A CURCS ITZ 0
  IM IN YR LOOP UPPIN YR CURCS WILE DIFFRINT CURCS AN BIGGR OF CURCS AN CSN
    I HAS A RWS
    I HAS A CLS
    GIMMEH RWS
    GIMMEH CLS
    RWS IS NOW A NUMBR
    CLS IS NOW A NUMBR

    I HAS A FLD ITZ A BUKKIT
    I HAS A ROW ITZ A NUMBR
    I HAS A COL ITZ A NUMBR
    ROW R 0
    IM IN YR RDLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
      COL R 0
      I HAS A LNE ITZ A BUKKIT
      IM IN YR RDLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
        LNE HAS A SRS COL
        GIMMEH LNE'Z SRS COL
        LNE'Z SRS COL IS NOW A NUMBR
      IM OUTTA YR RDLPC
      FLD HAS A SRS ROW ITZ LNE
    IM OUTTA YR RDLPR

    I HAS A HGHT ITZ 1
    IM IN YR CTLP UPPIN YR HGHT WILE BOTH SAEM HGHT AN SMALLR OF HGHT AN 100
      ROW R 0
      IM IN YR CTLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
        COL R 0
        IM IN YR CTLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
          I HAS A TML ITZ FLD'Z SRS ROW, BOTH SAEM TML'Z SRS COL AN HGHT, O RLY?
          YA RLY
            I HAS A RC ITZ 0
            I HAS A CC ITZ 0
            I HAS A TR ITZ 0
            I HAS A TC ITZ 0
            IM IN YR CNTLPR UPPIN YR TR WILE DIFFRINT TR AN BIGGR OF TR AN RWS
              I HAS A TTML ITZ FLD'Z SRS TR
              EITHER OF BOTH SAEM TTML'Z SRS COL AN HGHT AN BOTH SAEM TTML'Z SRS COL AN 0, O RLY?
              YA RLY, RC R SUM OF 1 AN RC
              OIC
            IM OUTTA YR CNTLPR
            IM IN YR CNTLPC UPPIN YR TC WILE DIFFRINT TC AN BIGGR OF TC AN CLS
              I HAS A TTML ITZ FLD'Z SRS ROW
              EITHER OF BOTH SAEM TTML'Z SRS TC AN HGHT AN BOTH SAEM TTML'Z SRS TC AN 0, O RLY?
              YA RLY, CC R SUM OF 1 AN CC
              OIC
            IM OUTTA YR CNTLPC
            BOTH SAEM RC AN RWS, O RLY?
            YA RLY
              TR R 0
              IM IN YR FLDLPR UPPIN YR TR WILE DIFFRINT TR AN BIGGR OF TR AN RWS
                I HAS A TTML ITZ FLD'Z SRS TR, TTML'Z SRS COL R 0
              IM OUTTA YR FLDLPR
            OIC
            BOTH SAEM CC AN CLS, O RLY?
            YA RLY
              TC R 0
              IM IN YR FLDLPC UPPIN YR TC WILE DIFFRINT TC AN BIGGR OF TR AN CLS
                I HAS A TTML ITZ FLD'Z SRS ROW, TTML'Z SRS TC R 0
              IM OUTTA YR FLDLPC
            OIC
          OIC
        IM OUTTA YR CTLPC
      IM OUTTA YR CTLPR
    IM OUTTA YR CTLP

    I HAS A K ITZ WIN
    ROW R 0
    IM IN YR CHKLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
      COL R 0
      IM IN YR CHKLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
        I HAS A TML ITZ FLD'Z SRS ROW
        K R BOTH OF K AN BOTH SAEM TML'Z SRS COL AN 0
      IM OUTTA YR CHKLPC
    IM OUTTA YR CHKLPR

    VISIBLE "Case #" AN SUM OF 1 AN CURCS AN ": "!
    K, O RLY?
    YA RLY, VISIBLE "YES"
    NO WAI, VISIBLE "NO"
    OIC
  IM OUTTA YR LOOP
KTHXBYE

C (J言語)

J言語は書きやすい言語です.これだけははっきりと真実を伝えたかった.

load'printf'

OUT =: 'C:\GCJ\qual2013\c.out'

S =. 1!:1 <'C:\GCJ\qual2013\c.in'

states =. 3 : 0
0 10 #: <. 10 * > -.&a: <@".;._2] 0 :0
)

splitWord =. 0;(states'');a.e.CRLF,LF
1.1 0
1 0.3
)

input =: splitWord ;: S
T =: ".>{.input
input =: }.input

largeSqrt =: 3 : 0
	'lo hi' =. 0; y + 1
	while. 1<hi-lo do.
		mid =. <.-:hi+lo
		if. y>:*:mid do. lo=.mid else. hi=.mid end.
	end.
	lo
)

comb=: 4 : 0
  if. x e. 0 1 do. z=.<((x!y),x)$ i.y
  else. t=. |.(<.@-:)^:(i.<. 2^.x)x
    z=.({.t) ([:(,.&.><@;\.)/ >:@-~[\i.@]) ({.t)+y-x
    for_j. 2[\t do.
      z=.([ ;@:(<"1@[ (,"1 ({.j)+])&.> ])&.> <@;\.({&.><)~ (1+({.j)-~{:"1)&.>) z
      if. 2|{:j do. z=.(i.1+y-x)(,.>:)&.> <@;\.z end.
    end.
  end.
  ;z
)

palindrome =: (=|.)@":

solveL =: 3 : 0
	if. y=1 do. 4 return. end.
	ks =. 1,(i.4)!<:<.-:y
	+/ks*>(2|y){1 1 1 1 1;2 3 3 2 2
:
	if. y=1 do. 4<.>:x return. end.
	res =. 0
	if. (t<:x)*.palindrome t=.2+2*10x^<:y do. res =. res+1 end.
	if. (1=2|y)*.(t<:x)*.palindrome t=.t+10x^<.-:y do. res =. res+1 end.
	for_p. i.4<.>:d=.<:<.-:y do.
		res =. res + +/x>:s=.(>:10x^<:y)+((10x^>:d+2|y)*(+/"1)10x^cs-~<:d)+10x*(+/"1)10x^cs=.p comb d
		res =. res + (2|y)*+/x>:s+10x^<.-:y
		res =. res + (2|y)*(2>p)*+/x>:s+2*10x^<.-:y
	end.
	res
)

solve2 =: 3 : 0
	N =. largeSqrt y
	res =. 0
	for_d. >:i.#":N do.
		if. d=#":N do. res =. res + N solveL d
		else. res =. res + solveL d end.
	end.
	res
)

solve1 =: 3 : 0
	'A B' =: y
	-/solve2"0 B,<:A
)

replace=: 4 : 0
 'p q'=. y
 j=. p nosindx x
 if. ''-:j do. x return. end.
 d=. p-&#q
 k=. (j+(0>.-d)*i.#j)+/i.#q
 select. *d
  case.  1 do. (0 (j+/(#q)+i.d)}1$~#x) # q k}x
  case.  0 do. q k}x
  case. _1 do. q k} (0 (d{."1 k)}1$~(#x)+(#j)*|d) #^:_1 x
 end.
)

nosindx=: 4 : 0
 s=. x I.@E. y
 i=. s I. s+#x
 (i.&_1 {. ]) (s,_1) {~ (i,_1) {~^:a: 0
)

solve =: 3 : 0
	'' 1!:2 <OUT
	for_n. >:i.T do.
		ps =. 'x',~(>(<:n){input) replace ' ';'x '
		('%d\n' sprintf n) 1!:2 <2
		('Case #%d: %d\n' sprintf (n,solve1".ps)) 1!:3 <OUT
	end.
)

solve''