読者です 読者をやめる 読者になる 読者になる

Xmas Contest 2016 B解説

B問題のギャラリーと解説です。


自由度の高い問題で、様々な解答があったため、12/26時点で1点以上取っている解答をvisualizeしてみました。
細長いものは縦横比が1:1なるように引き伸ばされているので注意です。
様々な工夫の凝らされたアートを鑑賞することができ、圧巻です。

ギャラリー:XmasContest2016B
「すべてダウンロード」をしていただくと、ファイル名(点数-user名の形式)がご覧になれます。

この中から、特に独創性/芸術性が高いと思ったものをpick upしてみました。

f:id:snuke:20161227081000p:plain
Hecさんの17点解です。
美しい。。
方針も面白くて、とりあえず三角形状に並べようとして、もし辺上に点があるようならgcdを取って辺を短くする、というような感じです。
コードも読みやすいので興味があれば読んでみるといいのではないかと思います。

f:id:snuke:20161227081109p:plain
untanさんの17点解です。
このタイプの解答自体はかなり多かったのですが、この作品には髭が生えていました。
この髭は一体なんなのでしょうか?
恐らく、右下の頂点を右上に放り出すことによって座標を1小さくしようとしたのではないかと予想しています。

f:id:snuke:20161227081429p:plain
obsprothさんの24点解です。
17点解を線対称にして幅を半分にする解答はいくつかありましたが、こちらは点対称にしています。
長方形にピッタリ収まっているあたりがクールです。

f:id:snuke:20161227081848p:plain
sugopurochakkuさんの24点解です。
多くの解答が縦(横)方向に点を並べている中、この解答では斜めに並べています。

f:id:snuke:20161227082041p:plain
omeometoさんの59点解です。
Stern–Brocot木を4方向に生やしています。
非常にスタイリッシュです。

f:id:snuke:20161227082251p:plain
cookie_marisaさんの70点解です。
縦と斜めを交互に使った見事なフラクタルです。

f:id:snuke:20161227082437p:plain
y3eadgbeさんの76点解です。
H型のフラクタルの末端の部分を縮約するという方針なのですが、縮約された部分の形が独特です。

f:id:snuke:20161227082700p:plain
square869さんの96点解です。
コンテスト時間中にこの高得点を獲得したことに対し敬意を表して。
このタイプの解答もいくつか見られたのですが、想定しておらず、感動しました。
美しい流線型が魅力的です。

f:id:snuke:20161227083002p:plain
yosssさんの100点解です。
コンテスト終了後ではありましたが、最速の満点を取られたことに敬意を表して。
まったくシンメトリーではないのに、不思議と神秘的な美を感じる図です。


さて、解説です。

まず、50点以上をもっとも楽に取る解法は、stern-brocot木をx=分母,y=分子として埋め込むことだと思います。

f:id:snuke:20161227090327p:plain

そもそもこの問題が出来た流れは「stern-brocot木っていうものがあるのかー」→「平面に埋め込めそう」→「これクリスマスコンかなにかでだそう」→「あれ、これ実はもっと小さく出来ない?」→「理論最小値も達成できそうな気がするな」→「できた」という流れで、stern-brocot木は想定部分点でした。
omeometoさんが開始わずか12分弱でこの解答を提出していてさすがだなぁと思いました。
結局この解答はomeometoさんだけでした。

次の想定部分点は、H型のフラクタル(70点)でした。

f:id:snuke:20161227090647p:plain

横長で、2倍損しています。末端を詰め込んでフラクタルの深さを1減らしてやると89点になります。

f:id:snuke:20161227090940p:plain

満点を取るには64*64にピッタリ収めなければいけません。
1/4ずつのフラクタルを考えると根は真ん中に持ってきたほうが良さそうなことが分かり、
また、分割される各正方形内では1箇所だけ空きマスが生じるはずでその空きマスをどこに持ってくるのかもポイントになりそうだと気づきます。
そして、方針を整理していくと、以下のような4パターンを再帰的に組み合わせればOKであることが分かります。

f:id:snuke:20161227091826j:plain

それで完成図はこうなります。

f:id:snuke:20161227091856p:plain

以上です。