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

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年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

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)

では、



Sponsored Link

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)

では、



Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第96回「圧縮できるパターンは何通り」

CodeIQ

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

f:id:ibeckuu:20160523223811j:plain

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

  • ランレングス圧縮（連長圧縮）を考える
  • 例えば、「AABBBCEEEE」の場合は「A2B3C1E4」のように変換する。この場合元の文字列が10文字に対し変換後8文字に短縮できる。
  • 標準入力から整数m,nが与えられる。m種類のアルファベットでn文字の文字列の内、元の文字列より短くなるものの総数を解答する。
  • {{m}^{n} \leq 65536}

方針

最大のケース（組み合わせ総数）が65536 (= {{2}^{16}})なので全探索でも解けると思ったが、組み合わせ論的に計算し、高速化を図ろうとした。が、結果的に失敗だった。
失敗というのは次の点から、

  • 短縮できる条件の設定を間違い正解できないケースがあった。この原因が判明するのにコードを書いた以上の時間を要した。
  • 思ったほど高速化にならなかった。(最大のケースで約0.3秒)
  • ソースコードが長く可読性の悪いものになった。

計算順序としては次の通り、

  • n文字の文字列の中で、1文字からn文字までの同じ文字が連続する部分文字列が何個あるかのパターンを列挙する。
  • それぞれのパターンについて同じものを含む順列を計算する。
  • さらに、連続する部分文字列に対し、組み合わせを計算し、順列と掛け合わせたものの総和を解答とする。

計算の詳細

  • 部分文字列のパターンの列挙
    1からnまでの重複組み合わせで文字数がnのものの全てのパターンを再帰関数にて列挙する。
    この時、短縮できる条件として、
    1文字が連続する(2文字以上連続しない)部分文字列の個数をp、2文字が連続する部分文字列の個数をqとすると、 元の文字列よりも短縮できる時、次の式がなりたつ。(式は短縮できる為の必要条件)

    {{0} \leq {p}} < {\lfloor {(n - 2q -1)} \div {2} \rfloor }　（{ \lfloor } { \rfloor} は床関数）

  • これを同時に、式が成り立つならば短縮できると思い込み、必要十分条件と勘違いした事が、エラーの原因だった。
    (短縮できない例)
    n=8で、1文字の連続が2個、3文字の連続が2個のケースなど。

  • 同じものを含む順列
    連続する文字の個数の順列を同じものの個数の順列で割れば良い。

  • 組み合わせ
    連続する文字それぞれに対し、最初の文字はm種類でm通り、2種類目以降の文字はその前の文字を除く(m-1)通りが選べる。
    これより、n文字の文字列中で、連続する部分文字列がk個あったとすると、
    {m} \times {(m-1)}^{(k-1)}通りとなる。

実装(Ruby)

では、



Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第94回「一筆書きでクルクル」

CodeIQ

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

f:id:ibeckuu:20160523223811j:plain

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

  • 横に4本、縦に5本の道路が並んだ格子状の地図がある。
  • 左上の地点から右下の地点まで移動する。一度通った道は通れないものとする。
  • 標準入力から直角に曲がる回数が指定され、ちょうどこの回数を曲がって左上から右下へ到達する経路が何通りあるかを解答する。

方針

再帰関数で探索して求める。
引数は以下の4つ

  • 曲がった回数
  • 現在の位置
    横方向の点の個数と縦方向の点の個数の積で整数値にエンコード
  • 一つ前にいた位置
    現在位置と同じく整数値
  • それぞれの道について既に通ったか、通っていないかの状態
    2点間の道に番号をつける。(横方向は2点の内小さい方の番号、縦方向は小さい方の番号+縦横の個数の積。0から35までの数値) この番号をフラグとしてビット演算で整数値にエンコード

再帰関数にて左上から右下までの一筆書きでの移動を試し、曲がった回数が所定のn回に一致するものを数え、解答とする。

考察

というか反省。
うまくメモ化できなかったのでメモ化なしの再帰で提出した。
結果は全てのケースで0.08秒でACだったためクリアできてよかったが、最適な解には程遠いと思われ、納得が行かない。

データ構造について、

今回、都合により全く時間がとれず、データ構造についていろいろ試してみる事が出来なかった。
取った方法はデータを全て整数値にエンコードし、4次元配列を用いてメモ化するコードを書いたが、4つの内1つの要素数が{{2}^{36}}という巨大なものになった為、メモ化であるのに、実行すると全く答えが返ってこない状態になり、早々にメモ化を諦めた。
ビット演算で状態を持つのではなく、単純にハッシュにすれば良さそうにも思ったが、3次元配列の中にハッシュが入れ子になっている構造を実装する気になれず、また、仮引数にハッシュを渡していわゆるシャローコピー（浅いコピー）で意図しない動きになる事を回避する（Marshalを使う）のも面倒だったので試してない。

実装 (Ruby)

では、



Sponsored Link