LoginSignup
8

More than 3 years have passed since last update.

【MarkovAO】マルコフアルゴリズムの典型テクニックまとめてみた

Last updated at Posted at 2020-05-25

前書き

初心者用&備忘録(ネタバレを含みます)
空白をわかりやすいように_で示します
MarkovAOのテクニック集的なあれです

カーソルテク

sという文字の後ろのみを変更するという規則を使い規則の暴発を防いだり色々する基本テク
以下はMarkovAOの0009の例
s0:1s
s1:0s
s::
_:s

文字送り(仮称)

文字を前や後ろに持っていきたい場合、カーソルを付けて、
s01:1s0
s10:0s1
s00:0s0
s11:1s1(後ろに持っていく場合)
とするのがすぐに思いつくと思うが、これでは文字数が増えた際O((文字数)^2)の命令数がかかって効率が悪い、そこで
s0:o
s1:oo
o0:0o
o1:1o
o:0
oo:1
というように一旦oに置き換えてから前や後ろに持っていき最後に0や1に変える事で、O((文字数))で文字を端に寄せることが出来る

括弧テク

色々奥が深い(らしい)テク
一番初歩的なのは
(((())))((()))
から)(を繰り返し取除くと
(((())))となることを利用して最大値を求めるテク
他にも色々あります
【MarkovAO】括弧列テクについて知っていることをまとめてみた

ユピテルさんがわかりやすくまとめてくれました!!

(原始的な)大小比較テク

1~5の数字の大小は
oooo|ooo
の様にシンプルな丸と仕切りで表してから
ooooo|ooooo
oooo|oooo
ooo|ooo
oo|oo
o|o
をなにかに置き換えてoが残ったほうと考える事ができる
左を数字のままにして
5ooooo
4oooo
3ooo
2oo
1o
を考えるのも良い

oの数をNで割った余りに置き換える

例えば3で割った余りは
oooo:o
とする、これだと3%3=3じゃないか!
と思うがそちらのほうが都合がいい場合が多い
もちろん3%3=0のほうが都合がいい場合はooo:_とする

文字数を減らす

golfを狙う場合基本的には使用する文字数を減らしたほうがいい
例えば
s010100101t0101001
の様な状況でsを左から右に持って行かないと行けない場合
st:tsを省くため、
tに当たる文字を予め10110111011110111110にしておくという手がある
01と混じらないのかと思うが、これは適切に扱えば混じらない
逆にraceの場合積極的に文字数を増やしておく事で暴発を防げる

足し算の基本

右から左に足すのを心がける
下の桁は左だからそれはそう(fastestがどうなってるかはしらない)

あとがき

adhocの中でも特に汎用性の高いテクをまとめたつもり

...この記事いる?

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
8