Markov Algorithm Online Test Contestに参加しました Mod 3でTop Playerを取りました

Markov Algorithm Online Test Contestに参加しました。

きみはだれ？

競プロerです。一応Highest水コーダーです。

これはなに？

AtCoderの社員かつレッドコーダーのすぬけさんが作ったマルコフアルゴリズムで遊ぶサイトMarkovAO : Markov Algorithm Onlineがあります。

昨日（2020/05/07）ついにMarkovAO最初のコンテストTest Contestが開催されたので参加しました。

たのしいので感想を書きます。

10問中6問しか解けず137位でした。しかし、自分の発想と問題が噛み合ったのでMod 3のTop Player（初めて最小行のコードを提出した人）になれました。

ネタバレあり。

f:id:hotarunx:20200508020159p:plain — problems

f:id:hotarunx:20200508020204p:plain — standing

#0016 Min

問題へのリンク

Line 1 Best 1

6文字を5文字に置換します。置換できなくなったら停止する。

oooooo:ooooo

0: ooooooo
1: oooooo
2: oooo

#0017 Max

問題へのリンク

Line 2 Best 2

5文字になるまで先頭にoを追加して、5文字になったら何も置換せずに停止します。もし1行目と2行目を逆にすると、永遠に1行目の置換規則が適用されてしまいます。コードの後ろの方の置換規則で先頭に何か文字を追加する処理は典型のようで、いくつかの問題で使われます。

序盤の問題ですが、かなり難しいです。

ooooo::ooooo
:o

0: oo
1: ooo
2: oooo
3: ooooo
4: ooooo

#0018 Win Draw Lose

問題へのリンク

Line 7 Best 7

まずxo:oxで文字列をソートします。（よく考えればxo:ox→xo:でよかった） ox:でoかxの多い方が残ります。答えを回答するためにoo:o,xx:xで残った文字の文字数を1つにして回答して停止します。

xo:ox
ox:
oo:o
xx:x
o::win
x::lose
::draw

0: xoxoo
1: oxxoo
2: oxoxo
3: ooxxo
4: ooxox
5: oooxx
6: oox
7: o
8: win

#0019 Sort 2

問題へのリンク

Line 5 Best 5

答えは必ず12345なので1234を空文字列に置換したあと5を12345に置換して停止します。ギャグ。

1:
2:
3:
4:
5::12345

#0020 Dot

問題へのリンク

Line 13 Best 12

最初の置換で....を先頭において、その後すべての要素をなめるように置換して停止させました。

こういう問題は最初の置換でダミー文字を挿入して最後に消すのが典型のようですが、ダミー文字の代わりに.を複数置いてみました。

各要素を置換する。
ダミー文字を取り除いて停止させる。
ダミー文字を先頭に挿入する。

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

0: 3141592
1: ....3141592
2: ..3...141592
3: ..3.1...41592
4: ..3.1.4...1592
5: ..3.1.4.1...592
6: ..3.1.4.1.5...92
7: ..3.1.4.1.5.9...2
8: ..3.1.4.1.5.9.2...
9: ..3.1.4.1.5.9.2
10: 3.1.4.1.5.9.2

#0023 Mod 3

問題へのリンク

Line 5 Best 5 Top Player

Win Draw Loseと同じ解き方ができると考えて次のコードを書きました。 0はすべて消去。12をソートしつつ11,22を置換。最後に1,2,12が残る。もし12なら0に置換して停止。

0:
11:2
22:1
21:12
12::0

しかし、このコードは入力が0のときにWAする。 0を空文字列ではなく12に置換すればいいとひらめいて終了。

Top Playerになれました。

0:12
11:2
22:1
21:12
12::0

upsolve

2020年6月28日追記

本番で解けなかった問題やります。

#0022 Mode

問題へのリンク

Line 11 Best 8

解法はこうです。

abcをまとめて消す。
1,2種類の文字が残る。
残った2種類の文字を1組ずつ消す。
1種類の文字が残る。
回答のため、残った1文字が2つ以上あるとき、1つにする。

abを#に変換して#cを消すことでabcをまとめて消した。

ランダム文字列未使用（Line 12）

ba:ab
ca:ac
cb:bc

#c:
#b:b#
#:
ab:#
ac:
bc:

aa:a
bb:b
cc:c

ランダム文字列使用（Line 11）

ba:ab
ca:ac
cb:bc

bbbbbbbbbbbbbbbbbbbc:
bbbbbbbbbbbbbbbbbbb:
ab:bbbbbbbbbbbbbbbbbbb
ac:
bc:

aa:a
bb:b
cc:c

bbbbbbbbbbbbbbbbbbb

#0024 Min digit

問題へのリンク

Line 11 Best 8

括弧列テクでMaxを取れます。問題をMaxを取る問題と読み替えて、括弧列テクでMaxを取ります。

5:()
4:(())
3:((()))
2:(((())))
1:((((()))))

)(:

((((()))))  ::1
(((())))    ::2
((()))      ::3
(())        ::4
()          ::5

#0025 Balanced

問題へのリンク

Line 5 Best 5

正しい括弧列ならば、()を消していけば括弧がなくなります。そうでないなら、残った括弧を消してnoに置き換えます。 (を全部)にして重複を消して行きました。

もし)を全部(にしたとすると、文字列を変換中に正しい括弧列になってしまう可能性があります。

():
(:)
)):)
)::no
::yes

#0026 Divide in half

問題へのリンク

Line 7 Best 7

カーソルsを2つ進めるたびにカーソル|を1つ進めます。 sが1つ進むたびにxを起きます。 xが2つあれば|を1つ進めます。

x=00000000000000000(0を17個)に置き換えることで、規則を減らせます。（ランダム文字列テク）

ランダム文字列未使用（Line 8）

|xx0:0|
|xx1:1|
0x:x0
1x:x1
s0:x0s
s1:x1s
s::
:|s

ランダム文字列使用（Line 7）

00000000000000000

|00000000000000000000000000000000000:0|
|00000000000000000000000000000000001:1|
100000000000000000:000000000000000001
s0:000000000000000000s
s1:000000000000000001s
s::
:|s