More than 5 years have passed since last update.

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

Last updated at 2019-10-09Posted at 2019-06-08

注意事項

$\rm\TeX$は2019年6月9日現在，AtCoderのジャッジシステムには含まれていません．手元の処理系で動作を確認しています．
~~11問中 6 8問しか解けていません．今後随時追加の予定．~~ 東大TeX愛好会@ut_tex_clubさんからの情報提供により全問解決できました．感謝です．

更新履歴

2019/06/08 #0, #1, #2, #4, #5, #8 公開
2019/06/09 #3, #6 追加
2019/06/25 ログ出力に関する情報について追記
2019/09/26 東大TeX愛好会@ut_tex_clubさんからの情報提供により #7, #9, #10を追加

まえがき

$\rm\TeX$はプログラミング言語．ならば競プロするしかない．
ということで解いてみました．

競プロ入門といえばおなじみの @drken さんの記事，AtCoder に登録したら次にやること～これだけ解けば十分闘える！過去問精選 10 問～ で紹介されている10問+チュートリアル1問を $\rm\TeX$で解いていきます．

もちろんAtCoderでジャッジすることは出来ないため手元で動作確認をしています．

実行環境はWindows 10，TeXLiveのtex.exe (Version 3.14159265 (TeX Live 2018/W32TeX))を使用．

$ tex source.tex < in.txt > out.txt

の形で実行．ただしこの実行方法では$\rm\TeX$の起動・終了時のログが出てしまうのが消せない（やり方わかる方，情報をお寄せいただけると嬉しいです）ため，以下提示する出力結果や正誤判定はこの部分を無視することとします．

2019/06/25 追記
起動・終了時のログについてコメントにて情報をいただきました．
どうやらこのログは抑制することは出来ないようです．
http://hak7a3.hatenablog.com/entry/2015/10/06/221727

実行例

This is TeX, Version 3.14159265 (TeX Live 2018/W32TeX) (preloaded format=tex)
(./source.texHello, world!
 )
No pages of output.
Transcript written on source.log.

実行速度が気になるものはWindows Subsystem for Linux(WSL)を経由してtimeコマンドで確認しました．

$ wsl time tex.exe source.tex < in.txt > out.txt
# =>  real    0m0.658s
#     user    0m0.000s
#     sys     0m0.000s

wsl <hoge>でWSLのコマンドを呼べ，さらに.exeを省略しなければWSL側からWindowsの実行ファイルを呼ぶことが出来ます．

一応コーナーケース等のチェックはしているつもりですが反例がある，バグが有るなどツッコミがあればご指摘等よろしくお願いします．

したいこと一覧

作成済みのものは記事内リンクを張ってあります．

標準入出力
空白区切り分割
算術演算
条件分岐
ループ
配列
- 配列のソート
HashMap, HashSet
文字列検索，置換

解法

0. practice contest A - Welcome to AtCoder

行区切り，及び空白区切りで入力を読み込み，算術演算と文字列の書き出しを行います．
既に普段$\rm\TeX$でやることとかけ離れているのでなかなか面倒です．

0.tex

\def\print#1{\immediate\write16{#1}}
\def\substitute#1 #2;{\def\inB{#1} \def\inC{#2}}
\def\blank{ }
%
\read-1to\inA%
\read-1to\inLine%
\expandafter\substitute\inLine;%
\read-1to\inS%
\newcount\result%
\result=\inA \advance\result by \inB \advance\result by \inC%
\print{\the\result\blank\inS}
\end

出入力

\read-1to\hoge

で標準入力から1行読み取って\hogeに格納することが出来ます．\readのあとの「-1」は受け取り方のオプション指定用引数のようで，0以上の数を入れるとプロンプトに\hoge=と出るようになります．

\immediate\write16{hoge}

でhogeを標準出力に書き出す事ができます．16を変えると出力先のストリームを指定できるらしいです．
immediateのスペルを間違えそうになるので私はマクロで\print#1を作っています．
ちなみにカウンタ(後述)などのレジスタを出力するときは\the\cntのようにする必要があります．この辺はタイプセットで出力するときと同じですね．

制御綴(\で始まるやつ)の直後のスペース(の連続)は字句解析の時点で無視されてしまうためスペースを出力したい場合はそれ用のマクロを用意しておく必要があります．

空白区切りの分割

マクロを\defで定義するとき，単に#1#2……を引数指定するだけでなくパターンマッチさせることもできます．この場合{}でくくらなくてもマッチするトークン列を引数に入れてくれます．
これを用いて，例えばhoge fugaのように空白区切りで2つの入力があれば

\def\substitute#1 #2;{\def\inB{#1} \def\inC{#2}}

のようにする¹ことで\substitute hoge fuga;で\inB=hoge，\inC=fugaとすることが出来ます．² ³

分割したい文字列が制御綴に格納されてる場合，文字列として展開された後にパターンマッチしてもらわないといけないので\expandafterを使います．
\expandafter \A \Bを一段展開すると\A <\Bの展開結果>になるのでめでたくパターンマッチさせることが出来ます．

算術演算

$\rm\TeX$にはいくつか"変数"が用意されており，カウンタには整数を格納することが出来ます．


\newcount\cntHoge %カウンタの宣言
\cntHoge=N %値の代入（Nは整数として解釈できる文字列またはカウンタ）（'='は省略可）
\advance \cntHoge by N % \cntHoge += N
\multiply\cntHoge by N % \cntHoge *= N
\divide  \cntHoge by N % \cntHoge /= N (整除）

負の数も扱えるため引き算はありません．⁴
x = a + b * c みたいな一時記憶が必要な演算は一時変数を使ったりしていちいち手作業しないといけません．アセンブラいじってるみたいな気持ちになりますね．

2. ABC 081 A - Placing Marbles

3桁の数字の桁に1がいくつ登場するかを数えます．

2.tex

\def\print#1{\immediate\write16{#1}}
%
\read-1to\inS%
\newcount\cX \newcount\cY \newcount\cZ%
\cX=\inS \cY=\inS \cZ=\inS%
\divide\cX by 100 \multiply\cX by 100%
\advance\cY by -\cX \divide\cY by 10 \multiply\cY by 10%
\advance\cZ by -\cX \advance\cZ by -\cY%
\divide\cX by 100 \divide\cY by 10%
\newcount\result \result=0%
\ifodd \cX \advance\result by 1 \fi
\ifodd \cY \advance\result by 1 \fi
\ifodd \cZ \advance\result by 1 \fi
\print{\the\result}
\end

100x+10y+zのかたちから頑張ってx,y,zを導きます．
剰余演算はないので $x % n= x - [x/n]*n$ を使って頑張って四則演算を繰り返すと導けます．
現れるのが1か0なので今回も\ifoddで分岐できますね．

この問題は$N$個の入力を受け取る必要があるため保留中です．
上で使った\substituteは入力数をこちらで指定しておかないといけないので使えません（それ以前に\defで使える引数は9個までなので限界があります)
$\rm\LaTeX$で配列パッケージを作っているのを見たことがあるのでそれを参考に頑張っています．
2019/06/09 追記
$N$個の要素が何回2で割れるかを求めます．
2で割り切れない要素が発生するまで繰り返し，繰り返し回数を出力します．

3.tex

\def\print#1{\immediate\write16{#1}}
\def\makeArray#1#2{ % <array name><array length>
  \expandafter\def\csname ArrayLength#1\endcsname{#2}%
  \count0=0%
  \loop%
    \expandafter\def\csname ArrayValue\the\count0#1\endcsname{0}%
  \advance\count0 by 1\ifnum \count0<#2 \repeat%
}
\def\setArrayValue#1#2#3{ %<array name><index><value>
  \expandafter\xdef\csname ArrayValue#2#1\endcsname{#3}
}
\def\getArrayValue#1#2#3{ %<array name><index><register>
  \expandafter\xdef\csname#3\endcsname{\csname ArrayValue#2#1\endcsname}
}
\def\popTop#1{ % <length><list>
  \def\subPopTop##1 ##2;{
    \def\tempTop{##1}%
    \def#1{##2}%
  }
  \expandafter\subPopTop#1;
}
%
\read-1to\inN%
\newcount\cntN \cntN=\inN%
\read-1to\inA%
\makeArray{arrA}{\cntN}%
%
\newcount\cnti \cnti=0%
\newcount\cntNm \cntNm=\cntN \advance\cntNm by -1%
\loop \ifnum \cnti<\cntN%
  \ifnum \cnti=\cntNm%
    \setArrayValue{arrA}{\the\cnti}{\inA}
  \else%
    \popTop\inA%
    \setArrayValue{arrA}{\the\cnti}{\tempTop}
  \fi%
\advance\cnti by 1 \repeat%
%
\newcount\cflag \cflag=1%
\newcount\ctmp \newcount\ctmpp%
\newcount\r \r=0%
\loop \ifnum \cflag=1%
  \cnti=0%
  {%
  \loop \ifnum \cnti<\cntN%
    \getArrayValue{arrA}{\the\cnti}{getTemp}
    \ctmp=\getTemp%
    \ctmpp=\ctmp \divide\ctmpp by 2 \multiply\ctmpp by 2%
    \ifnum \ctmp=\ctmpp%
      \divide\ctmpp by 2%
      \setArrayValue{arrA}{\the\cnti}{\the\ctmpp}
    \else%
      \global\cflag=0%
      \advance\cnti by \cntN%
    \fi%
  \advance\cnti by 1 \repeat%
  }%
  \advance\r by 1%
\repeat%
\advance\r by -1%
%
\print{\the\r}
\end%

配列の各要素が2の倍数ならば2で割り，2の倍数でなければflagを0にしてloopを抜けます．
breakする際にもifに辿り着く前，ループ回数のカウントをしてしまっているので余計な1を引いて答えになります．

配列

$\rm\TeX$では\csname hoge\endcsnameで\hogeという制御綴を作ることが出来ます．このhogeには英字以外の文字を含めることができる，すなわち数字を制御綴に埋め込む事もできるため「\ArrayValue<n番目><配列名>」という制御綴を配列の大きさだけ作成し，擬似的に配列を実現します．⁷

\def\setArrayValue#1#2#3{ %<array name><index><value>
  \expandafter\xdef\csname ArrayValue#2#1\endcsname{#3}
}
\def\getArrayValue#1#2#3{ %<array name><index><register>
  \expandafter\xdef\csname#3\endcsname{\csname ArrayValue#2#1\endcsname}
}

\csname自体をdefしたりしないよう，また制御綴に格納するのがカウンタや制御綴なのかその値なのかなど展開順序に気をつければ完成です．
上では\makeArray#1#2も作っていますが配列の長さと初期値を設定しているだけで，長さは入力のNを使えばよいためgetの前にsetするようにすれば初期化しなくても動きます．

4. ABC 087 B - Coins

$0\leq a\leq A,\ 0\leq b\leq B,\ 0\leq c\leq C,\ X=500a+100b+50c$ を満たすa,b,cを探索します．
素直に解けばa,b,cの3重ループで制約的に十分解けるはずですが，ループをネストさせると面倒なことになる（後述）ことと，$\rm\TeX$は遅いので割と間に合わなくなる可能性があるためループを1段にする工夫をします．

4.tex

\def\print#1{\immediate\write16{#1}}
%
\newcount\cntA \newcount\cntB \newcount\cntC \newcount\cntX%
\read-1to\inA \cntA=\inA%
\read-1to\inB \cntB=\inB%
\read-1to\inC \cntC=\inC%
\read-1to\inX \cntX=\inX%
%
\newcount\result \result=0%
\advance\cntA by 1 \advance\cntB by 1%A=A+1, B=B+1
\newcount\cntij \newcount\cnti \newcount\cntj \newcount\ctmpS \newcount\ctmpT
%\cntAB=(A+1)(B+1)+1
\newcount\cntAB \cntAB=\cntA \multiply\cntAB by \cntB \advance\cntAB by 1%
\multiply\cntC by 50 \advance\cntC by 1%C=50C+1
\cntij=0
\loop \ifnum \cntij<\cntAB%
  %0<=ij<=(A+1)(B+1)
  %0<=i<=A, 0<=j<=B
  \cnti=\cntij \divide\cnti by \cntB\relax
  \multiply\cnti by \cntB \cntj=\cntij \advance\cntj by -\cnti \divide\cnti by \cntB
  %
  \multiply\cnti by 500 \multiply\cntj by 100
  \ctmpS=\cntX \advance\ctmpS by -\cnti \advance\ctmpS by -\cntj
  \ifnum \ctmpS>-1
    \ctmpT=\ctmpS \divide\ctmpT by 50 \multiply\ctmpT by 50
    \ifnum \ctmpS=\ctmpT
      \ifnum \ctmpS<\cntC
        % if X-500i-100j>=0 && (X-500i-100j)%50==0 && (X-500i-100j)<=50C
        \advance\result by 1
      \fi
    \fi
  \fi
\advance \cntij by 1 \repeat
%
\print{\the\result}
\end

まず，#8 Otoshidama と同様，a,bが決まればcは決まるため適切な条件判定により3段目のループはなくすことが出来ます．
さらに，$0\leq a\leq A,\ 0\leq b\leq B$のとき，$x=a\times (B+1)+b$は$0\leq x<(A+1)(B+1)$の全域をとり，また$a=[x/(B+1)]$，$b=x%B=x-aB$と逆算することでa,bを復元することができます．
よって$0\leq x<(A+1)(B+1)$でループを取ることで2重ループを1重にすることが出来ました．
a,bに対してcが満たすべき条件は$c=(X-500a-100b)/50$が$0\leq c\leq C$の整数となること，すなわち0<=X-500a-100a && (X-500a-100b)%50==0 && (X-500a-100b)<=50Cですが$\rm\TeX$には論理演算はないのでif文をネストします．⁸

ループ

\loop
  <実行内容>
\if<条件> \repeat

でdo-whileループ，または

\loop \if<条件>
  <実行内容>
\repeat

の形でwhileループが実現できます．
ifで真なら続きを実行し\repeatで\loopに戻る，偽だったら\repeatに飛んで終了というような動作になります．

5. ABC 083 B - Some Sums

各位の桁の和を求める問題．#2 Productと同様に各位の桁にバラして足せば良いです．
制約は$10^4$までなので最大で5桁の数を判定できればよいため5桁全部計算してしまいます．

5.tex

\def\print#1{\immediate\write16{#1}}%
\def\substitute#1 #2 #3;{\def\inN{#1} \def\inA{#2} \def\inB{#3}}%
%\def\blank{ }
%
\read-1to\inLine%
\expandafter\substitute\inLine;%
\newcount\cntA \cntA=\inA \advance\cntA by -1%
\newcount\cntB \cntB=\inB \advance\cntB by 1% A<=k<=B ⇔ A-1<k<B+1
\newcount\cntN \cntN=\inN \advance\cntN by 1%
\newcount\cnti \cnti=1%
\newcount\tmp \newcount\result \result=0%
\newcount\disitA \newcount\disitB \newcount\disitC \newcount\disitD \newcount\disitE%
\loop \ifnum \cnti<\cntN%
  %高々5桁なので5桁調べる
  \disitA=\cnti \divide\disitA by 10000 \multiply\disitA by 10000%
  \disitB=\cnti \advance\disitB by -\disitA \divide\disitB by 1000 \multiply\disitB by 1000%
  \disitC=\cnti \advance\disitC by -\disitA \advance\disitC by -\disitB \divide\disitC by 100 \multiply\disitC by 100%
  \disitD=\cnti \advance\disitD by -\disitA \advance\disitD by -\disitB \advance\disitD by -\disitC \divide\disitD by 10 \multiply\disitD by 10%
  \disitE=\cnti \advance\disitE by -\disitA \advance\disitE by -\disitC \advance\disitE by -\disitC \advance\disitE by -\disitD%
  \divide\disitA by 10000 \divide\disitB by 1000 \divide\disitC by 100 \divide\disitD by 10%
  %\print{\the\disitA\blank \the\disitB\blank \the\disitC\blank \the\disitD\blank \the\disitE\blank}
  \tmp=\disitA \advance\tmp by \disitB \advance\tmp by \disitC \advance\tmp by \disitD \advance\tmp by \disitE%
  \ifnum \cntA<\tmp%
    \ifnum \tmp<\cntB%
      \advance\result by \cnti%
    \fi%
  \fi%
\advance\cnti by 1 \repeat%
\print{\the\result}
\end%

あまりにも計算ゴリ押しなのでコードの圧がすごくなってきました．

6.ABC 088 B - Card Game for Two

こちらも$N$個の入力がある上にsortが必要です．制約が小さいのでバブルソートでも行けそうですが実装できるでしょうか……？気合でなんとかしようとしているところです．
2019/06/09 追記
配列が作れたのでやりました．
ソートして大きいものから偶数番目はAlice，奇数番目はBobが取るのが最適なので偶数番目を足し，奇数番目を引いて和を取ればOKです．

6.tex

\def\print#1{\immediate\write16{#1}}
\def\makeArray#1#2{ % <array name><array length> 1-indexed
  \expandafter\def\csname ArrayLength#1\endcsname{#2}%
  \count0=0%
  \loop%
    \expandafter\def\csname ArrayValue\the\count0#1\endcsname{0}%
  \advance\count0 by 1\ifnum \count0<#2 \repeat%
}
\def\setArrayValue#1#2#3{ %<array name><index><value>
  \expandafter\xdef\csname ArrayValue#2#1\endcsname{#3}
}
\def\getArrayValue#1#2#3{ %<array name><index><register>
  \expandafter\xdef\csname#3\endcsname{\csname ArrayValue#2#1\endcsname}
}
\def\popTop#1{ % <length><list>
  \def\subPopTop##1 ##2;{
    \def\tempTop{##1}%
    \def#1{##2}%
  }
  \expandafter\subPopTop#1;
}
\def\arraySortDecend#1#2{
  %\expandafter\count0\csname ArrayLength#1\endcsname
  \count0=#2 \advance\count0 by -1
  \count1=0
  \loop \ifnum \count1<\count0
    \count2=0
    {
    \loop \ifnum \count2<\count0
      \getArrayValue{#1}{\the\count2}{getTempA}
      \count3=\count2 \advance\count3 by 1
      \getArrayValue{#1}{\the\count3}{getTempB}
      \count4=\getTempA\relax%
      \count5=\getTempB\relax%
      %\print{\the\count1,\the\count2,\the\count4,\the\count5}
      \ifnum \count4<\count5
        \setArrayValue{#1}{\the\count2}{\the\count5}
        \setArrayValue{#1}{\the\count3}{\the\count4}
      \fi
    \advance\count2 by 1 \repeat
    }
  \advance\count1 by 1 \repeat
}
%
\read-1to\inN%
\newcount\cntN \cntN=\inN%
\read-1to\inA%
\makeArray{arrA}{\cntN}%
%
\newcount\cnti \cnti=0%
\newcount\cntNm \cntNm=\cntN \advance\cntNm by -1%
\loop \ifnum \cnti<\cntN%
  \ifnum \cnti=\cntNm%
    \setArrayValue{arrA}{\the\cnti}{\inA}
  \else%
    \popTop\inA%
    \setArrayValue{arrA}{\the\cnti}{\tempTop}
  \fi%
\advance\cnti by 1 \repeat%
%
\newcount\cnti \cnti=0
\newcount\cntj \newcount\cTmpS \newcount\cTmpT
\arraySortDecend{arrA}{\the\cntN}
%
\cnti=0\relax%
\cTmpT=0\relax%
\loop \ifnum\cnti<\cntN%
  \getArrayValue{arrA}{\the\cnti}{getTemp}
  \cTmpS=\getTemp\relax%
  \ifodd\cnti
    \advance\cTmpT by -\cTmpS
  \else
    \advance\cTmpT by \cTmpS
  \fi
\advance\cnti by 1\repeat
\print{\the\cTmpT}
\end

配列のソート

制約の小ささに甘えてバブルソートです．

\def\arraySortDecend#1#2{
  %\expandafter\count0\csname ArrayLength#1\endcsname
  \count0=#2 \advance\count0 by -1
  \count1=0
  \loop \ifnum \count1<\count0
    \count2=0
    {
    \loop \ifnum \count2<\count0
      \getArrayValue{#1}{\the\count2}{getTempA}
      \count3=\count2 \advance\count3 by 1
      \getArrayValue{#1}{\the\count3}{getTempB}
      \count4=\getTempA\relax%
      \count5=\getTempB\relax%
      %\print{\the\count1,\the\count2,\the\count4,\the\count5}
      \ifnum \count4<\count5
        \setArrayValue{#1}{\the\count2}{\the\count5}
        \setArrayValue{#1}{\the\count3}{\the\count4}
      \fi
    \advance\count2 by 1 \repeat
    }
  \advance\count1 by 1 \repeat
}

これまで適当でしたが，カウンタへの代入など数字を扱うときは命令のあとに\relaxをつけたほうが無難です．\relaxは「なにもしない」命令で，これをつけておかないとたまに続きの命令をつなげて読んでしまってバグるということが起こりえます．

ちなみに\count<n>は$\rm\TeX$のデフォルトのカウンタで，宣言無しで使えますが，他のパッケージとの干渉の恐れがあり本当はそのまま使うべきではないです．
宣言がめんどくさくなってきたのでそのまま使ってしまっています．

配列が作れたので7と10もできそうですが取り急ぎここまで．

7. ABC 085 B - Kagami Mochi

重複を除く処理があるので汎用言語ならばsetが欲しいところです．sortができればなんとかなる……かも？

2019/09/26 追記
東大TeX愛好会@ut_tex_clubさんから解法を頂きました．
https://gist.github.com/domperor/e6492336e0650cc2ba4fef4d7674b94c

実装方針としては，例えば「100」という入力に対し\100という制御綴を生成することで既出か否かを判定することで重複判定を行い，重複しないものの数を数えるといったものです．
\hogeが既出であることは\ifx\hoge\relaxで判定されています．
制御綴とその内容の対応は概ねHashMapと同様なので，値域をUnitにすることでHashSetとして利用できるということですね．

HashMap, HashSet

上記のようにKeyを文字列として制御綴に埋め込むことでHashMap/Setを実現できます．

hashmap

\def\key{<key>}

% 値の設定
\expandafter\def\csname hogefuga\key\endcsname{<value>}

% 値の取り出し
\immediate\write16{\csname hogefuga<key>\endcsname}
% => <value>

csnameで定義する制御綴はかなり自由で，<や^,_といった通常制御綴に含められない文字を使用することができます．\keyのように制御綴を含む場合は内容が展開されてから解釈されます．(上記の場合は\keyは""という文字列に展開され\hogefuga<key>という制御綴が生成されます．ただし<,>を含むのでこのままではそのままは呼び出せず，\csnameを使用する必要があります．)

また，HashSetとして使う場合，制御綴が定義されているかどうかは\relaxと比較することで得られます

hashset

% 中身が空の制御綴を定義する
\expandafter\def\csname hogefuga\key\endcsname{}

\expandafter\ifx\csname hogefuga<key>\endcsname\relax
  % <key> ∉ Set の場合
\else
  % <key> ∈ Set の場合
\fi

8. ABC 085 C - Otoshidama

基本的に#4 Coinsと同様の問題ですがNが大きいため3段目のループを削減することは必須になります．

$a+b+c=N,\ 10000a+5000b+1000c=Y$を満たすa,b,cを見つけます．すなわち探索する範囲は
$0\leq a\leq N,\ 0\leq b\leq N-a, c=N-a-b$です．

8.tex

\def\print#1{\immediate\write16{#1}}%
\def\substitute#1 #2;{\def\n{#1} \def\y{#2}}%
\def\blank{ }
%
\read-1to\line%
\expandafter\substitute\line;%
\newcount\cntn \cntn=\n
\newcount\cntnn \cntnn=\cntn \advance\cntnn by 1\relax%
\newcount\cnty \cnty=\y \divide\cnty by 1000\relax%
\newcount\cnti \cnti=0\relax%
\newcount\ni \newcount\cntj \newcount\tmp \newcount\tmpp
\newcount\flag \flag=0\relax%
\loop \ifnum \cnti<\cntnn%
  \ni=\cntnn \advance\ni by -\cnti\relax%
  \cntj=0\relax%
  {
  \loop \ifnum \cntj<\ni
    \tmp=\cntn\relax%
    \tmpp=\cnti \multiply\tmpp by 9 \advance\tmp by \tmpp\relax%
    \tmpp=\cntj \multiply\tmpp by 4 \advance\tmp by \tmpp\relax%
    \ifnum \tmp=\cnty%
      \tmp=\cntn \advance\tmp by -\cnti \advance\tmp by -\cntj\relax%
      \print{\the\cnti\blank\the\cntj\blank\the\tmp}
      \global\flag=1\relax% globalのついた演算・代入操作
      \global\advance\cnti by \cntnn\relax%
      \advance\cntj by \cntnn\relax%
    \fi
  \advance\cntj by 1 \repeat
  }
\advance\cnti by 1 \repeat%
\ifnum \flag=0 \print{-1 -1 -1} \fi%
\end%

探索範囲が矩形でなくなり1重ループまで落とすと逆に面倒なのでループのネストをちゃんとやっていきます．
if文のように単にloopをネストすると内側の\repeatでどの\loopに飛ぶかということが確定せずエラーになります．
これを防ぐには内側のループ全体を{}で囲えばよいのですがこうするとカウンタの演算のスコープが{}の内部だけとなり，演算結果を外側に反映することが出来ません．
外側に反映させるにはカウンタの演算の前に\globalをつけます．

ちなみに入力例3:2000 20000000の実行時間は3.102sとAtCoderの制約をオーバーしてしまいました．
ループは最悪で2000*2000/2=2e6 回なので汎用のプログラミング言語なら十分間に合うはずですが流石に遅いですね．
詳細な実行時間ベンチマークについてはまたいつか．

9. ABC 049 C - Daydream

こちらは正規表現が欲しいところ．\defのパターンマッチをうまくやればできそうな気がしなくもないようなそうでもないような．

2019/09/26 追記
東大TeX愛好会@ut_tex_clubさんから解法を頂きました．
https://gist.github.com/domperor/317d7edfd92c676a76d4322329c136db

鬼のように\expandafterが出てきますが解法としては入力の文字列を後ろから順に"dream ","erase","dreamer","eraser"とマッチするかどうか判定していくというものです．
\expandafterで\expandafterの次の\expandafterを展開してさらにその次を展開する……みたいなことをするので\expandafterが連鎖するとえらいことになります．

文字列パターンマッチング

上記の問題は場合分けが多くてわけわからなみが強いのでもう少しシンプルに「文字列が"ab"の繰り返しであるか」を判定する問題を考えます．

9_sub.tex

\def\flag{YES}
\def\trim#1#2#3-{%
  \edef\two{#1#2}
  \def\ab{ab}
  \expandafter\ifx#1;
    % 文字列終端に達したため終了
  \else \ifx\two\ab
    % 頭2文字が"ab"だったため残りの文字列を再判定
    \expandafter\trim#3-
  \else
    % "ab"以外のパターンであるため終了
    \def\flag{NO}
  \fi\fi
}
\read-1to\input
\expandafter\trim\input;:-
\immediate\write16{\flag}
\end

入力が"ab"だった場合

まず
\expandafter\trim\input;:-，すなわち\trim ab;:-
が呼ばれて\trim中で#1="a", #2="b", #3=";:"がマッチします．さらに\two={ab}が定義されます．
最初の\ifx#1;は#1="a"≠";"なので偽．
次の\ifx\two\abでは\two={ab}=\abなので真．if文中で
\expandafter\trim#3-，すなわち\trim;:-
が呼ばれ，#1=";", #2=":", #3=""となり，今度は最初の条件分岐で#1=";"となり終了します．
\flagがYESのままなのでYESが出力されます．

入力が"c"だった場合

\expandafter\trim\input;:-はすなわち\trim c;:-
となり#1="c", #2=";", #3=":"，\two={c;}です．
最初の条件分岐は偽，次も\two={c;}≠{ab}なので偽となり，最後の部分で\flag={NO}となって終了します．

上記の問題ではマッチする文字列が4つあり，また一部が被っているので処理の順番を工夫する必要がありますが，流れとしては一緒です．
\expandafterでの展開制御に気をつけることと，入力の末尾に";:::::::"と文字列を付け足すことでパターンマッチが失敗しないようにしているのがミソですね．

10. ABC 086 C - Traveling

こちらは$N$個入力がある上に2次元とかなんかめんどくさそう．やばいですね☆

2019/09/26 追記
東大TeX愛好会@ut_tex_clubさんから解法を頂きました．
https://gist.github.com/domperor/0ba2e2ec24b2198c56d96521ab59a381

↑であんなことを言っていましたが丁寧にやれば普通の言語で解くのと同様にできます．
$i-1$番目から$i$番目に行くのが可能かどうかだけ判定してやればいいので配列も特に必要ありませんでした．
$i-1$番目から$i$番目に行くのが可能かどうかは移動距離が時間以下であるか($|x_i-x_{i-1}|+|y_i-y_{i-1}|\leq t_i-t_{i-1}$)，$x_i, x_{i-1}$と$y_i, y_{i-1}$がそれぞれ偶奇が一致するかで判定できます．

最後を;にしたのはなんとなくC言語風記法を踏襲したというだけで任意のトークンでいいです． ↩
ちなみにhoge fuga piyoのように区切りが2ヶ所あったりすると先のほうがマッチし，\inB=hoge，\inC=fuga piyoになります． ↩
グローバル変数に格納するみたいなやばいことをしていますがこの辺は汎用プログラム言語ではないゆえに仕方ないところですね，構造化プログラミングとか流石に厳しいです． ↩
扱える範囲は-2147483647～2147483647．大概の32bit整数型と同じですね． ↩
ところで\ifを閉じるのが\fiみたいなセンス，私は好きです．
\ifの部分はいくつか種類があり，競プロで特に使いそうなのが\ifnumでしょうか．
条件式のところには N<M, N=M, N>M のような数値比較が書けます．（残念ながら<=などはないです）
今回は偶奇判定ですが，おあつらえ向きに「hogeが奇数であるかどうか」で分岐する\ifodd hogeがあるのでそのまま使えます．⁶ ↩
偶奇判定だけわざわざ用意してあるのは見開きでページ割りするときなんかに使うんでしょうか．もともとカウンタの本来の用途はセクション数やページ数の管理ですし． ↩
$\rm\TeX$の制御綴はハッシュで管理されているらしい[要出典]ので整数→文字列→データの遠回りなHashMapを作っていることになりますね． ↩
論理積だけだったのでifを重ねて出来ますが，論理和が入っていればフラグを作って並列しないといけません． ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up