Markov Algorithm Online Test Contest

https://mao.snuke.org/contests/1

[@snuke_](https://twitter.com/snuke_)さん主催のマルコフアルゴリズムで闘うプログラミングコンテスト。面白い。全問解いた。でも、順位は提出順ではなく、コード行数なので70位。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/a3d6d813-cf28-8a8d-7400-550382e7af7b.png)

## マルコフアルゴリズムとは

[https://ja.wikipedia.org/wiki/マルコフアルゴリズム](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%82%B3%E3%83%95%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)

文字列の置換はチューリング完全。チューリング完全なので、理屈の上では好きなプログラミング言語で書いて変換できるはずだけど、まあ、コード長の制限とかもあるし、ちゃんと考える必要がある。

## 私の回答

### Min

https://mao.snuke.org/tasks/16

`oo...o` の長さを5文字以下にする。

入力が10通りしかないので全部並べても良いのだけど、最短を狙うなら6文字以上を短くする。

```
oooooo:ooooo
```

### Max

https://mao.snuke.org/tasks/17

5文字以上にする。

`ooooo`が存在すれば終了。そうでなければ伸ばす。

```
ooooo::ooooo
o:oo
```

### Win Draw Lose

https://mao.snuke.org/tasks/18

`o`と`x`のどちらが多いかで、`win`、`draw`、`lose`を答える。

`ox`と`xo`を消していって、残ったほうを……でいけるよね？と思いきや、嫌らしいことに`lose`には`o`が含まれている。`o`と`x`を一旦`0`と`1`に変換した。あとは`01`と`10`を消して、結果を整形。

```
01:
10:
win0:win
0win:win
win::win
lose1:lose
1lose:lose
lose::lose
o:0
x:1
0:win
1:lose
::draw
```

### Sort 2

https://mao.snuke.org/tasks/19

`1`から`5`の順列をソート。

何も考えずにスクリプトで以下のコードを生成した。これは`1`から`5`が含まれる任意の文字列をソートできるので、順列ということを何かしら活用すると最短の5行になるのだろうか？

```
21:12
31:13
41:14
51:15
32:23
42:24
52:25
43:34
53:35
54:45
```

### Dot

https://mao.snuke.org/tasks/20

ドットを挿入する。`3141592`を`3.1.4.1.5.9.2`にする。

最初は、

```
00:0.0
01:0.1
02:0.2
03:0.3
 :
```

という100行のコードを提出した。

先頭に`!`を付けて、`!`を右に動かしつつ`.`を挿入するようにして最短。

```
!1:1.!
!2:2.!
!3:3.!
!4:4.!
!5:5.!
!6:6.!
!7:7.!
!8:8.!
!9:9.!
!0:0.!
.!::
:!
```

### Mode

https://mao.snuke.org/tasks/22

`a`、`b`、`c`のみが含まれる文字列のうちもっとも多い文字を答える。

「`ab`とか`bc`とか2文字ごとに消していけば良いんじゃないの？」は、`abac`でダメ。`abc`はセットで消さないといけない。

`ab`と`ba`を`x`にして、`xc`と`cx`を消すということを考えた。`bc`は`y`にして、`xy`ならば`b`が1個余るので`b`にする。あとは、残った`xyz`を消して、`aa:a`などで1文字に。で、サンプルケースは通るものの、提出するとwrong answer。

考えても分からないので、急いでマルコフアルゴリズムを実行するスクリプトを書いて、ランダムケースを突っ込んだ。`cbcbab`が`cybx`でダメだった。`xyz`を後ろに送るようにして通した。

```
ab:x
ba:x
bc:y
cb:y
ac:z
ca:z
cx:
xc:
ay:
ya:
bz:
zb:
xa:ax
xb:bx
yb:by
yc:cy
za:az
zc:cz
xy:b
yx:b
yz:c
zy:c
xz:a
zx:a
x:
y:
z:
aa:a
bb:b
cc:c
```

### Mod 3

https://mao.snuke.org/tasks/23

`012`からなる数値列の各桁の和を3で割った余りを求める。

これは（最短を目指さなければ）簡単。

```
00:0
01:1
02:2
10:1
11:2
12:0
20:2
21:0
22:1
```

### Min digit

`1`～`5`の数値列の最小値を答える。

これも（最短を目指さなければ）簡単。

```
11:1
12:1
13:1
14:1
15:1
21:1
22:2
23:2
24:2
25:2
31:1
32:2
33:3
34:3
35:3
41:1
42:2
43:3
44:4
45:4
51:1
52:2
53:3
54:4
55:5
```

### Balanced

https://mao.snuke.org/tasks/25

括弧列が正しいかどうかを`yes` `no`で答える。

`()`を消していけば良い。最初は、（たしか）`(:no`のあとに`(no:no`を書いていて、`Code has an unreachable line.`を喰らった。ブラウザでは動くけど、サーバーでは到達しない条件があるとダメらしい。わざわざ弾くこともなさそうだけど、何か前処理をしているのだろうか :thinking: 

```
():
(:no
):no
nono:no
no::no
::yes
```

### Divide in half

https://mao.snuke.org/tasks/26

ビット列の中央に`|`を挿入する。

正解者数的に一番難しい問題。

1. 両端に`[`と`]`を挿入して、`[01101000]`のようにする
2. `]`を`!`にする（この後、左に動かしたいけれど、`]`のままだと右端に挿入する処理が動いて右に戻ってしまう）
2. 左側の`[`を1文字右に動かしつつ`x`を打ち出す
3. 右側の`]`は`x`を受け取ったら、1文字左に動いて、`y`を打ち出す
4. 中央に`[]`が来たら`|`にして終了

`y`を左に打ち出す処理、要らない気がするな :thinking: 　最初は`y`を受け取ったら`[`を動かすとか考えていたのかもしれない。

```
]0:0]
]1:1]
]:!
x0!:y!0
x1!:y!1
x0:0x
x1:1x
0y:y0
1y:y1
y:
[0:0[x
[1:1[x
[!::|
:[]
```