床関数・天井関数（floor function / ceiling function）の典型まとめ

考察をショートカットしたいので書きました。負の数が絡むと頭が壊れがち。

見つけ次第追加していこうと思います。

定義

床関数

$ x \in \mathbb{R} $ 以下の最大の整数を $ \lfloor x \rfloor $ で表し、$ \lfloor \cdot \rfloor $ を床関数（floor function）と呼びます。

例：$ \lfloor 1.2 \rfloor = 1$、$ \lfloor -3.1 \rfloor = -4 $

床関数、ガウス関数、整数部分は全部同じものです。

数直線上で自分のすぐ左にある整数を持ってくるイメージ。

$ x $ が有理数のとき

$ a $ を整数、$ b $ を正整数とします。整数 $ q $ と $ 0 \leq r < b $ を満たす整数 $ r $ を用いて $ a = bq + r $ と表せるとすると、 $$ \left\lfloor \frac{a}{b} \right\rfloor = \left\lfloor q + \frac{r}{b} \right\rfloor = q $$ が成り立ちます。

天井関数

$ x \in \mathbb{R} $ 以上の最小の整数を $ \lceil x \rceil $ で表し、$ \lceil \cdot \rceil $ を天井関数（ceiling function）と呼びます。

例：$ \lceil 1.2 \rceil = 2$、$ \lceil -3.1 \rceil = -3 $

$ x $ が有理数のとき

$ a $ を整数、$ b $ を正整数とします。整数 $ q $ と $ 0 \leq r < b $ を満たす整数 $ r $ を用いて $ a = bq - r $ と表せるとすると、 $$ \left\lceil \frac{a}{b} \right\rceil = \left\lceil q - \frac{r}{b} \right\rceil = q $$ が成り立ちます。

不等式評価

床関数

$x \in \mathbb{R}$ に対し、

$$ x - 1 < \lfloor x \rfloor \leq x $$

が成り立ちます。$ \lfloor x \rfloor \leq x < \lfloor x \rfloor + 1 $ の形で使うこともあります。

また、$a, b \in \mathbb{R}$ とすると

• $ a \leq b \Rightarrow \lfloor a \rfloor \leq \lfloor b \rfloor $
• $ \lfloor a \rfloor < \lfloor b \rfloor \Rightarrow a < b$

となります（逆は✗）。さらに、$a$ が整数のときは $$ a \leq b \Leftrightarrow a \leq \lfloor b \rfloor $$ が成り立ちます。

天井関数

$x \in \mathbb{R}$ に対し、

$$ x \leq \lceil x \rceil < x + 1 $$

が成り立ちます。$ \lceil x \rceil - 1 < x \leq \lceil x \rceil $ の形で使うこともあります。

また、$a, b \in \mathbb{R}$ とすると

• $ a \leq b \Rightarrow \lceil a \rceil \leq \lceil b \rceil $
• $ \lceil a \rceil < \lceil b \rceil \Rightarrow a < b$

となります（逆は✗）。さらに、$b$ が整数のときは $$ a \leq b \Leftrightarrow \lceil a \rceil \leq b $$ が成り立ちます。

noshi さんの記事 にも色々載っていてありがたいです。

noshi91.hatenablog.com

切り捨て除算を使った実装

C++ や Rust の整数除算は、小数点以下を切り捨てる仕様になっています *1 。すなわち、除算の結果が正のときは floor、負のときは ceil のような挙動をします。この項の目標は、割り算結果の floor や ceil を切り捨て除算で表現することです。

実数 $ x $ を $ 0 $ 方向に丸めたもの（小数点以下を捨てたもの）を $ \mathrm{round}(x) $ と書くことにします。

例：$ \mathrm{round}(5 / 3) = 1 $、$ \mathrm{round}(-5 / 3) = -1 $

$ b > 0 $ のとき、以下が成り立ちます：

$$ \left\lfloor \frac{a}{b} \right\rfloor = \begin{cases} \mathrm{round}(a / b) & (a \geq 0) \\ \mathrm{round}((a + 1) / b) - 1 & (a < 0) \end{cases} $$

証明（クリックで展開）

$ a \geq 0 $ のときは明らか。
$ a < 0 $ のとき $ \lfloor a / b \rfloor = \mathrm{round}((a + 1 ) / b) - 1 $ が成り立つことを示す。
整数 $ q $ と $ 0 \leq r < b $ を満たす整数 $ r $ を用いて $$ a + 1 = bq + r $$ と書けるとする。$ b \mid a+1 $ か否かで場合分けをする。
$ r = 0 $ のとき、 $$ \begin{split} (\text{左辺}) &= \left\lfloor \frac{bq - 1}{b} \right\rfloor \\\ &= \left\lfloor \frac{b(q-1) + (b - 1)}{b} \right\rfloor \\\ &= \left\lfloor q-1 + \frac{(b - 1)}{b} \right\rfloor \\\ &= q - 1 \end{split} $$ および $$ (\text{右辺}) = \mathrm{round}\left(\frac{bq}{b}\right) - 1 = q - 1 $$ となる。
$ r > 0 $ のとき、$ 0 \leq r - 1 < b$ と $ a = bq + (r - 1) $ を用いて $$ (\text{左辺}) = \left\lfloor q + \frac{r - 1}{b} \right\rfloor = q $$ また、 $$ (\text{右辺}) = \mathrm{round}\left(q + \frac{r}{b}\right) - 1 $$ $ a = bq + (r - 1) < 0 $ より $ q < 0 $ であり、$ q $ は整数なので $ q \leq -1 $。
$ 0 \leq r/b < 1 $ とあわせると $ q + r/b < 0 $ が分かるので、 $$ \mathrm{round}\left(q + \frac{r}{b}\right) = q + 1 $$ よって、 $$ (\text{右辺}) =(q+1) - 1 = q $$ となる。

$$ \left\lceil \frac{a}{b} \right\rceil = \begin{cases} \mathrm{round}((a - 1) / b) + 1 & (a > 0)\\ \mathrm{round}(a / b) & (a \leq 0) \end{cases} $$

証明（クリックで展開）

$ a \leq 0 $ のときは明らか。
$ a > 0 $ のとき $ \ceil a / b \rceil = \mathrm{round}((a - 1 ) / b) + 1 $ が成り立つことを示す。
整数 $ q $ と $ 0 \geq r < b $ を満たす整数 $ r $ を用いて $$ a - 1 = bq - r $$ と書けるとする。$ b \mid a-1 $ か否かで場合分けをする。
$ r = 0 $ のとき、 $$ \begin{split} (\text{左辺}) &= \left\lceil \frac{bq + 1}{b} \right\rceil \\\ &= \left\lceil \frac{b(q+1) - (b-1)}{b} \right\rceil \\\ &= \left\lceil q+1 - \frac{(b-1)}{b} \right\rceil \\\ &= q + 1 \end{split} $$ および $$ (\text{右辺}) = \mathrm{round}\left(\frac{bq}{b}\right) + 1 = q + 1 $$ となる。
$ r > 0 $ のとき、$ 0 \leq r - 1 < b $ と $ a = bq - (r - 1) $ を用いて $$ (\text{左辺}) = \left\lceil q - \frac{r - 1}{b} \right\rceil = q $$ また、 $$ (\text{右辺}) = \mathrm{round}\left(q - \frac{r}{b}\right) + 1 $$ $ a = bq - (r - 1) > 0 $ より $ q > 0 $ であり、$ q $ は整数なので $ q \geq 1 $。
$ 0 \leq r/b < 1 $ とあわせると $ q - r/b > 0 $ が分かるので、 $$ \mathrm{round}\left(q - \frac{r}{b}\right) = q - 1 $$ よって、 $$ (\text{右辺}) =(q-1) + 1 = q $$ となる。

$ b < 0 $ のときは、$ a \leftarrow -a,~b \leftarrow -b $ とすれば上の場合に帰着できます。競プロ用テンプレートに入れておくと便利。

template <class T>
T div_floor(T a, T b) {
    if (b < 0) a = -a, b = -b;
    return a >= 0 ? a / b : (a + 1) / b - 1;
}

template <class T>
T div_ceil(T a, T b) {
    if (b < 0) a = -a, b = -b;
    return a > 0 ? (a - 1) / b + 1 : a / b;
}

オーバーフローを避けて $ab$ と $c$ を比較する

この問題 で話題になったやつ。

$ a, b, c $ を正整数とします。$ ab $ と $ c $ の大小比較をしたいが、積 $ ab $ を求めようとするとオーバーフローして困る場面があります。

$ = $ と $ \leq $ さえ判定できれば他はこれらの組み合わせでできるので*2、$ = $ と $ \leq $ だけ考えます。

$ = $ については、

$$ ab = c \Leftrightarrow (a \mid c) \land \left(b = \frac{c}{a}\right) $$

です。$ \leq $ については、

$$ ab \leq c \Leftrightarrow b \leq \frac{c}{a} \Leftrightarrow b \leq \left\lfloor \frac{c}{a} \right\rfloor $$

より $ b \leq \lfloor c / a \rfloor $ が成り立つかどうかを見れば良いです。

このタイミングで言うのもなんですが、$ b/c $ と $ d/a $ の連分数展開を見比べれば $ ab $ と $ cd $ の大小比較ができるので、そっちを使っても良いと思います。

平方分割

$n$ を正整数とします。$x$ が正整数を動くとき、$\left\lfloor n / x\right\rfloor$ が取る値は

$$ 0, 1, 2, \ldots , \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor, \ldots, \lfloor n / 2 \rfloor, \lfloor n / 1 \rfloor $$

のいずれかです。列の前半は $ \left\lfloor n / x\right\rfloor $ が小さい場合、後半は $ x $ が小さい場合に対応しています。

種類数が $\lfloor n / \lfloor \sqrt{n} \rfloor \rfloor + \lfloor n \rfloor = O(\sqrt{n})$ しかないので DP の状態が減らせて嬉しい、みたいなことはよく起こります（例1 例2）。

数列 $a$ を

$$ a = (0, 1, 2, \ldots , \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor, \ldots, \lfloor n / 2 \rfloor, \lfloor n / 1 \rfloor) $$

とし、$ s = \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor $ とおきます。このとき、

$$ a_i = \begin{cases} i & (i \leq s) \\ \left\lfloor \frac{n}{s + \lfloor \sqrt{n} \rfloor - i} \right\rfloor & (i > s) \end{cases} $$

が成り立ちます。また、$ a $ における $ v $ のインデックスを $ a_v^{-1} $ と書くことにすると

$$ a_{v}^{-1} = \begin{cases} v & (v \leq s) \\ s + \lfloor \sqrt{n} \rfloor - \lfloor n / v \rfloor & (v > s) \end{cases} $$

となります。$ \lfloor n / i \rfloor = v $ かつ $ v > s $ のとき $ \lfloor n / v \rfloor = i $ が成り立つことを使っています。

証明（クリックで展開）

$ \lfloor n / i \rfloor = v $ かつ $ v > s $ とする。このとき、$ 0 \leq r < i $ を満たす整数 $ r $ が存在して $$ n = iv + r $$ が成り立っている。
$ r < v $ であることを示したい。そのためには、$ i \leq v $ となることが分かれば十分である。
$ i \geq n / \lfloor \sqrt{n} \rfloor $ と仮定すると、 $$ \frac{n}{i} \leq \frac{n}{n / \lfloor \sqrt{n} \rfloor} = \lfloor \sqrt{n} \rfloor $$ より、 $$ v = \left\lfloor \frac{n}{i} \right\rfloor \leq \lfloor \sqrt{n} \rfloor \leq \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor = s $$ となり矛盾。
よって、$ i < n / \lfloor \sqrt{n} \rfloor $ なので、$ i \leq s < v $ が成り立つ。

$ \left\lfloor \frac{n}{ab} \right\rfloor = \left\lfloor \left\lfloor \frac{n}{a} \right\rfloor / b \right\rfloor $

$ n, a, b $ を正整数とすると、

$$ \left\lfloor \frac{n}{ab} \right\rfloor = \left\lfloor \left\lfloor \frac{n}{a} \right\rfloor / b \right\rfloor $$

が成り立ちます。

証明（クリックで展開）

$ q $ を整数、$ r $ を $ 0 \leq r < ab $ を満たす整数とし、 $$ n = abq + r $$ と書けるとする。 このとき、 $$ \left\lfloor \frac{n}{ab} \right\rfloor = q $$ である。また、 $$ \begin{split} \left\lfloor \left\lfloor \frac{n}{a} \right\rfloor / b \right\rfloor &= \left\lfloor \left\lfloor bq + \frac{r}{a} \right\rfloor / b \right\rfloor \\\ &= \left\lfloor \left( bq + \left\lfloor \frac{r}{a} \right\rfloor \right) / b \right\rfloor \\\ &= \left\lfloor q + \left\lfloor \frac{r}{a} \right\rfloor / b \right\rfloor \\\ &= q + \left\lfloor \left\lfloor \frac{r}{a} \right\rfloor / b \right\rfloor \end{split} $$ ここで、$ \lfloor r/a \rfloor \geq b $ と仮定すると、$ r/a \geq b$ すなわち $ r \geq ab $ となり矛盾。
よって、$ \lfloor r/a \rfloor < b $ となるので $$ \left\lfloor \left\lfloor \frac{n}{a} \right\rfloor / b \right\rfloor = q + \left\lfloor \left\lfloor \frac{r}{a} \right\rfloor / b \right\rfloor = q $$ が成り立つ。

Sum of Floor of Linear

$ n, m, a, b $ が与えられます。

$$ \sum_{i = 0}^{n - 1} \left\lfloor \frac{ai + b}{m} \right\rfloor $$

を求めてね。

$ O(\log(\min \lbrace n, m, a \rbrace)) $ 時間で解けるらしいです。詳しくは えびちゃんの記事 などを参照してください。

rsk0315.hatenablog.com

*1:python の場合、// 演算子は床関数と同じ挙動をします。

*2:$ ab \geq c \Leftrightarrow \lnot (ab \leq c) \lor (ab = c) $ など

CTF を始めた

突然だが、二週間くらい前に CTF を始めた。 入門用の解説記事とかではなく、将来自分が読み返すための手記として記事に残しておく。

私について

生物情報系の修士一年生*1。DNA 配列解析アルゴリズムや系統樹推定の研究をしている。

学部一年の頃から競プロをやっており、普段は主に Rust、C++、python を書いている。

なぜ CTF を始めたか

ある程度の知識を前提とした上で、ひらめきや試行錯誤で問題を解いていくコンテンツが好きで、これまでに変化球クイズ、競技プログラミング、くそなぞなぞなどをやってきた。特に競プロには寝食を忘れるほど熱中し、凡人なりに精進を続け二年半かけて黄色に到達した。

しかし、色々あって以前ほど競プロにのめり込まなくなり、新しく始める競技系の趣味を探していた。

理論寄りの研究をやっている反動で、うんと実用的な部分（競プロ界隈ではパソコンと呼ばれる部分）に興味が湧いていたこともあり、隣のコンテンツである CTF に手を出すことにした。

やったこと・これからやること

まずは

うさぎさんのブログ

kmyk.github.io

ぴーよさんのブログ

ywmt.hatenablog.com

を読んで、雰囲気を掴んだ。

とりあえず CpawCTF を全部埋めた（半日くらいで終わった）。各ジャンルの印象を好き勝手に書いてみる。

Web

Web 系のインターンに行っていたことがあり、用語すらわからない……ということはない。しかし最低限の用語しかわからない。かなり勉強が必要そう。

Crypto

代数の講義で RSA と ElGamal 暗号くらいはやったことがある。上の方は整数論の知識が必要になってきて難しそうだが、一番とっつきやすい分野に見える。

Reversing

数年ぶりのアセンブリだったが、案外読めて嬉しかった。学部二年のときの演習が効いている*2。ただ、時間制限のあるコンテスト中に解くとなると情報の取捨選択が難しいんだろうなあと思う。経験と根気が必要そう。とはいえ、crypto の次にとっつきやすい。

Forensics

右も左もわからない。これは何？

PWN

まだ解いたことがない。

PPC

競プロからは逃れられない。

CpawCTF を埋めた後、ksnctf と picoCTF に手をつけ始めた。Twitter アカウントも開設した。アイコンがかわいい（原義の自画自賛）。

CTF を始めて一週間くらいになった

— りきぽん（CTF・競プロ） (@rk_pctf) 2022年12月22日

ksnctf の埋めが二進も三進もいかなくなってきたので、『詳解セキュリティコンテスト』を買った。Crypto の章から読み進めようと思う。

買った！

*1:とはいってもほぼ情報しかやっておらず、生物のことはあまり分からない……。

*2:生物情報科学科は情報科学科と合同で演習をやる。アセンブリを書いたり、scheme の処理系を scheme で書いたりする。

東京工業大学プログラミングコンテスト2022 参加記

11/5 (土) に、東京工業大学プログラミングコンテスト2022（TTPC2022）が開催された。 私にとっては初のオンサイトコンテストだったので、感想を書き留めておく。

コンテストページ：

atcoder.jp

開会まで

開場の 30 分前くらいに御茶ノ水駅に着いた。土地勘がありすぎて逆に不安になる。適当に散歩してから会場入りし、名札を受け取る。

えびちゃんには最初に会いに行こうと決めていたので、軽く挨拶をする。えびちゃんかわいいのチャンカワイの部分。*1

沙耶花ちゃんと話していると、ポッキーをむしゃむしゃ食べながら近づいてくるふっぴーさんがいた。

「お二人とも、どうしてそんなになぞなぞが強いんですか？」と質問したが、「こちらが聞きたいです」と返されてしまい、有益な情報は得られなかった。

ともかく、本当にうまそうにポッキーを頬張っていたのが印象に残っている。

はちじさんやのこさんなど、東大勢とも交流をする。

コンテスト開始間際に kichi さんが誘ってくださり、チームを組むことに成功。

コンテスト中

序盤は kichi さんが A~C、私が D, E を見ることにした。D は苦手っぽいので後回しにし、E を解く。

A は難なく AC。

B, C もデバッグを少し手伝い、AC。C は寄与に分解し、いつもの中央値テク（中央値が 以上 以上の数が 個以上）を用いる。中央値がちょうど になる場合の数を求めるには、 以上の場合から 以上の場合を引けば良い。 のうちどれが 以上になるかを bit 全探索する。微妙に TLE したが、kichi さんが高速化をしてくれた。

E は各テストケースあたり 時間で解かないといけないと思い込んで詰まっていたが、kichi さんに投げたところ「amortized になるので今のままでいいのでは」と言われて AC。結局、正解コードを前にして 10 分くらい頭を抱えていたことになる。愚かすぎる。

D はチームメイトがいつの間にか通していた。簡単な木 DP で解けるらしい。

残りの時間で F, L, M を考え続けるが、わからず……。3 時間くらい椅子を温めることになった。気まずくならないよう kichi さんが間を持たせてくれて、ありがたかった。

最後に G の部分点を取りに行こうという話になったが、バグったままコンテストが終了。

終了後

終了直後にえびちゃんが話しかけてくれて嬉しかった。そのあとは zkou さんと問題の感想を話していた。

解説会があった。裏話が中心で面白い。すくさんが Twitter のイメージ通りだった。

torisasami さん、かっつさんに挨拶をした。2019 年の 3 月 10 日、ちょうど WUPC の日に torisasami さんの東大合格ツイートを見た記憶があるので、感慨深い。

最後に noshi さんに会いに行った。「文字列アルゴリズムなどをやっている人として認識しています」と言われ、研究モチベが上昇した（競プロモチベを上げるオンサイトだったはずなのに……）。

*1:https://twitter.com/ricky_quikem/status/1597886247636463616?s=20&t=mhcmWaqBzaHk4lU6b5gW6w

くそなぞなぞレイドモードコンテスト002 参加記

皆さんこんにちは。くそなぞなぞ Beginner Contest admin のりきぽんです。

先日、「くそなぞなぞレイドモードコンテスト002」に参加しました。

shitforces.herokuapp.com

レイドモードコンテスト（以下、レイドコン）は、個人が正答数を競い合う普段のコンテストとは異なり、参加者が協力して大量の問題に挑むという形式で行われます。

3回目*1となる今回は koboshi さんによって100問のなぞなぞが用意され、20時間の回答時間が設けられました。

私は最後の2時間だけ参加していました。その際に行った考察などを、時系列に沿って書いていきます。 （今回のコンテストに限らず、過去のコンテストで出題された問題に関するネタバレが含まれます。ご注意ください！）

前半（18:00~18:30）

この時点で、未解決の問題は17~18問くらいあったと思います。 一周ざっと目を通して、4問を解きました。

BW 問題（700点）

バナナを食べるのを手伝ってくれる現象なーんだ？

〇〇現象は競技クイズ時代に詰め込んだので、腕が鳴ります。バナナの言い換えとして「芭蕉」が思い浮かびますが、その先は行き止まり……。

競技クイズでは現象・効果（・法則）をまとめて扱うことが多いことを思い出すと、「効果」が「剥こうか」の suffix であることに気付きます。

ムで終わる効果を脳内検索して「バーナム効果」を拾い、少しもじることで本日最初の AC を獲得しました。

答え：バナナ剥こうか（バーナム効果）

このあと CB 問題や CC 問題を考えていたら、15分くらい経ってしまいました。

CD 問題（800点）

病室を訪れるのをやめようとする現象なーんだ？

「病室を訪れる」の言い換えとして「見舞い」「面会」が挙がりますが、現象に繋がりません。

ここで、「さっきバーナム効果が出ていたので、『現象』や『効果』が後ろにつかないものが答えなのでは？」という大胆予想が立ちます（こういった考察は謎解きでは「メタ解き」と呼ばれ好ましくないものとされていますが、レイドコンは何でもありなので許されると思っています）。

自然現象、特に気象現象を列挙してみると、「蜃気楼」に「切ろう」が含まれている事に気付きます（アニメを3話で切る・一限の講義を切ると同じ使い方）。辞書で後方一致検索をして、正答を得ます。恥ずかしながら、答えとなる単語は知らないものでした。

答え：下位蜃気楼（回診切ろう）

問題数の多さゆえに、ジャンルや解法を通じて問題同士に関係性が生まれるのがレイドコンの醍醐味ですね。

ここからは調子が出てきて、立て続けに2問を AC します。

CS 問題（900点）

夫婦になるつもりのない恋愛の歌なーんだ？

「恋愛の歌」を見て、とりあえず「ラブソング」「相聞歌」を挙げてみると、それが答えでした。

答え：相聞歌（添うもんか）

CP 問題（900点）

筆箱好きな数学者だーれだ？

「筆箱」を見て、真っ先にレイドモードテストコンテストの T 問題である

うるさい筆箱のプレゼント企画なーんだ？

を思い浮かべました（過学習……）。なんと、これが正解ルートでした。

答え：ファン・カンペン（缶ペンのファンなので）

坪井先生の『幾何学II ホモロジー入門』を積んでおいてよかった〜（読め！）

後半（18:30~20:00）

2周目に入るにあたって、尺くんと通話を繋ぎました。ヒントが公開されていると教えてくれたので、ここから先はヒントありきの考察になります（尺くんがいなかったらヒントの存在に気付かないところだった……）。

koboshi-kyopro.hatenablog.com

AU 問題（500点）

表情を変えない騙し方なーんだ？

いの一番に「ポーカーフェイス」が思い浮かびますが、他の人が「ポーカーフェイク」で WA を出しているのを見て方針を切り替えます。

ヒントを見ると、

答えは3文字です。どんな表情をしないのか考えてみましょう。

とあります。尺くんが「3文字しかないのに否定語が入るんなら、最後の文字は『ん』やろ」と言うので、その線を追ってみます（最初の文字が「不」である可能性も考えたが、うまくいかなかったので捨てた）。

少しの間進捗がなかったのですが、会話をしていると「手練手管」が突然降ってきて正答に辿り着きました。

答え：手練（照れん）

「騙し方」という限定*2が適度な広さを持っていて上手ですね〜。競技なぞなぞにおいては、限定の部分に作問者の力量や個性が強く表れると感じています。私も上手な限定を捻り出せるようになりたいものです。

このあと、尺くんが BP 問題を通します（僕は何もしていない）。奈良県出身だから解きたかったな……

AV 問題（500点）

過去の失敗をずっと気にしている国どーこだ？

「サウジウジアラビア」が思いつきましたが、イマイチ……。ヒントに書いてある「国名そのものではありません」とはどういうことでしょう。

悩んでいると、尺くんが「『眠れる獅子』みたいな二つ名が答えなんじゃない？」という考察を投げてくれました。これを頭の片隅に置いた上で「過去の失敗をずっと気にしている」の言い換えを考えると、「引きずる」→「日出る」という具合に答えが出てきました。

答え：引きずる国（日出る国）

この手の問題で日本が答えになるのは初めて見ました。

CB 問題（700点）

泡変化球ビームなーんだ？

店長さんみたいな問題文ですね〜。「泡」「変化球」「ビーム」を個別に言い換えて繋げ、単語を作ることを考えます*3。

まずはビームから。Suffix が決まると、答えとなる単語の属性が見えやすくなります。「ray」「熱線」「光線」が挙がり、「この中では ray がダントツで使いやすいけど、光線が答えだったらかっこいいよね〜」という会話をしたのを覚えています。

次に、泡の言い換えです。尺くんが「バブル」を持っていたので、僕は「シャボン」「あぶく」「泡沫（うたかた、ほうまつ）」を出しました。あとは風属性のお店関係*4。

最後に、変化球を列挙します。カーブ、スライダー、フォーク、シンカー、スプリット……とやっていたら、尺くんが「魔球」を投げました。これが本当に偉かった。Qさま‼なら Fine Play のテロップが出ていることでしょう。

の全探索はやりたくないので他の問題を見ていたら、尺くんが答えを組み上げてくれました。ありがとう……

答え：阿武隈急行線（あぶく魔球光線なので）

BD 問題（600点）

経路探索アルゴリズムの駅どーこだ？

経路探索アルゴリズムといえば、幅優先探索、ダイクストラ法、ベルマンフォード法、SPFA、A* 探索などが思い浮かびますが、なかなか答えに辿り着けなくてもどかしく、俺は黄コーダーやぞ？　などと言っていました。不遜極まりない。

ヒントには

経路探索アルゴリズムの名前に含まれている要素をそれぞれ変換します。

とあり、ダイクストラを大/楠/虎と区切って言い換えを試みますが、うまくいかず……。

コンテスト終了間際になって、A* から星を切り取ることに成功します。残った A をひとまず「ア」と読んでみると、兵庫県の駅が見えてきました。関西人で良かった……！

答え：網干駅（A* なので）

最後の1分は CT~CV を考えていましたが、解けず。CV のヒントを見て「五黄の寅」が答えにならないか考えていましたが、ハズレ方針でしたね。

コンテストを通しての感想

遅刻参加しましたが、そこそこ問題が残っていたこともあり、楽しめました。通話をしたのも大正解でしたね。話をしながら考察を進めると、二人の実力の足し算を遥かに超える力が出ます。尺くんが「会話をすると、普段使っていない回路が刺激されて局所最適解から脱出できる」と言っていましたが、全くその通りです（前回のバチャ配信も見てね！）。

www.youtube.com

また、（僕が見た範囲では）整った問題文が多かったように感じました。BW 問題の「バナナ」と「剥く」、CS 問題の「夫婦」と「恋愛」、BD 問題の「経路探索」と「駅」のように、縁語で問題文が構成されているのが良いですね。意味の通った問題文になって満足感が増す上に、単語の切れ目がわかりにくくなることで難易度が高めになるなど、いい事ずくめです。

難易度推定も見事でした。僕はこれが下手くそで難易度逆転*5起きまくりなので、見習いたいところです。

欲を言うならあと2問、BT 問題と CT 問題は解きたかったな……。特に CT 問題は「流石に箱 V やろ〜」という会話はしていたので、せめてにじホロくらいは面倒くさがらずに列挙すればよかったですね。CU 問題と CV 問題は1000点の貫禄でした。あと1時間あっても解けなかったかもしれません。

おわりに

質・量ともに大満足のコンテストを用意してくださった koboshi さん、そして Sh*tforces 運営の店長さん、ありがとうございました。

レイドコンの writer は 尺P → cumin さん → koboshi さんと来ているので、次は私の番！？　勝手に圧を感じています。作問頑張ります……。

*1:通し番号は002ですが、「レイドモードテストコンテスト」を含めると3回目です。

*2:競技クイズにおいて、「〜な〇〇は何でしょう？」という問題文の〇〇の部分は「限定」と呼ばれています。ここでは、その用法を借りています。

*3:このような解法はチンゲンサイメソッドと呼ばれます。てぃーいけさんが解説放送で出した「珍しい通貨の動物なーんだ？」（答えは珍元サイ）という例題に由来します。

*4:泡が水じゃなくて風なの非自明ですよね（は？）

*5:難易度逆転とは、400点問題を解いた人数よりも500点問題を解いた人数のほうが多い、といった状態を指しています。

好きな日本語単語集

元ネタはこちら。できるだけ被らないようにしたい
focus-sash.hatenablog.com

単語	コメント
馥郁	レストランななつぼしにいる紳士のセリフで知った
濫觴	『濫觴生命』が好きです
端居
しとね	止マナイ雨ニ病ミナガラで知った
式神	東京レイヴンズで知った
獺祭	ださくない。カワウソを想像すると笑顔になる
辰砂
双対	漢字の並びのバランスが良い
顕現	シャナで知った
鵲	百人一首で知った
砂（いさご）
白皙	プリンセス・トヨトミで知った
塒（とや）
半夏生	おえかきの森とは関係がない
条鰭類	大体の魚がこれ
杠	ミカグラ学園組曲で知った
光芒	シャナで知った
靉靆	みんはやで出てきた。文字化けにしか見えない
揺蕩う	マジレンジャーで知った

随時追加する予定です