2016-06-22

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

2016-06-15

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

2016-06-02

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

2016-05-24

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第93回「ナルシストなナルシシスト数」

CodeIQ

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

f:id:ibeckuu:20160523223811j:plain

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

ナルシシスト数に関する問題。

(ウイキペディアより引用)

n桁の自然数であって、その各桁の数のn乗の和が、元の自然数に等しくなるような数をいう。例えば、 ${{1}^{3} + {5}^{3} + {3}^{3} = 153}$ であるから、153 はナルシシスト数である。

十進法に限らず、他の基数においても同様にナルシシスト数を定義できる。

標準入力から nが与えられる。n進数で2桁以上のナルシシスト数を小さい方からn個求め、標準出力にn進数で順に出力する。
nは10以下の整数。

方針

全探索( ${O(n)}$ )するより他に良い方法を思いつかなかった。
しかしながら、問題文より、答えを10個出力すれば打ち切れるので全探索をする事にした。

サンプルとして10進法の例が書かれてあり、10進法での10個目の答えは「93084」となっているので、（組み込み関数の内部処理を無視すれば）nの最大で約93,000回ほどのループ（x定数倍）で答えがでる。
その他の基数でのナルシシスト数の個数は不明で、10個に満たない場合、最悪のケースで ${{9}^{9}}$ =約3億8千万回ループする可能性があるが、それで時間制限に間に合わなかった場合は、改めて考え直す事にした。
実装してからローカルでテストすると、十分間に合ったのでそのまま提出した。
（提出結果は ${n=10}$ のケースで約0.3秒で正解）