CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第89回「一筆書きの交点」

CodeIQ

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

f:id:ibeckuu:20160420045549j:plain

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

  • 円周上に等間隔にn個の点がある。
  • 任意の点から一筆書きで最初の点へ戻るルートを考えた時、交差する回数の総計を解答する。
  • nの最大値は9

方針

今回は規則性を見つける事ができず、全探索を行うしかなかった。
当初、時間制限に間に合わないのを確認しながらRubyで提出、TLEだったので、
C++でほぼ同じコードを書き直し再提出。正解した。
(順列の生成に、Rubyでは Array#permutation を使用。C++では自前で実装。
ちなみにn=9の場合で、RubyではTLE、C++では表示0.0秒。事前の「実行くん」では0.02秒)

なお、組み合わせにより式を導いた@angel_p_57さんの解説はこちら、

t.co

素晴らしい。

実装

C++ (gcc 4.9.3)

では、


Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第88回「永遠に続くビリヤード」

CodeIQ

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

https://codeiq.jp/sites/default/files/styles/thumb_175x114/public/engineer/algorithm.jpg?itok=Z_awtPsU

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

  • ビリヤードについて考える。クッションに対して45度の角度にボールを打つとする。
    ボールの勢いが十分強くクッションに反射して同じ場所を繰り返して動くものとする。
  • 横にm個、縦にn個のマス目で任意の格子点から始め、通過したマス目の数をカウントする。
  • 標準入力からm,nが与えられた時、通過するマス目の数の最小と最大を解答する。
  • m,nはいずれも60以下の整数

方針

通過するマス目の数は下記の通り計算できる。

  • {m=1,n=1}のとき
    最小、最大とも{1}
  • {m},{n}の最大公約数が{1}以外のとき
    最小は{\frac{m \times n}{ \gcd (m,n)}}
    最大は{\frac{m \times n \times 2} { \gcd (m,n)}}
  • {m},{n}の最大公約数が{1} \Leftrightarrow m,n が互いに素のとき
    最小、最大とも{m \times n}

上記の説明

{m=1,n=1}のときは最小、最大ともに{1}である。

次に、{m=n (m,n \geq 2)}のとき、

最小は{m (=n)}

f:id:ibeckuu:20160413013337j:plain


最大は{2 \times m (=2 \times n)}である。

f:id:ibeckuu:20160413013629j:plain



{m,n}のいずれかがもう片方の倍数になっている場合、

仮に{m = k \times n}とすると、

最小は{m}

f:id:ibeckuu:20160413035531j:plain


最大は{2m}

f:id:ibeckuu:20160413032637j:plain


上記の他で最大公約数が1でない場合、

最小は {\frac{m \times n}{ \gcd (m,n)}}

f:id:ibeckuu:20160413033118j:plain


最大は{\frac{m \times n \times 2} { \gcd (m,n)}}

f:id:ibeckuu:20160413033325j:plain


互いに素のとき、

最小、最大とも{m \times n}

f:id:ibeckuu:20160413033530j:plain


実装

上記を利用して提出したコード (Ruby)

では、


Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第87回「3進法だとどう変わる？」

CodeIQ

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

codeiq.jp

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

  • 3進法を2通りの方法で表現する
    {0,1,2}の3つの数字で表現する場合
    {-1,0,1}の3つの数字で表現する場合
  • 標準入力より整数nが与えられる。
    0からnまでの整数のうち、上記のいずれの表現でも全ての桁が全く同じになるものの個数を解答する。

方針

-1を使って3進法を表現する時、上位桁に1を立てて-1を使って2を表現する。つまり-1と2は完全に対応する事になる。
2を使用しない数値はいずれの表現でも全ての桁が同じになるので、2を使用しない数値の個数を数えれば良い。

3進法でk桁目に2がでる数値を10進法で表すと、その数値を{{3}^{k+1}}で割った余りが{{3}^{k}}の2倍以上の時である。
これを用いて、{0}から{n}までの数値全てに対して、どの桁にも{2}が含まれないものの個数を数えて解答とする。

なお、この方法では計算量は{O(N log N)}となると思われる。
数学的に、包除原理を用いれば{O(log N)}で計算できると思って考えていたが、重複を差し引く良い方法が思いつかなかったので、実行時間制限をクリアできない事を覚悟で上記の方法で提出した。
幸い想定より入力が小さかったのでTLEにならず正解をもらえたが、全探索のコードを提出していては、自分としては負けた気がしている。

提出したコード(Ruby)

では、

Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第86回「アタック25に挑戦！」

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

https://codeiq.jp/sites/default/files/styles/thumb_175x114/public/engineer/algorithm.jpg?itok=Z_awtPsU

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

  • テレビ番組「アタック25」で次に選択できるパネル番号を求めるプログラムを書く問題。
  • 標準入力からプレイヤーの色、赤( R )、青(B)、白(W)、緑(G)ごとの現在獲得しているパネル番号が与えられる。
  • 各色ごとに、問題に正解した場合に選択できるパネルを列挙し解答する。

「アタック25」のルールはこちら
http://asahi.co.jp/attack25/rule/

パネルを選択できるルールについて確認

  1. 自分の色のパネルで他のプレイヤーのパネルを挟む事ができる位置がある場合 (優先順位1位)
    挟む事ができる位置の中から選ばなければならない。
  2. 自分の色のパネルで他のプレイヤーのパネルを挟む事ができる位置が無い場合で、次の問題に連続して正解したと仮定した時に挟む事ができる 状態になる位置。こちらもあればここから選ばなければならない。 (優先順位2位)
  3. 上記の条件で1箇所も選べる位置がない場合
    空白でないパネルに接している全ての空白パネル (優先順位3位)

選択できるかどうかの判定方法

上記のパネル選択ルールに基づき、コードに落とし込む為にパネルを選択できるかどうかの判定方法を説明する。
(下記の説明は1番のパネルを右方向に探索して選択できるかを判定する場合)

  • 隣のパネルが空白（誰も取っていないパネルを空白と表現する事にする)かパネルの枠外の場合
    パネルを選択できないのでスキップする
f:id:ibeckuu:20160331002313j:plain


  • 隣のパネルが自分と同じ色の場合
    他の色を挟む事も、次の正解時に挟める状態にする事もできない。優先順位3位とする。
f:id:ibeckuu:20160331002403j:plain


  • 隣のパネルから他の色が連続し、自分と同じ色が出現せず枠の終わりに達した場合
    優先順位3位とする
f:id:ibeckuu:20160331002435j:plain


  • 隣のパネルから他の色が連続し、空白に達した場合
    優先順位2位とする
f:id:ibeckuu:20160331002503j:plain


  • 隣のパネルから他の色が連続し、自分と同じ色に達した場合
    優先順位1位とする
f:id:ibeckuu:20160331002528j:plain


なお、例外があり、第1問・誰もパネルを取っていない初期状態では、正解した参加者は13番を指定するルールになっているので、誰もパネルを取っていない状態では全員が13番を選択できると解答しなければならない。
(この条件を考慮せずWAであった)

アルゴリズム

解答のアルゴリズムを大まかに説明する

{R,B,W,G についてループ
 {パネル1から25までループ
  {8方向をループしてパネルを選択できるか判定、   
   8方向の内、優先順位の最も高いものを選ぶ
   }
  対応する優先順位グループの配列にパネル番号を追加
  }
 要素がある優先順位グループの中最も優先順位の高いものを出力
}

実装

提出したコードは下記 (Ruby)

今回の問題はいつものパターンの総数を求める問題や、最大・最小を求める問題とは違っていた。
処理そのものは難しくなく、時間制限を気にする必要もなかったが、選択できるかどうかの判定が複雑で苦労した。
コードも100行近くなり見通しの悪いプログラムになってしまった。
長いコードを読んで頂いた皆さん、ありがとうございました。

では、

Sponsored Link

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第85回「隣り合えないカップル」

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

https://codeiq.jp/sites/default/files/styles/thumb_175x114/public/engineer/algorithm.jpg?itok=Z_awtPsU

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

  • {n}組のカップルを男女交互に円形に並べる事を考える。
  • カップルが隣同士に並ばないパターンの総数を解答する。
  • 円形なので回転したものは同じと見なすが、逆順は別とカウントする。
  • {n \leq 7}

方針

メモ化再帰を用いる
人数{n}人の女子を円形に並べ、その間にカップルが隣りあわない様に{n}人の男子を並べる配置を考える。
女子の組{\{g0,g1...g(n-1)\}}と添え字番号が同じ男子の組{\{b0,b1...b(n-1)\}}をカップルとして、添え字{i}と{i+1} ( {n-1}番目は{n-1}と1周して{0})以外の位置に男子{bi}を配置する全パターンをメモ化再帰により数える。
これに、女子の円順列の総数{(n-1)!}を掛けて解答とする

f:id:ibeckuu:20160323012059j:plain

提出したコード (Ruby)

数学的な解法

上記のコードを提出した後、色々と調べてこの問題が「menage problem」(正しくはフランス語表記)という数学の典型問題だと知った。
下記の英語のページに式の記載があるが簡単な式ではなかった。ご参考まで
Menage problem
では、

Sponsored Link

JavaScript (Spidermonkey) 標準入力のエラー回避の方法について

JavaScript

要旨

JavaScript(Spidermonkey)ではバージョンにより、readline()メソッドにバグがあり、標準入力が正しくできない場合がある。
これへの対処方法の紹介。
(但し根本的な解決にはならない)

注意点

バージョンの違いによるエラーの有無について

Spidermonkeyのバージョンの違いにより今回の記事で取り上げるreadline()メソッドに関するエラーの有無がある。
それをまとめたものが以下の表。

version 使用しているサービスの例 エラーの有無
spidermonkey-1.7 CodeIQ 「実行くん」 企業版ideone エラー有り
spidermonkey 24.2 コンシューマー版 ideone.com エラー無し

例えば、コンシューマー版ideoneで問題がなかったとしても、「実行くん」と同じ企業版ideoneを使用しているCodeIQに同じコードを提出した時に、意図した通りの動作をしない可能性がある。(記事公開時点での状況)
上記の表の通り、Spidermonkeyのバージョンが 24.2 以降の環境の場合はreadline()メソッドのバグによるエラーは無く、この記事の内容は無視してよい。

f:id:ibeckuu:20160321212215j:plain
コンシューマー版ideoneの例。 正しく動作している。

エラーの現象について

readline()メソッドを使用した時に起こり得るエラーの現象は次の2点

  1. 標準入力から入力された文字列の最後に改行文字が無い場合は最後の文字が入力されない。
  2. 複数行の入力の場合、EOFを検知できないので入力待ちの状態で止まる。

上記のいずれのエラーもバージョンが古い場合、Spidermonkeyを使用しない以外に根本的な解決策は無い。
(Rhino で標準入力を使用する場合はこちらを)

それでも、コードゴルフなどで、Rhino/Node.js等では記述が多く使いたくないなど、どうしてもSpidermonkeyを使いたい場合の対処方法を下記に述べる。

1.文字列の最後に改行文字が無い場合、最後の文字が入力されないエラーへの対処

リダイレクト、パイプ等で標準入力に渡すデータを自分でチェックできる場合は、文字列が改行文字で終わっている様にすれば良い。
readline()メソッドは文字列を改行文字が検出されるまで読み込み、改行文字の有無に関わらず、最後の文字を捨てている('\0'に置き換えている?)様に実装されていると思われる。

f:id:ibeckuu:20160321212853j:plain
文字列の最後に改行文字がある場合


以下の様に、文字列の最後に改行文字が付加されていない場合は文字列の最後の文字が正しく読み込まれないので、正しく処理できない。
CodeIQへのコードの提出の場合など、入力の最後に改行文字が間違いなく付加されているか確認できない場合はreadline()メソッドを使用してSpidermonkeyを使用する事は諦めざるを得ない。

f:id:ibeckuu:20160321212951j:plain
文字列の最後に改行文字がない場合


2.EOFを検知できないエラーへの対処

複数行の入力がある場合、readline()メソッドはEOF(入力の終わり)を検知できないので、
while((str=readline())!==null){
というコードを書くと、最終行を読み込んだ後、ずっと入力待ちの状態になり処理が止まる。
見かけ上処理が実行中なのか、入力待ちで止まっているのか分からない為、実行時間制限がある場合でタイムアウトした時に、実装の不備と思って間違った方向で悩む事があり得る。

f:id:ibeckuu:20160321213423j:plain


複数行の入力がある場合で、行数が分かっている場合は下記の様にループの回数を指定して記述すれば問題ない。
(但し、この場合も最後の行が改行文字が終わっていなければ最後の文字を正しく読み取れないエラーは発生する)

f:id:ibeckuu:20160321213517j:plain

複数行の入力で入力の行数が分からない場合はSpidermonkeyの使用を諦めざるを得ない。

以上。
では、

Sponsored Link

CodeIQ 挑戦の記録 : 第84回「今週のアルゴリズム：セルの結合で一筆書き」

CodeIQ

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

f:id:ibeckuu:20160316001650j:plain

問題文を要約すると、

  • 表計算ソフトのセルの結合を考える。
  • 標準入力から横が{m}、縦が{n}のセルの個数が与えられる。
  • セルの外周を図形として見たとき一筆書きをできる結合のパターンが 何通りあるかを答える。
  • {m \leq 10 \ ,\ n \leq 10}

提出したコード

Ruby(39byte)

m,n=gets.split(",").map(&:to_i);p m+n-1

Perlでも提出してみた。Perl(28byte)

<>=~/(.+),(.+)/;print$1+$2-1

コードの説明

一筆書きできるパターンを数えるが、その前に一筆書きができるかどうかについての判定法について述べる。
連結グラフにおいて、一筆書きが可能かどうかの条件をWikipediaから引用。

ある連結グラフが一筆書き可能な場合の必要十分条件は、以下の条件のいずれか一方が成り立つことである（オイラー路参照）。

  • すべての頂点の次数（頂点につながっている辺の数）が偶数 →運筆が起点に戻る場合（閉路）
  • 次数が奇数である頂点の数が2で、残りの頂点の次数は全て偶数　→運筆が起点に戻らない場合（閉路でない路）

何を言っているのか良くわからないかもしれないので解説する。　　

一筆書きができる図形の例(1)

f:id:ibeckuu:20160316001807p:plain

f:id:ibeckuu:20160316001830j:plain

全ての頂点の次数が偶数
青丸をつけた頂点（交差点と折り返し点）はつがなっている辺（線）の数が全て偶数
スタートした頂点に最後にもどる事ができる。

一筆書きができる図形の例(2)

f:id:ibeckuu:20160316001925j:plain

次数（つながっている辺の数）が奇数である頂点の数（赤丸）が2で、残りの頂点の次数は全て偶数（青丸） 次数が奇数である頂点を奇点と呼ぶ事にすると、一方の奇点からスタートし、もう一方の奇点を最後に訪れるたどり方しか一筆書きはできない。

一筆書きができない図形の例

f:id:ibeckuu:20160316002029j:plain

次数が奇数である頂点の数（赤丸）が2より多い
ある奇点からもう一方の奇点にたどり着くとどうしても通れない辺ができる。

この様に、奇点が0か2の図形しか一筆書きができない事になる。
これより、長方形のセルを結合した図形を考えた時、長方形の内部に縦か横に一本だけ線を加えたものと内部に線の無い長方形だけが一筆書きができるものとなる。

{m \times n}このセルの内部に一本だけ線を加えるパターン数は
{(m-1)+(n-1)}
これに線の無いパターン1を加え {m+n-1}
が求めるパターン数となる。
これを実装したのが上記のコード。

では、

Sponsored Link