読者です 読者をやめる 読者になる 読者になる

TeXで競技プログラミングは可能か?

TeX 競技プログラミング AtCoder

ジャッジシステムないので無理ですが.

というのも残念なので,まずはそもそも解くことができるかについて.問題はAtCoder Regular Contest #005のA,B,C*1

A

  • 単純な文字列比較.
  • 正規表現が使えないけど文字列比較を TeX に任せるくらいはできる
    • 実際は,パターンマッチが使えるのでもう少しキチガイコードにできるかも
コード
% const data
\def\tki{TAKAHASHIKUN}
\def\tkii{Takahashikun}
\def\tkiii{takahashikun}
\def\solve#1.{\ssolve#1 \relax.}
\def\rrelax{\relax}
\newcount\lovetk
\def\ssolve#1 #2.{%
\def\cmp{#1}%
\def\chkend{#2}%
% Is \cmp 'takahashikun' word? 
\ifx\cmp\tki\advance\lovetk1\fi
\ifx\cmp\tkii\advance\lovetk1\fi
\ifx\cmp\tkiii\advance\lovetk1\fi
\ifx\rrelax\chkend\else % data owari?
\ssolve#2.\fi}
\read-1to\stdin % read #words
\read-1to\stdin % read sentence
\expandafter\solve\stdin
\immediate\write16{\the\lovetk}%
\bye
出力(入力は元ネタの入力例5を標準入力から)

答えは1

$ tex a.tex < a.in
This is TeX, Version 3.1415926 (TeX Live 2012/dev/W32TeX)
 encTeX v. Jun. 2004, reencoding enabled.
(./a.tex1
 )
No pages of output.
Transcript written on a.log.

B

  • テーブル作って実装するだけ
コード
% move direction
\newcount\dx\dx0
\newcount\dy\dy0
\newcount\x
\newcount\y
\read-1to\tmp % readline
% function set x,y,W
\def\setfirstline#1 #2 #3.{%
\x#1\relax
\y#2\relax
\def\W{#3}}
\expandafter\setfirstline\tmp.
\def\calcW#1#2{\ccalc#1\ccalc#2}
\def\ccalc#1{%
\if#1R\dx1\fi
\if#1L\dx-1\fi
\if#1U\dy-1\fi
\if#1D\dy1\fi}
% function : W -> dx,dy
\expandafter\calcW\W\relax
\newcount\readline\readline1
% set map data
\def\setline#1#2#3#4#5#6#7#8#9{%
 \expandafter\def\csname data\the\readline1\endcsname{#1}%
 \expandafter\def\csname data\the\readline2\endcsname{#2}%
 \expandafter\def\csname data\the\readline3\endcsname{#3}%
 \expandafter\def\csname data\the\readline4\endcsname{#4}%
 \expandafter\def\csname data\the\readline5\endcsname{#5}%
 \expandafter\def\csname data\the\readline6\endcsname{#6}%
 \expandafter\def\csname data\the\readline7\endcsname{#7}%
 \expandafter\def\csname data\the\readline8\endcsname{#8}%
 \expandafter\def\csname data\the\readline9\endcsname{#9}}
% read map from stdin
\loop\ifnum\readline<10
  \read-1to\tmp
  \expandafter\setline\tmp
  \advance\readline1
\repeat
\newcount\chk
\def\buffer{}
\readline1
% output
\loop\ifnum\readline<5
 \edef\buffer{\buffer\csname data\the\y\the\x\endcsname}%
 \advance\readline1
 \chk\x\relax \advance\chk\dx\relax
 \ifnum\chk<1\multiply\dx-1\relax\fi
 \ifnum\chk>9\multiply\dx-1\relax\fi
 \advance\x\dx\relax
 \chk\y\relax \advance\chk\dy\relax
 \ifnum\chk<1\multiply\dy-1\relax\fi
 \ifnum\chk>9\multiply\dy-1\relax\fi
 \advance\y\dy\relax
\repeat
\immediate\write16{\buffer}
\bye
出力(入力例5)

答えは8878

$ tex b.tex < b.in
This is TeX, Version 3.1415926 (TeX Live 2012/dev/W32TeX)
 encTeX v. Jun. 2004, reencoding enabled.
(./b.tex8878
 )
No pages of output.
Transcript written on b.log.

C

コード
\read-1to\stdin % read one line from stdin to \stdin
% read H and W
\newcount\h
\newcount\w
\def\readHW#1 #2\relax{%
  \h=#1\relax
  \w=#2\relax}
\expandafter\readHW\stdin\relax
% read map
\newcount\loopcnt
\newcount\tmpw
\newcount\sh
\newcount\sw
\def\setmap{%
  \tmpw=0\relax\expandafter\setmapp\stdin\relax}
\def\setmapp#1#2{%
  \expandafter\def\csname map\the\loopcnt:\the\tmpw\endcsname{#1}%
  \if#1s
    \sh=\loopcnt
    \sw=\tmpw
  \else\fi
  \ifx#2\relax\def\next{}\else\def\next{\setmapp#2}\fi
  \advance\tmpw1\relax
  \next}
\catcode`\#=12\relax
\loop\ifnum\loopcnt<\h
  \read-1to\stdin
  \setmap
  \advance\loopcnt1\relax
\repeat
\catcode`\#=6\relax
% init deque data
\let\Data\relax
\edef\deque{\Data{\the\sh:\the\sw,0}}
\def\empty{}
% function : get topdata to \pos and \brcnt 
\def\getdata#1{\expandafter\ggetdata\expandafter#1\deque\relax}
\def\ggetdata#1\Data#2#3\relax{%
   \def#1{#2}\def\deque{#3}\parsePosBreak#2\relax}
\def\parsePosBreak#1,#2\relax{%
  \brcnt=#2\relax
  \def\pos{#1}}
% Breadth first search
\catcode`\#=12\relax
\def\start{s}
\def\goal{g}
\def\kabe{#}
\def\michi{.}
\catcode`\#=6\relax
%search main
\newcount\brcnt
\newcount\tw
\newcount\th
\def\search#1:#2(#3,#4){%
  \th=#1\relax\advance\th#3\relax
  \tw=#2\relax\advance\tw#4\relax
  \expandafter\ifx\csname map\the\th:\the\tw\endcsname\kabe
    % KABE NO NAKA NI IRU
    \ifnum\brcnt<2
      \advance\brcnt1
        % add to tail
        \edef\deque{\deque\Data{\the\th:\the\tw,\the\brcnt}}
      \advance\brcnt-1
    \fi
  \else
    % add to top
    \edef\deque{\Data{\the\th:\the\tw,\the\brcnt}\deque}%
  \fi}
\def\pos{}
\def\checked{true}
\def\solve{\let\next\relax%
   \ifx\deque\empty\immediate\write16{NO} % empty!
   \else
     \getdata\data % get top data
     \expandafter\ifx\csname flag\data\endcsname\checked
        % checked before -> continue
        \let\next\solve
     \else\expandafter\ifx\csname map\pos\endcsname\relax
        % out of map
        \let\next\solve
     \else
        % check
        \expandafter\let\csname flag\data\endcsname\checked
        \expandafter\ifx\csname map\pos\endcsname\goal
          % GOAL now
           \immediate\write16{YES}\let\next\relax
        \else
          \expandafter\search\pos(0,1)%
          \expandafter\search\pos(0,-1)%
          \expandafter\search\pos(1,0)%
          \expandafter\search\pos(-1,0)%
          \let\next\solve
        \fi
     \fi\fi
   \fi\next}
\solve
\bye
出力(入力例3)

答えはYES

$ tex c.tex < c.in
This is TeX, Version 3.1415926 (TeX Live 2012/dev/W32TeX)
 encTeX v. Jun. 2004, reencoding enabled.
(./c.texYES
 )
No pages of output.
Transcript written on c.log.

だれかジャッジ作らないかなー*2

*1:コンテスト時にJavaで解いた問題.

*2:あっても本番では使わないけど……