リーディングスキルテストの「あの問題」に対する私見

Twitter で一時期話題になった（テストの）問題がある。

（画像引用元）

率直に言って、ひどい文である。原作者によれば「意図的にわかりにくくした」ということだが、文が「わかりにくい」ことと「悪い」ことは直行する概念であって*1、悪文は悪文である。

これがどう悪いかは後で説明することとして、とりあえずは解答を確認しておこうと思う。

*1:「わかりにくいけどよくできた文」「わかりやすいけどひどい文」はそれぞれ存在する。

ICFPC 2016

今年は 4 年ぶりの単独参加。実は最近オレオレ言語、それもいわゆる日本語プログラミング言語を作っていて、今年は日本主催らしいし、それならばと半ば思いつきでその言語を使うことを決心。さすがに自分の趣味に他人を巻き込むわけにもいかないので、当然にして単独参加と決まったわけである。昨年のチームメートには声すらかけなかったのだけど、今になって思えば一言ぐらい言及してもよかったかなあ…。まあ固定のチームというわけではないので気にしないことにする。

もともとまともな戦いをするつもりはなかったが、実態は予想以上に困難であった。何と言ったって機能が足りない！この日のために準備（＝開発）をしてきたとはいえ使える時間には限りがあり、しかも一週間前に重大な問題が発覚して方針変更を余儀なくされたため、機能の一部は未実装だったり、実装しても試しに動かすことすらしていない状態のまま挑まざるを得なかった。コンテスト中に実装するまで this とか true/false に対応する単語はなかったし（ひどい）、コンストラクターを定義する手段は今でもない（本当にひどい）。もっとも後者はデフォルトコンストラクター（自動生成されるやつ）とクラスメソッドの組み合わせで何とかなってしまった*1という事情がある。ほかにもコンテスト中に処理系に加えた変更はこれだけ存在する

そんな状況だから、REST の API を叩いて、問題を一通りダウンロードするツールを書くだけで最初の 12 時間を使い切るなど、とても解法にまで手が回りそうな雰囲気はなかった。一方、審判の発言を素直に聞いて、適当に人手で問題を作ってアップロードしていたのだが、これがまるで解かれず、実質的にコードを 1 バイトも書かずして途中経過で 20 位前後まで浮上するという怪奇現象を見ることになる。最終的にはそれなりに解かれて点数も順位も下がったが、なお点数が 5 桁である可能性は極めて高い。

さらに、追い打ちをかけるように、ユーザー定義型を汎用型のパラメーターとして渡すとコンパイラーが謎の場所で落ちるというトラブルにも見舞われた（例：「頂点型の リスト型」*2）。これは、雑に言えば、コンパイル中はユーザー定義型は型として不完全な状態にあることに起因している（と思われる）のだが、頂点と多角形にあたる型をそれぞれ別のコンパイル単位で定義する（アセンブリを別にする）という逃げ道に気づかなければ自作言語の使用を諦めざるを得なかった可能性もあり、かなり危険な状況であった。

終了まで 16 時間を切った頃、ようやく「手で解いた手順をプログラムとして記述すると解答を出力してくれる」という現実的な着地点を見出し、そこで一気にモチベーションが上がる。最終的には徹夜してコンテスト終了まで完走するはめになったが、目的はほぼ達成された。以下はそのプログラムからの抜粋。

問題８を解くとは　メソッド
　　折り紙を準備する
　　「1,0」の　座標から　「0,0」の　座標に　折り紙を　折る
　　「0,1」の　座標から　「0,0」の　座標に　折り紙を　折る

大事なことなので 2 回言うが、これはれっきとしたプログラム（の一部）である。まあ、百戦錬磨の読者諸氏からみれば鉤括弧なり空白なりが不自然だからわざわざ言う必要もないか。どちらにせよ、プログラムをコンパイルしてこのメソッドを実行すれば「折り紙」の内部状態が正しく変化する。

このように、コンテストという観点からすれば単独参加＋独自言語という事情を勘案してもなおお粗末であったと言わざるを得ないが、言語設計に関してさまざまな知見が得られたのは有意義であった。正直、2 日目の夜頃にはこの言語は投げ捨てたほうがいいのではないかと思い始めていた。たとえば、二直線の交点を求めるメソッドの定義はこんな感じである。

※　＜相手＞と　＜自分＞の　交点　→　＜座標＞
※　ａｘ＋ｂｙ−ｃ＝０
交点は　メソッド
　　引数は　直線型
　　戻り値は　座標型

　　（引数を）　相手と　名付ける
　　相手の　ａと　自分の　ｂの　積から　相手の　ｂと　自分の　ａの　積を　引いて
　　　　約分して　分母と　名付ける
　　点Ｐは　座標型の　変数
　　相手の　ｃと　自分の　ｂの　積から　相手の　ｂと　自分の　ｃの　積を　引いて
　　　　分母で　割って　約分して　点Ｐの　Ｘ座標に　入れる
　　相手の　ａと　自分の　ｃの　積から　相手の　ｃと　自分の　ａの　積を　引いて
　　　　分母で　割って　約分して　点Ｐの　Ｙ座標に　入れる
　　点Ｐを　返す

こんなコードばかり書いていたのでは嫌にもなる。

しかし、垂直二等分線を求めるメソッドが必要だと気づいてコードを書いたところ、最終的には次のようなものになった。

※　＜点＞と　＜点＞の　垂直二等分線　→　＜直線＞
垂直二等分線は　クラスメソッド
　　引数は　座標型、座標型
　　戻り値は　直線型

　　（第二引数を）　点Ｑと　名付ける
　　（第一引数を）　点Ｐと　名付ける
　　点Ｐと　点Ｑの　中点をとおり　点Ｐと　点Ｑを　通る直線に　直交する直線

引数をスタックから一時変数に移しているのがダサいのは置いておくことにして、一番下の行を読んで欲しい。ブログラミングを知らなくたって、日本語話者で中学・高校レベルの数学ができれば、これはいかにも垂直二等分線を求めようとしていると一目見ただけでわかる。これでもちゃんと動くんだよ！このとき僕はこの言語のポテンシャルを垣間見たわけである。設計の一部は再考の必要があるが、Mind（もとにした言語）のよさはちゃんと息づいていた。

参戦記が思ったより長くなってしまったので、言語自体の細かい話は別の機会に譲ることにする。

*1:これはれっきとした Factory パターンなのでそんなに悪くなかったりする。

*2:C# の List<頂点型> にあたる。

Texas Hold 'em の勝率計算

年末にこんなコードを書いていた。

https://gist.github.com/yuizumi/a15bdde89f79fab9dded

ポーカー（テキサス・ホールデム）の大会中継なんかを見ていると、各プレイヤーの勝率（ポットを獲得する確率）が画面上に表示されたりする。聞いた話によると、それらの勝率の値はモンテカルロ・シミュレーションで計算されているらしいのだけれど、52C5 = ~2.6M だし、全パターン列挙しても大丈夫じゃないの？という話になった。

この見積もりは実際には少し甘い。たとえば一対一の場面（ヘッズ・アップ）であれば 48C5 × 7C5 × 2 = ~72M 回*1ほど役判定をしなければならず、毎回愚直に役判定を行ってしまうと秒単位で時間がかかる。しかしよく考えると、スートが関係する役ってフラッシュ（とストレート・フラッシュ）だけだし、ランク（数）の組み合わせって全部で 13^5 = ~370K ぐらいしかないし、競プロ御用達の前計算でもしておけば速くなるんじゃないの？みたいな感じでできあがったのが上のコードである。

手元のラップトップ（MBA w/ Core i7）で走らせるとこんな感じになる。計算時間的にはプレイヤーが 4 人のときが一番大変なのだが、それでも 200 ms 未満で結果が帰ってくる。

$ time ./holdem TC2D 2HQH 7D5D 4H2S
Player #1: TC2D --  17.66% / 80.68%
Player #2: 2HQH --  35.09% / 63.25%
Player #3: 7D5D --  34.06% / 65.11%
Player #4: 4H2S --  11.53% / 86.82%

real    0m0.165s
user    0m0.160s
sys     0m0.003s

一番上の行は 10♣2♦ を持ったプレイヤーの単独勝利（ポットを独占）の確率が 17.66% で、敗北（ポットを完全に失う）の確率が 80.68% であるという意味。引き分け（スプリット）があるので両者を足しても 100% にはならない。

一応、場札（の一部）の指定も可能にした。場札があると考えるパターンの数が激減するので計算も一瞬で終わるようになる。以下は場札の最初の 3 枚（フロップ）が 3♦3♥A♦ とわかった場面。

$ time ./holdem TC2D 2HQH 7D5D 4H2S +3D3HAD
Player #1: TC2D --   6.10% / 86.34%
Player #2: 2HQH --  28.78% / 63.66%
Player #3: 7D5D --  44.27% / 50.98%
Player #4: 4H2S --  13.29% / 79.15%

real    0m0.021s
user    0m0.018s
sys     0m0.003s

みなさまよいお年を。

〔22:45 更新〕つまらないことに気がついて 2〜3 割ほど高速化したので計算時間に関する記述を改めました。どれだけつまらないかは Revisions を参照してください。

*1:各々に 2 枚ずつ、合計 4 枚が手札として配られているので、場札は残り 48 枚のうちの 5 枚。また、手札 2 枚と場札 5 枚の合計 7 枚から任意に 5 枚を選ぶので 7C5 が掛かる。最後の 2 はプレイヤーの数。

ABC を bash で解いた話

この記事は Competitive Programming Advent Calendar 2015 の 10 日目の記事です。

はじめに

ここ最近はあまりやっていないのですが、ABC（AtCoder Beginner Contest）の過去問を bash で解くという謎の縛りプレイをやっています。一応、競技プログラマとしての経験があるにはあるので、普通の言語でよければ ABC の問題ぐらいは解けるのですが、bash 縛りとなると一筋縄ではいきません。それでも 30 問以上は解いていて、C 問題、D 問題もそれなりに解いています。

実際に書いたコードに関しては、こちらのリポジトリ（github.com）にリンクがあるのでそちらを参照してください。Wiki にも少しだけページがあって Tips 等が書いてあります。この記事ではもう少し背景寄りの話をしようかと思います。

あちこちで話はしている気がするので、聞き覚えのある人もいるかもしれません。

きっかけ

ある日、通勤電車の中だったか、TL を眺めていたらこんな Tweet が。

すごい→ Bashで競技プログラミング #w8lt #w8lt4 #w8lt http://t.co/usUsyEhk1Q

— 高橋 直大(chokudai) (@chokudai) 2015, 7月 30

僕は bash が大好きなので「おおっ」と思ったわけです。ちょっとしたライバル心みたいなものも芽生えました。ところが、実際にその中身を見てみると、

• 単に awk または bc を呼んでいるだけの解答が結構な割合で存在する
• 使われている文法がおしなべて古い（後述）
• スライドに嘘が書いてある（「ビット演算がない」とあるが実際は存在する）

というように、bash を十分に使いこなしていない様子がうかがえました。「bash の実力はこんなものではない。」ライバル心（?）はむしろある種の危機感へと変わっていったのであります。

〔おことわり〕この記事に jmatsu さんを貶める意図はありません。むしろ一方的に攻め立てる感じになってしまって申し訳ないです。

文法が古い？

いわゆる if 文などで条件判定をするとき、

[ "$a" = hoge ]
[ "x$a" = xhoge ]

のように書く人が多いと思いますが、bash では

[[ "$a" = hoge ]]

のように書くべきだろうと思います。[ ... ] は基本的にコマンドなので引数解釈が発生しますが、[[ ... ]] は bash のビルトインなので空文字列の扱いといった罠にはまることがありません。

コマンド展開も `...` ではなく $(...) のほうが便利だし安全です。前者はネストできませんが、後者ならばできます。途中に括弧があっても適宜解釈してくれるので「うっかり括弧を閉じてしまった」といった心配をする必要もありません。

算術演算に expr を使うのもやめるべきでしょう。代わりに $((...)) という組み込みの機能があるのでそちらを使いましょう。expr だと整数は 32 ビットになりますが、$((...)) ならば 64 ビットです。言うまでもなく、競技プログラミングでこの差はとても重要です。

ほかにもいろいろありますが、とりあえずこのぐらい抑えておけば十分でしょう。ちなみに、[[ ... ]] は bash にしかありませんが、$(...) と $((...)) は (d)ash にもあります。

〔追記〕何かの理由で expr は 32 ビットで計算されると勘違いしていましたが、改めて確認したところ、手元でも AtCoder の環境でも 64 ビットで計算されるようです。ここにお詫びして訂正します。（12/15）

使っているコマンド

厳格にやるならば bash の内部コマンドのほかは使わないということになるでしょうが、さすがにそれでは何かとしんどいので、いかにも /bin に入っていそうなコマンドは基本的に使っています。ただ、awk、bc に関しては、無制限に許すとそれだけで事足りてしまうので、以下のような制限を設けています。

• awk は引数抽出（e.g. '{ print $3 }'）に限って使用を認める
• bc は小数計算と多倍長計算に限って使用を認める

もっとも bc はあまり積極的には使っていません。出力として小数を要求されていても、値を適当に嵩上げするだけでたいてい事足ります。たとえば、値が 0.5 単位で変わるのであれば、常に値を 10 倍（あるいは 2 倍とか）しておけばいいわけです。固定小数点と言うこともできますね。AtCoderプログラミング講座（解答）はこの方法で解いています。

シェル芸

bash といえばいわゆるシェル芸…と言いたいところですが、実のところ出番はあまりありません。ほとんどのスクリプトは C++/Java と相互に直訳できるのではないかと思うほどで、そういったスクリプトでは bash らしさはまったく見当たりません。禁止された数字に対するこの解答は典型的な一例です。

もちろん、時にはシェル芸が使えることもあって、jmatsu 氏のスライドにも紹介されているような罠（解答）、回転（解答）などは好例です。あと、満点解法ではないけれどトランプ挿入ソートの部分点解法も bash でなければできない芸当だろうと思います。

つらみ

何がつらいって遅くて遅くてしょうがない。よくある計算時間の見積もりとして「繰り返しが 10^8 回ぐらいならば基本的にセーフ、10^9 回だとかなり危険」みたいなものがあると思います。Ruby とか Python とかだと 2 桁ぐらい下がって 10^6〜10^7 あたりが判断基準になりますね。bash ではさらに 2 桁下がります。つまり 10^4 は大丈夫だけど 10^5 は基本的にまずい。

これはとても大変です。トリボナッチ数列（解答）は普通にループを回していたのでは間に合わないので、行列の累乗という何ともオーバースペックな手法にお出まし願うことになります。感雨時刻の整理（解答）は入力に 10 万個の要素があって読み込むことすらままならないので、sed などで前処理をして bash で処理する入力の量を減らす必要があります。トランプ挿入ソート（解答）の満点解法となるともはや手段がなくて bc に魂を売らざるを得ません。

ほかには実数演算がないという問題がありますが、これは前出のとおり回避策があるし、いざとなれば bc を使えばいい話なので、ABC に限ればあまり困ることはありません。あとは文法に癖があるというぐらいで、道具立ては（ABC のレベルの問題に限れば）だいたい揃っているという印象があります。

やってよかったこと

易しく解ける問題でも解法をきちんと考えるようになったおかげで、以前に比べると、アルゴリズムを考えることに比重のあるタイプの問題がいくらか多く解けるようになった気がします。あと、有用かどうかは別として、今までほとんど知られていなかった知見が得られたというのは悪い話ではないでしょう。

最後に一言

bash はあくまでもシェルです。言語としてはチューリング完全ではありますが、複雑なプログラムを書くために作られたものではありません。コマンドの逐次実行に毛が生えた程度のものを超えるようなスクリプトを書くのは、そもそも勧められた選択ではない、ということは心に留めておいてもよいでしょう。

次は @n_knuu6 さんです。

KUPC 2015 の I 問題（ハウスシャッフル）の私的解説

懇親会の最中にハウスシャッフルの解説を複数の人から求められたので、私の解答を説明しておくことにします。

まずは、シャッフルという操作を理解しましょう。たとえば σ(1) = 3 だとします。シャッフルの定義により、b[i, 1] = a[σ(i), 3] または a[3, σ(i)] なので、1 列目にはもともと 3 列目にあったお菓子が現れます。図を描くとこういうことですね。

         .                    x
        . .                  x .
       . . x                x . .
      x . x .      -->     x . . .
     . x x . .            x . . . .
    . . x . . .          x . . . . .

同じように考えると、σ(x) = y のとき、x 列目にはもともと y 列目にあったお菓子が現れることがわかります。

このままでは少しやりにくいので、向きを反対にしましょう。たとえば 1 列目にあったお菓子がどの列に現れるのかを考えます。σ(x) = y のとき、x 列目にはもともと y 列目にあったお菓子が現れるのでした。今考えているのは y = 1 の場合ですから、σ(x) = 1 となるような x を考えればいいわけです。いちいち σ(x) = 1 を満たす x と書くのは面倒くさいので、代わりに σ'(1) と書くことにします。一般に σ(x) = y のとき σ'(y) = x ということにします。いわゆる逆置換ですね。σ' を用いると、もともと 1 列目にあったお菓子はシャッフルされると σ'(1) 列目に現れる、と言い換えることができます。σ' がわかれば σ もわかります。というか、ループを回して σ(σ'(k)) = k とするだけです。

さて、家を提示できるのは一度きりなので、それだけで σ ないし σ' が復元できるようにうまく細工しないとなりません。とはいえ、一度に全部を考えるのは難しいので、まずは σ'(1) だけでも求められる方法がないか考えてみます。すでに気づいている人も多いかと思いますが、1 列目に片方のお菓子を置いて、それ以外の列にはもう片方のお菓子を置くことにすれば、1 列目に置いたほうのお菓子がどの列に現れたかを確かめることで σ'(1) の値がわかります。ここではキャンディーを 1 列目に置くことにしましょう。要するにこういうことです（図は σ'(1) = 4 の場合）。

         @                    o
        @ o                  o o
       @ o o                @ o o
      @ o o o      -->     o @ o @
     @ o o o o            o o @ @ o
    # # # # # #          # # # # # #

この例について、それぞれの列にキャンディーが何個あるか数えてみると、4 列目には (N - 1) 個だけありますが、ほかの列には 1 個しかありません。なので、すぐに σ'(1) = 4 だとわかります。

σ'(1) を得られるようになりました。しかし、このままではほかの値がわかりません。そこでもう少しキャンディーを置くことにしましょう。ビスケットの真上の段に注目します。すると、座標が (2, 1)、(3, 2)、(4, 3)、…といったように値が 1 だけずれていることがわかります。試しにキャンディーを置いてみます。

         @
        @ o
       @ o o
      @ o o o
     @ @ @ @ @
    # # # # # #

このとき、それぞれの列のキャンディーの個数は次のようになっていることがわかります。

• 2 列目は (2, 1)、(3, 2) の 2 個。
• 3 列目は (3, 1)、(3, 2)、(4, 3) の 3 個。
• 4 列目は (4, 1)、(4, 3)、(5, 4) の 3 個。
• 以下、(N - 1) 列目までは同様。
• N 列目は (N, 1)、(N, N - 1) の 2 個。

なので、シャッフルした後の列を調べて、キャンディーが 2 個だったら、その列はもともと 2 列目だったか N 列目だったかのどちらかということになります。区別したいですね。(2, 1) のキャンディーをマシュマロにしてしまいましょう。

         @
        @ o
       @ o o
      @ o o o
     o @ @ @ @
    # # # # # #

こうすれば、2 列目は 1 個、N 列目は 2 個、となって区別がつきます。きっと 1 列目のキャンディーが (N - 1) 個から (N - 2) 個になっても大丈夫でしょう。念のため N の範囲を確認しますか。

6 ≤ N ≤ 200

1 列目には最低でも 6 - 2 = 4 個のキャンディーが現れます。大丈夫でしたねｗ。

これで σ'(1)、σ'(2)、σ'(N) は何とかなりました。あとは σ'(3)、…、σ'(N - 1) ということになりますが、実は σ'(3) はすぐにわかります。(2, 1) のキャンディーを取ってしまったので、2 列目には (3, 2) にしかキャンディーがありません。シャッフルすると 2 列目は σ'(2) 列目に移って、ただひとつのキャンディーは (σ'(3), σ'(2)) ないし (σ'(2), σ'(3)) に現れるわけですが、すでに σ'(2) はわかっているので、σ'(2) ではないほうの値が σ'(3) となります。

σ'(3) がわかれば、今度は σ'(3) 列目を調べて、そこにあるキャンディーのうち (σ'(3), σ'(1))、(σ'(3), σ'(2)) でないものが (σ'(4), σ'(3)) であるとわかり、先ほどと同じ理屈で σ'(4) がわかります。σ'(4) がわかると、σ'(5) もわかります。以下、同様にして σ'(N - 1) まで（あるいは σ'(N) まで）わかります。

というわけで、前出のとおりにお菓子を配置して、シャッフル後の家が提示されたらそれぞれの列のキャンディーの個数を数えて、(N - 2) 個だったらその列が σ'(1)、1 個だったら σ'(2)、あとは σ'(k) 列目を調べて σ'(k + 1) を求めて、最後に σ' から σ を求める、というのが正解（のひとつ）なのでした。

Super-deep Learning (?!)

　ディープラーニング（深層学習）が大きな盛り上がりを見せる中、さらにディープな世界に足を踏み入れた研究者のグループが現れ、科学者たちの間で大きな波紋を呼んでいる。その話題の元になっているのが、ヘット・バイル博士（Het Vile）たちのグループが発表した「半機械学習（Semi-machine Learning）」と名付けられた論文である。

　バイル博士たちのアイデアはあまりにも斬新である。一人の人間にあらかじめ特殊な電極を埋め込んでおき、計算機とそれらの電極を「変換器」と呼ばれる装置を挟んで接続する。計算機が学習データを受け取ると、そのデータは変換器によって人間の脳が直接理解できる電気信号に変換され、電極を通じて伝達される。電気刺激を受けた脳は活性化し、それによって脳細胞の内外で電位が変動する。その電位変動を先とは別の電極が感知し、出力信号として変換器を通して計算機に送られる。計算機はその出力信号をもとに「モデル」を構築する。計算機内部で完全なモデルを構築するため、一度学習が終われば、人間がいなくても入力データに対する出力を得ることができる。

　　（後略）

（ディープラーニングよりもディープな機械学習）

さすがにこれはやばいだろ…。

ICFPC 2014

昨年度と同一のメンバーで参加した。今年は（結果的に）それぞれが明確な役割を果たした形となり、その点において昨年よりも進歩したといえるが、自分自身については正直ぱっとしなかったと言わざるを得ない。直前に体調を崩してしまい、あまり食べ物が食べられず、体力もやや低下していたことが影響していたのか、終始集中力不足に苛まれていた。

基本的には Ghost AI の開発は比較的順調だったが、Lambda man AI は開発が遅れ、ベースができたのは終了のわずか 2〜3 時間前である。それから果物をとったりおばけを食べたりするコードを少し追加して、終了の 15 分前までデバッグをするはめになった。提出したのは締め切りのわずか 2 分前である。

そのような事情なので、Lambda man AI の活躍はあまり期待できないだろう。チームの成績は Ghost AI がどれだけ活躍できるかにかかっていると思われる。

リンク -- ホームページ | ソースコード

今年は、2010 年度の記事にならって、人物別にその果たした役割をまとめることとしたい。

@cocodrips

ほぼ'''初日'''から Ghost AI を書いていた。Lisp 系の言語の経験がなく、OCaml も苦手だったということもあって、Lambda man AI には手が出せない（コードが書けない）と踏んだらしい。結果的にはこの選択が大当たりすることになる。

本人がブログに参加記をあげているので、詳しいことはそちらを参照されたい。

@n__yoda（was @buno_y）

OCaml を GCC に変換するコンパイラを作成した。OCaml と書いたが、正確には OCaml 風の文法をもった型のない純粋関数型のオレオレ言語である。講義の課題で書かされたコンパイラをもとにしたらしい。

@yuizumi

基本的に Lambda man AI を書いていた。Lightning Division ではほとんど素の GCC で AI を書いた（プリプロセッサを書いていたのでラベルだけは使えた）。Full Division では n__yoda の言語を（慣れないなりに）使っていた。