Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

テトロミノの置き方を数えよう の 解説解題

問題

問題は
テトロミノの置き方を数えよう
に置いた。

タイトルのとおり、テトロミノの置き方を数える問題。
テトロミノの種類は裏返しや回転で同じになるものは同じとみなすので I, L, O, S, T の 5種類。

出題意図など

テトロミノでなんか一問作ろうと思ったんだと思う。まあ憶えていないわけだけど。
テトロミノと言えば
テトロミノ認識〜 横へな 2012.10.6 。
これをそのまま出すわけには行かないので、置き方を数える問題にした。んだと思う。

特に数学的背景やコンピューターサイエンス的含意はない。

実装方針

  1. 「ff 9d a5 a5 dd 9b b1 ff」のような入力文字列をなんとかする
  2. テトロミノの候補を列挙する
  3. テトロミノの候補がどのテトロミノなのか、同定する
  4. 集計結果の整形

の4段階になると思う。それぞれ説明すると。

入力文字列を何とかする

JavaScript 以外の環境だと 64bit 整数を扱える場合が多いと思う。
入力はちょうど 64bit なので、ひとつの整数にしてしまえばよい。
ruby で書くと、こんな

field=src.gsub(/\s/, "").to_i(16)

感じ。座標 x,y の値を知りたければ、ruby の場合

field[x+y*8]

でOK。

もちろん、空白で区切って 8個の整数にしてもいい。その場合は こんな

field=src.split(" ").map{|x| x.to_i(16) }

感じになる。座標 x, y の値は、ruby の場合

field[y][x]

となる。

テトロミノの候補を列挙する

列挙は、ビットが立っていないマスを集めてから combination すればいい。遅いかもしれないけど。
field に64bit 分の地図が入っているとすると、こんな感じになる：

whites=(8*8).times.select{|i| field[i]==0 }
whites.combination(4) do |a,b,c,d|
  # do something here
end

64個から4つ選ぶので、 64万通りぐらい。微妙。
ここは遅いかもね、と思いながら次へ進む。

テトロミノの候補がどのテトロミノなのか、同定する

裏返しや回転を無視するというルールなので、裏返しや回転に影響されない情報でテトロミノを記述すれば良い。
裏返しや回転 に影響されない情報といえば、距離。
というわけで、4つのマスの距離の自乗を収集してみると、これがズバリうまくいくのである。

具体的にはこんな感じ：

def dist( a, b )
  (ax,ay),(bx,by)=[a,b].map{ |x| x.divmod(8) }
  dx=ax-bx
  dy=ay-by
  dx*dx+dy*dy
end

def ident(*a)
    d=a.combination(2).map{|x,y|
      dist( x, y )
    }.sort.join
    case d
    when '111449' then 0 # I
    when '111245' then 1 # L
    when '111122' then 2 # O
    when '111225' then 3 # S
    when '111224' then 4 # T
    else
        nil
    end
end

ident(1,9,10,11) とかやると、"L" を意味する 1 が帰ってくる。

集計結果の整形

ident が返す値がインデックスになっているので、そのまま利用すれば良い。

ix=ident(a,b,c,d)
results[ix]+=1 if ix

という具合。

最初の実装

というわけで、全部つなげるとこうなる：

def dist( a, b )
  dx=a%8 - b%8
  dy=a/8 - b/8
  dx*dx+dy*dy
end

def ident(*a)
    d=a.combination(2).map{|x,y|
      dist( x, y )
    }.sort.join
    case d
    when '111449' then 0 # I
    when '111245' then 1 # L
    when '111122' then 2 # O
    when '111225' then 3 # S
    when '111224' then 4 # T
    else
        nil
    end
end

def impl(field)
  whites=(8*8).times.select{|i| field[i]==0 }
  whites.combination(4).with_object([0]*5) do |(a,b,c,d),r|
    ix=ident(a,b,c,d)
    r[ix]+=1 if ix
  end
end

def solve(src)
  impl(src.gsub(/\s/, "").to_i(16)).join(",")
end

で。実行すると手元のマシンで最悪5秒ぐらい。やっぱり遅い。
impl の combination が遅そうだとわかっているんで、ここを速くする。

aとbが離れているなら、cとdを試す必要ないよね、とか、aとc が離れているなら d を試す必要ないよね、とか、そういうことを書けば速くなりそうだ。

で。最終的に下記のようになる：

#マンハッタン距離
def mdist( a, b )
  dx=a%8 - b%8
  dy=a/8 - b/8
  dx.abs+dy.abs
end

#ユークリッド距離の自乗
def dist( a, b )
  dx=a%8 - b%8
  dy=a/8 - b/8
  dx*dx+dy*dy
end

def ident(*a)
    d=a.combination(2).map{|x,y|
      dist( x, y )
    }.sort.join
    case d
    when '111449' then 0 # I
    when '111245' then 1 # L
    when '111122' then 2 # O
    when '111225' then 3 # S
    when '111224' then 4 # T
    else
        nil
    end
end

def impl(field)
  whites=(8*8).times.select{|i| field[i]==0 }
  whites.combination(2).with_object([0]*5) do |(a,b),r|
    next if 3<mdist(a,b)
    whites.select{ |c| c<[a,b].min }.each do |c|
      next if [a,b].any?{ |x| 3<mdist(x,c) }
      whites.select{ |d| d<c }.each do |d|
        next if [a,b,c].any?{ |x| 3<mdist(x,d) }
        ix=ident(a,b,c,d)
        r[ix]+=1 if ix
      end
    end
  end
end

def solve(src)
  impl(src.gsub(/\s/, "").to_i(16)).join(",")
end

これで、最悪でも 0.1秒以下になる。
ident が呼ばれる回数が 約64万回だったのが、3205回に減った。200倍ぐらい違う。
枝刈り重要。

とはいえ

とはいえ、もっといいアルゴリズムがあるような気がしている。
どうだろう。

直角を探せ！ 〜ピタゴラスさんありがとう〜 の解説・解題

問題

問題は
直角を探せ！ 〜ピタゴラスさんありがとう〜
に置いた。

三辺の長さを与えるので、どこに直角があるのかを求めようという問題。
タイトルに「ピタゴラスさん」とあるので、三平方の定理を使うというところまでヒントがある。

出題意図など

この問題も、浮動小数点を使ったら負けるということを意図している。
テストケースの最後にある

5048.5204,8157.7159,9593.5336

は、浮動小数点をつかって計算すると

#ruby
[5048.5204,8157.7159].map{|x| x**2 }.sum #=> 92035886.93432897
9593.5336**2 #=> 92035886.93432897

となり、直角三角形であるように見えてしまう。
しかしこれは誤差なしで計算すると

#ruby
require "bigdecimal"
["5048.5204","8157.7159"].map{|x| BigDecimal(x)**2 }.sum #=> 0.9203588693432897e8
BigDecimal("9593.5336")**2 #=> 0.9203588693432896e8

あるいは

#ruby
[5048.5204r,8157.7159r].map{|x| x**2 }.sum #=> (9203588693432897/100000000)
9593.5336r**2 #=> (143806073334889/1562500)

なので、ほんの少し直角ではない。

というわけで、JavaScript の人には厳しい問題だったわけだけど、言語の選択は自由なので ruby や python のような有理数型がある言語を選べば良いと思う。

実装例

まあ ruby で。
主要部分のみだけど

def solve(x)
  lens=x.split(",").map( &:to_r)
  m=lens.max
  r=(lens-[m]).inject( m*m ){ |acc,e| acc-e*e }
  if r==0
    (lens.index(m)+?A.ord).chr
  else
    "x"
  end
end

こんな感じ。
「map」の中の「to_r」がポイント。ruby 便利だね。

過去問の振り返り #10〜#19

#9 から中学入試シリーズになっている。

10.中学入試から：単位のある計算

問題・解説・実装例が
中学入試から：単位のある計算」の解説・解題 - Codeへの愛とCuriosity
にある。

11.中学入試から：正三角形？二等辺？

問題・解説・実装例が
http://nabetani.hatenablog.com/entry/codeiq_clatri_q1097:titile
にある。

12.中学入試から：数字の個数

問題・解説・実装例が
「中学入試から：数字の個数」の 解説・解題 - Codeへの愛とCuriosity
にある。

13.中学入試から：図形と場合の数

問題・解説・実装例が
「中学入試から：図形と場合の数」の 解説・解題 - Codeへの愛とCuriosity
にある。

14.中学入試から：概数と計算

問題・解説・実装例 が
CodeIQ に出した「中学入試から：概数と計算」の 解説解題 - Codeへの愛とCuriosity
にある。

15.中学入試から：対称軸の本数を数えよう

問題・解説・実装例 が
CodeIQ に出した「中学入試から：対称軸の本数を数えよう」の 解説・解題 - Codeへの愛とCuriosity
にある。

16.対戦型 hello, world!

問題を
対戦型 hello, world! - CodeIQ q595
に置いた。
解説記事は
対戦型 hello, world! の解説・解題 - Codeへの愛とCuriosity
に書いてある。

対戦楽しかったよね。

17.Minority's hello, world

問題を
Minority's hello, world
に置いた。
解説記事は
Minority's hello, world の 解説・解題 - Codeへの愛とCuriosity
にある。

18.直角を探せ！ 〜ピタゴラスさんありがとう〜

この辺りから解説をサボっている。
問題は
直角を探せ！ 〜ピタゴラスさんありがとう〜
に置いた。
さて。解説どうしよう。

まあこの問題は簡単だし、あとで書くことにしよう。

……で、書いた。
直角を探せ！ 〜ピタゴラスさんありがとう〜 の解説・解題 - Codeへの愛とCuriosity

19.テトロミノの置き方を数えよう

これも解説をサボっている。
問題は
テトロミノの置き方を数えよう
に置いた。

これもあとで書くことにしよう。

……で、書いた。
テトロミノの置き方を数えよう の 解説解題 - Codeへの愛とCuriosity


今日のところはこれぐらいで。
宿題が２つもできてしまった。ぐぬぬ。

でも需要ある？

過去問の振り返り #0〜#9

0. カードゲームの役を判定する

2018-04-26から1日間の記事一覧 - Codeへの愛とCuriosity で問題を紹介している。
実装例と解説は
CodeIQ の「カードゲームの役判定」問題 by @Nabetani - 名古屋で数学するプログラマ(仮) に詳しい。

1. テトロミノ＋ビンゴ！

問題の紹介も、実装例も解説も拙記事
CodeIQ に出した「テトロミノ＋ビンゴ！」の解説・解題 - Codeへの愛とCuriosity
にある。

2. メソッド名を当てる空欄補充問題

問題の紹介と解説が 拙記事
CodeIQ に出した「メソッド名を当てる空欄補充問題」の解説・解題 - Codeへの愛とCuriosity
にある。

3. 最大公約フィボナッチ数(?)

問題の紹介も、実装例も解説も拙記事
CodeIQ に出した「最大公約フィボナッチ数(?)」の解説・解題 - Codeへの愛とCuriosity
にある。

4. カラフルな八面体を転がそう。

こちらも拙記事
CodeIQ に「カラフルな八面体を転がそう。」の、解説・解題 - Codeへの愛とCuriosity
に問題の紹介・実装例・解説 がある。

5. hello, world × 3

大変楽しい問題だった。
拙記事
CodeIQ に出した「hello, world × 3」の解説・解題 - Codeへの愛とCuriosity
に問題の紹介・実装例・解説 がある。

6. 4つの数と四則と括弧

拙記事
CodeIQ に出した「4つの数と四則と括弧」の解説・解題 - Codeへの愛とCuriosity
に、問題の紹介・実装例・解説 がある。

7. JavaScriptじゃんけん大会！

これも大変楽しい問題だった。
またどこかでやりたいぐらい。
拙記事
CodeIQ に出した「JavaScriptじゃんけん大会！」の解説・解題 - Codeへの愛とCuriosity
に、問題の紹介・実装例・解説 がある。
記事からリンクしている jangkeng.zip のリンク先は生きている。

8. 長くなるように、増え続けるように

拙記事
「長くなるように、増え続けるように」の 解説・解題 - Codeへの愛とCuriosity
に、問題の紹介・実装例・解説 がある。
面白い問題だったと思う。

9. 中学入試から：数列の和

中学入試シリーズの一問目。
拙記事
「中学入試から：数列の和」の解説・解題 - Codeへの愛とCuriosity
に、問題の紹介・実装例・解説 がある。
問題文から受ける印象よりも簡単だと思う。

今日のところはこれぐらいで。
最初の方は真面目に記事を書いていて、私偉いなぁと思った。

CodeIQ の出題者業のことを振り返ってみる

もともと yhpg( https://yhpg.doorkeeper.jp/ ) を 2012年7月からやっていて。
そのことがリクルートの人に見つかって。
CodeIQ に誘われて。
2013年 9月26日に、出題者となった。

yhpg に出している問題の焼き直しでいいと言われていたので、最初は「カードゲームの役を判定する」という問題で「ポーカー( https://qiita.com/Nabetani/items/cbc3af152ee3f50a822f ) 」の焼き直しにした。

それは、こんな問題だった：

■概要
6枚のカードを使って行うカードゲームがあります。その役を判定するプログラムを書いて下さい。

■役は下表のとおりです。

役名 記号 意味 例
アンサー An 同一ランクの4枚組と、同一ランクの2枚組 ♥2, ♠2, ♦2, ♣2, ♠A, ♥A
シンクダブルトリオ sDT 同一ランクの3枚組が、2組。各3枚組は、スートの組み合わせが同一。 ♠10, ♥10, ♦10, ♠Q, ♥Q, ♦Q
ダブルトリオ DT 同一ランクの3枚組が、2組。sDT ではない。 ♠10, ♣10, ♦10, ♠Q, ♥Q, ♦Q
シンクコントトリプルペア scTP 同一ランクの2枚組が、3組。各2枚組はスートの組み合わせが同一。3つのランクが連続している。 ♠9, ♥9, ♠10, ♥10, ♠J, ♥J
コントトリプルペア cTP 同一ランクの2枚組が、3組。3つのランクが連続している。scTP ではない。 ♠9, ♣9, ♠10, ♥10, ♦J, ♥J
シンクトリプルペア sTP 同一ランクの2枚組が、3組。各2枚組はスートの組み合わせが同一。scTP ではない。 ♠9, ♥9, ♠10, ♥10, ♠A, ♥A
トリプルペア TP 同一ランクの2枚組が、3組。scTP, sTP, cTP のいずれでもない。 ♠3, ♥3, ♦10, ♥10, ♠A, ♣A

■ランクの連続について

ランクは A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A のように並んでいると考えます。つまり、「A, 2, 3」や、「9, 10, J」、「J, Q, K」などは連続したランクですが、「2, 4, 6」、「7, 10, K」 などは連続したランクではありません。
なお、「K, A, 2」は連続したランクとはみなされません。通常のポーカーと同じです。

■入力について

入力は
HJ,D10,H2,H10,S2,CJ
のような形式をしています。見ての通り、各カードがコンマで区切られています。
各カードは HJ や D10 のような形式です。最初の文字がスートを表しています。スートは
S, H, D, C
のいずれかの文字で、それぞれ
♠, ♥, ♦, ♣
を表しています。
スートを除いた部分（つまり、 J や 10 ）がランクを表しており、ランクは
A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K
のいずれかの文字列で、見た通りのものを表しています。

■補足

手札にあるカードの順序は役に影響しません。
一組のトランプで作れる六枚組しかありません。つまり、 ♥3 が二枚あったりはしません。
不正な入力に対処する必要はありません。

※しかし、なんで「アンサー」なんだろう。全然憶えていない。

で。
data.txt に1万件ぐらい入力があって、各役がそれぞれ何件あるのかを数えるということになっていた。

data.txt を用意したのは、ソースコードを見る前に間違っているかどうかを知りたかったから。

挑戦者数は 50名募集のところ 52名だった。満員御礼。

フィードバックは
http://nabetani.hatenablog.com/entry/2013/10/12/231311
の通り、わりと時間を要した。
CodeIQで印象に残った問題 - カードゲームの役を判定する (q476) の通り、ciel さんが非常に珍しく（当時はそんなことは知らなかったが）ミスっていて、そのミスの原因を追ったりするのが楽しかったのを覚えている。

二問目は http://nabetani.sakura.ne.jp/codeiq/tetromino_bingo/ だった。なぜかこれだけは拙サイトに問題を上げてある。何故なのかは憶えていない。
わりと面倒な問題だったと思う。

一番印象に残っている問題は なんといっても hello, world x 3 。( see http://nabetani.hatenablog.com/entry/codeiq_hwx3_q766 )。問題としてはやや難しいけど、大変楽しい問題だった。

コンテスト形式の問題もいくつか出した。

で全部かな。
もっと出したかったんだけど、アイディアが浮かばず。

いずれも金銀銅のメダルは上位3名ぐらいに入らないと取れないという厳しいレギュレーションだった。

この中なら、じゃんけんが一番面白いかな。またどこかでやりたいぐらい。
わりとヘビーなコードが優勝して驚いたことを覚えている。

じゃんけんに限っては手元で実行する必要があるのでセキュリティの問題とかが気になって、投稿される度にソースコードのチェックを人力で行っていた。他は実行くんで動かしたんだけど、実行くんは生きているのだろうか。

あと。割と気に行っている問題は、これも yhpg で出した問題の焼き直しだけど、バス料金。
問題の詳細は http://sw-logic.com/Portfolio/Programing/CodeIQ/1937.php にある。
バスの料金って実世界で適度に複雑になっていて面白いんだけど、それをほぼそのまま出した問題。
大人料金、子供料金、定期券、特別割引、幼児は大人一人につき何人かまで無料で残りは子供料金、とか。

バス料金で思い出したけど、浮動小数点を使うと負けやすい問題を何個か出したよね。
プログラマなら浮動小数点は使い所をわきまえないとひどい目にあうことを知ってないとと思い、啓蒙のつもりで出していた。実際、多くの方がそれで負けていた。私の気持ちは伝わっただろうか。

難し目の問題も出した。
「正方形の分割」( see http://sw-logic.com/Portfolio/Programing/CodeIQ/3283.php )とか「回文数の中央値」( see https://blog.goo.ne.jp/r-de-r/e/ec7c5b11dd4d9d4c0d7b78486f80ab97 )がわりと難しかったんじゃないかなぁ。よくおぼえていない。
人によっては「ぐるぐるペンタゴン」( see http://ange1.hateblo.jp/entry/2017/02/26/233339 )や「外周の折り目」(see http://sw-logic.com/Portfolio/Programing/CodeIQ/3064.php)が難しかったかもしれない。
どうですか？＞読んでいる方

簡単な問題は、「周期表」「異世界のブラウザの判定」辺りかな。

そして。

「ぐるぐる曼荼羅」というそれなりの難しさで、まあまあきれい、それでいて面倒くさく、たぶんオリジナリティがある問題になってよかったと思う。
「ぐるぐる曼荼羅」の図はまだ http://nabetani.sakura.ne.jp/codeiq/3544/huge.html にある。消す予定は特にない。
ちなみに問題の方は

図のとおりに正の整数が全て並んでいます。
数をひとつ指定しますので、その数のマスの上下左右に隣接しているマスの数を、昇順にコンマ区切りで出力してください。
入力は、1以上 十兆以下です。

というものだった。
未挑戦なら是非。


というわけで、4年半に渡り CodeIQ の出題者をやった。
履歴書に書くべき項目が増えたり、Twitter のフォロワーが増えたり、オフラインリアルタイムどう書くに来てくださる人が増えたり、いいことがたくさんあったと思う。悪いことは特に思い当たらない。


終わってしまったのは本当に残念。


CodeIQ は終わってしまったけど、私は依然として オフラインリアルタイムどう書くで出題者をやっている。
次回は 5/26(土)。see https://yhpg.doorkeeper.jp/events/73080 。参加お待ちしています。

今まで出した問題のリスト

前回 今まで CodeIQ に出した問題のリスト - Codeへの愛とCuriosity
前々回 今まで CodeIQ に出した問題 - Codeへの愛とCuriosity
の続き。

まあ自分のためのメモ。

# 問題へのリンク 募集期間 挑戦者数
63 フィボナッチ進数 2017/05/11 ～ 2017/08/11 127人
64 正六角形の分割 2017/04/27 ～ 2017/07/27 145人
65 正方形の分割 2017/05/18 ～ 2017/08/18 57人
66 ハノイの塔ではありません 2017/06/01 ～ 2017/09/01 70人
67 構造体のアライメント 2017/06/08 ～ 2017/09/08 168人
68 正六角形ブロックの回転 2017/07/06 ～ 2017/10/06 74人
69 カーペット 2017/07/27 ～ 2017/10/27 73人
70 正二十面体の隣の面 2017/08/04 ～ 2017/11/04 98人
71 マス目を回す 2017/08/17 ～ 2017/11/17 85人
72 単調増加連数 2017/08/24 ～ 2017/11/24 115人
73 回文数の中央値 2017/09/21 ～ 2017/12/21 128人
74 ツリーの中にない数 2017/10/05 ～ 2018/01/05 135人
75 ドット絵の丸が２つ 2017/10/26 ～ 2018/01/26 89人
76 展開図上の反対側 2017/11/02 ～ 2018/02/02 52人
77 魔法使いの梯子(はしご) 2017/11/16 ～ 2018/02/16 101人
78 回文に分ける 2017/11/24 ～ 2018/02/24 101人
79 割り算 2017/12/14 ～ 2018/01/14 249人
80 迷路 2017/12/27 ～ 2018/01/27 96人
81 ぐるぐる曼荼羅 2018/01/25 ～ 2018/02/25 55人

現在出題中なのは、超長期出題の選択問題2問と、回文に分ける と ぐるぐる曼荼羅。

両方共結構気に入っている問題なので、挑戦いただければと思う。

CodeIQ に出した「ハノイの塔ではありません」の解説解題のようなもの

このブログは久々の更新になってしまった。すいません。

問題は、下記のような感じだった。

【概要】
「鷲」「鮫」「豹」と名付けられた三本の棒と、中心に穴が空いた円盤が何枚かあります。
最初は「鷲」の棒に、全ての円盤が刺さっています。
円盤を一回に一枚ずつどれかの棒に移動させることができますが、以下の条件を常に満たさなくてはいけません：

どの円盤も、自分よりも上には、自分よりも大きな円盤は1枚入以下しかない。
【入出力】
入力は
1234
のようになっています。
これは「鷲」に刺さっている円盤の大きさ(1〜9 の整数)を上から順に書いたものです。区切り文字はありません。

出力は、
6
のような感じです。
最小の手数を普通に10進数で出力して下さい。
【補足】
不正な入力に対処する必要はありません。
円盤の枚数は 1枚 以上、 7枚 以下です。
ゴールの状態としては「鮫」に全て刺さっていればOKです。元の順序を維持している必要はありません。

今回も数学的背景とかアルゴリズム的背景はいつもどおり特になくて、ふと思いついたから出したという感じ。

有名なハノイの塔をちょっと複雑にして、構造を汚くしてみた。

実装戦略としては、メモ化つきの幅優先探索が自然だと思う。

私の実装はあまりきれいに書けていないけどこんな感じ：

class Solver
  def initialize
    @k={}
  end

  def move( cur, from, to )
    m=cur[from][0]
    return nil unless m && okay( cur[to], m )
    o=3-from-to
    r=[]
    r[to]=m+cur[to]
    r[from]=cur[from][1..-1]
    r[o]=cur[o]
    r
  end

  def okay( c, m )
    k= @k[c] ||= (0...c.size).select{ |me|
      (0...me).any?{ |o| c[me]<c[o] }
    }.map{ |ix| c[ix] }.min
    !k || m<=k
  end

  def makekey(s)
    ((s[1]<=>s[2]) < 0 ? s : [s[0],s[2],s[1]] ).join("|")
  end

  def  solved?( s )
    s[0].empty? && (s[1].empty? || s[2].empty?)
  end

  def solve( state )
    q=[[ state, 0 ]]
    dones = { makekey(state)=>1 }
    moves = [0,1,2].permutation(2).to_a
    loop do
      cur, h = q.shift
      moves.each do |from,to|
        newstate = move( cur, from, to )
        next unless newstate
        return h+1 if solved?( newstate )
        key = makekey(newstate)
        next if dones[ key ]
        q.push([newstate, h+1 ])
        dones[ key ] = 1
      end
    end
  end
end

def solve( src )
  Solver.new.solve( [src, "", "" ] ).to_s
end

puts( solve( gets.strip ) )

50行以上あってちょっと残念な感じだけど、私の実装はこんな感じ。

普通に、メモ化つき幅優先探索。

permutation が地味に便利。move の実装がダラダラしているのが不満なんだけど、これよりいい方法が思いつかない。

探索済みのチェックのときに「鮫」と「豹」を区別しないようにしてちょっと枝刈りしている。

一番複雑なケースで、手元のPCで0.1秒前後。CodeIQ の( ideone の？ )サーバーはもう少し速いので、たぶん 0.0秒になると思う。

計算量のオーダーを劇的に減らす計算方法があるかもしれないけど、検討していない。

そんなところかな。

挑戦者数は 70名。初回正答率は 37%。

条件がちょっとごちゃごちゃしていてい難しく感じられたかもしれない。どうだろう。