Codeへの愛とCuriosity

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

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

前回 今まで 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 ドット絵の丸が2つ 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%。

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

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

自分のためでもある、今まで CodeIQ に出した問題のリスト。つまり、前回( 今まで CodeIQ に出した問題 - Codeへの愛とCuriosity )の続き。

一年以上たっているので、だいぶ問題が出ている。
前回は 29番までだったんだけど、20番以降は挑戦者数が増えていたりするので再掲。

# 問題へのリンク 募集期間 挑戦者数
20 バスの料金を計算しよう(ややリアル編) 2015/09/11 ~ 2016/08/31 180人
21 バスの料金を計算しよう(初級編) 2015/09/11 ~ 2016/08/31 308人
22 先制 hello, world 2015/09/03 ~ 2015/09/21 106人
23 ボタンを押して数を作ろう 2015/10/06 ~ 2016/08/31 497人
24 くねくね最短経路 2015/10/23 ~ 2016/08/31 106人
25 最寄りの素数 2015/11/26 ~ 2016/08/31 139人
26 【機械学習 超初級】【選択式】機械学習の基本のようなそうでもないような問題です 2015/12/03 ~ 2017/06/30 861人
27 遠い昔、はるか彼方の銀河系の カレンダー(初級編) 2015/12/24 ~ 2016/03/24 186人
28 遠い昔、はるか彼方の銀河系の カレンダー(ややリアル編) 2015/12/24 ~ 2016/03/24 113人
29 パスカルの 三角形では ありません(字余り) 2016/01/21 ~ 2016/08/31 233人
30 1の並びで小さい方から 2016/02/25 ~ 2016/08/31 111人
31 世界は歪んでいる。それでも君は歩む。 2016/03/17 ~ 2016/08/31 100人
32 2つの円の位置関係 2016/04/21 ~ 2016/07/21 135人
33 円と線分の位置関係 2016/04/21 ~ 2016/07/21 83人
34 カードを使って数を作ろう(簡単編) 2016/06/02 ~ 2016/09/02 114人
35 カードを使って数を作ろう(両面編) 2016/06/02 ~ 2016/09/02 89人
36 共通の祖先は誰だろう 2016/05/19 ~ 2016/08/19 105人
37 排他的n乗数 2016/06/09 ~ 2016/09/09 182人
38 うそつきがいる!(いないかもしれません) 2016/06/23 ~ 2016/09/23 135人
39 連分数の足し算 2016/06/16 ~ 2016/09/16 123人
40 等比? 等差? フィボナッチ?? 2016/07/14 ~ 2016/10/14 258人
41 限られた数字で作れる数の、まんなかの値 2016/07/21 ~ 2016/10/21 158人
42 【100名限定】変進小数の足し算【手動採点】 2016/07/28 ~ 2016/08/08 101人
43 チェックポイントを順番に 2016/08/10 ~ 2016/11/10 73人
44 三角形と点の関係 2016/08/18 ~ 2016/11/18 120人
45 共通部分は何角形? 2016/08/25 ~ 2016/11/25 75人
46 左と右の有理数 2016/09/15 ~ 2016/12/15 132人
47 ヘックス上の最長狭義単調増加列 2016/09/29 ~ 2016/12/29 109人
48 単調増加で単調減少な数 2016/10/13 ~ 2017/01/13 102人
49 異世界のブラウザの判定 2016/10/20 ~ 2017/01/20 141人
50 撤去作業の果てに現れる数列 2016/10/27 ~ 2017/01/27 124人
51 ちょっと奇妙な足すと引く 2016/11/02 ~ 2017/02/03 160人
52 ダブルテトロミノ 2016/11/17 ~ 2017/02/17 69人
53 ぐるぐるスクエア 2016/11/24 ~ 2017/02/24 138人
54 ぐるぐるペンタゴン 2016/11/24 ~ 2017/02/24 51人
55 外周の折り目 2016/12/08 ~ 2017/03/08 69人
56 放物線とマス目の関係 2016/12/15 ~ 2017/03/15 177人
57 縦線と横線でマス目を塗る 2016/12/22 ~ 2017/03/22 183人
58 境界線の長さ 2017/01/19 ~ 2017/04/19 162人
59 周期表 2017/01/26 ~ 2017/04/26 162人
60 素数の足し算で 2017/02/23 ~ 2017/05/23 164人
61 ◯はぴったり☓は無し 2017/03/02 ~ 2017/06/01 82人
62 メビウスの亀 2017/03/23 ~ 2017/06/23 77人

というわけで、いままで 63問出したらしい(最初が0なので)。

常にネタ切れ感があって自転車操業なんだけど、自転車は好きだよ。

最近のお気に入りはぐるぐるペンタゴンメビウスの亀。他にも色々だけど。
地味な感じだけど周期表も結構好き。

CodeIQ に出した「等比? 等差? フィボナッチ?? 」の解説解題ではない何か

CodeIQ に出した「等比? 等差? フィボナッチ?? 」の解説解題は CodeIQ Magazine (
https://codeiq.jp/magazine/2016/10/46246/ ) の方に書いたので、ここに書くのはそれ以外の何か。

出題意図

解説解題を読んでいただければわかる通り、肝は等比数列
息をするように有理数を選んだ人(私もそうすると思う)は気づかないような肝だけど、出題意図はそこにあった。

フィボナッチはむしろオマケの感じだった。

問題文の罠

当初は「等差? 等比?」の順だったんだけど、問題文の順にテストをしたときに
「9999999990 9999999991 9999999992 9999999993 9999999994 」
のようなテストデータで失敗するように、「等比? 等差?」の順にした。

テストデータ

数列は「ハズレ」を含めて 4種類×3件 にした。
浮動小数点で来た人が不正解になるように頑張ってデータを作った。
まずは前掲のデータ。これはかなりの精度で等比数列っぽくなっている。しかしこれだけでは、評価の順序を変えると等差数列であって等比数列ではないとバレてしまう。
で。等差数列ではない、等比数列っぽい数列を探したところ。
フィボナッチ数(のようなもの)が該当することに気がついた。

たとえば、12番の「1032569015 1670731762 2703300777 4374032539 7077333316」はフィボナッチ数的な数列になっている。これが非常に等比数列っぽい。初項が異なるので、この問題の意味ではフィボナッチ数ではない。というわけで、このテストデータは2つの意味で罠になっている。

反省

64bit 整数しかないのに a1×a3=a2×a2 で判定した場合にちゃんと負けるような問題にできていなかった。
詰めが甘い。

それと。 long double だと浮動小数点でも勝ってしまう


(ciel さん ありがとうございます)

ようで、ここも詰めが甘いなという感じ。

反省。

CodeIQ に出した「1の並びで小さい方から」の解説解題

CodeIQ に「1の並びで小さい方から」( https://codeiq.jp/q/2706 )という問題を出した。

問題の概要はこんな感じ:

数を2進数で表します。このとき、1 の連なりの最大の長さを
F(n)
と書きます。
X と Y という2つの数を与えます。
1以上の整数 n について、F(n)=X である n のうち、小さい方から Y 番目の数を求めてください。

入力は、XとY をコンマ区切りで繋いだ文字列です。
ただし:

  • X は、1以上32以下の整数です。
  • Y は、1以上1000以下の整数です。

数学的背景とかアルゴリズム的背景はいつもどおり特になくて、ふと思いついたから出したという感じ。
「32,10000」とか「1,1000」で計算時間が多くなりすぎて敗北しがちなのがこの問題の面白みだと思う。

で。どうするか。

比較的読みやすいけど実行時間はギリギリになりやすい実装から。

字句解析を省略するけど、こんな感じ:

def f(n)
  len=maxlen=0
  m=1
  loop do
    if 0 != (m & n )
      len+=1
      maxlen = len if maxlen<len
    else
      len=0
    end
    return maxlen if n<m
    m<<=1
  end
end

def solve( keta, ord )
  cands = {(1<<keta)-1=>true}
  memo={}
  keta.upto(Float::INFINITY) do |k|
    cands.keys.each{ |x|
        [x*2, x*2+1, x+(1<<k)].each do |y|
          cands[y]=true if (memo[y]||=f(y))==keta
        end
    }
    return cands.keys.sort[ord-1] if ord<cands.size
  end
end

たとえば X が 3 の場合。
まず、0b111 だけがある集合(実装の都合で Hash だけど)を用意する。
桁数を X から順に増やしていって、集合に含まれている要素について

  • 右にゼロをつける( x*2 )
  • 右に 1 をつける( x*2+1 )
  • k 桁目に 1 をつける( x+(1<<k) )

の3つの数について調査して、F(n) が X であれば集合に追加する。
集合のサイズが Y を超えたところで小さい方から Y 番目を返せば終了。

でも、この実装だとちょっとギリギリ。

f は to_s(2) を使えばもっと短く書けるんだけど、実行速度を優先して整数演算のみにした。

もうちょっと速い実装はだいぶ長いんだけどこんな感じ:

# 1の連なりが len 個で、桁数 keta 桁以下の数のリスト
def just_lte(len,keta)
  (len..keta).flat_map{ |k|
    just_just(len,k)
  }
end

# 1の連なりが len 個で、桁数 keta 桁の数のリスト
def just_just(len,keta)
  return [] if keta<len
  return [2**len-1] if keta==len
  #len より少ない 1の連なり + ちょうど len 個を含むパターン
  lt_just=(1...len).flat_map{ |x|
    lows=just_lte(len, keta-x-1)
    head = (2**x-1)<<(keta-x)
    lows.flat_map{ |o|
      o+head
    }
  }
  #ちょうど len個の 1の連なり + len 以下のパターン
  lt_just+lte_lte(len, keta-len-1).flat_map{ |o|
    ((2**len-1)<<(keta-len))+o
  }
end

$memo={}
# 1の連なりが len 個以下で、桁数が keta 桁以下の数のリスト(メモ化)
def lte_lte(len,keta)
  $memo[[len,keta]]||=lte_lte_impl(len,keta)
end

# 1の連なりが len 個以下で、桁数が keta 桁以下の数のリスト(実装)
def lte_lte_impl(len,keta)
  len = [len, keta].min
  (len+1).times.flat_map{ |x|
    head = (2**x-1)<<(keta-x)
    lows=lte_lte(len, keta-x-1)
    lows=[0] if lows.empty?
    lows.flat_map{ |o|
      o+head
    }
  }
end

def solve( len, ord )
  r=[]
  (len..Float::INFINITY).each do |k|
    r+=just_just(len, k)
    if ord<r.size
      return r.sort[ord-1]
    end
  end
end

行ったり来たりの再帰呼び出しになっていて追いにくい。すいません。
1の連なりが len 個以下で、桁数が keta 桁以下の数のリスト をメモ化付き再帰呼び出しで創りだして、そこからちょうどのものを構成するという流れ。
自分でもわかりにくいと思う。

パスカルの 三角形では ありません(字余り) の解説解題

CodeIQ に、「パスカルの 三角形では ありません(字余り)」( https://codeiq.jp/q/2630 ) という問題を出していたんだが、先日締め切られた。

で。解説解題。

二次元の表に数字が埋まっていて、表外の数字を外挿して計算せよ、という問題。

表の数字などについては
http://ange1.hateblo.jp/entry/2016/09/06/124121
を参考にしていただくとして、規則性の方はタイトルの通りパスカルの三角形からヒントを得た二次元数列になっていて。
左上隅を {a(0,0)} とすると、こんな感じ:

{ \displaystyle
a(x,y)=1~~if~x<0~\lor~y<0
}
{ \displaystyle
a(0,0)=1
}
{ \displaystyle
a(x,y)=a(x-1,y)+a(x,y-1)+a(x,y-2)~~otherwise
}

で。これを定義のとおりに計算すれば良いという簡単な問題だったつもり。まあ計算量を減らすためにメモ化ぐらいはした方がいい。

とはいえ。

ルールが簡単なので、漸化式ではない形にできてしまう。

計算のために、先ほどの式に以下のように意味づけする:

縦の道が x+1 本。横の道が y+1 本ある経路を左上から右下まで最短経路で行く方法の場合の数。ただし、横方向に行く方法は、1マス進む「歩く」と、2マス進む「ジャンプ」の2通りがある。そして「歩く」と「ジャンプ」は区別する。

で。

ジャンプが n回の場合を考える。
ジャンプをいつ使うのかを気にしなければ、横方向のマスが n 個減った場合と同じなので
{\binom{x+y-n}{y-n}}
となる。
横方向の移動は x-n 回ある。そのうち n 回「ジャンプ」を使うのでジャンプする場所の選び方は
{\binom{x-n}{n}}
となる。
したがって、ジャンプが n 回の場合の場合の数は
{\binom{x+y-n}{y-n}×\binom{x-n}{n}}
になる。
ジャンプの回数は 0回以上 {\lfloor x/2 \rfloor}回以下なので、

{\displaystyle a(x,y)=\sum_{n=0}^{\lfloor x/2 \rfloor}{\binom{x+y-n}{y-n}×\binom{x-n}{n}}}

となる。

とまあ、こんな計算をしてもいいんだけど、むしろこちらは想定外。

想定解答はあくまでもメモ化付きの漸化式なのでありました。

CodeIQ に出した「共通の祖先は誰だろう」の解題解説

CodeIQ に出した「共通の祖先は誰だろう」の解題解説

「共通の祖先は誰だろう」( https://codeiq.jp/q/2825 )という問題を CodeIQ に出していたが、先日締め切られた。

100名を超える方の挑戦をいただいた。ありがとうございます。

で。

まずは問題。

問題

問題は

f:id:Nabetani:20160820141059p:plain
図のような家系図があります。
紙面の都合で 29 までしか書いていませんが、正の整数が全て含まれています。
上が祖先で下が子孫です。
上から順、左から順に 1, 2, ... と番号が振られています。
偶数には子が2人、奇数には子が3人います。
で。
複数の数を与えます。共通の祖先の番号のうち、最大のものを出力してください。

  • 入力の値は、10億を超えることはありません。
  • 入力の数は、10個を超えることはありません。
  • 「祖先」には自分自身を含みません。[A]と[Aの親]の共通の祖先は[Aの親の親]ということになります。
  • 「共通の祖先」に該当する数がない場合には「-」を出力して下さい。

というような内容だった。

解題解説

作問の意図としては、ツリーを扱う問題を作ろいうという辺り。
やや不規則なツリーを扱うという辺りが見どころかも。

ツリーをじっと見ると。あるいはもう少し大きな数まで作ってみるともっと明らかなんだけど、だいたい 2.5 で割ると親になる。偶数と奇数をセットにすると 親2人に対して子が5人なので、その比率になる。

たとえば、 27。27÷2.5=10.8。実際の親は 11。だいたい合っている。
あとは端数を微調整すると親を求めることができるようになる。
親が計算できれば、そのまた親、そのまた親 と辿っていける。

自分自身は「祖先」に含まないとか、「1」には祖先がいないとか、その辺りが要注意。

実装例

ruby による実装例は以下の通り:

def parent(x)
  return nil if x==1
  x/5*2 + ( x%5<2 ? 0 : 1 )
end

def parents(x)
  pas=[]
  loop do
    pa = parent(pas.last || x)
    return pas unless pa
    pas.push pa
  end
end

def solve(src)
  ( src.split(",").map{ |x|
    parents(x.to_i)
  }.inject(&:&).max || "-" ).to_s
end

puts solve(gets.strip)

ツリーの構造は parent メソッドにに入っている。parents メソッドで祖先をたどり、solve で共通部分の最大値を求めている。
簡単でしょ?

他の方の実装

他にもありましたら twitter のメンションなどで教えていただけると助かります。