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

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秒で正解）

なお、rubyでは

  • 10進法の数値を任意のn進法の文字列に変換して表示するメソッド
  • n進法の文字列を10進法の数値に変換するメソッド

をともに備えているので、これを利用し、n進法で2桁の最小値({{n}^{1}})からn桁の最大値({{n}^{n}-1})までの整数を都度n進法に変換し比較、ナルシシスト数と一致したものを出力した。
組み込み関数を用いればRubyでの実装は簡単であった。

実装(Ruby)

では、



Sponsored Link

CodeIQ 挑戦の記録 :「レッド・アンド・ホワイト」問題

CodeIQ

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

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

  • マス目が直線上に限りなく並んでいる（初期状態は全て白色）
  • このうちの1つを赤色に塗る。
  • 次のルールに従いマス目の色を塗り替える時、n秒後の赤色のマス目の個数を解答する。
  • 1秒ごとに下記の通り変化する
    左右のマス目が白赤または赤白のマス目->赤色に塗る。
    左右のマス目が白白または赤赤のマス目->白色に塗る。

方針

題意に従い、二次元配列を使って状態の変化を表示してみる。
赤色のマス目を「1」で、白色のマス目を空白で表示すると、パスカルの三角形に似た図形が表示される。

f:id:ibeckuu:20160518025212j:plain

この図形は、パスカルの三角形の奇数部分を塗りつぶしてできる「シェルピンスキーのギャスケット」と同様のものである。

パスカルの三角形には様々な規則性が隠れているが、n行目（最初を0行目とする）に含まれる奇数の個数はnを2進法で表記した時の1の個数を{p}とすると{2^p}に等しい事が知られている。

[パスカルの三角形と2進法]
http://www7b.biglobe.ne.jp/~fukagawa/documents/mod2pascal.pdf

実装

上記の性質を用いて解答する。(Ruby・27文字)

なお、標準入力からの数値を2進法で文字列化する時に、Rubyではsprintfが使えるが、これの代わりに「%」で書式文字列が使えるのでこれを利用して2進法表記の文字列とし、その中の1を数えている。

p 2**(("%b"%gets).count'1')


おまけ

上記の規則性に気づく前に提出した1回目の解法

この三角形は0行目が1が1個、1行目が1が2個の2行でなる三角形が2行ごとに2倍ずつ繰り返し現れ、 2のべき乗行目に2に戻る事を繰り返している。
これより、与えられた数をその数より小さい最大の2のべき乗で引いていき、その回数の2倍を解答とする。

n=gets.to_i;a=1;while n>0;a*=2;n-=2**Math.log2(n).floor;end;p a

では、


Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第92回「最短距離で往復できる形は？」

CodeIQ

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

f:id:ibeckuu:20160420045549j:plain

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

  • 格子状の道路があり、左下のA点から右上のB点まで最短距離で移動し、A-B点の移動を繰り返す。
  • このとき、一度通ったルートは通らず全てのパターンを通ったとき、最終的にA点で終わる場合を考える。
  • A-B間の移動距離nが標準入力から与えられたとき、最終的にA点で終わる形のうち、横幅が最小になるものを解答する。
  • A点で終わるものがない場合は0を出力する。
  • {n \leq 99999}

f:id:ibeckuu:20160518001127p:plain

方針

幅{w}、高さ{h}の格子状の対角線上の位置{A,B}を最短距離で移動する時の場合の数は
組み合わせ {_{w+h} C _w} ( = {_{w+h} C _h} ) 通りである。

{A,B}を往復し全てのルートを通って出発地点に戻るためにはこの組み合わせが偶数であれば良い。
これより、問題の距離を幅{1}から始めて場合の数が最初に偶数になる幅を解答とする。

{_n C _r}の値が最初に偶数になる{r}を探すが、普通に計算すると大きい入力で計算値が大きくなりすぎ、時間がかかるため、分母・分子をその都度最大公約数で割り(約分)、分子が最初に偶数になった時の回数を解答とする。

実装(Ruby)

では、

Sponsored Link

(JavaScript) アスタリスクで菱形を書いてみた

JavaScript

こんなブログを見かけた。

www.2dgod.com

未経験でWebエンジニアになって1ヶ月の人が、どういう訳か、JavaScirpt、アスタリスクで菱形を表示する事になったらしい。
表示するのはこんなの、

f:id:ibeckuu:20160504164559j:plain

面白そうなのでやってみた。

問題の仕様

  • JavaScript
  • for文を使う
  • console.logでアスタリスクを使って表示する

方針

5行9列の場合でアスタリスクを表示する位置は
(0,4)
(1,2),(1,3),(1,4),(1,5),(1,6)
(2,0), .. ,(2,8) (2行全て)
(3,2),(3,3),(3,4),(3,5),(3,6)
(4,4)

この場合のアスタリスクを表示する位置を数式で表すと、
行(i)が0から4、列(j)が0から8の範囲で(i,j)について、

{|j-4|} < {5-|4-i \times 2|}

( | | は絶対値)
が成立する時である。

実装 JavaScript (Node.js)

上記の数式を用いて実装する。

  • 上記の例では5行のみだが、定数を変更する事により任意の奇数行で表示できる様にしてある。
  • 実行環境はideone.com上でNode.jsとして可能(console.logを使用するので)のほか、htmlに埋め込んでFirefoxのFirebugでも動作確認済み。
  • コードはGistに埋め込み

では、

Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第91回「最短で当たるビンゴゲーム」

CodeIQ

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

f:id:ibeckuu:20160420045549j:plain

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

  • ビンゴカードの数字が4枚分標準入力より与えられる。
  • この数字は1から75までの整数で、1枚の中では同じ数字が2回現れる事はない。
  • 一般的なビンゴカードと違い真ん中のマスも「FREE」ではなく数字が書かれている。
  • 4枚全てがビンゴになる時、出る数字の種類が最も少ない場合の数字の個数を解答する。

方針

{5 \times 5}マスのカードのビンゴになる並びは縦・横・斜めの{12}通りである。
全てのカードについて全ての並びの組み合わせを試しても{{12}^{4} = 20,736}通りなので1秒の時間制限にも十分間に合う。
なので、全ての組み合わせを試し、その中で最も数字の種類の少ないものを選んで解答する事とする。
なお、数字の種類を数える方法は、組み合わせの数字全てをハッシュに代入し、ハッシュのサイズで比較する事にする。

全ての組み合わせを試す方法としては、4重ループにせず、再帰を用いた。
再帰を用いた方法であれば、時間はかかるが、カードが何枚でもコードを修正せずに答えを出せる。

実装 (Ruby)



Sponsored Link