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

JavaScript 標準入力・標準出力でJavaのメソッドを使う方法

JavaScript

要旨

JavaScriptで、標準入力・出力にJavaのメソッドが使用できるのでその紹介。
(但し、rhinoに限る。 spidermonkey/node.jsでは不可。
また、この記事は標準入出力での使用方法について書いたものなので、JavaScriptの本来用途としてのブラウザ上の表示では動作しない）

「標準入力」「標準出力」について

JavaScriptは動的なWebサイトを構築するのに必須の技術であるが、基本的にブラウザ上で何かをするものなので、Web系の人など
「標準入力」「標準出力」ってナニ？
状態の人が少なからずいる様だ。

ざっくり言えば、「標準入力」とはキーボードからの入力、「標準出力」とはディスプレーへの出力である。
詳細は下記を参照頂きたい。

標準入力、標準出力、標準エラー出力、パイプとは?
標準ストリーム - Wikipedia

Webの仕事においては知らなくても全然困らないであろうが、CodeIQ・paizaなどのサイトでコードを提出する際 は「標準入力」「標準出力」を利用できるコードを書く必要がある。 しかし、 JavaScriptではこれが簡単ではない。

一応下記のサイトで幾つかの言語について標準入出力のサンプルを紹介されているが説明は十分ではない。

各言語の標準入出力サンプル - CodeIQ
（ログインしないと見られない事もあるかもしれない）

そこで、下記の様な方法でJavaのメソッドを利用できれば便利だという話。

方法

入力の例(BufferdReaderを使用）

importPackage(java.io);
importPackage(java.lang);

var br = new BufferedReader(new InputStreamReader(System['in']));
var str;
while((str=br.readLine())!==null){
    System.out.println(str);
}

上記の例では入力にBufferedReader、出力にSystem.out.printlnを使用している。
Javaに詳しくない方の為に少し解説する。
Javaでは標準入力からの入力の方法が2つある。
java.io.BufferedReader を使う方法と、java.util.Scanner を使う方法である。
こちらは最初の方法

  • 変数(この例ではbrとした)を宣言し、標準入力を示すSystem['in']から読み込むインスタンスをnewして代入する。
  • テキストを1行読み込むreadLine()メソッドの返り値を変数に代入し、入力がある限り標準入力の内容をそのまま標準出力に出力する。
    （readLine()は読み込めた場合はそのテキスト、EOFに達した場合はnullを返す）

入力の例（Scannerを使用）

importPackage(java.lang);

var sc = new java.util.Scanner(System.in);
while(sc.hasNext()){
    var str = sc.next();
    var num = parseInt(str);
    System.out.printf("%3.0f\n",num);
}

2つめの例
java.util.Scanner を使う方法。

  • System. in（System['in']でも良い）より読み込むインスタンスをnewして変数（ここではscとした）に代入する。
  • 入力文字があるかないかを返すboolean hasNext()メソッドがfalseを返すまで読み込み、出力する。
  • 出力の際、文字列を数値に変換、小数点以下を切り捨て、3桁目までを右揃えで桁を揃えて出力。

　 なお、Scannerでは正規表現が使え、文字列、数値等必要なものを選んで取り込む事ができるが、その方法は別に調べて欲しい。
next()を使ったこの例では文字列をそのまま返し、parseInt()で処理している。

おまけ

この例では出力にprintfを使っている。
JavaScriptで書式化文字列を使用できたらと思っていた人は多いのではないかと思う。
Javaのパッケージを利用する事で、printf が使えるのである。
但し、これはあくまでも標準出力での限定の話であるし、元々静的型付け言語ではないJavaScriptでの書式指定は完全な互換性がある訳では無い様で、調べた限りではparseInt()しても%dによるint型での書式化はできず、あくまでも浮動小数点型(%f)でしか動作しないなど、何でもできる訳ではなさそうである。

以上。
では、

Sponsored Link

CodeIQ 挑戦の記録 : 「ロング・ロング・ストリング」問題

CodeIQ

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

codeiq.jp

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

  • 自然数{n}に対して関数{F(n)}を{{n}^{n}}を10進数で表した時の桁数と定義する。
  • 2以上の自然数{m}に対して関数{F(n)=m}となる{n}の値を{G(m)}と定義する。
    そのような{n}が存在しない時は{G(m)=-1}と定義する。
  • 標準入力から{ m \ (2 \leq m \leq {10}^{10})}が与えられる。
  • {G(m)}を出力する。

方針

題意より{F(n)=m} は次の数式で表す事ができる。
\begin{align} floor( \log_{10} {n}^{n} ) + 1 =m \end{align}

これを変形し、
\begin{align} m-1 \leq \log_{10} {n}^{n} < m
\end{align} これを{n}について解けば{O(1)}のコードが書けるが、この数式を解く能力は自分には無いのであっさり諦める。
上式を
\begin{align} floor( n \log_{10} n)+1=m \end{align}
と変形し{F(n)=m}となる{n}を探索する事にする。
但し、線形探索{O(N)}では、入力の最大{{10}^{10}}に対して1秒の時間制限をクリアする事は出来無い。
そこで、二分探索{O(\log N)}を自前で実装する事とする。

実装

提出したコードは下記の通り
(実際は下記をワンライナーにしたもの。134byte)

では、


Sponsored Link