sankantsuの日記

技術メモ・競プロなど

LaTeXの\@ifnextcharマクロ

概要

LaTeXカーネルで定義されている\@ifnextcharというマクロについて説明する. このマクロを使うとトークンの先読みを行うことができ,オプション引数の実装などに応用できる. カーネルやパッケージのソースにはよく登場するので,これらを読んでみたい場合には役立つ知識になるだろう.

以下,\makeatletterの状態で考える (@が英文字と同等扱い).

動作

\@ifnextcharは,3つの引数をとる.

\@ifnextchar<token>{<true case text>}{<false case text>}...

と書くと,3つ目の引数の次にくるトークン(上で言うと...の部分の先頭)を先読みし,このトークンが<token>に一致していれば<true case text>が展開され,一致しなければ<false case text>が展開される.

使用例

最も重要な使用例は,オプション引数の実装である. LaTeXの多くのコマンドは,[...]で囲んだ部分をオプション引数として渡せるようにしてある.

\defによるマクロで[...]の形の引数を受け取ろうと思うと,次のように書くことになる.

\def\foo[#1]{(option:#1)}

この定義により,\foo[...]のような形で引数を渡すマクロを作れる. 問題はこの定義だと[]の括弧は省略不可能になり,これに沿わない形式の引数を与えるとエラーとなることである.

\@ifnextcharを用いると,この問題点を次のような方法で解消できる.

\def\foo{\@ifnextchar[\@foo\@@foo}
\def\@foo[#1]{(option:#1)}
\def\@@foo{(no option)}

このように定義することで,\fooは次にくるトークンを先読みして[と等しいかどうか調べることができる. 等しい場合にはオプション引数を取るバージョンである\@fooを展開し, 等しくない場合にはオプション引数を取らない\@@fooを展開する.

したがって,オプション引数がある場合とない場合でそれぞれ次のような結果が得られる.

\foo[bar] % -> (option:bar)
\foo      % -> (no option)

実装

LaTeXカーネルのソース(latex.ltx)を読んで実装を追ってみる.

\long\def\@ifnextchar#1#2#3{%
  \let\reserved@d=#1%
  \def\reserved@a{#2}%
  \def\reserved@b{#3}%
  \futurelet\@let@token\@ifnch}

まず,引数をそれぞれ\reserved@d,\reserved@a,\reserved@bというマクロに保存しておく.

その後にくる\futureletというプリミティブが鍵で,これは

\futurelet\cs<token1><token2>...

と書くと\let\cs=<token2>を実行したあとで<token1>を展開するものである. この動作により,\csに先読みトークンを保存した上で<token1>の展開が行えるので,<token1>の定義の中で\csの中身を見ての分岐を行うことができるようになる.

つまり,今回の場合には\@let@tokenという制御綴に先読みトークンを保存しておいてから\@ifnchの展開を行う. この\@ifnchは次のように定義されたマクロである.

\def\@ifnch{%
  \ifx\@let@token\@sptoken
    \let\reserved@c\@xifnch
  \else
    \ifx\@let@token\reserved@d
      \let\reserved@c\reserved@a
    \else
      \let\reserved@c\reserved@b
    \fi
  \fi
  \reserved@c}
\def\:{\let\@sptoken= } \:  % this makes \@sptoken a space token
\def\:{\@xifnch} \expandafter\def\: {\futurelet\@let@token\@ifnch}

\ifxは,\ifx<token1><token2>の形で<token1><token2>の一致判定を行うプリミティブである. 最初の分岐は先読みトーク\@let@tokenが空白文字かどうかを判定して,もし空白文字なら読み飛ばすということをしている.

次の分岐が重要で,先読みトークンが事前に保存しておいた\@ifnextcharの第1引数\reserved@dに等しいかどうかを判定する. 等しければ保存された第2引数\reserved@aを実行するようにセットし, 等しくなければ第3引数\reserved@bを実行するようにセットする.

まとめ

  • \@ifnextcharの動作と応用例を説明した.
  • \futureletを用いた\@ifnextcharの実装を説明した.

TeXでドラゴン曲線を描く

概要

ドラゴン曲線というフラクタル曲線の一種をTeXを使って描いてみる. この題材はTeXブックに載っている有名(?)なもので,今回は元のプログラムを参考にしつつ簡易的なバージョンに書き直した.

出力結果を画像にすると以下のような感じ.

ドラゴン曲線

コード

github.com

pdftexコンパイルできるサンプルを用意した. 以下,実装について説明する.

解説

全体の流れ

まず,線の構成要素をボックスとして用意しておく. ここでは縦/横方向の線を構成要素として使った(線は\vruleを使って描ける). 基本的にはこの縦線または横線を\kern, \raiseといったTeXのプリミティブを使って位置を調整しながら並べることで任意の線を描く.

毎回プリミティブを使って位置制御をするのは大変なので,現在の位置から紙面の上下左右に向かって線を伸ばすという操作をするマクロを定義する (\goEast, \goNorth, \goWest, \goSouth).

また,現在の進行方向に対して相対的に直進,後退,左折,右折ができるようなマクロも用意する (\S,\B,\L,\R). さらに,\S,\B,\L,\Rを並べた命令列を受け取って連続した線を描くようなマクロpathを用意する.

最後に,ドラゴン曲線の再帰的な定義を使って\pathコマンドを使ってドラゴン曲線を描く.

縦線と横線の用意

\newdimen\lineLength
\newdimen\lineWidth
\newbox\vLine
\newbox\hLine

\lineLength=5pt
\lineWidth=0.3pt

\setbox\vLine=\hbox{\vrule height\lineLength width\lineWidth}
\setbox\hLine=\hbox{\vrule height\lineWidth width\lineLength}

\newdimen, \newboxというのはそれぞれレジスタを確保するための命令で,それぞれ寸法 (pt とか cm とか) を保存するレジスタ,ボックス (文字列を組版したまとまりを入れておく箱) を保存するレジスタを確保する.

線の長さ, 幅の適切な寸法をそれぞれ \lineLength, \lineWidth という名前で設定しておく.

設定した寸法を使って \vrule を使って線を描き,縦の線を \vLine, 横の線を \hLine というボックスに入れておく.

上下左右の移動

\newcount\dir
\newdimen\y

\def\goEast{\raise\y\copy\hLine \global\dir=0\relax}
\def\goNorth{\raise\y\copy\vLine \kern-\lineWidth \global\advance\y\lineLength \global\dir=1\relax}
\def\goWest{\kern-\lineLength \raise\y\copy\hLine \kern-\lineLength \global\dir=2\relax}
\def\goSouth{\global\advance\y-\lineLength \raise\y\copy\vLine \kern-\lineWidth \global\dir=3\relax}

\yというのは,現在のy座標を覚えておくためのレジスタである. 線を描く前に \raise\y として \y に入っている値ぶんだけ組版位置を上方向に上げておくことで上下位置の調整を行う.

x方向の調整は,文字の組版によって自動的にx座標が右に文字幅ぶんだけ動くことと,\kern という命令によって明示的に左右方向の位置を動かすことによって行う.

\dir はここまでの分ではなくてもかまわないのだが,現在の進行方向を入れておくためのレジスタで,次に進行方向に対する相対的な移動を実装するために使う.

進行方向に対する相対的な移動

\def\S{\ifcase\dir \goEast \or\goNorth \or\goWest \or\goSouth \fi} % move straight
\def\B{\ifcase\dir \goWest \or\goSouth \or\goEast \or\goNorth \fi} % move back
\def\L{\ifcase\dir \goNorth \or\goWest \or\goSouth \or\goEast \fi} % move left
\def\R{\ifcase\dir \goSouth \or\goEast \or\goNorth \or\goWest \fi} % move right

\def\path#1{\hbox{\dir=0\y=0pt#1}}

このステップは比較的単純で\ifcaseという命令を使って現在の進行方向\dirを参照して紙面での上下左右移動を選択するだけである.

\ifcaseについて簡単に説明しておくと,

\ifcase<number> <case0> \or<case1> \or<case2>... \else<other cases>\fi

という書式で,<number>の値が0なら<case0>を展開,1なら<case1>を展開... という具合に分岐し,どれにも当てはまらなければ <other cases> を展開する.

\pathは単にy座標と向きを初期化したあと渡された命令列を展開してできた組版結果をまとめるだけである.

ドラゴン曲線を描く

\newcount\n
\def\dragon{\ifnum\n>0{\advance\n-1 \dragon\L\nogard}\fi}
\def\nogard{\ifnum\n>0{\advance\n-1 \dragon\R\nogard}\fi}

\centerline{\path{\n=13 \dragon}}

いよいよ最後のステップであるドラゴン曲線の描画である. ドラゴン曲線は次数によって再帰的に定義されていて,

  • 最初 (n=1) はただの直線
  • n=k+1 の曲線は,n=k の曲線を描いたあと左に曲がり,逆向きに n=k の曲線を描いたもの

という手順で構成できる.

Wikipedia にアニメーションが置いてあって,とてもわかりやすい.

Dragon curve - Wikipedia

実装は素直に再帰的定義をなぞったものになっていて,\nを1減らして\dragonを描き,左に曲がって\nogard(\dragonの逆)を描く. ポイントとしては,\n を1減らす \advance\n-1 という命令の効果が {...} で囲んだグループに対してローカルになるところで,\dragonが展開されるたびにローカルに \n を更新することで再帰的な定義を再現できるようになっている.

ARC 140 感想・反省

atcoder.jp

結果

atcoder.jp

A1完 (64:23 + 2ペナ)

初めて実レート減少

最初に参加したARC(138)でも1完でひどいパフォを出し,今回はせめて2完したいと思っていたが撃沈 やっぱり同じ配点の問題でもABCよりARCのほうがずっと難しいと感じる. 苦手意識による思い込みなのか,問題傾向が苦手なのか,それともたまたま解けなかっただけなのか....

コード

github.com

終了後に実装を修正している

各問題の振り返り

A

文字列をできるだけ短い周期で繰り返すパターンに編集する問題

N \leq 2000の制約を見るに,O(N^ 2)ぐらいが目安かなと見積もる.

最初に考えたのは,周期について2分探索できないかという方針. しかし,これはある周期を達成できるならそれより長い周期はかならず達成できるという前提に基づいていて,正しくない.

2分探索はできないが,調べる周期のパターンを少なくしたいというモチベーションは悪くなさそうである. 周期としてありうる数がなんであるかということをもう少し考えてみると,Nの約数だけが周期となりうるということに気づく. 約数の数はそれほど大きくならないと考え,ひとつの周期に対する達成可能であるかの判定にO(N^ 2)で約数について全探索すれば解けるのではないかと考えてみる.

ある周期が達成可能かどうかをO(N^ 2)で調べる方法だが,周期の各位置にあたる文字を一番出現回数の多い文字に合わせるという作業を O(N)で行い,これを文字列の開始位置をずらしてすべて調べればよいだろうと考えた.(実際,文字列の開始位置をずらす作業は意味がない.計算量がO(N^ 2)で良いだろうという思い込みがあったことから無駄に気づけなかった.)

テストケースが通ったので提出してみるとWA. 見直してみると,周期内の各位置について調べるという部分が実は周期内の1点しか調べていないというミスをしていることに気づき,修正.

しかしこれを提出してみるとなぜかRE. よく見てみると,なぜか同時に開いていたB問題のほうに提出してしまっていた. 改めて提出し直すと,1ケースだけTLEになった.

なんとか速くならないかと見直してみるが,なぜか実際文字列の開始位置をずらす作業が無駄であることには気づかず. 代わりに,約数を全探索するのではなく,ある約数Mについてそれを周期とすることができないなら,Mの約数についても周期にすることはできないという点に気づいて修正し,なんとかACになった.

B

文字列に対して特定の操作を行うことができる回数の最大値を求める問題.

操作可能な箇所すべてについて順番をかえて再帰的に探索するのでは間に合いそうもないので,最適な操作順というものを考えてみる. 奇数回目の操作の後,操作箇所のまわりで新たにARCという文字列ができるのは,もともとがAARCCという並びになっていたときである. 偶数回目の操作の後,操作箇所のまわりで新たにARCという文字列ができることはない.

よって,AARCCというのような並びがある部分はできるだけ奇数回目に操作することにするのが最適になる.

最適な操作について,より具体的に考える.  A^ k R C^ kという並びを文字列の中からすべて探し,重複を含むkの集合(multiset)を考える. - 奇数回目の操作ではkが最も大きいものを選び,k\gt1であればkを1減らして集合に戻す.k=1であれば要素を取り除く. - 偶数回目の操作ではkが最も小さいものを選び,要素を取り除く. このようにして行える操作の回数を求めれば答えが求まる.

後は, A^ k R C^ kという並びを与えられた文字列から探すというサブ問題が解ければ良い.

この並びを探す部分について実装がごちゃごちゃになってしまい,原因はよくわからないがバグって通らなかった. コンテスト終了後,ランレングス圧縮をしてから並びを探すと比較的見通しが良いことに気づいて実装し直してみるとACできた.

Bまでは正答したかったが,残念.まあ実力不足だろう.

ABC251 E - Takahashi and Animals 解説

atcoder.jp

以下のN個の行動がある.

  • 行動1: 動物1と動物2A_1円で餌をあげる
  • 行動2: 動物2と動物3A_2円で餌をあげる

    \vdots

  • 行動N: 動物Nと動物1A_N円で餌をあげる

すべての動物に餌をあげるための最小コストを計算したい.

少し観察すると,次の特徴がわかる.

  • 動物iに餌をあげるためには,行動 i\mathord-1 か行動 i の少なくとも一方は行う必要がある.

したがって,まず動物1に対して行動1か行動Nのどちらかによって餌を与えるか決め,さらに動物2,3と順に餌を与える方法を決めていく動的計画法で解けそうとわかる.

  • dp[0] [j] : 行動 Nを使って1,\ldots,j番目の動物に餌を与えるための最小コスト
  • dp[1] [j] : 行動 Nを使わずに1,\ldots,j番目の動物に餌を与えるための最小コスト

と定める.

動物jに餌を与える方法は行動 j\mathord-1 か行動 jのいずれかであるから,

\displaystyle dp [i] [j] = \min \{ dp [i] [j-2] + A[j-1] ,\, dp[i] [j-1] + A[j] \}

によって求められる.

行動 0 を使っていた場合にはすでに動物 N には餌を与えているので, dp [0] [N-1]  dp [1] [N] の小さいほうが答えである.

実装例

github.com

文章の説明と添字がずれているのと,テーブルの更新順が若干違うことに注意.

ABC251 D - At Most 3 (Contestant ver.) 解説

atcoder.jp

数列をうまくつくることで,数列から3個以下の数を選んでW以下の任意の数をつくれるようにせよという問題

 Wが最大値10^ 6であるときに解となる数列さえ求めれば,この数列を使って10^ 6以下の任意の数がつくれるのでW \lt 10^ 6を満たす任意の Wに対する解にもなっていることがわかる. よって, W=10^ 6の場合の解を求めることに注力すれば良い.

与えられた数をいくつかの数の和に分解したいので,このために都合の良い表示を考えたい. このときに桁を分けて考えるというのが有効な考え方になる. 例えば,適当に2563という数を考えると,2563 = 2000 + 563 や,2563 = 2500 + 63 のように桁が独立している数どうしの足し算は考えやすい.

 10^ 6未満の数は10進で6桁の数として表せるので,2桁ずつに分解して各グループについて00から99まですべての数をつくれば,各グループから1つずつ数を選んで組み合わせることで6桁以下の任意の数を表現できる.(00は 0 であり,そのグループからは数を選ばないということによって表現できるので,明示的につくる必要はない)

最後に,1000000という数だけは7桁なのでこれだけ別に数列に加える. 以上で任意の数を構成できた.

実装例

github.com

備考

もちろん10進ではなく2進表示などでも原理的にはよいのだが,たとえば2進で10^ 6以下の数を表現しようとすると20桁いる. 7桁,7桁,6桁に分けて各グループについてすべての数をつくると,2^ 7 + 2^ 7 + 2^ 6 = 320程度の数が必要になるので制約を満たさない. 今回は上限が10^ 6という10進できりの良い数になっているので10進表示で考えるのが一番無駄がないということだろう.

ABC251 感想・反省

atcoder.jp

結果

atcoder.jp

ABCE4完 (69:09)

コード

github.com

各問題の振り返り

A

文字列を適当な回数繰り返し出力するだけの問題

簡単

1.5分消費

B

与えられた数列から3個以下を選んで和としてつくれる数の個数を数える問題

N\leq300と小さいので,O(N^ 3)の全探索で良さそうとわかる.

3個選ぶ全探索なので3重ループで書くのが基本だが,それだけだと1個や2個の場合がカバーできない. 少し考えて,仮想的に重さ0のおもりを2つ足して考えることで単一の3重ループで書けるようにした 解説にあるように1個や2個は別処理で書いたほうが素直だった気もする. A,B問題はあまりひねらず愚直に書いたほうが結果的に早く書けることが多いような.

8.5分消費

C

キー(文字列)が重複していない要素の中から最も高いスコアのものを選ぶ問題

文字列の重複判定を,それ以前に出現したすべての文字列と比較することによって行う愚直な解法だとO(N^ 2)でTLEなので,重複判定を高速化する必要がある.

重複判定をhashで行うことを考えたが,C++の hash tabel (unorderd_map) はあまり使い勝手がよくない.

重複判定は O(log N) でも十分間に合うのでset で十分ということに気づき,set を使って書いた.

8分消費

D

B問題の変種で,与えられた数以下の任意の数を3個以下の和としてつくれるような数列をひとつ求める問題

他の問題とは少 し異質で,Heuristic コンテストみたいな印象を受ける. 方針が浮かばないので小さいほうから詰めていったり,適当にO(2^ x)を詰めてみたり試してみるがうまくいかず. 途中でE問題に移行した.

コンテスト中には解法浮かばず. 解説を見て,解けなかったのは悔しいが面白い問題だと思った.

解説を書いた. https://sankantsu.hatenablog.com/entry/2022/05/15/021351

E

 N 個の頂点が円形につながっているグラフの最小点カバーを求める問題とみなせる.

ある頂点をカバーするためには,つながっている辺のどちらか1方はとる必要がある. このことを利用して,頂点1から頂点iまでをカバーするために必要な最小コストを順にDPで求める. 頂点1を選ぶときに行動1を使うか行動Nを使うかで場合分けすると良い.

60分消費 (D問題の試行錯誤もあるので,実質は30~40分ぐらい?)

解説を書いた. https://sankantsu.hatenablog.com/entry/2022/05/15/115203

F

ほぼ手をつけていない

ABC250 感想・反省

atcoder.jp

結果

atcoder.jp

ABCDE5完 (85:55 + 2ペナ)

コード

github.com

各問題の振り返り

A

隣接マス数を調べる問題

コンパクトに場合分けを書こうとして,行/列がひとつしかないような場合を見落としてし,修正に少し時間食ってしまう. 入出力例がそれなりにしっかりしていたのでWAは避けられたが,サンプル次第ではWA出てもおかしくなく危なかった. 絶対の自信があるわけじゃないなら,最初から愚直に書くほうが良いか.

サンプルが多く,入出力コピペにかかる時間もまあまあ消費していたような気がするので atcoder-tools の導入をするか,自作の同等のツールを改修するかしたい.

6分消費

B

チェス盤のような模様を描く問題

それほど問題なく書けたと思う.

5分消費

C

ボールの入れ替えをシミュレーションする問題

安直に書くとボールの入れ替え一回にO(N)かかるので,多少工夫が必要. 現在のボールの状態を並べた配列と,ボールの値から位置を調べる配列の2つを用意して管理することで解ける.

最初の提出で配列の範囲外アクセスを起こしてしまい,WA1回. 訂正したのはいいが,cerrへのデバッグ出力を消し忘れたまま提出していまいTLEでさらに+1ペナ. 間違い無く今回一番のやらかし.

配列はとりあえず何も考えずにmax+10ぐらいとっておいたほうが良いかも.

19分消費

D

特定の形に因数分解できる数の個数を調べる問題

3乗して10^ {18}以下にする必要があるので,10 ^6以下の素数について全探索すれば良さそうとわかる.

それほど問題なく書けたと思う. エラトステネスとかはライブラリ化しておくと時間削減できそうではあるが,実装練習という意味合いも考えて今はまだやらなくてもいいかなあと思っている.

9分消費

E

2つの数列の先頭を含む部分列に含まれる数の集合の一致判定をする問題

集合の一致判定にO(N)かかるナイーブな方法だとO(NQ)でTLEなのはすぐにわかる. 集合の一致判定をO(\log N)以下にしたいという発想.

A,Bの先頭x項に含まれる値の集合をSA_x,SB_xとする 先頭から順に要素を見ていったとき,すでに出現している要素がまた現れても集合としては要素は増えないので,新しい要素が出たときだけ注目すれば良いとわかる. A,B それぞれに対して新しい要素が出現するときの添字を計算した配列 v_A,v_B をつくってみる.

v_A,v_B を使うと集合のサイズの判定は定数時間で済むが,中身の一致判定はまだO(N)かかるので,これを削減したい. そこで,集合のサイズが同じになる場合に要素集合も同じかどうか事前計算しておけないか考えてみる.

一致判定のために集合の要素を全走査するとO(N)は避けられない. そこで,集合の要素が増えるタイミングで,いま増やした要素が差分に影響するかどうか考える. つまり, |SA_{x-1}| \lt |SA_x|, |SB_{y-1}| \lt |SB_y|, |SA_x| = |SA_y| を満たすようなx,yについて,a_x,b_yがそれぞれSB_y,SA_xに含まれるかどうかを考えることによって差分を管理する. この方法ならO(N \log N)で集合の一致判定まで含めた前処理が可能で,あとは1クエリあたりO(\log N)時間で処理できる.

時間はまあまあかかったが,水diff(diff 1421)なのでとりあえず解けただけで上等

55分消費

F

すぐに思いつくのは頂点ペア全探索のO(N^ 2) これだとTLEなので,探索するペアの数を減らせないか考える.

一個の頂点Aを固定してもう一方の頂点Bを動かしていったとき,囲む面積が1/4を超えたらもうそれ以上見る意味はない. そのタイミングでAを1個ずらしてまたBを動かしていくという感じのしゃくとり法でうまくできそうというところまでは思いつく.

三角形の面積は,外積を使ってうまく計算できる.

実装時間全然足りず,コンテスト終了

終了後に自力AC. Eまでを速く解けるようにすることで,そのうち6完も狙っていきたい.