12B構文続編
をテンプレートにして作成
[
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
メニュー
]
開始行:
[[HOJ講座]]
*12B構文続編 [#x5007692]
まず，12B構文自体が初耳という方は[[有理数の成長速度2]]を...
本講座は，12B構文を使いこなす上でポイントとなりうる点を，...
12B構文及びその変種についてはmasさんが書いた講座[[12B構文...
執筆者も当然使いこなせているわけではないので，他にポイン...
やや長くなったので目次を先に書いておきます．~
�‘団蠅寮�長段階切り出し~
��15B構文？~
��クレイジー12B構文~
�ね諭垢扮�用~
��solver作成時の注意点および枝刈りポイント~
**1. 特定の成長段階切り出し [#w4bef241]
こちらは12B構文の記事の「より複雑な構文」にて説明されてい...
以下のコードを実行してみましょう．
a(X):a(X-1)sa(X-1)l
a(9)
#ref(HOJ_12Bapp_01.png,nolink)
本コードは以下のコードにて実行されるXの10段階目を展開する...
f(X):Xf(XsXl)
f()
実際数値を用いて以下のように書くと同一の動きを書くことが...
a(X):a(X-1)sa(X-1)l
b(X):a(X)b(X+1)
b(1)
例題: [[Problem 2001]] ~
続いて以下のコードを見てみましょう．
a(X):a(X-1)sa(X-2)l
a(9)
#ref(HOJ_12Bapp_02.png,nolink)
このコードも実は以下の10段階目を切り抜いている，と説明で...
f(X,Y):Xf(XsYl,X)
f(,)
実際に以下を実行すると同一の動きが実現されていると確認で...
a(X):a(X-1)sa(X-2)l
b(X):a(X)b(X+1)
b(1)
一般にa(X):ua(X-n)va(X-m)w という書き方では，u [n段階前の...
(max(n,m)変数で実行部単一文字，初項はなし，というコードが...
基本的に既存の乱歩の成長段階ズラして組み合わせたものを実...
検索している人が多くない印象なので，今15B以下のbest解でも...
----
ちなみに小ネタになりますが，乱歩的な動きの方は実は https...
ただし後ろを+にして規則的動きを実現する，いわゆる「12B構...
このコラム（？）によると1424は本家マシンで実行3時間かかっ...
ガチ勢に知識の共有を求めている文章もあって，こういうのを...
**2. 15B構文？ [#h5a5e392]
ここでは
a(X):[1]a(X-i)[2]a(X-j)[3]a(X+k)
a(n)
という形の構文について触れます．i,j,k,nは正整数です．意味...
構造としてはiで割った商の回数[1]を実行し，iで割ったあまり...
構造上，以下の制約があります．
-a(X-i)の部分が定期的に実行されるために j-1+k > i
-a(X-j)の部分が実行されるために，i > j
また，12B構文で実現可能な動きとの差別化を図る上で i は j ...
最後の X+k が「 i で割った商がちょうど切り替わりそうな値...
k として i * n - j + 1 ~ i * n - 1 あたりを採用すると特有...
また，[1][2][3]全てに命令を入れれば基本的に特異な動きには...
実際に以下の二つのコードを動かしてみましょう
a(X):sa(X-27)a(X-4)ra(X+52)
a(29)
#ref(HOJ_12Bapp_03.png,nolink)
a(X):sa(X-27)a(X-4)ra(X+53)
a(29)
#ref(HOJ_12Bapp_04.png,nolink)
一つ目は 2(初項) [7 3 7] [7 3 7]...という数列を実現します...
二つ目は 2(初項) [3 7 3] [3 7 3]...という数列を実現します...
12B構文と異なるのは，数列に現れる数の差をある程度大きくで...
次に，実際に数列を作成してみましょう．~
実際に作成するとなると，出てくる数値の調整はともかく，周...
問題1 5 9 2 9 9 2 9 9 2 9~
問題2 2 7 6 3 7 6 3 7 6 3~
---
答え1
a(X):sa(X-35)a(X-4)ra(X+33)
a(142)
前の例と合わせて a b a a b a （a>b) というタイプの数列を...
i = (a - 1) * 4 + 3 , j = 4, k = (a - 1) * 4 + 1 + (b - 2...
と置くとうまくいきます．a < b のケースも一般化してみてく...
答え2
a(X):sa(X-27)a(X-5)ra(X+51)
a(29)
こういう数列も実現可能です．~
jをいじってどんな周期が実現できるか実験するのが良いと思い...
最後に，いくつか綺麗な模様を紹介して終わります．いろんな...
まだまだ未知な部分も多いので調査して行って欲しい範囲です．~
a(X):sa(X-43)rsla(X-17)ra(X+165)
a(2)
#ref(HOJ_12Bapp_05.png,nolink)
a(X):sa(X-144)sra(X-52)ssa(X+159)
a(2)
#ref(HOJ_12Bapp_06.png,nolink)
a(X):sa(X-43)rsra(X-17)ra(X+165)
a(2)
#ref(HOJ_12Bapp_07.png,nolink)
関連問題: [[Problem 1589]] [[Problem 1955]] [[Problem 197...
**3. クレイジー12B構文 [#dd33d0bb]
命名は_misakiさんの雑記から引用しています．~
まずは12B構文を一般化して表記した以下の形を確認してみまし...
a(T):[1]a(AT+B)[2]a(CT+D) a(E)
AT+Bの部分について，上記の構文が意味をなすものに絞ってみ...
・途中で255を超えない
・繰り返す途中で0以下になる
基本的なケースにおいては，上記条件をすべて満たし，意味づ...
Aの正負で少し状況が変わるので，それぞれ見ていきましょう．
***Aが正の時 [#p12e28bf]
Bは負なので，見易さのためにAT-B （B>0) と書き直すことに...
発散を防ぐために，代入後に値が小さくなる必要があることを...
この辺に注意をして，数値設定をする必要があります．~
こちらも応用が効きそうなものや綺麗な模様がたくさんありま...
いくつかの例を紹介しておきます．
a(X):sa(X+X-113)ra(X+13)
a(11)
#ref(HOJ_12Bapp_08.png,nolink)
a(X):sa(X+X-177)ra(X+X)
a(1)
#ref(HOJ_12Bapp_09.png,nolink)
a(X):sa(X+X-169)ra(169-X)
a(1)
#ref(HOJ_12Bapp_10.png,nolink)
（見やすくするために最初ちょっと移動してます）
CT+Dの部分は大きすぎると桁溢れしてしまいます．CはA以下ま...
また，Aが3以上になるとAT-Bが0以下になるスピードが一気に高...
***Aが負の時 [#kb3c00e1]
A=-1は二種類の値が交互に出てきてしまう形になるため，意味...
Aが正の時と異なり，一項目で発散由来の条件に気をつける必要...
いくつかの例を紹介します．
a(X):sa(219-X-X)ra(229-X)
a(1)
#ref(HOJ_12Bapp_11.png,nolink)
a(X):sa(109-X-X)la(X-9)
a(1)
#ref(HOJ_12Bapp_12.png,nolink)
どの形についても，周期的に繰り返される影響で見た目自体は...
また，この手法だと基本的な12B構文（後ろ側をいじるもの）よ...
関連問題: [[Problem 2068]], [[Problem 2071]]~
2068はa(X):sa(X+X-n)la(X+X) a(m) のパターンです．大まかな...
2070は実は盤面上の数字を使うと当てはまるものがあったりし...
**4. 様々な問題への適用 [#h959a61a]
12B構文は非常に汎用性が高く，様々な応用があります．上で述...
ひとまず三つ紹介します．~
*** 4-1 向きを動かす12B構文 [#e5c92175]
12B構文はパーツの長さの数列を制御するもの，という捉え方が...
r ないし l は4の倍数個並ぶと打ち消されるため，特定のパー...
以下の例のようなパーツの並べ方を実現できます．
a(X):ra(X-56)ssa(X+17)
a(2)
#ref(HOJ_12Bapp_13.png,nolink)
また，状況によっては同じ12B構文でもこちらの方法で縮むこと...
a(X):lsrsa(X-3)ra(X+7)
a(2)
a(X):la(X-10)srsa(X+37)
a(2)
#ref(HOJ_12Bapp_14.png,nolink)
上は15Bですが下は14Bになっています．上の向きの無駄を下で...
パーツの両端のどちらかが向きの時はこの圧縮が使える可能性...
関連問題 [[Problem 1705]]
*** 4-2 成長速度を制御する12B構文 [#x00808f6]
基本的な12B構文は特定のパーツを実行する回数の数列を制御す...
以下のコードを実行してみましょう．
a(X,Y):a(sX,Y-5)Xra(X,Y+3)
a(,11)
#ref(HOJ_12Bapp_15.png,nolink)
成長過程の数列に対して適合する12B構文を見つけることでいろ...
関連問題 ~
*** 4-3 パーツ実行回数の方を制御する12B構文 [#y3f9ab37]
4-2のような成長速度を制御するタイプの類似物ですが，パーツ...
以下を見てみましょう．
a(X,Y):Xa(X,Y-5)a(ssX,Y+23)
a(r,11)
#ref(HOJ_12Bapp_16.png,nolink)
渦の長さで言うと次のような数列を実現しています．~
> [0 0 0 2 2 2 2 2 4 4 4 4 4 4 5 5 5 5 5 ]~
同じパーツごとに個数を書く形で整理すると以下の通りです．~
>[0が3個] [2が5個] [4が6個] [6が5個] [8が6個]~
このように成長させたパーツを何回実行するか，という部分を...
関連問題 [[Problem 0091]][[Problem 0372]]など~
平方数の時に成長をいじるタイプもこの手法で圧縮が効くケー...
*** 4-4 12B構文で生成されるパーツを（擬似的に）使い回す [...
4-2とほぼ同様ですが，少し応用的なコードを紹介します.~
まず，有理数の成長にある以下のコードを思い出しましょう．
a(X):sa(X-37)ra(Y+83)
a(1)
~
ロの字を書くコードになります．このロ字をパーツとしていろ...
そこで，以下のコードを実行してみてください．
a(X,Y):a(X-37,Ys)Ya(X+83,Yr)
a(1,)
#ref(12B_new_app.png,nolink)
12B構文で生成しているパーツの途中経過を二変数目に保存して...
うまい活用方法は現在調査中です．
----
以上四つを紹介しました．当然数値の部分についてクレイジー1...
特に乱歩的構成（12B構文のB,Dがマイナスのパターン）と4-2や...
**5. solver作成時の注意点および枝刈りポイント [#ref46524]
本構文を用いた解を見つけるときに，理由づけがしにくいもの...
もちろん安直に作成しても良いですが，使用用途に応じて形ご...
----
***数列作成 [#z99a12c0]
mapに対して解けるかどうか，ではなく数列のみを照合するプロ...
HOJの仕組み上，天井関数で数列が決まる点に注意です．~
----
***solverの分類 [#yb53dc69]
12B構文のA,B,C,Dの正負に応じてsolverを分けてしまうという...
特にBとDがマイナスとなるケースは，第二項の後ろに命令をつ...
また，Dは0でも意味のあるケースが存在する点に注意です．
----
***乱歩的構成の枝刈り [#h9ec95df]
a(X):[0]a(X-i)[1]a(X-j)[2] a(k)という形のものの検索につい...
もっと良いものもあるかもしれません．全てを検索するのはど...
-i,j<k~
-a(X-i)やa(X-j)が4回以上呼ばれる（少なすぎる動作ステップ...
-[0]がsで壁にぶつかるケースや[0]が空文字のケースでa(k)はa...
-i,jの最大公約数は1~
i,jの最大公約数をgとすると, a(X):a(X-i/g)a(X-j/g) a(c...
----
執筆：Ktya
終了行:
[[HOJ講座]]
*12B構文続編 [#x5007692]
まず，12B構文自体が初耳という方は[[有理数の成長速度2]]を...
本講座は，12B構文を使いこなす上でポイントとなりうる点を，...
12B構文及びその変種についてはmasさんが書いた講座[[12B構文...
執筆者も当然使いこなせているわけではないので，他にポイン...
やや長くなったので目次を先に書いておきます．~
�‘団蠅寮�長段階切り出し~
��15B構文？~
��クレイジー12B構文~
�ね諭垢扮�用~
��solver作成時の注意点および枝刈りポイント~
**1. 特定の成長段階切り出し [#w4bef241]
こちらは12B構文の記事の「より複雑な構文」にて説明されてい...
以下のコードを実行してみましょう．
a(X):a(X-1)sa(X-1)l
a(9)
#ref(HOJ_12Bapp_01.png,nolink)
本コードは以下のコードにて実行されるXの10段階目を展開する...
f(X):Xf(XsXl)
f()
実際数値を用いて以下のように書くと同一の動きを書くことが...
a(X):a(X-1)sa(X-1)l
b(X):a(X)b(X+1)
b(1)
例題: [[Problem 2001]] ~
続いて以下のコードを見てみましょう．
a(X):a(X-1)sa(X-2)l
a(9)
#ref(HOJ_12Bapp_02.png,nolink)
このコードも実は以下の10段階目を切り抜いている，と説明で...
f(X,Y):Xf(XsYl,X)
f(,)
実際に以下を実行すると同一の動きが実現されていると確認で...
a(X):a(X-1)sa(X-2)l
b(X):a(X)b(X+1)
b(1)
一般にa(X):ua(X-n)va(X-m)w という書き方では，u [n段階前の...
(max(n,m)変数で実行部単一文字，初項はなし，というコードが...
基本的に既存の乱歩の成長段階ズラして組み合わせたものを実...
検索している人が多くない印象なので，今15B以下のbest解でも...
----
ちなみに小ネタになりますが，乱歩的な動きの方は実は https...
ただし後ろを+にして規則的動きを実現する，いわゆる「12B構...
このコラム（？）によると1424は本家マシンで実行3時間かかっ...
ガチ勢に知識の共有を求めている文章もあって，こういうのを...
**2. 15B構文？ [#h5a5e392]
ここでは
a(X):[1]a(X-i)[2]a(X-j)[3]a(X+k)
a(n)
という形の構文について触れます．i,j,k,nは正整数です．意味...
構造としてはiで割った商の回数[1]を実行し，iで割ったあまり...
構造上，以下の制約があります．
-a(X-i)の部分が定期的に実行されるために j-1+k > i
-a(X-j)の部分が実行されるために，i > j
また，12B構文で実現可能な動きとの差別化を図る上で i は j ...
最後の X+k が「 i で割った商がちょうど切り替わりそうな値...
k として i * n - j + 1 ~ i * n - 1 あたりを採用すると特有...
また，[1][2][3]全てに命令を入れれば基本的に特異な動きには...
実際に以下の二つのコードを動かしてみましょう
a(X):sa(X-27)a(X-4)ra(X+52)
a(29)
#ref(HOJ_12Bapp_03.png,nolink)
a(X):sa(X-27)a(X-4)ra(X+53)
a(29)
#ref(HOJ_12Bapp_04.png,nolink)
一つ目は 2(初項) [7 3 7] [7 3 7]...という数列を実現します...
二つ目は 2(初項) [3 7 3] [3 7 3]...という数列を実現します...
12B構文と異なるのは，数列に現れる数の差をある程度大きくで...
次に，実際に数列を作成してみましょう．~
実際に作成するとなると，出てくる数値の調整はともかく，周...
問題1 5 9 2 9 9 2 9 9 2 9~
問題2 2 7 6 3 7 6 3 7 6 3~
---
答え1
a(X):sa(X-35)a(X-4)ra(X+33)
a(142)
前の例と合わせて a b a a b a （a>b) というタイプの数列を...
i = (a - 1) * 4 + 3 , j = 4, k = (a - 1) * 4 + 1 + (b - 2...
と置くとうまくいきます．a < b のケースも一般化してみてく...
答え2
a(X):sa(X-27)a(X-5)ra(X+51)
a(29)
こういう数列も実現可能です．~
jをいじってどんな周期が実現できるか実験するのが良いと思い...
最後に，いくつか綺麗な模様を紹介して終わります．いろんな...
まだまだ未知な部分も多いので調査して行って欲しい範囲です．~
a(X):sa(X-43)rsla(X-17)ra(X+165)
a(2)
#ref(HOJ_12Bapp_05.png,nolink)
a(X):sa(X-144)sra(X-52)ssa(X+159)
a(2)
#ref(HOJ_12Bapp_06.png,nolink)
a(X):sa(X-43)rsra(X-17)ra(X+165)
a(2)
#ref(HOJ_12Bapp_07.png,nolink)
関連問題: [[Problem 1589]] [[Problem 1955]] [[Problem 197...
**3. クレイジー12B構文 [#dd33d0bb]
命名は_misakiさんの雑記から引用しています．~
まずは12B構文を一般化して表記した以下の形を確認してみまし...
a(T):[1]a(AT+B)[2]a(CT+D) a(E)
AT+Bの部分について，上記の構文が意味をなすものに絞ってみ...
・途中で255を超えない
・繰り返す途中で0以下になる
基本的なケースにおいては，上記条件をすべて満たし，意味づ...
Aの正負で少し状況が変わるので，それぞれ見ていきましょう．
***Aが正の時 [#p12e28bf]
Bは負なので，見易さのためにAT-B （B>0) と書き直すことに...
発散を防ぐために，代入後に値が小さくなる必要があることを...
この辺に注意をして，数値設定をする必要があります．~
こちらも応用が効きそうなものや綺麗な模様がたくさんありま...
いくつかの例を紹介しておきます．
a(X):sa(X+X-113)ra(X+13)
a(11)
#ref(HOJ_12Bapp_08.png,nolink)
a(X):sa(X+X-177)ra(X+X)
a(1)
#ref(HOJ_12Bapp_09.png,nolink)
a(X):sa(X+X-169)ra(169-X)
a(1)
#ref(HOJ_12Bapp_10.png,nolink)
（見やすくするために最初ちょっと移動してます）
CT+Dの部分は大きすぎると桁溢れしてしまいます．CはA以下ま...
また，Aが3以上になるとAT-Bが0以下になるスピードが一気に高...
***Aが負の時 [#kb3c00e1]
A=-1は二種類の値が交互に出てきてしまう形になるため，意味...
Aが正の時と異なり，一項目で発散由来の条件に気をつける必要...
いくつかの例を紹介します．
a(X):sa(219-X-X)ra(229-X)
a(1)
#ref(HOJ_12Bapp_11.png,nolink)
a(X):sa(109-X-X)la(X-9)
a(1)
#ref(HOJ_12Bapp_12.png,nolink)
どの形についても，周期的に繰り返される影響で見た目自体は...
また，この手法だと基本的な12B構文（後ろ側をいじるもの）よ...
関連問題: [[Problem 2068]], [[Problem 2071]]~
2068はa(X):sa(X+X-n)la(X+X) a(m) のパターンです．大まかな...
2070は実は盤面上の数字を使うと当てはまるものがあったりし...
**4. 様々な問題への適用 [#h959a61a]
12B構文は非常に汎用性が高く，様々な応用があります．上で述...
ひとまず三つ紹介します．~
*** 4-1 向きを動かす12B構文 [#e5c92175]
12B構文はパーツの長さの数列を制御するもの，という捉え方が...
r ないし l は4の倍数個並ぶと打ち消されるため，特定のパー...
以下の例のようなパーツの並べ方を実現できます．
a(X):ra(X-56)ssa(X+17)
a(2)
#ref(HOJ_12Bapp_13.png,nolink)
また，状況によっては同じ12B構文でもこちらの方法で縮むこと...
a(X):lsrsa(X-3)ra(X+7)
a(2)
a(X):la(X-10)srsa(X+37)
a(2)
#ref(HOJ_12Bapp_14.png,nolink)
上は15Bですが下は14Bになっています．上の向きの無駄を下で...
パーツの両端のどちらかが向きの時はこの圧縮が使える可能性...
関連問題 [[Problem 1705]]
*** 4-2 成長速度を制御する12B構文 [#x00808f6]
基本的な12B構文は特定のパーツを実行する回数の数列を制御す...
以下のコードを実行してみましょう．
a(X,Y):a(sX,Y-5)Xra(X,Y+3)
a(,11)
#ref(HOJ_12Bapp_15.png,nolink)
成長過程の数列に対して適合する12B構文を見つけることでいろ...
関連問題 ~
*** 4-3 パーツ実行回数の方を制御する12B構文 [#y3f9ab37]
4-2のような成長速度を制御するタイプの類似物ですが，パーツ...
以下を見てみましょう．
a(X,Y):Xa(X,Y-5)a(ssX,Y+23)
a(r,11)
#ref(HOJ_12Bapp_16.png,nolink)
渦の長さで言うと次のような数列を実現しています．~
> [0 0 0 2 2 2 2 2 4 4 4 4 4 4 5 5 5 5 5 ]~
同じパーツごとに個数を書く形で整理すると以下の通りです．~
>[0が3個] [2が5個] [4が6個] [6が5個] [8が6個]~
このように成長させたパーツを何回実行するか，という部分を...
関連問題 [[Problem 0091]][[Problem 0372]]など~
平方数の時に成長をいじるタイプもこの手法で圧縮が効くケー...
*** 4-4 12B構文で生成されるパーツを（擬似的に）使い回す [...
4-2とほぼ同様ですが，少し応用的なコードを紹介します.~
まず，有理数の成長にある以下のコードを思い出しましょう．
a(X):sa(X-37)ra(Y+83)
a(1)
~
ロの字を書くコードになります．このロ字をパーツとしていろ...
そこで，以下のコードを実行してみてください．
a(X,Y):a(X-37,Ys)Ya(X+83,Yr)
a(1,)
#ref(12B_new_app.png,nolink)
12B構文で生成しているパーツの途中経過を二変数目に保存して...
うまい活用方法は現在調査中です．
----
以上四つを紹介しました．当然数値の部分についてクレイジー1...
特に乱歩的構成（12B構文のB,Dがマイナスのパターン）と4-2や...
**5. solver作成時の注意点および枝刈りポイント [#ref46524]
本構文を用いた解を見つけるときに，理由づけがしにくいもの...
もちろん安直に作成しても良いですが，使用用途に応じて形ご...
----
***数列作成 [#z99a12c0]
mapに対して解けるかどうか，ではなく数列のみを照合するプロ...
HOJの仕組み上，天井関数で数列が決まる点に注意です．~
----
***solverの分類 [#yb53dc69]
12B構文のA,B,C,Dの正負に応じてsolverを分けてしまうという...
特にBとDがマイナスとなるケースは，第二項の後ろに命令をつ...
また，Dは0でも意味のあるケースが存在する点に注意です．
----
***乱歩的構成の枝刈り [#h9ec95df]
a(X):[0]a(X-i)[1]a(X-j)[2] a(k)という形のものの検索につい...
もっと良いものもあるかもしれません．全てを検索するのはど...
-i,j<k~
-a(X-i)やa(X-j)が4回以上呼ばれる（少なすぎる動作ステップ...
-[0]がsで壁にぶつかるケースや[0]が空文字のケースでa(k)はa...
-i,jの最大公約数は1~
i,jの最大公約数をgとすると, a(X):a(X-i/g)a(X-j/g) a(c...
----
執筆：Ktya
ページ名:
![[PukiWiki]](image/hojwiki.png "[PukiWiki]")
