2016-07-19

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

CodeIQ

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

f:id:ibeckuu:20160523223811j:plain

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

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

方針

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

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

実装(Ruby)

では、

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

2016-07-07

CodeIQ 挑戦の記録 : 「アフター・ドット」問題

CodeIQ

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

f:id:ibeckuu:20160707020612p:plain

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

自然数 ${n}$ に対し、 ${1 \leq a \leq n}$ , ${1 \leq b \leq n}$ を満たし、かつ小数で表した ${a \div b}$ が有限小数となるような自然数の組 ${(a, b)}$ の個数を ${F(n)}$ と定義する。
（有限小数…小数点以下の桁数が有限である小数。）
標準入力から ${n}$ が与えられる。 ${F(n)}$ を解答する。
${1 \leq n \leq {10}^{4}}$

方針

自然数 ${a, b}$ について、以下の条件が成り立つ時、 ${a \div b}$ は有限少数になる。

aがbの倍数である場合。
bが1か2か5かの内のいずれか1つまたはいずれかの複数だけの積である場合。
(1か2か5以外の素数を含まない)

よって、 ${1 \leq a \leq n}$ , ${1 \leq b \leq n}$ において、 ${b}$ が ${{ 1,2,5 }}$ のいずれかの積で構成される整数の場合は、 ${a \div b}$ が有限少数になる ${a}$ は ${n}$ 個ある。
素因数分解して ${{ 1,2,5 }}$ 以外の素数を含む合成数については、 ${{ 2,5 }}$ で割り切れるだけ割った時の商の倍数の個数だけ ${n}$ 個中に ${a}$ が存在する。

これより、 ${1}$ から ${n}$ までの整数について、 ${2}$ と ${5}$ で割り切れるだけ割り、商 ${m}$ について ${n}$ 個中の個数 ${n \div m}$ を求め、これの総和を解答とする。

なお、 ${2}$ と ${5}$ で割り切れるだけ割る方法について、入力の最大値 ${{10}^{4}}$ までの整数に含まれる可能性のある2と5の積の最大値との最大公約数を取り、検査値を最大公約数で割る事によって、 ${2}$ と ${5}$ の因数を取り除く。
${{10}^{4}}$ を超えない最大の ${2}$ のべき乗は ${log_2 10000}$ ${= 13.28...}$ なので ${13}$
${{10}^{4}}$ を超えない最大の ${5}$ のべき乗は ${log_5 10000}$ ${= 5.72...}$ なので ${5}$

よって、 ${{2}^{13} \times {5}^{5}}$ ${= 256 \times {10}^{5}}$ との最大公約数を取れば良いが、
文字数削減の都合上、 ${{20}^{8}}$ ( ${{2}^{16} \times {5}^{8}}$ ${= 256 \times {10}^{8}}$ ) との最大公約数を取る事にする。
これにより、 ${n = {10}^{5}}$ までは正確に答えが出る。

実装 (Ruby ・ 50byte)

p (0..n=gets.to_i).inject{|s,i|s+i.gcd(20**8)*n/i}

Ruby では Enumerable#inject というメソッドがある。
（reduce という別名もあり）
配列などの要素をブロックの中で繰り返し計算する事に使う便利なメソッドであるが、ブロック中で変数を宣言して使う時、初期値を明示的に指定しないと、最初の要素が初期値として扱われ、2番目以降の要素が計算の対象となる。
今回は範囲オブジェクトの要素を計算しているが、最初の要素を「1」とするとb=1の時が計算されない。「0」としても初期値としてこれに加算されるだけなので、ゼロ割りは発生しない。
今回は良いが注意が必要である。

では、

Sponsored Link

2016-07-05

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第99回「均等に分配されるカード」

CodeIQ

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

f:id:ibeckuu:20160523223811j:plain

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

m 枚のカードがあり、それぞれに 1～m までの数字が1つずつ書かれている。これらのカードを n 人に配る時、それぞれの持つカードの数の和が全員同じになる分け方が何通りあるかを求める。
${m \leq 16}$

方針

メモ化再帰を用いる。
組み合わせ論的に考えようとしたが良い方法が思いつかなかったので、再帰で探索する事にした。
1からmまでの数値を全ての組み合わせについて加算していき、1からmまでの総和 ${m \times (m+1) \div 2}$ をnで割った 1人に配る数の和sumに一致すれば和の組iを加算する。
iがnに一致すれば1通りとし、総数を数える。
カードの数値の組はビット演算でフラグとする。

反省

自分が改めてメモ化がヘタクソだと思った。
提出したメモ化では高速化の効果は少ないと思いながら書いたが、案の定メモ化でありながら最大のケースで約0.4秒近くかかった。
1回WAであった。
原因はすぐ分かった。解答は組み合わせではなく順列だった。
重複なく数え上げるアルゴリズムは思いつかなかったので、不本意ながら最終的に解答を ${n-1}$ の階乗で割って解答とした。
(1を含む組のみ最初に固定して組み合わせを作ったので、n組から1を引いた個数の順列)

実装(Ruby)

では、

Sponsored Link

2016-07-01

ブログを開設して半年が経ったので少しまとめてみた

今日は2016年7月1日。
はてなサンからこんなメールが来た。

f:id:ibeckuu:20160701235038p:plain

1月1日にブログを始めたので丁度半年経った事になる。
簡単なまとめ

項目	合計
アクセス（合計）	1668
投稿数	32
コメント数	0
読者	7人

32記事の内、27個までが「CodeIQ 挑戦の記録」であってそのほとんどが「今週のアルゴリズム」問題の自分の解答を恥ずかしげもなく世間に晒すという厚顔無恥極まりないブログである。
それにも関わらず7人もの方が読者として登録して頂けている事に本当に感謝している。

最も良くアクセスされている記事は下記のページ
JavaScript 標準入力・標準出力でJavaのメソッドを使う方法
で、本日までのアスセス数約314回（全体の内18.8%）
ほとんどがGoogle,Yahoo!の検索からとなっている。
3月13日に書いた記事だが、今でも定期的にアクセスされていて、やはりまともな記事も少しは書かないといけないなあ・・・と思う。（この記事がまともかどうかは？だが）

半年経ったが、思いの他、継続して読んで頂いたり、スターをつけたりして応援して下さる方がいる事に本当にありがたく思っています。
読んで頂ける方が少しでも面白いと思ってもらえる記事を書ける様にこれからも続けていきたいと思う。
（仕事が忙しくなると結構キツイ時もあるが・・・）

では、

Sponsored Link

2016-06-29

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第98回「オリンピックの開催地はどうやって決まる？」

CodeIQ JavaScript

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

f:id:ibeckuu:20160523223811j:plain

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

オリンピックの開催地決定について「繰り返し最下位消去ルール」が使われる。これを用いた投票パターンについて考える。
下記は問題文の引用

開催地の決定に使われるのが「繰り返し最下位消去ルール」です。
トップが過半数を超えると、1回の投票で決定します。
トップが過半数を取れない場合、最下位を除外してもう一度投票を行います。
過半数を得るまでこの方法で投票を繰り返します。

ここでは、最下位が複数になった場合は、最下位1つが決まるまで上記の逆の投票を行うことにします。
（つまり、最下位が過半数を超えると1回で決定、過半数が取れない場合、最上位を除外してもう一度投票）
なお、投票を行ったときにすべての候補が同数になることはないものとします。

(中略)

n 個の候補地について、十分多くの人が投票することを考えます。
1つの候補地が決まるまでに必要な投票パターンが何通りあるかを求めてください。

例えば、n = 3の場合、
・1回目で1つが過半数を超えて決定
・1回目で1つが脱落し、2回目で残り2つの決戦投票
・1回目で下位2つが並び、2回目で下位2つの投票、3回目で決選投票
の3パターンがあります。

標準入力から国の数nが与えられ、nの場合の投票パターンの総数を解答する。
nの最大は7

方針

当初、問題文が理解できなかった。特に

最下位1つが決まるまで上記の逆の投票を行うことにします。

最下位が過半数を超えると1回で決定

最下位が過半数とはどういう事か、過半数を獲得すれば「最上位」では無いかと悩んだが、最下位が複数になった場合の「逆の投票」というのが、当選させる国に投票するのではなく、落選させたい国に投票する。
との意味と考えると辻褄があった。

そうすると、投票パターンは「決戦投票」と「最下位決定戦」があるが、そのいずれもで、

1国の過半数で終了。
単独最下位が存在し、国を1つ減らして同じ事の繰り返し。
同率最下位が複数存在し、同率最下位の国の中で最下位決定戦を行う。
(2からその時の国の数-1まで。題意より全ての国が同じ得票数になる事は無いが、トップ1国を除く全ての国が同率最下位になる事はある為。)

のパターンに分岐する事になる。

よって、対象の国の数nの時のパターン数を ${f(n)}$ とすると、下記の漸化式で表す事ができる。

${f(1)=0}$
${f(n)= {( \sum_{i=2}^{n-1} f(i) +1)} \times {f(n-1) +1}}$

となる。
これを用いて実装する。

実装

golf解 Ruby(49byte)

a,s=0,0;(gets.to_i-1).times{a=(s+1)*a+1;s+=a};p a

通常解 JavaScript (SpiderMonkey)

では、

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第97回「アダムズ方式で議席数を計算して！」

CodeIQ

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

f:id:ibeckuu:20160523223811j:plain

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

選挙における議席数の割り当て方法に「アダムズ方式」がある
「アダムズ方式」とは、各選挙区の人口をある特定の数値で割り、その商の合計が議席数の合計に一致する様に特定の数値を調整するもの。
割り算の際、商の少数点以下は切り上げる。
（切り上げる事により、議員がゼロ人になる選挙区は無くなり、人口の少ない選挙区に有利になる）
標準入力から、1行目に議席数の合計、選挙区の数が、2行目以降にそれぞれの選挙区の人口が与えられる。
アダムズ方式で計算したそれぞれの選挙区に割り当てられた議席数を改行区切りで解答する。
総人口の最大は1500万人、選挙区の最大は50、一意に決まらないテストケースはない。

方針

議席数の合計をn、人口の合計をmとする。
割る数dの初期値をm/nに設定し、各選挙区の人口をdで割り、少数部を切り上げたものの合計を計算する。
その合計がnより大きければ、dを大きくし、
その合計がnより小さければ、dを小さくして
合計がnと一致するまでこの計算を繰り返す。

この探索に高速化の為、二分探索を使用する。
（結果的には1つずつインクリメントする線形探索でも十分なサイズではあったが、二分探索で全てのケースで0.0秒だった）

但し、二分探索では、範囲が決められていない場合、探索する範囲を正しく設定しないと正しい結果が得られない

今回、特に根拠は無かったが、dの上限をdの2倍とした。
${O(logN)}$ の二分探索では上限を10倍にしても100倍にしても実行時間はほとんど変わらないが、あえて2倍とした。
理由は、選挙区ごとの人口の偏り方により、割る数が10〜20%程度の変動でも、人口と議席数の比率の違い、「一票の格差」が数倍になる場合もあると考えた為である。
今回のテストケースでは全て2倍で正しく計算できた。

実装 (Ruby)

では、