Codeへの愛とCuriosity

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

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 ドット絵の丸が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}}}

となる。

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

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