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''
