LoginSignup
9
1

More than 1 year has passed since last update.

@Mopepe51(雪下)

AtCoderに登録したら解くべき精選過去問10をLaTeX(expl3)で解いてみた

Last updated at Posted at 2021-12-16

まえがき

本記事は TeX ＆ LaTeX Advent Calendar 2021 12日目の記事です．11日目はhilsshさん，13日目は h-kitagawa さんです．
期日を1週間勘違いしていたため大幅に遅刻してしまいました．申し訳ありません．
ひとまず全解法が出来た段階で公開しますが，コードの具体的な解説等はまたいずれ追記します．

AtCoder Beginners Selection の問題1をexpl3で解いていきたいと思います．
以前，同様の企画をplain TeXで行いましたが，plain TeX と expl3 ではコードの見た目も書き味もかなり異なります．
plain TeX 見比べて大きく可読性の向上した expl3 を実感してもらえればと思います．

2021/12/16: 公開
2021/12/25: 説明追記

expl3とは

TeXがチューリング完全であることは有名な事実ですが，実際にTeXでプログラミングを行うと非常にしんどいことは以前の記事にも記しました．
解決の一つにluaLaTeXのようにプログラミング部分を外部言語に任せるという手もありますが，expl3はLaTeX上で完結し，（TeX言語をそのまま書くことと比べれば）書きやすく設計されたプログラミング言語です．

LaTeXで行う組版処理をマークアップ・レイアウト設計・プログラミングの3階層に分離しようというLaTeX3のプロジェクトの中でプログラミング言語を担当するのがexpl3です．
素のTeX言語と比べ，関数のモジュール化や明確な命名規則により可読性の向上が図られており，またスペースの有無による難解な挙動の変化や展開制御の煩雑さを解決し，かなりプログラミング言語らしいプログラミング言語に近づいています．

基本文法はワトソン (wtsnjp) さんのTeX Conf2017での発表資料「expl3入門」 (https://blog.wtsnjp.com/2017/10/29/intro-expl3/) や「TeX 言語者のための expl3 入門」がわかりやすいと思います．
その他詳細は公式ドキュメント The LaTeX3 Interfaces (interface3.pdf) に事細かに記載されています．

普通のTeX/LaTeXとの見た目上の大きな違いは制御綴に_や:が使われることでしょう．
変数は\<スコープ>_<パッケージ名>_<変数名>_<型名>， 関数は\<パッケージ名>_<関数名>:<引数指定子>..という命名規則が定められています．
例えば，ファイルから入力を読み取って変数に格納する関数\ior_str_get_term:nN ⟨prompt⟩ ⟨token list variable⟩ は\ior_str_get_term:nNまでが制御綴です．
引数指定子とは引数の数とその形を指定するもので，

  • n: 普通のトークン列
  • N: 単一トークン
  • T/N: if式における真/偽の場合の値
  • v/V: 引数(トークン列/単一トークン)を展開した形で使用する
  • ……

などがあります．

また，"空白"はコード上ですべて無視されます．明示的に空白を扱いたいときは~や定数\c_space_tlなどを使用します．

変数の型には以下のようなものがあります．

  • tl: トークンリスト
  • str: 文字列(空白などの扱いが違う)
  • int: 数値
  • bool: boolean
  • seq: map操作やstack操作に適したデータ構造

etc...

処理系

TeX Live 2021 for Windows でインストールされた LaTeX を使用しています．

tlmgr revision 60693 (2021-10-04 04:24:25 +0200)
tlmgr using installation: C:/texlive/2021
TeX Live (https://tug.org/texlive) version 2021

pdfTeX 3.141592653-2.6-1.40.23 (TeX Live 2021/W32TeX)
kpathsea version 6.3.3
Copyright 2021 Han The Thanh (pdfTeX) et al.
There is NO warranty.  Redistribution of this software is
covered by the terms of both the pdfTeX copyright and
the Lesser GNU General Public License.
For more information about these matters, see the file
named COPYING and the pdfTeX source.
Primary author of pdfTeX: Han The Thanh (pdfTeX) et al.
Compiled with libpng 1.6.37; using libpng 1.6.37
Compiled with zlib 1.2.11; using zlib 1.2.11
Compiled with xpdf version 4.03

expl3は活発に開発が進められているため，古いバージョンだと使っている関数の一部が未定義だったりします．
コードは

template.tex
\documentclass{article}
\usepackage{expl3}
\begin{document}
\ExplSyntaxOn

% ここにコードを書く
\iow_term:x { Hello,~world! }

\ExplSyntaxOff
\end{document}

のようなテンプレートで記述します．
\ExplSyntaxOnと\ExplSyntaxOffの間に書かれた記述がexpl3のコードとして解釈されます．
以下の解法説明ではこの部分の記述だけを掲載します．

実行する際は

>latex answer.tex

とすると

This is pdfTeX, Version 3.141592653-2.6-1.40.23 (TeX Live 2021/W32TeX) (preloaded format=latex)
 restricted \write18 enabled.
entering extended mode
(./answer.tex
LaTeX2e <2021-11-15> patch level 1
L3 programming layer <2021-11-22>
(c:/texlive/2021/texmf-dist/tex/latex/base/article.cls
Document Class: article 2021/10/04 v1.4n Standard LaTeX document class
(c:/texlive/2021/texmf-dist/tex/latex/base/size10.clo))
(c:/texlive/2021/texmf-dist/tex/latex/l3kernel/expl3.sty
(c:/texlive/2021/texmf-dist/tex/latex/l3backend/l3backend-dvips.def))
(./answer.aux)<標準出力>
(./answer.aux) )
No pages of output.
Transcript written on expl3_4.log.

のような出力が得られます．
解答による標準出力の前後のログ出力はどうも抑制することはできないようです（ https://hak7a3.hatenablog.com/entry/2015/10/06/221727 ）．

実行時間の計測はWSLのtimeコマンドを利用して

>wsl time latex.exe answer.tex < test_input.txt

とすれば

real    0m1.292s
user    0m0.000s
sys     0m0.016s

のような形でできます．

解法

0. practice contest A - Welcome to AtCoder 

% 1行目を読み込み
\tl_new:N \l__A_tl
\ior_get_term:nN {} \l__A_tl

% 2行目をstrで読み込み
\ior_str_get_term:nN {} \l_tmpa_str
% strを空白splitしてseqに格納
\seq_set_split:NnV \l_tmpa_seq { ~ } \l_tmpa_str
% seqから要素をpop
\tl_new:N \l__B_tl
\tl_new:N \l__C_tl
\seq_pop_left:NN \l_tmpa_seq \l__B_tl
\seq_pop_left:NN \l_tmpa_seq \l__C_tl

% 3行目を読み込み
\tl_new:N \l__S_tl
\ior_get_term:nN {} \l__S_tl

% $"{A + B + C} {S}" を出力
\iow_term:x { \int_eval:n {\l__A_tl + \l__B_tl + \l__C_tl} ~ \l__S_tl}

プリミティブの型には\l_tmpa_<type>, \l_tmpb_<type>などの変数が定義されており，ユーザーが定義しなくても一時変数として使用することが出来ます．

  • \tl_new:N ⟨変数名⟩
    新たな token list 変数を定義する．
    tl部分がstr,intなどパッケージによって違うものが型ごとに定義されている．
  • \ior_get_term:nN ⟨prompt⟩ ⟨tl 変数⟩
    ターミナル入力から ⟨tl 変数⟩ に文字列を代入
  • \ior_str_get_term:nN ⟨prompt⟩ ⟨str 変数⟩
    標準入力を文字列strとして取得
  • \iow_term:x {⟨tokens⟩}
    token列をターミナルに標準出力
  • \seq_set_split:Nnn ⟨seq 変数⟩ {⟨delimiter⟩} {⟨token list⟩}
    文字列をdelimiterで分割した結果をseq変数に代入
  • \seq_pop_left:NN ⟨seq 変数⟩ ⟨tl 変数⟩
    seq変数から要素をpopしてtoken list 変数に代入
  • \int_eval:n {⟨integer expression⟩}
    token列を数式表現として解釈して計算する

1. ABC 086 A - Product 

% 1行目をstrで読み込み
\ior_str_get_term:nN {} \l_tmpa_str
% strを空白splitしてseqに格納
\seq_set_split:NnV \l_tmpa_seq { ~ } \l_tmpa_str
% seqから要素をpop
\tl_new:N \l__A_tl
\tl_new:N \l__B_tl
\seq_pop_left:NN \l_tmpa_seq \l__A_tl
\seq_pop_left:NN \l_tmpa_seq \l__B_tl

% (A * B is even)? "Even": "Odd" を出力
\iow_term:x {
    \int_if_even:nTF {
        % 条件節: A * B がeven
        \l__A_tl * \l__B_tl
    }{
        Even % 真のとき
    }{
        Odd % 偽のとき
    }
}

if文は
⟨if関数⟩ ⟨if関数の引数⟩ ⟨true code⟩ \else: ⟨false code⟩ \fi:
の形式で⟨true code⟩と⟨false code⟩に分岐できる他，引数にTFが付加されたif関数が定義されており，
⟨if関数(TF付き)⟩ ⟨if関数の引数⟩ {⟨true code⟩} {⟨false code⟩}
のようにif式として使うことも出来ます．map処理など結果をそのまま次の関数の引数に使うことが多いのでこちらの形式が便利です．

上のコードでは\int_if_even:nTFという偶数判定用のif式を使っていますが，数値を比較する\if_int_compare:wを使ってif文の形式で書くことも可能です．

\if_int_compare:w \int_eval:n { \int_mod:nn{ \l__A_tl * \l__B_tl } { 2 } } = 0
    \iow_term:x { Even }
\else:
    \iow_term:x { Odd }
\fi:
  • \int_if_even:nTF {⟨数式表現⟩} ⟨true節⟩ ⟨false節⟩
    数式表現を計算した結果が偶数ならtrue節，奇数ならfalse節を返す
  • \if_int_compare:w ⟨数値1⟩ ⟨比較演算子⟩ ⟨数値2⟩ ⟨true節⟩ \else: ⟨false節⟩ \fi:
    >,<,= で数値を比較して条件分岐
  • \int_mod:nn {⟨数値1⟩} {⟨数値2⟩}
    数値1 ％ 数値2 を計算

2. ABC 081 A - Placing Marbles 

% 1行目を token list で読み込み
\tl_new:N \l__S_tl
\ior_str_get_term:nN {} \l__S_tl

% S の中の 1 の数を数える
\int_new:N \l__result_int
\int_set:Nn \l__result_int { 0 }
% token list `\l__S_tl` の内容に対し for-each する
\tl_map_inline:Nn \l__S_tl {
    \int_add:Nn \l__result_int {
        % (#1 == 1)? 1: 0
        \int_compare:nNnTF { #1 } = { 1 } { 1 } { 0 }
    }
    %\int_add:Nn \l__result_int { #1 }
}
\iow_term:x { \int_eval:n{ \l__result_int } }

map 系の関数でfor-each操作ができます．\hoge_map_functionでは第2引数に関数オブジェクトを，\hoge_map_inlineでは inline function （引数を#1とした無名関数）を書くことができます．
Kotlinのitを使ってパラメータ名定義を省略した無名関数と似ていますね．

上の解では愚直に「要素が1なら答えを1，そうでないなら0増やす」という操作をしていますが，制約的に入力は0か１しか無いので（コメントアウト行のように）直接#1を足すだけで良いです．

  • \int_set:Nn ⟨int変数⟩ {⟨数値⟩}
    変数に値を代入
  • \int_add:Nn ⟨int変数⟩ {⟨数値⟩}
    変数に数値を足す
  • \int_compare:nNnTF {⟨数値1⟩} ⟨比較演算子⟩ {⟨数値2⟩} {⟨true節⟩} {⟨false節⟩}
    \if_int_compare:w文の式バージョン
  • \tl_map_inline:Nn ⟨tl変数⟩ {⟨inline function⟩}
    tl変数の要素を#1に展開しながらfunctionを適用する

3. ABC 081 B - Shift Only 

% 1行目をstrで読み込み
\tl_new:N \l__N_tl
\ior_str_get_term:nN {} \l__N_tl
% 2行目をtlで読み込み，空白でsplit
\ior_str_get_term:nN {} \l_tmpa_tl
\seq_new:N \l__A_seq
\seq_set_split:NnV \l__A_seq { ~ } \l_tmpa_tl

% すべての要素が2で割れる回数を求める
\int_new:N \l__shift_count_int
\int_set:Nn \l__shift_count_int { 0 }
\bool_new:N \l__all_even_flag_bool
\bool_set_true:N \l__all_even_flag_bool
% すべての変数が2で割れる間ループする
\bool_do_while:Nn \l__all_even_flag_bool {
    % すべてのAの要素が2で割れるかを確認，そうなら2で割った商をAに格納
    \seq_clear:N \l_tmpb_seq
    \seq_map_inline:Nn \l__A_seq {
        \int_if_odd:nTF { #1 } {
            \bool_set_false:N \l__all_even_flag_bool
        }{
            \seq_push:NV \l_tmpb_seq { \int_div_round:nn { #1 } { 2 } }
        }
    }
    \seq_set_eq:NN \l__A_seq \l_tmpb_seq
    \bool_if:NTF \l__all_even_flag_bool {
        % フラグが真なら答えを1増やす
        \int_incr:N \l__shift_count_int
    }{
    }
    % フラグが偽なら終了
}
\iow_term:x { \int_eval:n{ \l__shift_count_int } }
  • \bool_do_while:Nn ⟨bool変数⟩ {⟨code⟩}
    bool変数が真である間 codeを繰り返し実行する
  • \seq_clear:N ⟨seq変数⟩
    seq変数を空にする
  • \seq_push:Nn ⟨seq変数⟩ {⟨要素⟩}
    seq変数に要素を追加する．
    引数指定子を\seq_push:NVと変更することで計算式を評価した結果をpushするようにできる
  • \seq_set_eq:NN ⟨seq変数1⟩ ⟨seq変数2⟩
    seq変数2をseq変数1にコピーする
  • \int_div_round:nn {⟨数式表現1⟩} {⟨数式表現2⟩}
    (数式表現1)÷(数式表現2)を"最も近い整数"に丸めた値を返す
    切り捨てではないので注意
  • \int_incr:N ⟨int変数⟩
    int変数に1足す

4. ABC 087 B - Coins 

% 入力をtlで読み込み
\tl_new:N \l__A_tl
\tl_new:N \l__B_tl
\tl_new:N \l__C_tl
\tl_new:N \l__X_tl
\ior_str_get_term:nN {} \l__A_tl
\ior_str_get_term:nN {} \l__B_tl
\ior_str_get_term:nN {} \l__C_tl
\ior_str_get_term:nN {} \l__X_tl

\int_new:N \l__result_int
\int_set:Nn \l__result_int { 0 }
% 0<=a<=A, 0<=b<=B, 0<=c<=C の3重ループ
\int_new:N \l__a_counter_int
\int_new:N \l__b_counter_int
\int_new:N \l__c_counter_int
\int_set:Nn \l__a_counter_int { 0 }
\int_do_while:nn { \l__a_counter_int <= \l__A_tl } {
    \int_set:Nn \l__b_counter_int { 0 }
    \int_do_while:nn { \l__b_counter_int <= \l__B_tl } {
        \int_set:Nn \l__c_counter_int { 0 }
        \int_do_while:nn { \l__c_counter_int <= \l__C_tl } {
            \int_add:Nn \l__result_int {
                % 500a+100b+50c=X なら1を，そうでなければ0をresultに足す 
                \int_compare:nNnTF {
                     \l__a_counter_int * 500 + \l__b_counter_int * 100 + \l__c_counter_int * 50
                } = { \l__X_tl } { 1 } { 0 }
            }
            \int_incr:N \l__c_counter_int
        }
        \int_incr:N \l__b_counter_int
    }
    \int_incr:N \l__a_counter_int
}
\iow_term:x { \int_eval:n{ \l__result_int } }

inline functionを使うfor-eachループはパラメータ変数#1が被ってしまうためネストできません．
そのため条件文を使った普通のfor文を使います．

  • \int_do_while:nn {⟨(不)等式表現⟩} {⟨code⟩}
    等号，不等号を含む式を評価した結果がtrueの間ループする

5. ABC 083 B - Some Sums 

% N,A,Bを読み込み
\tl_new:N \l__N_tl
\tl_new:N \l__A_tl
\tl_new:N \l__B_tl
\ior_str_get_term:nN {} \l_tmpa_str
\seq_set_split:NnV \l_tmpa_seq { ~ } \l_tmpa_str
\seq_pop_left:NN \l_tmpa_seq \l__N_tl
\seq_pop_left:NN \l_tmpa_seq \l__A_tl
\seq_pop_left:NN \l_tmpa_seq \l__B_tl

\int_new:N \l__result_int
\int_set:Nn \l__result_int { 0 }

\int_new:N \l__n_counter_int
\int_new:N \l__digit_sum_int
\int_set:Nn \l__n_counter_int { 1 }
\int_do_while:nn { \l__n_counter_int <= \l__N_tl } {
    % int を token list にキャスト
    \tl_set:NV \l_tmpa_tl \l__n_counter_int
    \int_set:Nn \l__digit_sum_int { 0 }
    \tl_map_inline:Nn \l_tmpa_tl {
        \int_add:Nn \l__digit_sum_int { #1 }
    }
    \bool_if:nTF { \int_compare_p:n { \l__A_tl <= \l__digit_sum_int <= \l__B_tl} }{
        \int_add:Nn \l__result_int { \l__n_counter_int }
    }{
        %\iow_term:x { { \int_use:N \l__n_counter_int} ~ {\int_use:N \l_tmpa_int} }
    }

    \int_incr:N \l__n_counter_int
}
\iow_term:x { \int_use:N \l__result_int}

関数の結果を展開して別の関数の引数に使う，という操作をするには元の関数が副作用なしの関数である必要がある（参考：expl3な言語で完全展開可能な関数（マクロ）を作る件について (1)）のですが，このようなコードを書くには筆者の技量が足りない（具体的にはデータ列の sum を取る操作でfor文でカウントしていく（代入操作がある）以外の方法がわからない）のですべてベタ書きしています．

tlやstrなどを条件比較文などでintとして演算するときはevalがかかっているため明示的にキャストする必要はありませんが，intからtlにキャストする際は明示的操作が必要となります．
\tl_set:NV \l_tmpa_tl \l__n_counter_int で \l_tmpa_tl に代入する際，引数指定子がVになっているので\l__n_counter_intはトークン列に展開されてからtlに代入されます．

6. ABC 088 B - Card Game for Two 

% 入力を読み込み
\tl_new:N \l__N_tl
\ior_get_term:nN {} \l__N_tl
\seq_new:N \l__A_seq
\ior_str_get_term:nN {} \l_tmpa_str
\seq_set_split:NnV \l__A_seq { ~ } \l_tmpa_str
% 降順にソート
\seq_sort:Nn \l__A_seq {
    \int_compare:nNnTF { #1 } < { #2 }{ \sort_return_swapped: }{ \sort_return_same: }
}

% 交互にAlice, Bobに点を足す
\int_new:N \l__alice_counter_int
\int_new:N \l__bob_counter_int
\int_set:Nn \l__alice_counter_int { 0 }
\int_set:Nn \l__bob_counter_int { 0 }
\bool_new:N \l__alice_or_bob_bool
\bool_set_true:N \l__alice_or_bob_bool
\bool_do_until:nn {\seq_if_empty_p:N \l__A_seq} {
    \seq_pop:NN \l__A_seq \l_tmpa_tl
    \bool_if:NTF \l__alice_or_bob_bool {
        \int_add:Nn \l__alice_counter_int {\l_tmpa_tl}
    }{
        \int_add:Nn \l__bob_counter_int {\l_tmpa_tl}
    }
    \bool_set_inverse:N \l__alice_or_bob_bool

}
\iow_term:x { \int_eval:n {\l__alice_counter_int - \l__bob_counter_int } }
  • \bool_do_until:nn {⟨真偽式⟩} {⟨code⟩}
    ～whileと逆に真偽式が真になるまで（偽である間）ループする
  • \bool_set_inverse:N ⟨bool変数⟩
    bool変数の真偽を反転する

7. ABC 085 B - Kagami Mochi 

% 入力を読み込み
\tl_new:N \l__N_tl
\ior_get_term:nN {} \l__N_tl
\seq_new:N \l__D_seq
\int_step_inline:nn { \l__N_tl } {
    \ior_get_term:nN {} \l_tmpa_tl
    \seq_push:NV \l__D_seq \l_tmpa_tl
}

% 重複を除去
\seq_remove_duplicates:N \l__D_seq
% 要素の個数を出力
\int_set:Nn \l_tmpa_int { \seq_count:N \l__D_seq }
\iow_term:x { \int_use:N \l_tmpa_int }
  • \seq_remove_duplicates:N ⟨seq変数⟩
    seq変数から重複要素を削除する

8. ABC 085 C - Otoshidama 

% 入力を読み込み
\ior_str_get_term:nN {} \l_tmpa_str
\seq_set_split:NnV \l_tmpa_seq { ~ } \l_tmpa_str
\tl_new:N \l__N_tl
\tl_new:N \l__Y_tl
\seq_pop_left:NN \l_tmpa_seq \l__N_tl
\seq_pop_left:NN \l_tmpa_seq \l__Y_tl

\int_new:N \l__result_a_int
\int_new:N \l__result_b_int
\int_new:N \l__result_c_int
\int_set:Nn \l__result_a_int {-1}
\int_set:Nn \l__result_b_int {-1}
\int_set:Nn \l__result_c_int {-1}

% 2重ループ
\int_new:N \l__IOOOO_counter_int
\int_new:N \l__SOOO_counter_int
\int_set:Nn \l__IOOOO_counter_int { 0 }
\bool_do_while:nn {
        \int_compare_p:n{ \l__IOOOO_counter_int <= \l__N_tl }
        && \int_compare_p:n{ \l__IOOOO_counter_int * 10000 <= \l__Y_tl }
        } {
    \int_set:Nn \l__SOOO_counter_int { 0 }
    \bool_do_while:nn {
            \int_compare_p:n{ \l__IOOOO_counter_int + \l__SOOO_counter_int <= \l__N_tl }
            && \int_compare_p:n{ \l__IOOOO_counter_int * 10000 + \l__SOOO_counter_int * 5000 <= \l__Y_tl } 
            } {
        \int_set:Nn \l_tmpa_int {\l__N_tl - \l__IOOOO_counter_int - \l__SOOO_counter_int}
        \int_compare:nNnTF 
            {10000 * \l__IOOOO_counter_int + 5000 * \l__SOOO_counter_int + 1000* \l_tmpa_int} = {\l__Y_tl}
        {
            \int_set_eq:NN \l__result_a_int \l__IOOOO_counter_int
            \int_set_eq:NN \l__result_b_int \l__SOOO_counter_int
            \int_set_eq:NN \l__result_c_int \l_tmpa_int
        }{
        }
        \int_incr:N \l__SOOO_counter_int
    }
    \int_incr:N \l__IOOOO_counter_int
}

\iow_term:x { \int_use:N \l__result_a_int \c_space_tl \int_use:N \l__result_b_int \c_space_tl \int_use:N \l__result_c_int }

これはちゃんと時間計算量 $O(N^2)$ の解法になっているはずなのですがが，最悪ケース（$N=2000, Y=20000000$）で30秒以上もかかってしまいます2．

特に2重のwhile文が遅いらしく，ループの1つをforループに変更すると4.5秒くらいまでは縮まるのですが，やはり制約を超過してしまいます．

内部ループをfor文に変えたパターン
\int_new:N \l__IOOOO_counter_int
\int_set:Nn \l__IOOOO_counter_int { 0 }
\bool_do_while:nn {
        \int_compare_p:n{ \l__IOOOO_counter_int <= \l__N_tl }
        && \int_compare_p:n{ \l__IOOOO_counter_int * 10 <= \l__y_int }
    } { 
    \int_step_inline:nnn { 0 } { \l__N_tl - \l__IOOOO_counter_int } {
        \int_set:Nn \l_tmpa_int { \l__N_tl - \l__IOOOO_counter_int - #1}
        \int_compare:nNnTF { 10 * \l__IOOOO_counter_int + 5 * #1 + \l_tmpa_int - \l__y_int } = { 0 } {
            \int_set_eq:NN \l__result_a_int \l__IOOOO_counter_int
            \int_set_eq:NN \l__result_b_int #1
            \int_set_eq:NN \l__result_c_int \l_tmpa_int
        } {
        }
    }
    \int_incr:N \l__IOOOO_counter_int
}

よって， $O(1)$ の解法で解きます．
解法の内容は ABC085 C - Otoshidama O(1)解法 を参照．
切り捨て/切り上げ除算が必要なのですが，実装されているのは四捨五入\int_div_round:nnと0への丸め\int_div_truncate:nnだけなので$\pm \infty$ への丸めを行う int_div_floor:nn/int_div_ceil:nn を実装します．

\cs_new:Npn \int_div_floor:nn #1 #2 {
    \int_compare:nNnTF { #1 } < { #2 }{
        \int_div_truncate:nn { #1 } { #2 } + \int_compare:nNnTF { \int_mod:nn { #1 } { #2 } } = { 0 } {
            0
        } {
            -1
        }
    } {
        \int_div_truncate:nn { #1 } { #2 }
    }
}
\cs_new:Npn \int_div_ceil:nn #1 #2 {
    \int_compare:nNnTF { #1 } < { #2 }{
        \int_div_truncate:nn { #1 } { #2 }
    } {
        \int_div_truncate:nn { #1 } { #2 } + \int_compare:nNnTF { \int_mod:nn { #1 } { #2 } } = { 0 } {
            0
        } {
            1
        }
    }
}

% 入力を読み込み
\ior_str_get_term:nN {} \l_tmpa_str
\seq_set_split:NnV \l_tmpa_seq { ~ } \l_tmpa_str
\tl_new:N \l__N_tl
\tl_new:N \l__Y_tl
\seq_pop_left:NN \l_tmpa_seq \l__N_tl
\seq_pop_left:NN \l_tmpa_seq \l__Y_tl

\int_set:Nn \l_tmpb_int { \int_div_floor:nn { \l__Y_tl - 1000 * \l__N_tl } { 1000 } }
\int_set:Nn \l_tmpa_int { \int_mod:nn { \l_tmpb_int } { 4 } }
\int_set:Nn \l_tmpb_int { \int_div_floor:nn { \l_tmpb_int - 9 * \l_tmpa_int } { 4 } }

\int_new:N \l__k_min_int
\int_new:N \l__k_max_int
\int_set:Nn \l__k_min_int { \int_max:nn
    { \int_div_ceil:nn { -1 * \l_tmpa_int } { 4 } }
    { \int_div_ceil:nn { \l_tmpa_int + \l_tmpb_int - \l__N_tl } { 5 } } }
\int_set:Nn \l__k_max_int { \int_div_floor:nn { \l_tmpb_int } { 9 } }

\iow_term:x { \int_compare:nNnTF { \l__k_min_int } < { \l__k_max_int + 1 } {
        \int_eval:n {4 * \l__k_min_int + \l_tmpa_int}
        \c_space_tl
        \int_eval:n { -9 * \l__k_min_int + \l_tmpb_int }
        \c_space_tl
        \int_eval:n { \l__N_tl - 4 * \l__k_min_int - \l_tmpa_int + 9 * \l__k_min_int - \l_tmpb_int }
    } {
        -1~-1~-1
    }
}

これで0.5秒ほどで解けるようになりました．

  • \int_step_inline:nnnn {⟨初期値⟩} {⟨step⟩} {⟨終値⟩} {⟨code⟩}
    初期値から終値までstep間隔で繰り返す．
    step=1を省いた\int_step_inline:nnn，初期値=1,step=1を省いた\int_step_inline:nnのバリエーションがある
  • \cs_new:Npn ⟨関数名⟩ ⟨パラメータトークン⟩ {⟨処理内容⟩}
    関数(control sequence)を定義
  • \c_space_tl
    空白文字を表す定数
    \iow_term:x内で制御綴と~を含んだ表現を出力しようとすると2つ目以降の~が無視されるというよくわからない挙動をするが，これだと期待通りの動作をする．仕組みはよくわかんない

9. ABC 049 C - Daydream 

% 文字列を読み取り
\str_new:N \__input_str
\ior_str_get_term:nN {}{\__input_str}

% 置換
\regex_replace_all:nnN { eraser }  { ! } \__input_str
\regex_replace_all:nnN { erase }   { ! } \__input_str
\regex_replace_all:nnN { dreamer } { ! } \__input_str
\regex_replace_all:nnN { dream }   { ! } \__input_str
\regex_replace_all:nnN { ! } {} \__input_str

% 空文字列ならYES, そうでなければNOを出力
\iow_term:x { \str_if_empty:NTF { \__input_str }{ YES }{ NO } }

この問題はTeXのコードと比べると劇的にわかりやすくなって感動的です．
「空文字列に dream dreamer erase eraser のいずれかを追加してできる文字列かどうか」を判定する問題ですが，この問題は eraser→erase→dreamer→dream の順で置換し，すべてマッチするか確認することで解くことができます．
置換のための関数が用意されているので，そのまま記述すれば終わりです．

  • \regex_replace_all:nnN ⟨正規表現⟩ ⟨置換⟩ ⟨tl変数⟩
    ⟨tl変数⟩を正規表現で置換

10. ABC 086 C - Traveling 

% 入力を読み込み
\tl_new:N \l__N_tl
\ior_get_term:nN {} \l__N_tl
\seq_new:N \l__T_seq
\seq_new:N \l__X_seq
\seq_new:N \l__Y_seq
\int_step_inline:nn { \l__N_tl } {
    \ior_str_get_term:nN {} \l_tmpa_str
    \seq_set_split:NnV \l_tmpa_seq { ~ } \l_tmpa_str
    \seq_pop_left:NN \l_tmpa_seq \l_tmpa_tl
    \seq_push:NV \l__T_seq \l_tmpa_tl
    \seq_pop_left:NN \l_tmpa_seq \l_tmpa_tl
    \seq_push:NV \l__X_seq \l_tmpa_tl
    \seq_pop_left:NN \l_tmpa_seq \l_tmpa_tl
    \seq_push:NV \l__Y_seq \l_tmpa_tl
}

\tl_new:N \l__pre_t_tl
\tl_new:N \l__pre_x_tl
\tl_new:N \l__pre_y_tl
\tl_new:N \l__now_t_tl
\tl_new:N \l__now_x_tl
\tl_new:N \l__now_y_tl
\tl_set:Nn \l__pre_t_tl { 0 }
\tl_set:Nn \l__pre_x_tl { 0 }
\tl_set:Nn \l__pre_y_tl { 0 }
\bool_new:N \l__result_bool
\bool_set_true:N \l__result_bool
\bool_do_until:nn {\seq_if_empty_p:N \l__T_seq} {
    \seq_pop_right:NN \l__T_seq \l__now_t_tl
    \seq_pop_right:NN \l__X_seq \l__now_x_tl
    \seq_pop_right:NN \l__Y_seq \l__now_y_tl
    % |Δx|+|Δy|<=Δt かつ (Δx+Δy+Δt)%2==0 ならOK
    \bool_if:nTF{
            \int_compare_p:nNn{
                \int_abs:n {\l__now_x_tl - \l__pre_x_tl} + \int_abs:n {\l__now_y_tl - \l__pre_y_tl}
            } < {
                \l__now_t_tl - \l__pre_t_tl + 1
            } && \int_compare_p:nNn{
                \int_mod:nn {\l__now_x_tl - \l__pre_x_tl + \l__now_y_tl - \l__pre_y_tl + \l__now_t_tl - \l__pre_t_tl} { 2 }
            } = {
                 0
            }
    } {
        % pass
    } {
        \bool_set_false:N \l__result_bool
    }
    \tl_set_eq:NN \l__pre_t_tl \l__now_t_tl
    \tl_set_eq:NN \l__pre_x_tl \l__now_x_tl
    \tl_set_eq:NN \l__pre_y_tl \l__now_y_tl
}

\iow_term:x { \bool_if:NTF \l__result_bool {Yes} {No} }
  • \bool_set_true:N ⟨bool変数⟩
    他の型のset関数と違い1引数でtrue/false用の関数が用意されています．
  • \bool_if:nTF {⟨真偽値⟩} {⟨true節⟩} {⟨false節⟩}
    複数の条件をbool演算するときは～_pという真偽値を返す条件式のbool演算を使います．

あとがき

TeX言語で解いたしんどさを思うとかなり楽に書くことが出来ました．
公式ドキュメントがしっかりしていて命名規則がわかりやすいため，新しい機能を探すのが（比較的）簡単3というのも大きいです．

プログラミングをするあたり初歩的に必要な機能は一通り触れられたと思うので，本記事が expl3 の入門の足がかりになれば幸いです．
今回使った関数を足がかりに The LaTeX3 Interfaces から必要な関数を探していくといいと思います．

解答コードは GitHub で公開しています（ https://github.com/Yukishita26/abs-solve/tree/master/LaTeX(expl3)/source ）．

  1. AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～(@drken さん) にて紹介されている過去問題 ↩

  2. マイナー 言語で 解こうとするといつもこの問題で引っかかってしまいますね．多重ループは鬼門です． ↩

  3. 当然全部英語なので英弱の私には辛いものがありましたが． ↩

9
1
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
9
1