『デスコロC #1』の感想
はじめに
『デスコロC #1』で優勝しました！
前回が最終回だった tbpgr さんの『デスマコロシアム』シリーズを引き継いで、新たに ciel さんの『デスコロC』シリーズが始まりました。企画の内容は前シリーズとほとんど変わっていないはずですが、出題者が交代した影響は想像以上に大きいようで、全く違った雰囲気になっています。一言で言うと、超ガチです。スーパーガチです。その理由は、主に次の2点です。
- 『デスマコロシアム』シリーズ最大の特徴であった、役によるバトルが、バッサリとカットされ、一切の運要素が排除されています。
- 前シリーズでは、コード長と言語ペナルティがトップに届いていなくても、僅差ならバトルでの逆転に期待することができましたし、大差でも「デスマーチ」による一発逆転が用意されていました。これにより、誰もが優勝の可能性を持って参加できました。
- 今シリーズでは、純粋にコード長と言語ペナルティだけで競うため、トップに1ポイントでも負けていれば、絶対に優勝できず、絶望するしかありません。逆に言うと、トップの人はトーナメントの組み合わせにかかわらず優勝が約束されています。
- 出力文字列が、かなり複雑なものになっています。もはや、コーディングの工夫だけではどうにもならず、知識、考察、閃きなどの総合力が試されます。
また、途中経過が毎日ではなく数日おきだったり、ツイートのまとめが行われなかったりしたことも、ストイックさを醸し出す要因になっていたと思います。
私は、初日に2桁バイトのコードを提出し、そのまま最後までアベベのごとく独走状態でした。初日に提出した時点では、暫定トップに立ってみたもののすぐに追いつかれて後はガチゴルフ勝負、といういつもの展開を予想していたのですが、意外な展開となってしまいました。
私の解答
print/.$/gfor sort map/.{999}/?$_=$'.$&:y/9Zz0-z/Aa0-z/<s/s$/sNtUUVb/,(A^eUVb)x3822Perl (83) です。3822回ループを回していますが、このうち先の2822回で1000文字のデータを生成し、後の1000回で1文字ずつローテートさせながら、ソートして出力しています。
問題の解説
この問題の出力文字列は、ある文字列をブロックソート（BWT）した結果になっています。短いコードを書くためには、このことに気付かなければなりません。
どうすればこれがブロックソートだと気付くのでしょうか？ 出力文字列を見てまず気付くのは、同じ文字が連続して現れるなど、ある程度の規則性があることです。もちろん、今までのデスマコロシアムの出力文字列にも規則性がありました。今回違うのは、規則性がありながらも、具体的に調べていくと、細かい部分が不規則になっていて、これをそのままコードに落とすのは困難だということです。
次に気付くべきは、文字列の先頭付近にある、あからさまに怪しい $ の文字です。いかにも何かの終端を表していそうです。ところで、上記の Wikipedia の記事によると、ブロックソートの変換後のデータは「ccoaa, 3」のように、変換後の文字列と開始位置の組で表されています。しかし、変換前の文字列に終端文字を付加しておけば、開始位置の情報を別途持たなくても、変換後の文字列に埋め込まれた終端文字の位置から特定することができ、実際にそのような実装も存在します。
したがって、
- ブロックソートの結果は同じ文字が連続する傾向がある
- ブロックソートをするときには終端文字を付加することがある
この2つを知っていれば、もしかしてブロックソートかな？ と気付くことができます。
推測ができたところで、実際にブロックソートであることを確認してみます。まず、出力文字列に現れる文字の出現頻度を、ASCIIコード順に調べると、次のようになります。
| 文字 | 頻度 |
|---|---|
| $ | 1 |
| 0 | 16 |
| 1 | 16 |
| 2 | 16 |
| 3 | 16 |
| 4 | 17 |
| 5 | 17 |
| 6 | 15 |
| … | … |
次に、出力文字列を、先頭から、この頻度に従って切り分けてみます。
| 文字 | 頻度 | 文字列 |
|---|---|---|
| $ | 1 | b |
| 0 | 16 | PP00$zzzuuuVVUUU |
| 1 | 16 | QQ11000vvvWWWVVV |
| 2 | 16 | RRR22211wwXXXWWW |
| 3 | 16 | SSS333222xxYYYXX |
| 4 | 17 | TTT444333yyyZZZYY |
| 5 | 17 | UUU555444zzzaaZZZ |
| 6 | 15 | VV66555000bbaaa |
ちょうどいい位置で切れていますね。ブロックソートで間違いなさそうです。
次に、ブロックソートする前の文字列の生成ですが、結果記事によると、「線形合同法っぽい方法で生成」できるようです。これは全く気付きませんでした（○○○○○=「ROT13」かな？とか思っていました）。もし気付いていたら、もっと違ったコードになっていたかもしれませんね。私のコードでは、この文字列を6文字単位のローテートと解釈して、 y と s を使ってなんとか生成しています。
（2015/11/7追記）「線形合同法っぽい方法」の部分について、 angel さん（アイコンが急にかわいくなった！）が詳しく考察されています。
ところで、ブロックソートは、データを縮めるための前処理として行われるものですが、今回はコードを縮めるためにわざわざ圧縮元のデータに遡るところが面白いと思いました。下手をしたら、圧縮データを埋め込んで逆符号化したほうが短くなるなんてことにもなりかねないわけで、うまくバランス調整されていると感じました。
まとめ
今回の問題はかなり難易度が高かったようで、題意通りに解けた人がわずかしかいなかったとのことですが、私としては、今までの問題よりパズル的な要素が強くて、とても楽しめました。
ciel さん、出題及び集計お疲れ様でした。次回も楽しみにしています。
