読者です 読者をやめる 読者になる 読者になる

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第104回「整数倍の得票数」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

f:id:ibeckuu:20160523223811j:plain

問題文を要約すると下記の通り

  • 選挙での候補者数と得票数について、最下位の候補者の得票数を1としたときに、ほかの候補者の得票数が整数倍になるようなパターンについて考える。
  • 例:3人の候補者に対して7人が投票するとき、その得票数のパターンは以下の4通り。
    5-1-1
    4-2-1
    3-3-1
    3-2-2
    (候補者は区別せず、得票数のみに着目する)
    この場合で、3-2-2は最下位の候補者を1とすると他の候補者の得票数が整数倍にならない為対象外。
    よって3パターンとなる。
  • 標準入力から{m,n}が与えられ、{m}人の候補者に対して{n}人が投票するときこの様なパターンは何通りあるかを解答する。
    {(0 \lt m \lt n \lt 80)}

方針

メモ化再帰により探索する。
{m}人の候補者に対して{n}人が投票する場合で、最下位の候補者の得票数を{b}とおくと、その他全ての候補者の得票数が最下位の候補者の得票数の整数倍になるならば、以下が成り立つ。

  • {n}{b}の倍数である。
  • 最下位の候補者を除く{m-1}人の得票数の合計は{n-b}票である。

これより、{b}{1}から{\lfloor {n/m} \rfloor}まで、{n}を割り切る時のみ、題意のパターンをメモ化再帰で探索し、そのパターン数の合計を解答とする。
なお、探索では、全て{b}の整数倍のものを探すので、初めから{n}{b}で割ったものを調べる事で探索数を減らす事とする。
また、例えば7票を3人で分ける場合で、1-1-5パターンとこれを並び替えた1-5-1、5-1-1は同じパターンとみなすので、重複カウントを防ぐ為に、再帰関数の中で得票数のパターンを昇順のみ探索する様にしている。

実装(Ruby)

では、


Sponsored Link

CodeIQ 挑戦の記録 : 【100名限定】変進小数の足し算【手動採点】

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

codeiq.jp

問題文を要約すると下記の通り

  • <小数第n位が11-n進数> というルールの計算を「変進小数」と呼ぶ事にする。
    (例えば、小数第1位は10進数、小数第9位は2進数)
  • 変進小数での足し算を考える。
    入力の例 8.622+3.177
    出力の例 11.811
  • テキストファイルが与えられ、以下の数値がTAB区切りで複数行含まれている。
    {データID, 変進小数の足し算, 変進小数で表された足し算の結果}
    ほとんどのデータは正しい結果になっているが、正しくないデータが幾つか含まれている。
    正しくないデータのデータIDをコンマ区切りで解答する。

方針

題意の通り変進小数の和の演算を実装し、与えられたデータと比較する。
計算方法は以下の通り。
整数部と小数部を分けて計算する。
小数部は再帰にて実装する。
小数点以下1桁めから、再帰関数で1桁ずつ降りていき、2数の内短い方に達したら長い方の数値のそれ以下は計算する必要がないのでそのまま外部変数(配列)に代入する。
短い方の最下位桁から順に11-n進数として計算、繰り上がりを返り値で返し、加算する。
加算した数値は順に配列に代入する。
整数部まで繰り上がりを計算し、整数部と合わせて足し算の答えとする。
この答えと与えられたデータとの比較をする。
小数点以下で最終桁が0とか、小数点の表示されていない答えとの照合の為、 正誤の判定は2つを浮動小数点に変換して比較する。

注意点

下記の様なコーナーケース(注意しないと間違い易いデータ)を想定した。

  • 浮動小数点数計算を行うと誤差を生じ、計算結果が異なる可能性がある。
  • 文字列として比較すると小数点以下で最終桁が0で終わると表示が同じにならない。
  • 同様に結果が整数になった場合、小数点、小数点以下が表示されず同じ表示にならない。

この対策の為、変進小数の計算は配列に代入した各桁ごとに計算し、比較については一旦文字列にしたものを浮動小数点数に変換して比較した。
この点につき、解答にコメントとして記入して提出すると、下記の様なフィードバックを頂いたので一部要旨を紹介する。
(フィードバックありがとうございました。)

  • 浮動小数点数での計算に誤差の恐れがあるのであれば、Rubyで書いているのだから有理数を用いてはどうか?
    特に、最後で浮動小数点数として2数を比較している部分について。

RubyにはRationalクラスという分数をそのまま扱えるクラスがあるので、誤差を生む心配なく計算ができる。
しかしながら、Rationalクラスの存在は知っているが、使った事がなかったので、その発想もなかった。

実装(Ruby)

では、


Sponsored Link

CodeIQ 挑戦の記録 : 「プライム・ホッパー」問題

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

f:id:ibeckuu:20160707020612p:plain

問題文を要約すると下記の通り

  • ある素数に対し、変換1と2を次の通り定義する。
    変換1:元の数の右または左に1~9のいずれかの数字一つをつなげる。
    変換2:元の数の右端または左端の数字一つを取り除く。
    (ただし、最上位桁が0で始まる数値への変換は不可)
  • 標準入力から素数{p}{q}が与えられる。({{p} \lt {q}})
    素数{p}から始めて、変換1または2を繰り返して{q}を作る最小の交換回数を解答する。
    (途中の数は全て{q}以下の素数)
  • {{p} \lt {q} \leq {10}^{5}}

方針

幅優先探索を用いる。
qまでの配列を用意し、初期値として素数の項を0、合成数の項を-1とする。
題意の通り変換できる限り素数を変換していき、使用していない素数であればキューに追加し、幅優先探索で探索する。
同時に何回めの変換かを配列に記録する。
変換した数がqと一致すると配列に記入した回数を解答する。

実装(Ruby)

では、


Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第103回「まわり将棋に挑戦!」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

問題文を要約すると下記の通り

  • まわり将棋を考える
    (まわり将棋とは金将4つをサイコロの代わりに使い、9x9マスの将棋盤の周囲を双六の様にコマを進めるゲームである)
  • 振った金将の状態により金将1つあたり下記の得点が得られる。4つの合計が進むマスの数となる。
    ・裏向き:0
    ・表向き:1
    ・横向き:5
    ・上向き:10
    ・下向き:20
  • あるコマが角の位置からスタートした時、n回振って4つの角の内どこかの角にいるパターンが何通りかを解答する。
  • コマの動きは動くマスの数のみに着目する。並び順は区別する。
    例えば n=2 のとき、「1回目に3マス、2回目に5マス」動いたときと、「1回目に5マス、2回目に3マス」動いた場合は別々とカウントする。
  • nの最大は7

方針

メモ化再帰により探索する。
金将4つの得点の合計が1回に進むマスの数になり、これのn回の和が進んだマスの数。
9x9マスの周囲を回るので、角からスタートすれば、進んだ数が8の倍数であればどこかの角にいる事になる。

実装としては、あらかじめ金将4つの得点の合計の組み合わせ
{0,1,5,10,20}の中から4つを選んだ組み合わせの和を計算し、配列に記録しておく。
n回コマを振った場合に進む、全てのコマ数の組み合わせをメモ化再帰で試し、合計が8の倍数になるものを数え解答とする。

実装(Ruby)

では、


Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第102回「長男はいつも弟のことを考える?」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

f:id:ibeckuu:20160523223811j:plain

問題文を要約すると下記の通り

  • マス目状のチョコレートを縦か横に一直線に分割する事を考える。
    (マスの途中では割れない)
  • 標準入力から縦・横・人数が与えられ、全員が食べられる様に分割するパターンが何通りかを解答する。
    分割の方法・・・縦か横に一直線に切り取り、左か上のものを取り除き、残ったものを同じ方法でカットを繰り返す。
  • 縦・横の最大はそれぞれ20、人数の最大は10

方針

3通りのアルゴリズムで解答する。

  1. メモ化再帰
  2. 動的計画法
  3. 組み合わせ論で計算

アルゴリズム

1. メモ化再帰

縦h、横wのマスをn人で分ける場合の数を考える。

f:id:ibeckuu:20160727223647j:plain

n人で分けるためにはn-1回分割する事になる。

1回目からn-1回目までのカットにおいて、前回のカット位置の縦・横それぞれの次の位置からh-1、w-1の位置まで全てのカット位置を試し、n-1回カットしたパターンを再帰関数で数える。
高速化の為、メモ化を用いる。

実装(Ruby)


2. 動的計画法

縦h、横wのマスを縦i、横jのカット位置でk回目に切り取る場合の数は下記の漸化式で表す事ができる。

{f(1,i,j)=1} ({1 \leq i \leq h-1} , {j=0}) または ({i=0} , {1 \leq j \leq w-1})
{f(k,i,j)= } {\sum _{p=0}^{i-1} f(k-1,p,j)  +  } {\sum_{q=0}^{j-1} f(k-1,i,q)}

  • 漸化式の説明

k回目に(i,j)の位置をカットする場合の数は、

f:id:ibeckuu:20160727224653j:plain

  • k-1回目に(0,j)の位置でカットされたものから(i-1,j)の位置でカットされたものの全ての場合の数を加算したものと

f:id:ibeckuu:20160727224604j:plain

f:id:ibeckuu:20160727224629j:plain

  • k-1回目に(i,0)の位置でカットされたものから(i,j-1)の位置でカットされたものの全ての場合の数を加算したものである。

f:id:ibeckuu:20160727224723j:plain

f:id:ibeckuu:20160727224741j:plain

実装(JavaScript / SpiderMonkey)


3. 組み合わせ論による

縦h、横wのマスを縦か横かにn-1回カットする場合の数は、
h-1個の区切り位置からi個を選び、

f:id:ibeckuu:20160727224845j:plain

w-1個の区切り位置からn-1-i個を選ぶ組み合わせ

f:id:ibeckuu:20160727224907j:plain

縦・横の同じものを含む順列を掛けたもの。
これをiについて0からh-1かw-1の小さい方までの総和で計算できる。

式は下記の通り。

{s=min(h,w),b=max(h,w),r=min(s,n)}とする
{f(n)=} {\sum_{i=0}^{r-1}} {\verb#{#} {  _{s-1}C_{i} } { \times _{b-1}C_{n-1-i} \times \frac{ (n-1)!} { {i!} \times {(n-1-i)!} }} { \verb#}# }

実装(JavaScript / SpiderMonkey)

では、


Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第101回「道順は違っても結果は同じ」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

f:id:ibeckuu:20160523223811j:plain

問題文を要約すると下記の通り

  • 正方形が縦横に敷き詰められたマス目を考える。
    このマス目を上下左右に一筆書きの要領で移動するとき、その経路を以下の要領で記録する。
  • 上への移動は「U」、下への移動は「D」、右への移動は「R」、左への移動は「L」
  • 上記の要領で移動した経路が標準入力から与えられる時、通ったマスと同じ形の図を異なった順序で移動する場合に一筆書きで移動できる経路が何通りあるかを解答する。

方針

再帰により探索し一筆書きができたパターンを数える。

入力文字の最大をMAX_Lとすると、縦横がMAX_L*2+1のサイズの二次元配列を2つ用意する。
(問題文の経路の読み込み用と訪問したマスの記録用)
標準入力より移動経路を読み込み配列に記録。 二次元配列の全てのマスより出発し、移動が可能なマスで未訪問である限り、4方向を探索する。
一筆書きが出来ればカウントする。

実装(Ruby)

では、



Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第100回「100問目!100人限定!百マス計算!」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

f:id:ibeckuu:20160523223811j:plain

問題文を要約すると下記の通り

  • 標準入力より0から9までの整数がコンマ区切りで10個で1行分、これが2行分与えられる(合計20個)
  • 1行目の数を横軸に、2行目の数を縦軸に方形に並べ、数値の交差する位置にそれぞれを加算した数値を置く(100マス計算)
  • 計算した数値に対して、左上から右下のマスまで縦横に移動する時、通ったマスの数値を加算した場合に、合計が最も小さい移動経路を求め、その合計数を出力する。

「今週のアルゴリズム・100問目」について

今回、今週のアルゴリズムが記念すべき100回目であった。
その記念に、挑戦を受け付ける人数を先着100人限定とし、優秀正解者の中から10人に出題者の著作をプレゼントするという企画であった。
最近の挑戦者数の増加と、問題の難易度から挑戦できる100人は出題日当日に埋まると予想した為、珍しく当日の夕方に解答を提出した。仕事中にちょっとサボって会社のノートPCでコーディングしてそのまま提出したが、結果的にはそれ程慌てる必要は無かった。
久しぶりの手動採点問題で、正解をもらえたが、フィードバックをもらうまでなかなかの緊張感を味わえた。

方針

問題文を読んだ瞬間はダイクストラ法一択だと思った。
(もちろん他にも良い解法はある。自分が思いつかないだけである)
しかし、コーディングをし始めて何故か、書きなれた再帰で実装していた。
ダイクストラ法は基本的にキューを使った幅優先探索を用いて実装するのが一般的で、出発点から最も近い接点を順に確定しながら、連結している全ての接点への最短距離を求めるアルゴリズムである。
それに対して、今回再帰により実装した方法は、100マスと同じ構造の二次元配列をメモとして用意し、それぞれのマスに移動する時、メモと比較し、メモよりも合計が小さくできればメモを更新し、移動する。小さくできなければその先へ進まないという方法の「メモ化再帰」というより「枝刈り探索」といった方が良いものかもしれない。
今回の問題のサイズではこの方法でも十分に短時間で答えがでるので、他の方法を考えることなく提出した。

実装(Ruby)

今回、手動採点で、コメントを含めた可読性も評価対象との事であった。
コメントについて、最近は手抜きが多かったが、割とマジメに書いたので、提出時のままで記載する。

では、


Sponsored Link