cat a.out を防ぐ

今日は七夕だったようですが、あいにくの雨でした。

出力ファイルを全部つなごうとcat *.outと打ったところ、a.outも巻き込まれてコンソールが大変なことになりました。 このミスは二回目なので、対策することにしました。

あまりうまい方法が思いつきませんでしたが、以下のようにしました。

  • まず、.bashrcや.bash_aliasなどに、alias cat='~/.cat'と書くことで、catコマンドではなく自作の~/.catというスクリプトが呼び出されるようにする
  • その呼び出される~/.catは以下のようにする
#!/bin/bash

args=$(echo $@ | sed -e 's/^a.out / /' -e 's/ a.out / /' -e 's/ a.out$//' -e 's/^a.out$//')

cat $args

どういう仕組みになっているかというと、

  1. echo $@でいったんパス名を展開する（ワイルドカードの*を展開する）
  2. sedでa.outを削除（ファイル名の部分文字列としてa.outを含むものが消えてしまわないようにする）
  3. a.outがなくなった引数をcatする（このcatは本物になります）

ファイル名にスペースが入っているとだめですが、そんな名前を付けることはまずないと思います。

$@と$*の使い分けではスペースの問題は解決しないようです。

なんだか無駄が多いコードに見えるので、頭をひねってみたところ、trコマンドを使うと少しすっきりしそうです。

echo $@ | tr ' ' '\n' | grep -v ^a.out$

もっとうまい方法はあるのでしょうか……？

テンプレートメタプログラミングでQuineを書いた

最近テンプレートメタプログラミング (Template meta programming, TMP) から離れているなぁと思ったので、また書いてみました。

Quine（クワイン）とは、自分のソースコードを出力するプログラムのことです。

ソースコードは以下に公開してあります。C++11の機能のみを使った、伝統的なスタイルのTMPで書かれています。 なお、ソースコードはすべて手で打ち込んだものであり、自動生成した部分は一切ありません。

GitHub - lpha-z/TMP-Quine: A quine written in C++ template meta programming

TMPでQuineを書くとなると結構なコード量になるかと思っていたのですが、実際には十分に短いプログラムになりました*1。 プログラムサイズ自体が小さいため、以前に作ったTMPによるC言語コンパイラ ltmpc の時に開発した、メモリ消費量を抑えるテクニックなしでも、現実的な時間・メモリ使用量でコンパイルが可能です。 clang++-4.0を用いた場合、9秒・1.3GBでコンパイルできました。

Quineの仕組み

自分のソースコードを出力するプログラムを素直に作ろうとすると、文字列として自分自身のソースコードを埋め込むことになります。 つまり、C言語の場合、以下のようになります。

#include <stdio.h>
int main() { puts("#include <stdio.h>\nint main() { puts(\"...\");}"); }

しかし、このようにしてしまうと、循環参照的になっているため、...の部分を書くことが不可能であることに気づきます。 よって、このようなナイーブな方法ではうまくいきません。

典型的なQuineの作り方

典型的には、Quineは以下のような構成になっています。

  1. ライブラリ部分
  2. データ領域
    1. ライブラリ部分のソースコードを文字列化したもの
    2. 出力部分のソースコードを文字列化したもの
  3. 出力部分
    1. 「ライブラリ部分のソースコードを文字列化したもの」を読み込んで、そのまま出力
    2. 「ライブラリ部分のソースコードを文字列化したもの」を読み込んで、それを解釈し、その文字列表現を計算し、それを出力
    3. 「出力部分のソースコードを文字列化したもの」を読み込んで、それを解釈し、その文字列表現を計算し、それを出力
    4. 「出力部分のソースコードを文字列化したもの」を読み込んで、そのまま出力

この場合、重要なのは「ソースコードを文字列化したものを読み込んで、それを解釈し、その文字列表現を計算する」部分です。

ソースコードを文字列化したデータを読み込んでも、その文字列表現は得られません。 例えば、C言語の文字列は"ABC"みたいになっていますが、これを読み込んでもABCというデータが得られるだけで、"のデータは得られません。

しかし、「ソースコードを文字列化したもの」を規則正しく作っておくことにより、ABCから"ABC"を「計算により」復元することができます。

C言語の例の場合、「規則正しく」の部分がわかりづらいかもしれません。

これは、"A""BC"などと文字列化してはいけないということを示しています。 このようにしてしまうと、"を余分に出力しないとQuineになりませんが、その場所がどこかを示すデータが別途必要になってしまい、問題がややこしくなります。

あるいは、AABCを"A\101BC"などと気まぐれに文字列化してしまうと、場所によってどう計算すべきかが変わってしまい、問題がややこしくなります。

TMPでのQuineの実現

出力方法

TMPには出力機能がないため、純粋なTMPだけでQuineを達成することは不可能です。

今回は、Quineという型変数が、String<（ソースコードの一文字一文字をchar...に入れたもの）>となるようにしました。

それだけだと本当にQuineが完成したかの確認が困難なため、以下の実行時コードがついています。

#include <cstdio>
#include <initializer_list>
template<class>
struct Printer;
template<template<char...>class Container, char... Chars>
struct Printer<Container<Chars...>> {
    Printer() {
        using Swallow = std::initializer_list<int>;
        Swallow swallow { putchar(Chars)... };
    }
};
Printer<Quine> printer;
int main() {}

Swallowは、initializer_listを使ってパラメータパックを展開するときのイディオムです。 関数の引数でパラメータパックを展開すると、その実行順は保証されませんが、initializer_listの中であれば前から順番に実行されることが保証されます。

ソースコードの文字列化方法

ソースコードを文字列化するためには、素直に文字リテラルを用いました。なお、文字リテラルの間には必ず,が入っています（規則的に書かれています）。

文字リテラルを用いたのは、ソースコードを手書きするにはそのほうがやりやすかったためです。 しかし、エスケープが不可避なため、ソースコードが長くなってしまいます。

ソースコードを自動生成する前提ならもっと短くなる方法があります。 例えば文字リテラルではなく、その文字コードを直打ちするという方法です。この場合、エスケープは不要です。 十進数で書くと2桁のものと3桁のものができてしまって不便なため、八進数で書き、leading zerosを使って桁数をそろえるとよさそうです。

ソースコードを文字列化したものを読み込んで、それを解釈し、その文字列表現を計算する方法

BuildSource構造体テンプレートがその計算をする部分です。 ソースコードの文字データの先頭は、, 'C'の形になっていないため、別途生成しています。 そのため、先頭の一文字を落としてEncodeChar構造体テンプレートに渡しています。

EncodeChar構造体テンプレートは、Cというデータから, 'C'という文字列表現を計算する部分です。エスケープが必要な場合、特殊化されたテンプレートが選ばれ、必要な\を出力します。

これを各文字について行い、文字列表現を計算します。その際に行われる結合は「大きいものに小さいものをマージ」戦略によっているため、メモリ使用量・コンパイル時間がソースコードサイズに対して二乗のオーダーとなってしまっています。

*1:ただし、Concatenateと書いていたらぎりぎりで再帰深度1024の壁を越えてしまったので、Catに直しました……。

gcc9.1.0をソースコードからコンパイルした

gcc8以前と比較して、gcc9はバイナリ生成部分が更新されているようです。 既存のコンパイラのバイナリ生成に不満を持ったため、gcc9.1.0をビルドすることにしました。

前回gcc8.2.0をソースコードからコンパイルしました。 その時の知見が生かせたので、今回はスムーズにコンパイルできました。 道しるべとして今回も記録しておきます。

今回も3stageビルドを行いましたが、意味がなかったような気がします。 3stageビルドを無効化する場合、--disable-multilibの横に--disable-bootstrapを付けます。

mkdir build_gcc91_stuff
cd build_gcc91_stuff/
wget http://ftp.gnu.org/gnu/gcc/gcc-9.1.0/gcc-9.1.0.tar.gz
tar xf gcc-9.1.0.tar.gz
cd gcc-9.1.0
./contrib/download_prerequisites
cd ..
mkdir build
cd build/
../gcc-9.1.0/configure --prefix=/home/lpha/gcc91 --enable-languages=c,c++ --disable-multilib
make -j 6 BOOT_CFLAGS='-march=native -O3'
make install

バイナリ生成の違い

詳しく解析したわけではないのでよくわからないですが、以下の既存の系列とは違ったバイナリ生成を行うようです。

  • gcc8以前
  • clang全て

定数との整数演算命令の最適化は、clangより弱いままです。しかし、総合的な最適化力はclangより高そうに見えます。特に、機械語命令の順番がいい感じになっています。

リリースノートには、switch文の最適化をいい感じにしたとか書いてありました。

干し柿落としゲームのGrundy数を求めてみた

干し柿落しゲームは、takaken氏の作成した対戦ゲームで、石取りゲーム(Nim)を拡張したものです。

遊んだことがなければ、この記事を読む前に遊ぶことをおすすめします。ぜひ、自分で必勝戦略を構築してみてください。

干し柿落としゲームはNimより複雑であり、自明にGrundy数に帰着できるわけではありませんが、意外ときれいな構造を持っていることがわかりました。

まず準備として、Grundy数の雰囲気の説明から書きます（厳密な議論は行わないので、すでに知っている読者は飛ばしてかまいません）。

Grundy数の雰囲気

Grundy数は、不偏ゲームの局面に割り当てられる非負整数です。

不偏ゲームとは、二人零和有限確定完全情報ゲームであり、さらに手番がどちらのプレーヤーにあるかと無関係に有効な着手の集合が決まるものです。 有効な着手がなくなった時点で、勝利プレーヤーが決まります。

Grundy数は、不偏ゲームの局面が必勝局面であるか、どんな着手をすればよいかの判断に役立ちます。

将棋やチェスは、手番によって動かせる駒が異なりますので、不偏ゲームではありません。 囲碁やオセロも、手番によって置ける石の色が異なりますので、不偏ゲームではありません。 このように普通の対戦型ボードゲームは不偏ゲームではありません。

しかし、意外と身近に不偏ゲームは存在します。 まずは、不偏ゲームの例とその必勝法を見てみます。

不偏ゲームの例とその必勝法

21を言ったら負けゲーム

以下のようなゲームを考えます。

  • 先手番プレーヤーは、1から始まる連続する自然数を1つか2つか3つ言う（つまり、「1」「1、2」「1、2、3」のどれかを言う）
  • 以下、プレーヤーは交互に、直前のプレーヤーが言った数に続く連続する自然数を1つか2つか3つ言う（「1、2」「3、4、5」「6」「7、8、9」のように進行する）
  • 21を言ってしまったプレーヤーの負け

これは不偏ゲームになっています。 「21を言ってしまったら負け」という部分は、「21は言えない」ということにすれば「有効な着手がないので負け」で解釈できます。

このゲームは、後手必勝です。必勝戦略は、以下の通りです。

  • 相手が1つ言ったら3つ、2つ言ったら2つ、3つ言ったら1つの自然数を言う

こうすることで、自分の手番を常に4の倍数で終わらすことができます。 特に、自分は20を言うことができます。 つまり、相手は21を言わざるを得ない（有効な着手がない）状況に追い込まれます。

二山石取りゲーム

以下のようなゲームを考えます。

  • 盤面には、石の山が二つあり、片方の山にはk1個、もう片方の山にはk2個の石が含まれる
  • 先手番プレーヤから交互に、「石が存在する山を一つ選び、そこから1つ以上任意個の石を取り除く」を行う
  • 石が取れなくなったプレーヤーの負け

これも不偏ゲームになっています。

このゲームは、k1=k2であれば後手必勝です。必勝戦略は、以下の通りです。

  • 相手が選ばなかったほうの山から、相手と同じ数の石を取り除く

こうすることで、k1=k2を保ったまま相手に手番を回すことができます。 ゲームが進行し、k1=k2=0となった時、相手には有効な着手がありませんのでこちらの勝ちです。

不偏ゲームの必勝法の特徴

二つの例から一般化するのは乱暴ですが、実際に以下のような特徴があります。

  • 何か指標があり、それが特定の値であるとき、必敗局面である
    • 21を言ったら負けゲームでは、最後に言った自然数を4で割った余り（0で手番が回ってくると必敗）
    • 二山石取りゲームでは、各山に含まれる石の数の差（0で手番が回ってくると必敗）
  • 相手の任意の着手に対して、指標の変化を"打ち消す"ような着手をすることにより、必勝局面を維持できる

Grundy数

先ほど見つけた"指標"は場当たり的で、他の不偏ゲームへの適用は不可能でした。 Grundy数は、この"指標"を統一的に割り当てる方法で、いろいろと良い性質があるようです。

具体的にどういう数が割り当てられるかというと、

  • 有効な着手がない場合、0が割り当てられる
  • k未満の任意の非負整数tについてGrundy数がtである局面へ遷移する着手があり、かつG数がkである局面へ遷移する着手がない場合、kが割り当てられる

言い換えると、次のようになります。

  • Grundy数が0である局面へ遷移する着手がない場合、その局面のGrundy数は0
  • Grundy数がkの場合、k未満の任意の非負整数tについて、Grundy数がtである局面に遷移する着手がある
    • 特に、Grundy数が0である局面に遷移する着手があることが重要

このことからGrundy数は、その局面が必敗局面であるときに0、必勝局面であるときに正の数が割り当てられることがわかります。

min-max法を用いてこのゲームの必勝戦略をみつけるだけであれば、正の数を使い分ける必要はありません。 しかし、その場合には最悪指数的に大きいゲーム木を探索する必要があります。

不偏ゲームの場合、いくつかの独立な不偏ゲームの和に分解できることがあります。 この時、その局面のGrundy数は分解されたゲームのGrundy数から求めることができます。 つまり、その局面のGrundy数を、探索することなく直に計算することができます。 これが、わざわざ正の数を使い分けることの利点です。

具体的には、各部分ゲームのGrundy数を二進法で表し、そのビットごと排他的論理和(xor)が全体ゲームのGrundy数になるという性質があります。

本題：干し柿落としゲーム

遊んでみましたか？ 時間がないという場合でも、自分で遊んだほうがルールが理解できると思います。 ぜひ、以下を読む前に遊ぶことをおすすめします。最初の数問だけでも、ぜひ。

干し柿落しゲームは、以下のようなゲームです。

  • 盤面には、干し柿の山（連？）がいくつかあり、各山に何個かの干し柿が含まれる
  • 先手番プレーヤから交互に、以下の3つのうちのどれかを行う
    • 干し柿が存在する山があるとき行える：干し柿が存在する山を一つ選び、そこから1つ以上任意個の干し柿を取り除く
    • "勝利条件"が確定していない場合行える："勝利条件"を【最後に着手したプレーヤーの勝ち】に確定させる
    • "勝利条件"が確定していない場合行える："勝利条件"を【最後に着手したプレーヤーの負け】に確定させる
  • 有効な着手がなくなった時、"勝利条件"によって勝者を決める

手を動かしてみる

"勝利条件"が確定していない場合をA、"勝利条件が【最後に着手したプレーヤーの勝ち】の場合をW、勝利条件が【最後に着手したプレーヤーの負け】の場合をLと書きます。 ゲームの盤面は、山に含まれる干し柿の数を並べて書きます。山に含まれる干し柿の数は一桁の数字で表せます。

例えば、三山あり、干し柿の数がそれぞれ1、2、3であり、"勝利条件"が確定していない盤面のことを、123Aと書きます（ステージ6の初期盤面です）。

以下、ネタバレが含まれます。

山が一つの場合

  • 0Wで手番を迎えた場合、相手が最後に着手しているのでこちらの負けです。
  • 0Lで手番を迎えた場合、相手が最後に着手しているのでこちらの勝ちです。

  • 0Aで手番を迎えた場合、「"勝利条件"を【最後に着手したプレーヤーの勝ち】に確定させる」着手を行えば勝ちです。相手には有効な着手がないためです。

  • 1Wで手番を迎えた場合、最後の一つの干し柿を落として勝ちです。

  • 1Lで手番を迎えた場合、最後の一つの干し柿を落とすしかなく、負けです。

  • 1Aで手番を迎えた場合、「"勝利条件"を【最後に着手したプレーヤーの負け】に確定させる」着手を行えば勝ちです。[]の付録に詳しく説明が書かれています。

  • 2Wで手番を迎えた場合、二つの干し柿を一度に落とせば勝ちです。

  • 2Lで手番を迎えた場合、干し柿を一つだけ落とせば、必敗局面である1Lを相手に押し付けることができて勝ちです。
  • 2Aで手番を迎えた場合、負けです。有効な着手により遷移できる局面は0A, 1A, 2W, 2Lですが、いずれも必勝局面だからです。この局面を作ることが勝利への道です。

山が複数ある場合

  • 干し柿の数が同じ山のペアがある場合、そのペアを取り除いた局面が必勝局面であれば、元の局面も必勝局面です。
    • 石取りゲーム（二山）と同様に、相手の着手と同じ着手をすることで、必勝局面を維持できるためです。

その他

  • 13Aは必敗局面です。

一般化してみる

山が一つの場合

  • kW(k>2)で手番を迎えた場合、全ての干し柿を一度に落とせば勝ちです（必敗局面0Wへの遷移）。
  • kL(k>2)で手番を迎えた場合、干し柿を一つ残すように他全部を落とせば勝ちです（必敗局面1Lへの遷移）。
  • kA(k>2)で手番を迎えた場合、干し柿を二つ残すように他全部を落とせば勝ちです（必敗局面2Aへの遷移）。

つまり、3個以上の干し柿が残っている局面で手番を迎えた場合、ルール部分に依存せず必勝です。

山が二つで、片方の干し柿が1つの場合

  • 11Wで手番を迎えた場合、負けです。二山石取りゲームk1=k2=1と全く同じ状況です。
  • 11Lで手番を迎えた場合、勝ちです。

  • 11Aで手番を迎えた場合、「"勝利条件"を【最後に着手したプレーヤーの勝ち】に確定させる」ことで必敗局面11Wを相手に押し付けることができて勝ちです。

  • 12Wで手番を迎えた場合、11Wへ遷移すれば勝てます。

  • 12Lで手番を迎えた場合、1Lへ遷移すれば勝てます。

  • 12Aで手番を迎えた場合、2Aへ遷移すれば勝てます。

  • 13Wで手番を迎えた場合、11Wへ遷移すれば勝てます。

  • 13Lで手番を迎えた場合、1Lへ遷移すれば勝てます。

  • 13Aで手番を迎えた場合、負けです。有効な着手で遷移できる先は1A, 11A, 12A, 3A, 13W, 13Lですが、いずれも必勝局面だからです。

  • 1kW(k>3)で手番を迎えた場合、11Wへ遷移すれば勝てます。

  • 1kL(k>3)で手番を迎えた場合、1Lへ遷移すれば勝てます。
  • 1kA(k>3)で手番を迎えた場合、13Aへ遷移すれば勝てます。

山が二つで、片方の山の干し柿が2つの場合

  • 22Wで手番を迎えた場合、負けです。二山石取りゲームk1=k2=2と全く同じ状況です。
  • 22Lで手番を迎えた場合、負けです。有効な着手で遷移できる先は12L, 2Lしかなく、いずれも必勝局面だからです。

  • 22Aで手番を迎えた場合、2Aにするなり、22Wや22Lにするなど選択肢がたくさんありますが、いずれにせよ勝ちです。

  • 2kW(k>2)で手番を迎えた場合、22Wへ遷移して勝てます。

  • 2kL(k>2)で手番を迎えた場合、22Lへ遷移して勝てます。
  • 2kA(k>2)で手番を迎えた場合、2Aへ遷移して勝てます。

これ以上頑張っても法則が見えてくるわけではないので、結論に移っていきます。

【最後に着手したプレーヤーの勝ち】ルールの時

これは石取りゲーム(Nim)とまったく同様です。

各山にある干し柿の数のxorがGrundy数となっています。

山が二つ以下の場合の表を書いてみます。

W 0 1 2 3
0 0 1 2 3
1 1 0 3 2
2 2 3 0 1
3 3 2 1 0

Grundy数の定義に従っていることを確認しておきます。 あるマスの値は、そのマスの左にあるマスに存在しなく、上にあるマスにも存在しない最小の非負整数になっていることがわかります。

【最後に着手したプレーヤーの負け】ルールの時

一般的なゲームでは、着手がなくなったプレーヤーの負けです。 それに対して着手がなくなったプレーヤーの勝ちというルール、一般的なゲームにおいて負けることを目的にプレイすることと同義です。 こういった勝利条件が反転したゲームは、misére ゲームと呼ばれます。

【最後に着手したプレーヤーの負け】に確定したゲームは、mis'ereゲームになっています。

一般に、miséreゲームのGrundy数を求めることは容易ではありません。 しかし、石取りゲーム(Nim)の場合には比較的簡単に求めることができます。

山が二つ以下の場合の表を書いてみます。

L 0 1 2 3
0 1 0 2 3
1 0 1 3 2
2 2 3 0 1
3 3 2 1 0

この場合でもGrundy数の定義に従っていることが確認できます。

そもそも、Wの場合と見比べるとほとんど変わっていないことがわかります。0L, 1L, 11Lの部分だけが異なります。 なぜ他の部分は変わらないのでしょうか。

00L,01L,10L,11L以外の局面のGrundy数を定義に従って計算する場合を考えます。 重要なのは、00L, 01L, 10L, 11Lの部分はGrundy数の位置を入れ替えただけであるという点です。 位置を入れ替えただけであるため、「左にあるマスに書かれている数∪上にあるマスに書かれている数」は集合として一致します。 よって「そのマスの左にあるマスに存在しなく、上にあるマスにも存在しない最小の非負整数」という部分に影響を及ぼしません。

山が三つ以上ある場合を考えます。 その場合、三次元、四次元、……の表を考えることになります。 Wの場合とGrandy数が変わるのは、111...111Lより内側だけになります。 その外側では、上で書いたこととまったく同じように、"集合として一致"するためGrundy数はWの場合と変化しません*1

つまり、【最後に着手したプレーヤーの負け】ルールの時、その局面のGrundy数は以下のように算出されます。

  • 干し柿が2個以上残っている山がある場合、各山にある干し柿の数のxorがGrundy数になっている
  • 干し柿が1個の山しかない場合、各山にある干し柿の数のxorを求め、さらに1とxorしたものがGrundy数になっている
    • 干し柿が1個の山しかない場合、もっと簡単に求める方法として、「山の数が奇数なら0、偶数なら1」がありますが、「各山にある干し柿の数のxor」を用いたほうが統一感があります

ルールが未確定の時

山が二つ以下の場合の表を書いてみます。

A 0 1 2 3 4 5 6 7
0 2 3 0 1 5 4 7 6
1 3 2 1 0 4 5 6 7
2 0 1 2 3 7 6 5 4
3 1 0 3 2 6 7 4 5
4 5 4 7 6 1 0 3 2
5 4 5 6 7 0 1 2 3
6 7 6 5 4 3 2 1 0
7 6 7 4 5 2 3 0 1

Grundy数の定義に従っていることを確認しておきます。 あるマスの値は、そのマスの左にあるマスに存在しなく、上にあるマスにも存在しなく、さらにW/Lの表の同じ位置にも存在しない最小の非負整数になっていることがわかります。

どうやらこれも排他的論理和的な雰囲気があります。 実は、以下のような法則があります。

  • A33より内側は、各山にある干し柿の数のxorを求め、さらに2とxorしたものがGrundy数になっている
  • それ以外は、各山にある干し柿の数のxorを求め、さらに1とxorしたものがGrundy数になっている

このようになる理由は、A33より内側の部分はGrundy数の出現位置を入れ替えただけであり、ラテン方陣である性質を維持しているからです。

なお、山が三つ以上ある場合も同様になっています。

注意点として、いくつかのゲームに分解してこの表の値をxorするのでは正しくも止まりません。 分解された各ゲームは、"勝利条件"を決めるという手を共有してしまっていて、独立していないからです。

干し柿落としゲームにおけるGrundy数の求め方

まとめます。

  • 【最後に着手したプレーヤーの勝ち】ルールの時、各山にある干し柿の数のxorがGrundy数
  • 【最後に着手したプレーヤーの負け】ルールの時、干し柿が2個以上残っている山があれば、各山にある干し柿の数のxorがGrundy数
  • 【最後に着手したプレーヤーの負け】ルールの時、干し柿が2個以上残っている山がなければ、各山にある干し柿の数のxorと1をxorしたものがGrundy数
  • ルールが未確定の時、干し柿が4個以上残っている山があれば、各山にある干し柿の数のxorと1をxorしたものがGrundy数
  • ルールが未確定の時、干し柿が4個以上残っている山がなければ、各山にある干し柿の数のxorと2をxorしたものがGrundy数

干し柿落としゲームにおける必勝法

  • 初期局面のGrundy数が0であれば、後手必勝
  • そうでなければ、以下の条件を満たす手があるはずで、それを打ち続ければ先手必勝
    • Grundy数(G)を二進法で表した時の最高位をKとおく（K=1,2,4,...）
    • 【最後に着手したプレーヤーの勝ち】ルールの時、干し柿の数を二進法で表した時にKの位が1である山のうち一つを選び、その山に残っている干し柿の数をS個として、それがS xor G個になるように取り除く
    • 【最後に着手したプレーヤーの負け】ルールの時、かつ干し柿が二つ以上残っている山がない場合
      • 干し柿が1つの山から1つ取り除く（これしか可能な着手がないですが、勝利への道です）
    • 【最後に着手したプレーヤーの負け】ルールの時、かつ干し柿が二つ以上残っている山がある場合
      • 干し柿の数を二進法で表した時にKの位が1である山のうち一つを選び、
        • その山に残っている干し柿の数をS個として、その山がS xor G個になるように取り除くと？
          • 干し柿が二つ以上残っている山がなくなるのであれば、その山がS xor G xor 1個になるように取り除く
          • そうでなければ、その山がS xor G個になるように取り除く
    • ルールが確定していないとき、かつ干し柿が4個以上残っている山がない場合
      • Grundy数が1であれば、干し柿が奇数個ある山から干し柿を1つ取リ除く
      • Grundy数が2であれば、"勝利条件"を【最後に着手したプレーヤーの勝ち】に確定させる
      • Grundy数が3であり、かつ干し柿が2個以上残っている山がない場合、"勝利条件"を【最後に着手したプレーヤーの負け】に確定させる
      • Grundy数が3であり、かつ干し柿が2個以上残っている山が一つだけということはないはず
      • Grundy数が3であり、かつ干し柿が2個以上残っている山が二つ以上ある場合、干し柿が2個の山から干し柿を1つ取り除くか、干し柿が3個の山から干し柿をすべて取リ除く
    • ルールが確定していないとき、かつ干し柿が4個以上残っている山がある場合
      • 干し柿の数を二進法で表した時にKの位が1である山のうち一つを選び、
        • その山に残っている干し柿の数をS個として、その山がS xor G個になるように取り除くと？
          • 干し柿が二つ以上残っている山がなくなるのであれば、その山がS xor G xor 3個になるように取り除く
          • そうでなければ、その山がS xor G個になるように取り除く

おわりに

干し柿落としゲームにおけるGrundy数を求めてみました。一般に、miséreゲームのGrundy数や、ルールが途中で変化するゲームのGrundy数を求めることは難しいです。 しかし、干し柿落としゲームにおいては、特定の境界線があり、その内側と外側で計算方法を変化させれば、よくあるxorを用いる方法を少し拡張するだけでGrundy数を求めることができるというきれいな性質があることがわかりました。

必勝法は、その境界をまたぐ操作であるかによって場合分けが発生し、複雑です。

しかし、境界は二の冪であり、境界をまたぐ手を打つべきかどうかは求めることができます。 よって、まず「境界をまたぐ手を打つべきか」を求め、その後具体的にどのような手を打つべきかを求めることで必勝法を構成することができました。

*1:余談ですが、擬ポテンシャルに似ている感じがします。

AtCoderを退会するための問題（ABC077/ARC084のD問題）を別解法で解いた

AtCoderを退会するための問題、の元ネタは以下のツイートです。

twitter.com

どうやらこの問題はAtCoder Regular Contest (ARC) 084のD問題「Small Multiple」として出題されたことのある、過去問のようです（併設のBeginner Contest (ABC) 077のD問題でもあります）。

この問題を自力で解いた提出が以下になります。ABC側に提出しましたが、このような併設開催だったコンテストの過去問の場合、どれに提出するのが一般的なんでしょう……？

Submission #5698661 - AtCoder Beginner Contest 077 | AtCoder

私の提出した解法は、他の提出とは異なる解法のようです。 というかあまりにもdouble ended queue (deque)による0-1BFS*1を用いた解法ばかりです。 どうやらコンテストの解説資料がこの解法によるものになっているようです。 つまり、最近の提出は「過去問演習で解けなかったので解説を見てから提出」というパターンで提出されたものなので、こういう提出ばかりになったものと思われます。

……と思っていたら、コンテスト中に提出された解法もほぼすべてが似た解法でした。さすがに洗練された0-1BFSではなく、単なるBFS（幅優先探索）やDFS（深さ優先探索）によるものもありますが、グラフの構築法は同じです。

こういう解き方もあるんだよという啓発になればと思って記事を書きます。

目次的なもの

以下の節は思考の垂れ流しなので、アルゴリズムを知りたい場合は読まなくてよいです。 ただ、「なんでこんな発想に至ったのか」ということを知る方法はあまりないので、参考にしたいことがあるかと思い一応書いておきます。

着想に至った経緯

お風呂に入っていたら思いつきました。

問題文を見てからの思考

  • なるほど、7なら1001だから2と答える感じかぁ
  • すごく大きなKの倍数が1000....0001の形になるかを判断するのは難しそう
  • 2n 5m の形なら1が答えになる
  • 2n 5m K の形なら、Kの答えと同じになる
  • もしかして2n 5m 以外だと全部1000...0001の形にできて2が答えになるのかな
    • これは間違い、例えばK=3だと3が答えになる
  • 3の倍数だけ特殊扱いすればいいのかな……？*2
  • Kは小さいので、指数時間アルゴリズムを用いてよい（※入力長log Kに対しての指数時間アルゴリズムが通るという話であって、Ο(2K)が通るという話ではないです）
  • お風呂入ろう

お風呂での思考

  • 素因数分解する問題ではなさそう
    • そもそも、大きな素数に対してどう解けばいいのか不明
  • 具体的に構成する方法がありそう
    • 根拠なし
  • まず7の時にどうやって1001にたどり着くかを考えよう
  • KのT倍について考える
  • Mの1の位から考えていく
  • 1001にたどり着く場合、7×3=21を最初に選んだわけで、Tの1の位は3
    • つまり、1倍～9倍のなかで1の位が小さくなるものを選べばよさそう
    • もちろん、貪欲にやってうまくいくとは限らなさそう
  • そうすると、10の位に2が余る
  • ここで7×14=98を選べば、さっき余った2と合わせて100になって、十進法を用いたときに各桁の和が最小となる
  • つまり、7の倍数+2の形をしたものについても十進法を用いたときに各桁の和が最小となるものを探せばよい
  • 一般に、Kの倍数だけではなく、Kの倍数+rの形をしたものに対しても探せばよい
  • rの作り方は一般に複数通りある*3ので、DPっぽい*4
  • Tのu桁目tとしてあり得る0～9のすべてに対し、r+Ktを考えて、それを10で割った余りがKTのu桁目に対応
    • 下の位から確定させていくとき、KTのu桁目を変えられるラストチャンスはTのt桁目の時
    • KTを十進法で表したときの各桁の和は、確定した部分のみの和より少なくなることはあり得ない
  • r+Kmを10で割って切り捨てたものが次のr
  • rとしてあり得るのは0～K-1のK通り
  • rに対応する頂点と、遷移（今のr→次のr）に対応する辺を考えると、頂点数K・辺数10Kの疎なグラフについての最短路問題となる
  • 辺のコストとしてありえるのは0～9
  • よって優先度付きキューを用いたdijkstra法のようなソートが必要な最短路アルゴリズムではなく、キューををたくさん用意する最短路アルゴリズムが使える
  • お風呂出よう

ここまで20分くらいでした。紙とペンがあったらもっと早く思考をまとめられたのでしょうか……？

アルゴリズムの概略

スタート地点となる頂点からは9本の辺が出る。枝t(0<t<10)は頂点K*t/10への辺である。その辺のコスト（距離）は、K*t%10である。 頂点0はゴール地点である。その他の頂点rからは10本の辺が出る。枝t(0≦t<10)は頂点K*t/10への辺である。その辺のコストは、K*t%10である。

スタート地点からゴール地点への最短路長が求める答えである。

アルゴリズムの実装における工夫

  • 辺のコストは0～9であるため、キューを10個用意する幅優先探索を行う。
    • 実際に提出したコードでは、キューは再利用せず使い捨てている。その場合、キューは54個用意する必要がある。
  • グラフをあらわに持つことはせず、その頂点を訪れたときにその場で生成する。

実装は35分くらいかかりました。もっと早く書けるようになりたいなぁ……。

提出ソースコードの解説

キューとして何を用いるべきか

キューの挿入される回数の上限値が事前にわかっているため、static_vectorが最適です。検討した他のコンテナは以下の通りです。

  • std::vectorは、push_backするとイテレータが無効になるため注意が必要です。必要な量が前もってわかるため事前に確保しておけば問題ないですが、確保量を間違えた場合に危険です。
    • 必要な容量はKです。
  • std::dequeは、危険性はありません。しかし、事前に確保できないため複数回newが走り、遅いです。
  • std::queueは、普通は内部実装がstd::dequeです。
  • std::listは、毎回newが走り、非常に遅いです。

まぁそこまで遅いアルゴリズムではないので、std::queueを使っても問題にはならないでしょう。

range-based-forを使わない理由

途中でendイテレータが変更されるためです。range-based-forは最初に一回だけend( Container )を評価します。そのため、ループの中でその後にpush_backをしてendイテレータが変更されても、ループ開始前にキューに入っていたものしか取り出されません。 「距離0」が存在するような幅優先探索に用いるキューを取り扱うためには不適です。

最短路を求める方法

q.at( cost ).push_back( rem )により、「頂点remへたどり着くためのコストは、costである」ことを記憶します。 今の頂点rにたどり着くのに必要なコストがiである場合、q.at( i + cost ).push_back( rem )により、「頂点remへたどり着くためのコストは、i + costである」ことを記憶します。 これは正確には「頂点rを直前に通って、頂点remへたどり着くまでのコスト」なので、他の行き方がある可能性が残されます。 例えば、頂点0にたどり着けるとしても、その行き方が最短路ではなく、他の行き方だともっと低コストでたどり着ける可能性が残されています。 よって、枝を張る部分（内側のfor文）でrem == 0の時にi + costを出力するのでは間違いです。

このキューをコストの低いほうから順にみていけば、ある頂点rを初めて訪れた（visited.at( r ) == false）時、その時のコストiが頂点rにたどり着くための最低コストになっています。 頂点0であればゴール地点にたどり着いたので、コストを出力して終了です。 頂点0以外であれば探索を進めます。 頂点への二回目以降の訪問は、遠回りをして到着した場合なので、その先に探索を進める必要はありません。

どこまで探索すればよいか

求めるべき答えは、Kを十進法で表したときの各桁の和以下であることが明らかです。 K=99999の場合が最も大きく、その値は45です。 よって、iは0～45の範囲を探索すればよいです。

キューは何個用意すればよいか

i = 45の場合、必ず答えが出力される（つまり終了する）ことが保証されています。 よって内側のfor文に入る時、iは最大で44です。 costは最大で9なので、q.at( 53 )へのアクセスがあり得ます。 それ以上はあり得ないので、キューは54個用意すれば十分です。

実際には、同時に使われるキューの数は10個であり、使い捨てずに節約することが可能です。

想定解法との違い

想定解法の速い実装としては、準急くきさんの提出Submission #1742945 - AtCoder Regular Contest 084 | AtCoderがわかりやすいでしょうか。

アルゴリズムの違い

考えているグラフの違い

実は考えているグラフはほとんど同じものです。 想定解法では×10, +1の二種類だけを用いたグラフです。そうではなく、×10, +1, +2, +3, +4, +5, +6, +7, +8, +9の十種類の辺を用いたグラフとすれば私の解法と同じグラフになります。 繰り上がりの部分で余計なことを考えなくてよいので、十種類の辺を用いたグラフを考えるのも自然です。

辺の向きの違い

想定解法と私の解法では以下の点が異なります。

  • スタート地点とゴール地点が入れ替わっている。
  • 有向辺の向きが逆向きになっている。

この違いは、構築を上位桁から行うか、下位桁から行うかに対応しているようです。

想定解法では、上位桁から求めていっています（10倍する操作は、考える桁を一つ下に移動することに対応します）。 私の解法では、下位桁から求めていっています（10で割る操作は、考える桁を一つ上に移動することに対応します）。

下位桁から構築するのもそんなに不自然ではないと思うのですが、競技プログラマーのほとんどが想定解法で解いているようで、不思議です。 「十進法で表したときの各桁の和」に対する典型解法だったのでしょうか……？

辺を構築しやすいか

想定解法では、辺がどの頂点とどの頂点を結んでいるか、その辺のコストはいくらか、がほぼ自明です。 私の解法では、そんなに自明ではありません。

計算量

この手のBFSの正しい時間計算量

想定解法は0-1BFSにより時間計算量Θ(K)で解けるとしています。 競技プログラミングの文脈では正しいのかもしれませんが、計算量理論的にはこれは誤りです。 なぜなら、キューの一エントリは0～K-1を格納するためにΘ(log K)ビット必要で、それがΘ(K)エントリ必要ならば空間計算量はΘ(K log K)となるからです。 空間計算量より時間計算量が小さいことはあり得ませんから、0-1BFSを用いたところでΘ(K log K)であることには変わりません。

私の解法も、同様の理由により時間計算量Θ(K log K)の解法です。

なお、普通の優先度付きキューを用いたDijkstra法の時間計算量は同様の理由により時間計算量Θ(K (log K)2)となるので、それよりオーダーとして高速なアルゴリズムだという点は間違いではありません。 Radix Heapを用いた場合は、時間計算量Θ(K log K log log K)になります。

mod Kの存在

想定解法では、10倍してmod Kをとる操作があります。 私の解法では、mod 10をとる操作があります。

一般に、変数による剰余は低速です。最近のIntel CPUだと26サイクルかかるようです。 一方、定数による剰余は乗算命令とシフト命令に最適化されるため、高速です。

私の解法ではK*tを求める部分がありますが、これは誘導変数*5であり、乗算は不要です。 実際、最近のコンパイラはこの最適化を行ってくれるようです。

一頂点からでる辺の本数

想定解法では2本であり、私の解法では10本です。

この違いは大きいようで、私の解法は想定解法より3倍程度遅いです。

おわりに

こういう問題、競技プログラミングの問題として出される（＝高速な解法があることが保証される）から解けるけれど、そういうメタな情報が無かったら愚直に探す解法しか思いつけなかったような気がします。 それでも、答えを見ずに解けたときはうれしいです。 それが独自の解法であったときは特にそうです。

あと、AtCoderを退会できるくらいの実力があることはわかったので、少し自信がついたかもしれません。

*1:0-1BFSとは、辺の距離が0または1だけの場合に使える、高速な最短路発見アルゴリズムです。

*2:小さな素数には反例がなかったのでこういう思考に至ったのですが、どうやら31に対しては3が答えとなるようです。

*3:7×3=21、7×4=28なので、r=2を作る方法は二通り（以上）あります。

*4:ここでいう「DPっぽい」は、探索中の特定の状態へのたどり着き方（経路）が複数通り存在し、その先の探索には経路の情報が不要なため、全探索より効率的に探索できる状況のことを言っています。

*5:誘導変数とは、ループの周回ごとに一定量増えるような変数のことを言います。帰納変数とも呼ばれます。

二重かっこの高さを中身に合わせるtexマクロを解読する

[\![3]\!]のような二重角かっこは、\[\!\[3\]\!\]と入力すれば出すことができます。 nath.styを導入すると、\double[とか\lBrackなどと書けるようです。

しかし、このままでは中身に高さのあるもの（分数など）を入れた場合に見栄えが良くありません。 中身に応じた高さにしてくれる\leftマクロは\double[やlBrackには適用できないようです。

\!で間隔を詰める方法の場合、高さが二倍くらいの分数であれば、\!\!を使って\left\[\!\!\left[ \frac{1}{2} \right]\!\!\right]のようにすれば見栄えはよくなります。 つまり、中身の高さに応じて詰める間隔を変えないといけないということです。 どうにかして自動で変わってくれないでしょうか。

これを可能にしたマクロがBracket: LaTeXにありました。 それは、以下のようなものです。

\makeatletter
\def\Left#1#2\Right{\begingroup%
   \def\ts@r{\nulldelimiterspace=0pt \mathsurround=0pt}%
   \let\@hat=#1%
   \def\sht@im{#2}%
   \def\@t{{\mathchoice{\def\@fen{\displaystyle}\k@fel}%
          {\def\@fen{\textstyle}\k@fel}%
          {\def\@fen{\scriptstyle}\k@fel}%
          {\def\@fen{\scriptscriptstyle}\k@fel}}}%
   \def\g@rin{\ts@r\left\@hat\vphantom{\sht@im}\right.}%
   \def\k@fel{\setbox0=\hbox{$\@fen\g@rin$}\hbox{%
      $\@fen \kern.3875\wd0 \copy0 \kern-.3875\wd0%
      \llap{\copy0}\kern.3875\wd0$}}%
      \def\pt@h{\mathopen\@t}\pt@h\sht@im%
      \Right}%
\def\Right#1{\let\@hat=#1%
   \def\st@m{\mathclose\@t}%
   \st@m\endgroup}
\makeatother

このマクロを解読していきます。 私はtex言語は全くの素人なので間違った解釈があるかもしれない点に注意してください。

制御綴り

\の後に「通常の文字」がいくつか並んだものを制御綴りというそうです。 もっぱらマクロ名や変数名に使われている印象です。

\makeatletter, \makeatother

@を「通常の文字」扱いに変更する命令と、「その他の文字」扱いに戻す命令のようです。 このマクロの中で現れる制御綴りはすべて@を含んでいます。 ユーザーランドでは@は「その他の文字」であるので、うっかり@を含む制御綴りを定義することはありません。 よって@を含む制御綴りは、一種の予約語としてシステムが使うことができます。

末尾の%

末尾の改行は半角スペースに変わってしまいます（和文だとこれを取り除いてくれる機能がplatexにあるようです）。 行末に%を置くことで、半角スペースの挿入を抑止できます。 しかし、インデントのために半角スペースを入れているので意味がない気がします。 他の効果もあるようですが、よくわかりません。

\Left#1#2\Right

パターンマッチという引数の取り方で、\Leftの次のトークン（開きかっこ）を#1に入れ、\Rightが見つかるまでの残りのすべてのトークン（かっこの中身）を#2に入れるようです。

\begingroup, \endgroup

{や}の代替であり、グルーピングに使うようです。 変数の代入などは、この範囲でしか影響を及ぼさないという効果があるようです。 C言語でいうところのスコープのようなものでしょうか。

なぜ代替する必要があるのかはよくわかりませんでした。

\ts@r

いきなり読めない意味不明なマクロ名ですが、{\nulldelimiterspace=0pt \mathsurround=0pt}に置換されるだけです。 \mathsurroundは、数式モードに出入りするときの空白に関するパラメータのようです。数式モードでないところで書いたときでも内部的には数式モードで描画される（後述）ので、その調整用っぽいです。 \nulldelimiterspaceはよくわかりませんでした。

\@hat

これは開きかっこを保持する変数のようです。後では閉じかっこを保持することになります。

\sht@im

かっこの中身を保持する変数のようです。

\@t

今の環境（数式モードの中か？など）によって表示するものを切り替える機能を持つ\mathchoiceを使っているようです。

\g@rin

\left\@hat\vphantom{\sht@im}\right.によって正しい高さの開きかっこだけを描画しています。 \vphantomは中身を描画せず中身を描画した時の高さになるようなものです。 \right.は閉じかっこを描画しないで\leftを閉じるものです。

k@fel

二重かっこを描画する部分です。まず\setbox0=\hbox{$\@fen\g@rin$}で適切なかっこを数式モード描画したものをbox0変数に入れます。 \kernは水平方向の位置制御、\wd0はbox0変数の幅、\llapは中身を重ねて描画するもののようです。 \copy0でbox0変数の中身を描画しています。

pt@h

開きかっこの詰め具合で必要な開きかっこを描画するようです。

本体

\pt@h\sht@im\Rightが本体で、適切な開きかっこと中身を打ち出し、このマクロのパターンマッチで消えた\Rightを復活させます。

\Right

\@hat変数に閉じかっこを入れてから\@tを呼び出すことで、上と同じ方式でうまく二重かっこを描画しています。

参考文献