Suuさんのブログ

たまに見かける三種類の文字の二項演算について

AtCoder 競技プログラミング

はじめに

三種類の文字 $A, B, C$ があって二つの文字 $x, y$ について

$x = y$ のとき $x ( = y)$ を返す
$x \neq y$ のとき $x$ とも $y$ とも異なる文字を返す

というような二項演算が出てくる問題をたまに見かけます

こういう問題の解説を見ると~~よくわからない~~天才的な変換が書いてあることがしばしばあると思います。
それで納得できるならそれでいいのですが、そうもいかないという人に向けて~~全く参考になる気がしない~~自分がしている考え方を紹介しようと思います。（あくまでも「お気持ち」です）

お気持ち

この二項演算を $f$ とします

$f(A, A) = A, \quad f(A, B) = C$ となるような演算ということです。

さて、ここで登場する文字は三つだけなので、考えやすそうな数字に変換しましょう。

どんな順番でもいいですが、とりあえず

$A = 0$
$B = 1$
$C = 2$

とします。（問題が $R, G, B$ とかだったらそれに置き換えて考えてください）

こうすると、ここで求められる演算というのは

$f(0, 0) = 0$
$f(0, 1) = 2$
$f(0, 2) = 1$
$f(1, 0) = 2$
$f(1, 1) = 1$
$f(1, 2) = 0$
$f(2, 0) = 1$
$f(2, 1) = 0$
$f(2, 2) = 2$

こうなってほしいわけです。

さて、一気に考えるのは大変なのでとりあえずどちらも同じ数字のやつだけ考えてみます。

$f(0, 0) = 0$
$f(1, 1) = 1$
$f(2, 2) = 2$

突然ですが、二項演算と聞いてみなさん何を思い浮かべるでしょうか

だいたい最初に出てくるのは足し算・かけ算なのではと思っています。

ということでとりあえず足してみましょう。

とはいえそれだと二倍になってしまうので、足して 2 で割ってみましょう。

つまり、

$f(x, y) = \cfrac{x + y}{2}$

としてみます。こうするととりあえず今回考えている三つはみたしますね。

ついでに $f(0, 2) = 1$ なんかもみたしています。

しかし、このままでは $f(0, 1)$ とかで困ります。どうしましょうか

ここで、文字が三種類しかないということを生かしてみます

どうせ三つしかないので $\pmod 3$ の世界で考えてみるということです。

そうすると $2$ と $3$ は互いに素なので逆元が存在するはずで、

$2 \cdot 2 \equiv 4 \equiv 1 \pmod 3$

ということで

$2^{-1} \equiv 2 \pmod 3$

となります

よって

$f(x, y) \equiv 2(x + y)$

となり、

$f(0, 1) \equiv 2(0 + 1) \equiv 2 \pmod 3$

となってなんかいい感じです

そして、これはみたしてほしい関係をすべてみたしてくれます。

$2 \equiv -1$ なので $f(x, y) \equiv -x - y$ とも書けます。解説スライドでこの形の式を見かけた気がします。

と、こんな感じで二項演算の式を導くことができました。

割と自然な変換しかしていないつもりなのですが、どうでしょうか

例題

と、いうことでこの式で典型90 - 047 を考えてみます。

今回数えたいのは

${}^\forall i$ で $f(s_i, t_{i+k}) = c$ となるような $k$ の数です（ $c$ は定数）

さっきの式にばらして

$f(s _ i, t _ {i+k}) \equiv 2s _ i + 2t _ {i+k} \equiv c$

とします

ここで両辺に $2$ をかけると

$2(2s _ i + 2t _ {i+k} ) \equiv 2c$

$s _ i + t _ {i+k} \equiv 2c$

となって、 $t$ を移項して

$s _ i \equiv 2c - t _ {i+k}$

としてみます

ここで $- t _ {i+k}$ とはなんぞやということを考えてみると、

今三種類の文字を $0, 1, 2 \pmod 3$ として考えているのでそれをマイナスにしてみると

$-0, -1, -2 \equiv 0, 2, 1$

となりますね

E8さんの解説に登場した G→B、B→G という置き換えはこの式からも分かります。

また、 $c$ というのは何らかの定数ということにしているので

$u _ {i+k} \equiv 2c - t _ {i+k}$

と置いてみると

$s_i \equiv u _ {i+k}$

となって、ここまでくれば Z-algorithm などで共通する長さを求めてほげほげみたいなことをすればいいということがわかります。*1

おわりに

ということで、大した内容ではないですが天才じゃない人の思考過程にも多少は価値があるんじゃないかな～ってお気持ちで書いてみました。

いかがでしたか？

*1:ここから先はE8さんの解説などを見てください