TeX on AtCoder!!!!!!!!!

はじめに

この記事は、

TeX ＆ LaTeX Advent Calendar 2025 17日目の記事です
- 16日目は yuracoさんの縦書きで本を作るだけのTeXユーザでした
traPアドベントカレンダー2025 17日目の記事です
- 16日目は@tidusの朝カラはいいぞ, @n3の【c++】二分探索より速いisqrtを実装するでした。

この記事は、外部と内部、二つのアドベントカレンダーの性質を併せ持つ…♢

追記(2025/12/17)

AdC告知の部分を整理しました。

挨拶

こんにちは、東京科学大学デジタル創作同好会、2025年度学部入学生 (25B) の @Suima (aka Kiri Nakuni(Alph))です。
普段は (個人で) TeX したり、(みんなで) TeX したり、TeX 以外 (アレレ) をしたりしています。ふむ…

あらかじめ

今回は AtCoder を念頭に置いているため、LuaTeX などの、高機能でモダンでステキな TeX のお話は、しません。残念。

同様の理由で、LaTeXとかConTeXtとか、そもそもe-TeX拡張の話も、しません。 ~~ぶっちゃけ e-TeX 拡張は使えても良いだろとは思うけど…もう遅い~~

本題

実は、AtCoder では ABC430 から (plain) TeX が提出言語として利用できます。できちゃうんですね。そう、できるんですよ。

じゃあ、やらない理由、ないですよね？

ということで、今回は、AtCoder で †カンタン† に TeX で AC をとる方法を、教えていきます。
~~TeX の LO(その言語でのAC数が最多である人)が言うんだから間違いない~~

0. 環境構築

TeX はバナー出力 (バージョン情報などの表示) をするため、本来は 必ず負ける言語 です。(参照：やばいFIZZ BUZZのある記事)

ですが、AtCoder は良い感じの解決をしているので、なんとかなります。これをローカルにも構築しておいた方が、デバッグがしやすくていいでしょう。私は Docker を使って構築しました。(Docker Hubに上がっています。リンク)

1. ライブラリ盆栽

この分野には素晴らしい先駆者がいらっしゃるので (Mopepe51（雪下）氏、東大TeX愛好会には頭が上がりませんね)、それらのものをライブラリとして使えるように仕上げたものを利用していきます。
ソートは、制限が緩ければ if 分岐で愚直なバブルソートを実装し、緩くないのならヒープソートを実装するのが良いと思います。(何れにせよ言語制約上 C 問題以降は厳しいことが多いですが)

今回は、一部を抜粋して非 TeXer 向けに解説をします。

標準入出力

これは、私が過去にやったような無骨な方法を使う必要は無く、主に二つのプリミティブと、その仕様を利用します。

TeX がファイルを開くときにはファイルストリームを利用する必要があります。C 言語でファイルディスクリプタを触ることを想像していただければ、全く違う、ということはないと思います。

TeX のファイルストリームにも、C のファイルディスクリプタと同様、最初から開いているものがありますが、実はこれは \read 命令と \write 命令で違う挙動を示すことに注意が必要です。

\readでは厳密には最初から開いているファイルストリームはありません。但し、負整数を指定すると標準入力から入力を受け取るようになります。

また、16 以上の正整数ストリームの場合、対話中のインタプリタが入力待ちになります。(標準入力としてはAtCoderでは使い物になりません…念のため。)

対して、\write で最初から開いているファイルストリームは (ある意味で) 負整数ストリームと、第 16 ストリーム、第 17 ストリーム、第 18 ストリーム (条件 (-shell-escape オプション) 依存) です。

負整数は全てログファイルに割り振られています。
第 16 ストリームはログファイルとファイルディスクリプタ 1 番 (標準出力) に割り振られています。
第 17 ストリームはログファイルとファイルディスクリプタ 1 番 (標準出力) に割り振られていますが、-interaction オプションが batchmode 等だと負整数と同じ挙動になります。
第 18 ストリームはシェルスクリプト実行に割り振られています。 (但し、-shell-escape オプションに依存します。)

(また、19 番以降は 16 と同じ挙動になります)

ストリーム番号	割当先	備考
負整数	ログ出力
16	ログ, 標準出力
17	ログ, 標準出力	標準出力は通常時のみ
18	シェルスクリプト実行	`-shell-escape` オプション有効時

ここら辺の話は、今日は本題でないのでこの程度で…。

さて、実際には標準入出力は次のようなマクロを組んでおくと容易でしょう。

\def\readline{\read-1to}
\def\println{\immediate\write16}

因みに、\message を使わない理由ですが、これは改行とスペースの挙動が少々扱いにくいからですね。良い感じの解決との相性の問題だと言っても差し支えないでしょう。

注意が必要なのは、\readline と \println の挙動と使い方です。

\readline は \readline\hoge の形で、標準入力一行を \hoge に代入します。代入です。(競技プログラミングで使うかはさておき) \afterassignment フックが発動します。*¹

\println は \println{hoge} の形で、標準出力に出力をして改行します。(Rust の println! マクロや Python の print のデフォルトの挙動に似ていますね)
フラッシュは必要ありません。

また、一度でも \read-1 を使っていない状態で \immediate\write16 をすると、標準出力の一行目に余分な改行が現れて WA になります。気をつけてください。 ~~標準入力が標準出力に影響するなんてアリ？~~ これも、後から出力をシェルスクリプトで整形している関係です。注意してください。

また、終了は TeX プリミティブである \end を推奨するとともに、これをしないと WA になることを警告しておきます。

字句解析と展開制御

競技プログラミングに於いては、TeXを言語として難しくしている所以である展開制御から逃れられません。

そして、展開制御から逃れられないということは、字句解析からも逃れられないということです。なんてこった。

しかし、TeX は字句解析だけでも記事になる(例1, 例2)し、展開制御だけでも記事になる(例1, 例2, 例3)
これでは、コマッタ…おや？

どうやら先駆者の記事がたくさんあるようですね。
ということで、自分でたくさん実験したり(幸いにもTeX は対話型実行可能なインタプリタ言語ですから、対話型実行して遊んでみるのも手です)、先駆者の記事を読んでいただければ、と思います。
本当はちゃんと説明したかったんですが、流石に分量が…

では、私たちはTeXの字句解析を完全に理解しないとTeXが出来ないのでしょうか？

答えは、部分的に、そう。です。

ここで重要なのは、競技プログラミング、それもABCのA, B問題程度ならば、TeX言語を完全に理解していなくても十分に扱える、ということです。(ぶっちゃけTeXで書けるアルゴリズムを書き出す方が難しい。)

そのため、今回はA問題を解く上で重要なもの=パターンマッチと数値終端について説明します。(数値終端はカウンタの後に説明します)
パターンマッチ中の\expandafterはおまじないです。知りたければexpandafterで検索しましょう。

パターンマッチ

TeX の \def 系命令にはパターンマッチがあります。これが競技プログラミングの場合は非常に強力な入力処理となります。(TeX はエラーを起こしたら、のような条件分岐は出来ないため、制約が厳格な競技プログラミングでないと容易には扱えないです。強力なことに変わりないですが。)

\newcount\i
\newcount\j
\def\split#1 #2;{\def\A{#1} \def\B{#2}}
\read-1to\hoge
\expandafter\split\hoge;
\immediate\write16{\A,\B}

として、標準入力に C D などと渡せば、C,D と出力されて、確かにこれでスペース区切りが出来ることが理解できるでしょう。*²
また、次の入力に注目してください。

\def\hoge{1 2 3 4}
\def\split#1 #2;{\def\A{#1}\def\B{#2}}
\expandafter\split\hoge;
\immediate\write16{\A}

この実行結果はどうなるでしょうか。未定義動作？

いいえ、TeX にとってこれは定義済み動作です。そして、その出力は 1 です。つまり、パターンマッチは最短一致で進行します。

これらを利用することで、TeX は ABC の B 問題までの受け取りに十分な表現能力を持ちます。*³

カウンタ

TeX に整数型はあるんでしょうか？

実はあります。整数レジスタ (カウンタ) といい、32bit 符号付き整数が 256 個 0 初期化で既に宣言されています (新規宣言は出来ません)。
\newcount マクロを利用することで、制御綴に未使用のカウンタを割り振ることが出来ます。

カウンタの扱いは次の六つを記憶すれば良いでしょう。

代入

\newcount\i
\i = 10

このようにすると、\i というカウンタに 10 を代入することが出来ます。

\newcount\i
\i10

= を省略しても行けます。

加算代入、乗算代入、整数除算代入

減算代入はありません。- を使いましょう。
また、単なる加算演算などは存在しません。(e-TeX拡張にはあるのですが…)

\newcount\i% i32 i = 0;
\newcount\j% i32 i = 0;
\advance \i by 10  % i += 10;
\j=2
\advance \i by -\j % i += (-j);
\multiply\i by \j  % i *= j;
\divide\i by \j    % i //= j;

因みに、by は省略できますし、スペースも基本的に省略できます。

ifnum

\newcount\i
\ifnum\i<10
hoge
\else
fuga
\fi

if 文は、古き良き if-fi 型です。(マクロ展開でif分岐なので当然と言えば当然ですが)因みに、if(条件式) のような柔軟なことは (そもそもブーリアンがないので) 出来ません。

数値の場合は \ifnum、
文字 (トークン) 一致は \if、
トークンの意味の一致は \ifx、

で行います。他にも色々あります。調べてみてください。

\the

カウンタを 10 進文字列として得たい場合は、\the を利用します。

\newcount\i
\i30
\immediate\write16{\the\i} % 30

数値終端

TeXは数値が来ると想定される場所では、数値を読めるだけ読むという挙動をします。
具体的に見ていきましょう。

\newcount\i

\i=1000%ここで改行を「コメントアウト」する
00
\ifnum\i=1000 %ここでは、空白で数値を終端させている
\immediate\write16{iは1000ですね}
\else
\immediate\write16{iは1000ではないですね}
\fi

上記のコードの出力結果は、iは1000ではないですねです。
基本的に、数値の直後には空白か改行を明示的に入れるようにするのが吉です。
因みにここで数値終端に使われた改行や空白は消費されて消滅します。
もう少し厳密な話はこちらの記事が参考になるかと思います。(私が前に数値終端の扱いをミスったときにZR氏が反応してくださったものです)

また、数値終端のミスは頻出なので、特に\ifnumでちゃんと数値を終端させているのか確認しましょう。

配列

TeX には配列などという便利なデータ構造は ありません が、便利なことに動的に変数名 (厳密には、制御綴名) を宣言できます。これを利用していきます。

つまり、A[i][j] を宣言したければ、iAj という名前の制御綴を宣言すればいいわけです。

これは、i, j がカウンタ名だとすると、\csname\the\i A\the\j\endcsname とすることで実現できます。

この制御綴をマクロとして定義する場合、\expandafter\def\csname\the\i A\the\j\endcsname{<Value>} とすれば良いとされています。

ここら辺は展開制御が絡むので、ZRさんの記事を読むと理解しやすいかと思います。

ループ処理

TeXは再帰処理が出来ます。
\def\hoge{\message{hoge}\hoge}とすれば、無限ループすることが確認できるかと思います。(Ctrl+CやCtrl+Zなどで通常のプログラム同様強制終了できます)

ここで、AtCoderでも利用されているマクロパッケージ体系である、plain TeXには便利なマクロが組み込まれています。

\loop...\if...\repeatマクロです。(\ifの部分は他の\if系命令に置き換えることが出来ます。)

こちらのマクロの動作について、軽く説明をしておきます。

\loopから\repeatで挟まれた部分を、\ifが真の間ループし続けます。\ifは恒真式でも構いませんが、必ず存在する必要があるほか、\loopから\repeatで挟んだ部分をマクロの定義にし、そのマクロを反復して呼び出すことで解決をしているため、ネストする場合は(\loop...{\loop...\if...\repeat}...\if...\repeat} 等のように)グルーピングをしてスコープを分けてあげる必要があります。というのも、\loop...\repeatマクロは、内部でループ用のマクロを定義するので、スコープを分けてあげないと内側のループが、外側のループ用のマクロを上書きしてしまってバグります。

因みに、グルーピングした内部で定義したマクロはスコープから離れると(当然ながら)消滅します。
但し、\global\def, \gdef, \global\edef, \xdefなどとすると大域定義になるため、消滅しません。
その辺は普通の言語と同じなので、ちゃんとスコープを認識しながら実装しましょう。

ループの詳しい挙動については ZRさんの記事がやはり参考になるかと思います。

2. 練習

ABC430 から 436 までの A, B 問題は 全て TeX で解けます。何故断言するかといいますと、私が全て解きました。 なので、練習をするなら、先ずこれらの問題で AC を取りましょう！
結局は 競技プログラミング なので、練習が大事です。
私の体感で最も難しかったのは、ABC430 の B 問題と、ABC436 の B 問題です。

今回はこれらの解説を行います。

ABC430 B - Count Subgrid

この節は TeX で A 問題は解ける人向け です。

問題リンクはこちら
そして、私の解法 (にコメントを追加したもの) はこれです。

% カウンタ用意
\newcount\i
\newcount\j
\newcount\k
\newcount\l
\newcount\m
\newcount\n
\newcount\amount
\newcount\N
\newcount\M
%入力読み込み1(数値の部分)
\read-1to\hoge%
%読み込んだ行の処理
\def\split#1 #2;{\N#1 \M#2}%
\expandafter\split\hoge;%
%catcode処理
\catcode`@=6 %@を#の代わりに利用
\catcode`#=11 %#を通常の文字扱いにする
%マクロ定義
\def\NIL{\NIL}
\let\.=\relax
\let\#=\relax
\def\println@1{\immediate\write16{@1}}%
\def\split@1@2;{\expandafter\xdef\csname\the\j A\the\i\endcsname{@1} \xdef\hoge{@2}}
%TeX の \read は行末に空白が入る仕組みがあるため、スペース区切りの split マクロが最後の要素でもうまく機能します
%入力読み込み2(マスの部分)
\loop%
  \read-1to\hoge%
  {%
    \loop%
    \expandafter\split\hoge;
    \advance\j1
    \ifnum\j<\N
    \repeat%
  }%
  \advance\i1
\ifnum\i<\N
\repeat%
%数値処理
\advance\N-\M
\advance\N1
\i0
\j0
\k0
\l0
%文字列変数用意に当たる
\xdef\hashname{}
%四重ループで部分正方形を文字列化してパターンマッチ
\loop%
  {%
    \loop%
      {%
        \loop%
          {%
            \loop%
              {%
                \n\l
                \advance\n\j
                \m\k
                \advance\m\i
                \xdef\hashname{\hashname\csname\the\n A\the\m\endcsname}
              }%
              \advance\l1
            \ifnum\l<\M
            \repeat%
          }%
          \advance\k1
        \ifnum\k<\M
        \repeat%
      }%
      {%
        \expandafter\ifx\csname\hashname\endcsname\relax%
          \expandafter\gdef\csname\hashname\endcsname{\NIL}%
          \global\advance\amount1%
        \fi%
      }%
      \xdef\hashname{}
      \advance\j1
    \ifnum\j<\N
    \repeat%
  }%
  \advance\i1
\ifnum\i<\N
\repeat%
%出力
\println{\the\amount}
%終了
\end

解法としては、かなり力業、というか普通の全探索です。
全体像は

入力を読み込む
$N \times N$ のグリッドから、あり得る全ての $M \times M$ の領域を切り出す
切り出した領域を文字列に変換する
その文字列が既出かどうかを判定し、初めて出たならカウントする

となっています。普通～～～

細かい解説をしていきます。

カテゴリーコードについて

この問題では、# と . の羅列が入力として渡されます。ですから、# は普通の文字 (あるいは記号) として扱えないと困ります。

そのため、# のカテゴリーコードを 11 (通常の文字) に、代わりに @ を 6 (パラメタ文字) に置き換えています。

カテゴリーコードって何？という方は、wtsnjpさんの記事などをご覧になると良いかと思います。

文字列結合について

TeX での文字列結合は、単に並べればできます。

\def\hoge{fu}
\def\hogehoge{ga}
\def\fuga{gaha}
\immediate\write16{\expandafter\csname\hoge\hogehoge\endcsname}%gaha

ここで、
\xdef\hashname{\hashname\csname\the\n A\the\m\endcsname} は、普通の言語のコードにすると次のようになります。
global hashname = hashname + A[n][m]
この辺は完全展開というものが絡んでくるので、しっかりした理解はここでは目指しません。

因みに、この実装はグローバル変数へのアクセスと更新を含むため、些か重いです。(具体的には、文字列長を $L$ , $M$ とすると $O (L + M)$ かかります)
もっと賢い実装もあるかと思いますが、(私が最初に実装したのがこれである上)かなり自明な実装ではあるので、今回はこの実装を採用しています。

csname の挙動について

\csname~\endcsname プリミティブは、間に挟んだ文字の名前の制御綴が既に定義されていれば、その制御綴に展開される、というものです。*⁴
では、仮に未定義の場合はどうなるでしょうか？

エラーを回避するためか、その制御綴の意味を \relax (何もしないプリミティブ) と同義として定義します。

言い換えると、\csname~\endcsname で挟んだ文字列の名前の制御綴が (\relax 以外の意味で) 定義されているかどうか、\ifx(トークンの意味の一致判定命令) を使って判断するために使えます。

ここでは、\csname~\endcsname で、 $M \times M$ の部分領域を文字列に変換したものを挟んで、その制御綴が \relax と同義だったら \amount を 1 追加して、この制御綴の意味を \relax 以外に変えています。

因みに、plain TeX では元から \# と \. が定義されているので、これらを予め \relax と同じ意味にしておく必要があります。

既存の制御綴と意味をそろえたい場合は、\let 命令を使います。

\let\hoge = \relax

のようにすると、\hoge が \relax になります。

因みに、制御綴の探索は内部的にはハッシュマップです。これ自体は高速で、いいね。

結論

これらのトリックによって、定数倍重めの $O (N^{2} M^{2})$ で通ります。
因みに12msです。
この問題の制約が $N \times N = 10 \times 10$ とかなり緩いからTLEせずに通る解法ですね。

因みに、当然ではありますが、TeX はネタ言語枠です。遅くて、データ構造が貧弱で、可読性に欠けるインタプリタ言語だと思っていただければ…。

ABC436 B - Magic Square

問題リンクはこちら

そして、私の解法(にコメントアウトを附したもの)がこれです

\newcount\N
\newcount\M
\newcount\R
\newcount\r
\newcount\c
\newcount\k
\newcount\MEMA
\newcount\memc
\newcount\memr
\newlinechar=`\^^J %標準出力中の改行文字の指定
\read-1to\hoge
\N\hoge
\M\N
\R\N
\c\N
\def\println{\immediate\write16}
\def\mod#1#2{%剰余の定義、TeXに剰余演算は存在しないので用意する必要があります
  \MEMA#1
  \divide\MEMA#2
  \multiply\MEMA#2
  \advance#1-\MEMA
  \ifnum #1<0 \advance#1 #2 \fi%負になったときの処理
}
\multiply\N\N
\advance\N-1
\advance\c-1
\divide\c2
\k1
\expandafter\xdef\csname\the\r:\the\c\endcsname{\the\k}
\loop
\memr\r
\advance\r-1
\memc\c
\advance\c1
\mod\r\M
\mod\c\M
\advance\k1
{
  \expandafter\ifx\csname\the\r:\the\c\endcsname\relax
    \expandafter\xdef\csname\the\r:\the\c\endcsname{\the\k}
  \else
    \advance\memr1
    \mod\memr\M
    \global\r\memr
    \global\c\memc
    \expandafter\xdef\csname\the\r:\the\c\endcsname{\the\k}
  \fi
}
\advance\N-1
\ifnum\N>0
\repeat
\def\ans{}%文字列変数の用意にあたります。
\loop
\advance\M-1
{%\Rの初期化は不要(グルーピングがあるため)
  \loop
  \advance\R-1
  \long\xdef\ans{\csname\the\M:\the\R\endcsname\space\ans}
  \ifnum\R>0
  \repeat
  \ifnum\M=0
  \else
  \xdef\ans{^^J\ans}
  \fi
}
\ifnum\M>0
\repeat
\println{\ans}
\end

^^記法について

TeXを使っているとよく目にする^ですが、これには実は二つの性質があります。

一つ目は皆さんご存知の通り、上付き文字を作る機能です。f^{-1} と書けば右上に文字が乗りますね。*⁵

二つ目が、拡張文字入力機構としての働きです。^ が2回連続して出現した場合、TeXの字句解析器は以下の規則に従って文字コードを解釈します。

直後に小文字の16進数字が2つ続く場合：それを8bitの文字コードとして解釈する。

それ以外の場合：直後の文字コードと64 (0x40) のXORを取った値の文字として解釈する。

例として、^^J はASCIIコードにおけるLF（Line Feed）と等価です。

標準出力に関する補足

(plain)TeX で、標準出力中に明示的に空白を入れたり、明示的にLF で改行をしたい時って、ありますよねぇ…

そんなときにはそれぞれ解決策があります。

空白について
空白を標準出力中に明示的に入れたいときは、\ (コントロール・スペース)ではなく、\spaceマクロ(plain TeX組み込み)を利用します。
改行について
標準出力中の改行コードを明示したいときには、\newlinecharプリミティブを用います。
\newlinecharプリミティブはカウンタのように振る舞い、ここに代入されている文字コードを標準出力での改行コードとして扱います。
ここでは、^^J(LF)を明示しています。

結論

これらの追加のトリックも利用することで、 $O (N^{4})$ 程度となって1884msでAC!
制限が $N \leq 99$ とやや緩いからこそギリギリで通ります。
文字列結合がボトルネックとなっているので、それを回避すれば早い解法はありますが、文字列結合はコードが書きやすいので…

おわりに

ま、†カンタン†でしたね(決して簡単ではない)
After you have played with TeX in AtCoder, what will you be: An ATeXoder?

補足

TeX の \read は行末に空白が入る仕組みがあるため、スペース区切りの \split マクロが最後の要素でもうまく機能します

これは実際には\read命令は入力を一行ずつ(改行まで含めて)読み込みます。
また、単一の改行をスペース(実際には\endlinecharの値に対応する文字)に置換する、という処理も存在するため、結果的にそのような挙動になっています。…まあ\endlinecharを弄らない限りこの説明は必要ないですが。

また、今回の記事ではグループとトークンの違いについての説明を避けています。いつか書くかも

余談

言語サーバーのsed -e '1d;2s@^(\./Main.tex@@'をsed -e '1d' -e "2{ /^(\.\/Main\.tex *$/N; s@^(\./Main\.tex *\n*@@; }"に書き換えてくれると助かる命があるんですが…(気づくのが遅かった)(次回のサーバーアップデートで修正されるととても助かる…)

注釈

ここで出てくる \read-1to の to はキーワードと呼ばれます。キーワードの扱いは複雑ですので、気になる方はZRさんの記事を参考にされると良いかと思います。
より正確には、#1 には \split 制御綴の直後から最初のスペースまでを代入されます。
競技プログラミングは制限が厳格なので、"悪い"入力を想定する必要は無いですからね。
一回展開をすると、単にその制御綴に展開される。但し未定義の場合は同時に \relax に \let する、というのが正確な動作です。
因みに、上付き文字が^なのは、TeXの開発者であるKnuthの矢印記法(の省略記法)と関連しているらしいです。

AdC次の人紹介

TeX ＆ LaTeX Advent Calendar 2025
- 18日目は 1997_takahashiさんです
traPアドベントカレンダー2025
- 18日目は@mumumuです