第20回

名称

SSSK

日時

2021/11/20 16:00～17:20

場所

Zoom

参加者

6名

概要

加藤	サイトスワップ数独
セバスちゃん	サイトスワップから状態数を求める
西野	サイトスワップから状態数を求める
森下	サイトスワップ手書き略記
セバスちゃん	シンプルで読み難いマルチハンドの表記法
セバスちゃん	ジャグリング競技プログラミング

サイトスワップ数独

数独のルールに加え、タテ、ヨコ、3×3ブロックの9個の数字の並びがいずれもサイトスワップになっていなければならないというもの。こちらのサイト に絵付きの詳しい説明と実際に遊べる機能があります。その上データ保存、問題生成、自動解答とこれ以上ないぐらい機能が豊富です。

タテ、ヨコ、3×3ブロックがサイトスワップのものを「完全サイトスワップ数独」、タテ、ヨコだけのものを「部分サイトスワップ数独」と呼び、前者は324個、後者は14,256個の解盤面があるそうです（既に数え上げられている！）。通常の数独の解盤面が 6.67×10²¹ 個あると言われていることから考えるとサイトスワップ条件はかなりきつい制約のようで、中にはヒントマス2個で解が決定するものもあるそうです。それはとても手で解けそうにない…

サイトスワップから状態数を求める

2年前の [SSS18] で提示された、与えられた周期サイトスワップからその状態数を求める問題の解法についてです。

まず各桁の数字に対し後ろから 0, 1, 2, … を引きます。例えばサイトスワップ 531 なら 210 を引いて 321 とします。結果のそれぞれの値が状態数（二進数）で 1 のある桁に対応します。この場合は3桁目と2桁目と1桁目に 1 があるということで状態数は 111 です。

引き算の結果が 0 以下になった場合は無視し、周期を超えている場合は周期を引いた値も考慮します。例えばサイトスワップ 315 なら 210 を引いて 105 となるので 0 は無視し、5 は周期の 3 を超えているので 3 を引いた 2 も状態数の 1 のある桁になります。結果的に 1, 5, 2 が有効となるため状態数は 10011 です。

この方法は、状態数は時間軸上でのボールの着地点という意味をなぞって構成されています。

サイトスワップから状態数を求める

同じ議題ですが、西野さんの解法はまた違った観点を出発点にしています。

まずサイトスワップを十分な長さ、具体的には最大の投げの高さまで繰り返します。531 を例にとると最大高さが 5 なので5桁になるまで繰り返して 53153 とします。次にそれと同じ長さの降順数列 54321 を作成して桁ごとに比較します。この降順数列は何拍前に投げたかを表します。前者が後者以上のとき 1 を、後者未満のとき 0 として並べます。この場合左から 1, 4, 5桁目が 1 で 2, 3桁目が 0 なので 10011 となります。1 はボールが空中にまだいることを意味するはずだからこの列が状態数になるという考えです。

同じように 315 なら 31531、153 なら 15315 を考えることで状態数 111、1101 が出せます。

操作が単純なので実用的です。しかし、色々計算してみると微妙に合わない場合もあり、謎が生まれているようです。皆で検討した結果、逆再生サイトスワップの状態数を見ているのでは？ という意見が出されました。

サイトスワップ手書き略記

サイトスワップの一般的な表記法は広く定着していますが、あれこれ考えながら紙上に手書きするのにはそれほど向いていません。そこで標準ルールで混同されにくく、 手書きが楽な表記を考えてみたという内容です。詳細は以下の通りです。

• 10以上のサイトスワップは b → 1.1 （b = 11 = 1.1e+1 というイメージ）
• マルチは [33] → 3+3、[333] → 3+3+3
• シンクロは (6,6) → 6-6
• シンクロクロススローは 6x → 6 あるいは 6^
• 空白、コンマは好きなときに使っていい

アルファベットは数字として分かりにくい、括弧はややこしく思考の流れを止める、x はより書きやすく表記できる、空白とコンマは手書きだと自然であるという理由からです。サイトスワップについては高さ 99 まで考えるとします。

別案として10以上のサイトスワップは 1¹ のように2桁目を上付きで小さく書くというものもあります。他の案もあれば見てみたいとのことでした。会場からのコメントとして、色分けを活用するのはどうか、シンクロは2列表記が考えやすいし自然なのでいい感じに表記できないかというものがありました。

シンプルで読み難いマルチハンドの表記法

手が何本もあり、スローのタイミングは合わせているマルチハンドジャグリングを考えます。例としては多人数シンクロパッシングが近いでしょうか。これを表記するには、各時刻のスローの高さの他にどこへ投げるかという送り先を示さねばならず、表記としては煩雑です。その全ての送り先をまとめてたった1つの数で表せる表記法の提案でした。

具体的に手が3本の場合を考えてみます。それぞれの手を A, B, C とし、ある時刻で A が A に、B が B に、C が C に向かって投げるとします。これを三進数の数字で表します。投げる先が A なら 0、B なら 1、C なら 2 とすれば 012 となり、これを十進数に直して 5 が得られます。同様に A が B に、B が A に、C が C に投げるなら得られる数字は三進数で 102、十進数では 11 です。各手のスローの高さとこの数字を表記すれば各手がどこにどの高さで投げるかの完全な情報が含まれます。なお、何進数かは高さを表す数字が何個あるかで分かるのでわざわざ書く必要はありません。手の数が何百何千になろうと新しい記号が必要ないのもよい点です。

「11 って言われたけど、結局どこに投げたらいいの？」というのは…難しいけど頑張って計算すれば出ます。

ジャグリング競技プログラミング

最近、認知度もどんどん広がってきている競技プログラミングで、ジャグリングに関する問題を出題したいということで現在プロジェクト進行中とのことです。

一例を挙げます。「ジャグ君は、出先でボールをN個もらいました。彼は家に持って帰ろうとしましたが、手が小さいので一度に全部持てません。そこでジャグ君はジャグリングをしながら帰ることにしました。彼がボールを投げる高さを表す数列Sが与えられるので、それがジャグリング可能ならばボールの個数を、不可能ならば -1 を出力してください。」

このような問題を皆さんにも出してもらうことで、脇からジャグリングの普及を進めたいという素晴らしい活動です。