2016年8月 5日 (金)

「プライム・ホッパー問題」の高度じゃないコード

「高度じゃないコード」シリーズその16「プライム・ホッパー問題」です。

まずは問題の内容です。(挑戦履歴より転載させていただきました)

ある素数に対し、次の変換1と2のいずれかを適用し、新たな素数を作ります。

変換1:元の数の右または左に1~9のいずれかの数字一つをつなげる。
(例:2→23、13→139、3→13、29→229)

変換2:元の数の右端または左端の数字一つを取り除く。
(元の数が 2 桁以上の場合のみ。例:31→3、673→67、23→3、673→73)

例えば 7→227、17→37 は有効な変換ではありません。
また 103→03 のように、先頭に 0 のつく数への変換はできません。

さて、素数 p と q(p < q)が与えられたときに、素数 p から始めて、変換1または2により q 以下の素数を作るということを繰り返し行い、最小の変換回数で q を作ることを考えましょう。

p=5,q=67 のときの一例を示します。
計 5 回の変換で 67 に変換できます。途中の数がいずれも 67 以下の素数であることに注意して下さい。
なお必ずしも変換1と2の両方を行う必要はありません。

  5 → 53 → 3 → 37 → 7 → 67

素数 p, q に対し、p から始めて q を作るときの最小の変換回数を F(p, q) と定義します。
そのような作り方が存在しない場合は F(p, q) = -1 と定義します。
例えば F(5, 67) = 5,F(3, 29) = 3,F(5, 541) = 10,F(3, 7) = -1 です。

標準入力から、半角空白区切りで素数 p, q(p < q かつ q ≦ 105)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

今回、殺戮ケースがあるという話を予め聞いてはいましたが、最初に作ったコードはそれにまんまと引っ掛かってしまいました。とりあえず、そのコードでの考え方を説明します。

最初に配列に p のみを入れます。そして、配列に入っている全ての数字に対して、変換1か変換2を行ってできる数字であり、q 以下であり、今まで出てきてなくて、そして素数である数を新たな配列に入れ、次回はその配列を処理の対象とします。これを、カウントしながら q が出てくるまで、または、配列が空になるまで繰り返すわけです。

ところが、これで提出すると、テストケースの1つが不正解となります。最初は、意味がわからなかったのですが、問題文をよく読み返してみてわかりました。
「また 103→03 のように、先頭に 0 のつく数への変換はできません」
これを考慮してなかったからでした。それに対する回避コードをつけて提出して全テストケースクリアとなりました。

その後、上記条件があるお陰で、逆向き、つまり、q から始めて p を作ることも同じ処理でできることに気が付きました。しかも、どうやら、そちらの方が最初の処理での発散が少なくなることから、処理時間も短くなりそうです。ということで、逆向きの処理に直して最終提出したのが次のコードです。(なぜか、手違いで1行目~8行目までがダブった状態で提出していました。エラーが出なかったので全く気付きませんでしたが)


(28行目の sort は、最初のコードで d[-1] が q であるか調べていた名残なので、今では不要です)

ちなみに、この逆向きコードで殺戮ケース避けである21行目最後の「if s[1]>?0」を除いて8つのテストケースを試してみましたが、その状態でも全テストケースクリアとなりました。どうせやるのなら、逆向きコード用の殺戮ケースも用意しておかないと・・・。

| | コメント (0) | トラックバック (0)

2016年7月20日 (水)

「階乗フィーバー数問題」の高度じゃないコード

「高度じゃないコード」シリーズその15「階乗フィーバー数問題」です。この問題は、7月16日に開催されたCodeIQ感謝祭の階乗・・・じゃない、会場限定で出題された問題で、解けた方には賞品も出たそうです。私も行きたかったけど、その日はエアコン取り付け工事の仕事も入っていたし、地方在住なのでなかなかこういったのに行く機会がないからなぁ・・・。

そして、その後、ネットで問題が公開されました。

【階乗フィーバー数問題】

最初は、ずっとくそ真面目に全桁計算をしていました。前回インラインアセンブラで敗北したC(gcc)を使って、1バイト1桁・4バイト4桁・4バイト6桁などで区切って計算しましたが、全て実行くんで1秒では全く終わる気配がありません。結局、家のPCでVCを使って計算しました。CPUがしょぼいせいもあるかもしれませんが、答えが出るのに数十秒かかりました。

しばらく、そのままで放置していましたが、ふと、正解ページの掲示板に「stirlingの公式で近似」と書かれているのを読んでようやく気がつきました。上位の6桁だけが間違いなく計算できさえすればよくて、全桁計算する必要なんて全くないことに・・・。

これに気が付きさえすれば後は簡単です。上位6桁の計算に影響を及ぼさない有効桁数を決め、それより下はばっさり捨てます。本当は、四捨五入した方がいいのかもしれませんが、桁数を増やせば切捨てで問題ないと予想。もちろん、指数部分も結果とは関係ないので無視します。

» 続きを読む

| | コメント (2) | トラックバック (0)

2016年7月 7日 (木)

「アフター・ドット問題」の高度じゃないコード(高速編)

「高度じゃないコード」シリーズその14「アフター・ドット問題」、その後編(高速編)です。

前回のままのやり方ではそんなに高速にはならないだろうから、根本的に処理を変える必要がありました。まず、前回、b を 2 と 5 で割れるだけ割って b' を求めましたが、逆に、この b' を基準に考えてみます。さて、b' とは 2 でも 5 でも割り切れない数字なので、一の位が 1, 3, 7, 9 の自然数です。それ以外の、一の位が 0, 2, 4, 5, 6, 8 の数字は、b' に 2 と 5 をある回数掛けることで出てきます。

ここで、ある b' に対して、2 と 5 のべき乗の積を掛けたのが b ということになるので、n ÷ b' 以内に存在する 2 と 5 のべき乗の積の数が b の取り得る値の数(これを x とします)、そして、a の取り得る値の数は、前回と同様、n ÷ b'(これを y とします)なので、その2つの積( x × y )を求めればいいわけです。

さて、このように、n 以下で、一の位が 1, 3, 7, 9 の自然数全てで上記の計算をやれば答えは求めることができますが、個別に計算していたらやはり時間がかかります。そこで、上記の x が同じ値になるものを纏め、またその中で、y に関しても商によって個別で計算する部分と、同じ商が並ぶ部分は纏めて計算することで高速化することにしました。まずは、Ruby のままで、この考え方でコードを作ってみました。実行くんで 1011 が 0.9s でした。(ただし、バージョンアップ後は 0.67s に向上)

» 続きを読む

| | コメント (0) | トラックバック (0)

「アフター・ドット問題」の高度じゃないコード(ゴルフ編)

「高度じゃないコード」シリーズその14は「アフター・ドット問題」です。今回の記事は、高速編がでかくなりそうなので、前編・後編と2回に分けますが、その前編(ゴルフ編)です。

自然数 n に対し、1 ≦ a ≦ n,1 ≦ b ≦ n を満たし、かつ小数で表した a÷b が有限小数となるような自然数の組 (a, b) の個数を F(n) と定義します。
(有限小数…小数点以下の桁数が有限である小数。)
標準入力から、自然数 n(1 ≦ n ≦ 104)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

最初に、a ÷ b が有限小数となるための条件を考えます。どんな自然数でも、2 のべき乗と 5 のべき乗で割ると有限小数となるので、b を 2 と 5 で割れるだけ割ります。そして、a がその商 b' の倍数であれば有限小数になります。1 ≦ a ≦ n におけるその個数は、n ÷ b' の整数部ということになります。後は、1 ≦ b ≦ n の条件でループさせれば、F(n) を求めることができます。

今回は、ゴルフ解を作って一旦終了したように思えましたが、自然数 n(1 ≦ n ≦ 104)の制限を外し、どこまで大きな値まで計算できるかを競うことになり、非常に悩みましたがとても楽しませていただきました。

» 続きを読む

| | コメント (0) | トラックバック (0)

2016年6月18日 (土)

「マイナー・ゲーム問題」の高度じゃないコード

「高度じゃないコード」シリーズその13は「マイナー・ゲーム問題」です。

問題の内容は次の通りです。(挑戦履歴より転載させていただきました)


n 人のプレイヤーで「少数決」というゲームを行います。
ゲームは次の手順で進みます。

 各プレイヤーは、投票用紙にAまたはBの文字を記し投票します。投票は記名式です。他のプレイヤーの投票内容は分かりません。
 全員が投票し終わったら開票します。その結果、少数派になる回答をした者が勝者となります。例えばAが 3 票、Bが 4 票の場合は、Aを投票した 3 名が勝者です。AとBが同数の場合や、全員がAの場合、全員がBの場合は、全員が勝者です。
 勝者はそのまま勝ち残り次の投票に進めますが、敗者はそこで脱落します。
 以上が 1 回の「ターン」です。この要領でターンを繰り返し、勝ち残りが 1 人か 2 人になるまでゲームを続けます。

各プレイヤーはAまたはBをランダムに選んで投票します。
このとき、n 人のプレイヤーから始めてゲームが終了するまでのターンの回数の期待値を F(n) と定義しましょう。

例えば F(3) = 4/3 です。3 人の投票の仕方は計 23= 8 通りあります。このうち全員がAまたは全員がBの場合(2 通り)は 3 人ともが勝者となりますが、それ以外の場合(6 通り)は 1 名の勝者が決まりゲーム終了します。

1 回目のターンでゲームが終了する確率は 6/8 = 3/4 です。
2 回目のターンでゲームが終了する確率は (1/4)×(3/4) です(1 回目で終了せずかつ 2 回目に終了する確率)。
3 回目のターンでゲームが終了する確率は (1/4)2×(3/4) です(1, 2 回目で終了せずかつ 3 回目に終了する確率)。

したがって期待値は 1×(3/4)+2×(1/4)×(3/4)+3×(1/4)2×(3/4)+… = 4/3 となります。

同様に、F(4) = 2,F(5) = 16/15,F(7) = 1.7566137…,F(8) = 2.2028985… となることが確かめられます。

標準入力から、自然数 n(3 ≦ n ≦ 100)が与えられます。

標準出力に、F(n) を 106 倍した値の整数部分を出力するプログラムを書いてください。

4つの条件に分けて考えます。求める F(n) は次の各場合の合計になります。

1.人数が減らない場合(勝敗がつかない)
 全員が A の場合、全員が B の場合、それと、人数が偶数で半々に分かれた場合です。
 回数が 1 増えただけで、2回目以降の期待値は F(n) と等しいことになります
 [この条件の組合せ数]*(1+F(n))/(2n)

2.上記まで以外で、少ない方を選んだ人が1人(勝敗がつく)
 [この条件の組合せ数]*(1+F(1))/(2n) ※ただし F(1)=0

3.上記まで以外で、少ない方を選んだ人が2人(勝敗がつく)
 [この条件の組合せ数]*(1+F(2))/(2n) ※ただし F(2)=0

4.上記まで以外で、少ない方を選んだ人がt人(t≧3)(勝敗がつかない)
 [この条件の組合せ数]*(1+F(t))/(2n)

ここで、1番の[組合せ数]を j、2番以降の分子の合計を k とすると

F(n)=j*(1+F(n))/(2n)+k/(2n)

(2n)*F(n)=j*(1+F(n))+k

(2n-j)*F(n)=j+k

F(n)=(j+k)/(2n-j)

ということで、後はこの式を使って、必要な F(n) を順次計算していきます。(メモ化利用)

» 続きを読む

| | コメント (0) | トラックバック (0)

2016年5月25日 (水)

「レッド・アンド・ホワイト問題」の高度じゃないコード

非常に遅ればせながらの「高度じゃないコード」シリーズその12、「レッド・アンド・ホワイト問題」です。

数学の問題をプログラミングで解こう!「レッド・アンド・ホワイト」問題解説

最初には1箇所だった赤マスがルールに従って1秒毎に変化していきます。その時、n秒後(1 ≦ n ≦ 108)の赤マスの数を答えろという問題です。
イメージがわきにくいので、まずは1秒~32秒のパターンを調べてみました。0が白マスで1が赤マスです。

01秒101
02秒10001
03秒1010101
04秒100000001
05秒10100000101
06秒1000100010001
07秒101010101010101
08秒10000000000000001
09秒1010000000000000101
10秒100010000000000010001
11秒10101010000000001010101
12秒1000000010000000100000001
13秒101000001010000010100000101
14秒10001000100010001000100010001
15秒1010101010101010101010101010101
16秒100000000000000000000000000000001
17秒10100000000000000000000000000000101
18秒1000100000000000000000000000000010001
19秒101010100000000000000000000000001010101
20秒10000000100000000000000000000000100000001
21秒1010000010100000000000000000000010100000101
22秒100010001000100000000000000000001000100010001
23秒10101010101010100000000000000000101010101010101
24秒1000000000000000100000000000000010000000000000001
25秒101000000000000010100000000000001010000000000000101
26秒10001000000000001000100000000000100010000000000010001
27秒1010101000000000101010100000000010101010000000001010101
28秒100000001000000010000000100000001000000010000000100000001
29秒10100000101000001010000010100000101000001010000010100000101
30秒1000100010001000100010001000100010001000100010001000100010001
31秒101010101010101010101010101010101010101010101010101010101010101
32秒10000000000000000000000000000000000000000000000000000000000000001

すると面白いことがわかります。この中で1(赤マス)の数が2つしかないのは1秒・2秒・4秒・8秒・16秒・32秒、つまり2のべき乗秒です。そして、それより1秒前は1(赤マス)と0(白マス)が交互に並びます。そうして調べていくと、秒数を2進数にした時の1の数を m とすると、2m が1(赤マス)の数があることがわかります。

» 続きを読む

| | コメント (0) | トラックバック (0)

2016年5月13日 (金)

「コード・トライアスロン2」の高度じゃないコード

またまた一ヶ月以上間が開いてしまいましたが、「高度じゃないコード」シリーズその11、「コード・トライアスロン2」です。

数学の問題をプログラミングで解こう!「コード・トライアスロン2」問題解説

この問題は、三角関数の誤差で悩みました。第一段階で求めた答えが少しずれると、最後の答えが全く違った値になるからです。でも、実際は、誤差のせいではなく、私がπの値として「PI」を使わずに「3.1416」を使っていたからなのでした。そして、そのような状態でも、6問のうち5問まではクリアできてしまっていたので、そこが悪いことになかなか気付かなかったのでした。

思い起こしてみると、Cとかでも今までπや三角関数を使ってプログラムを書いたことが一度もありませんでした。円(楕円)を描くプログラムを作ったことはありますが、描くだけならせいぜい二乗とルートしか使いませんので。

さて、今回の問題は、3つの問題を合わせたものですが、第一問の角度を求める問題で早くも躓いてしまいました。色々と補助線を引いたりしましたが、なかなか解決方法がわからず、仕方がないのでネットで検索して求め方を拾ってきました。

次に第二問ですが、n を d で割った余りが 1 になるということは、d は n-1 の約数ということです。ということで、約数の合計を求めますが、約数のうち 1 だけは取り除く必要があるので 1 を引きます。

最後の第三問は、2つのステップに分けて計算することにしました。m の桁数未満の回文数の合計と、m の桁数と同じ桁数の回文数の合計です。まぁ、別に分けなくても充分時間には余裕があるようでしたが・・・。テストプログラムを作って走らせてみると、桁数未満の回文数合計は次のような結果となりました。

リミット値回文数合計桁増え増分
100 540
100050040+49500
10000545040+495000
10000050045040+49500000
1000000545045040+495000000
1000000050045045040+49500000000


この表からわかるように、1桁増えると増分は10倍と100倍を交互に繰り返しています。ということで、これを使えば、m の桁数未満の回文数合計は桁数回のループで計算できます。その後は、m の上半分の桁の数を増やしながら、それをリバースした数を後ろにくっつけます。ただし、m の桁数が奇数の場合はくっつける数の最初の桁を取り除きます。

» 続きを読む

| | コメント (0) | トラックバック (0)

2016年4月 7日 (木)

「ディビジョン・ナイン問題」の高度じゃないコード

先月初めの連続記事からちょっと間が開きましたが「高度じゃないコード」シリーズその10、「ディビジョン・ナイン問題」です。

1 から 4 の数字を使って作る n 桁の整数のうち、9 の倍数となるものの個数を F(n) と定義します。
標準入力から、自然数 n(1 ≦ n ≦ 20)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

数学の問題をプログラミングで解こう!「ディビジョン・ナイン」問題解説

9の倍数と言われてまず思いつくのが、9で割った余りは各桁の和を9で割った余り、つまり、各桁の和が9で割り切れる数字は9の倍数ということです。1~4の数字を組み合わせて9・18・27・・・という9の倍数になる組み合わせを求めるわけです。例えば、n桁の4進数と考えると、各桁の数字は0~3となりますが1足すことで1~4となるので、n桁の4進数の各桁の和に桁数を加えたものが9の倍数かどうかを調べることになります。ただし、最大20桁の4進数となると、420で約1.1兆通りの数字を逐一調べるのは効率が悪く、タイムアウトになるのは目に見えています。

この考え方のままで効率よく計算させる方法は残念ながら思いつかなかったので、とりあえず、9で割った余りが0~8になる数字がそれぞれ幾つあるかを、桁数を1桁づつ増やしながら調べていくことにしました。

さて、1桁増えた場合の処理ですが、2通りの方法が考えられます。ループで変化させる数値を、増えた桁の数1~4にするか余りの数0~8にするかです。そう、「プラス・マイナス・ゼロ問題」の高度じゃないコードの時と同じです。今回、前者を選ぶと、同じ配列要素に値を4回に分けて足すことになるので、それに伴い値の初期化も必要になります。後者を選ぶと、1つの配列要素の計算は1回でできるので、値の初期化も不要になります。私は後者を選びましたが、実装次第でどちらが短くなるかは変わりますね。まぁ、今回はコードゴルフは考えてないので・・・。

そして、1桁増えた時の計算方法は次のようなものになります。
・余り0の数は、1桁増える前の余り8(+1)・余り7(+2)・余り6(+3)・余り5(+4)の数の和
・余り1の数は、1桁増える前の余り0(+1)・余り8(+2)・余り7(+3)・余り6(+4)の数の和
・余り2の数は、1桁増える前の余り1(+1)・余り0(+2)・余り8(+3)・余り7(+4)の数の和
・余り3の数は、1桁増える前の余り2(+1)・余り1(+2)・余り0(+3)・余り8(+4)の数の和
・余り4の数は、1桁増える前の余り3(+1)・余り2(+2)・余り1(+3)・余り0(+4)の数の和
・余り5の数は、1桁増える前の余り4(+1)・余り3(+2)・余り2(+3)・余り1(+4)の数の和
・余り6の数は、1桁増える前の余り5(+1)・余り4(+2)・余り3(+3)・余り2(+4)の数の和
・余り7の数は、1桁増える前の余り6(+1)・余り5(+2)・余り4(+3)・余り3(+4)の数の和
・余り8の数は、1桁増える前の余り7(+1)・余り6(+2)・余り5(+3)・余り4(+4)の数の和

なお、私のコード中では0桁の場合に余り0が1通りのみをスタートとしましたが、1桁の場合に余り1~4がそれぞれ1通りというのをスタートにした方がわかりやすいかもしれません。もちろん、どちらにしても、ループの回数が1回変わるだけで結果は同じになりますが・・・。

» 続きを読む

| | コメント (1) | トラックバック (0)

2016年3月11日 (金)

「ロング・ロング・ストリング問題」の高度じゃないコード

「高度じゃないコード」シリーズその9は「ロング・ロング・ストリング問題」です。今月はこれで4つ目となります。

F(n) を、nn(n は自然数)の10進数で表したときの桁数とします。
G(m) を、F(n) = m(m は 2以上の自然数)となる n の値とします。
(ただし、そのような n が存在しないなら、G(m) = -1)
標準入力から、自然数 m(2 ≦ m ≦ 1010)が与えられます。
標準出力に G(m) の値を出力するプログラムを書いてください。

数学の問題をプログラミングで解こう!「ロング・ロング・ストリング」問題解説

1010桁の数字なんてそのままでは扱えませんが、このような桁数やべき乗の問題は常用対数をとればいいですね。
問題に F(n) やら G(m) やら出てきてわかりにくいですが、簡単に書くとこういうことです。
10(m - 1) ≦ nn < 10m
対数をとるとこのようになります。
m - 1 ≦ n * log10(n) < m
m - 1 以上 m 未満ということは、n * log10(n) の小数点以下を切り捨てた値が m - 1 に等しいということです。

まずは、m ≦ 1010 の上限に最も近くて G(m) が -1 にならない m をオフラインで調べてみました。
すると、m = 9999999995 の時に G(m) = 1105747502 で最大値となることがわかりました。
一方、m = 2 の時の G(m) = 3 が最小値です。(もちろん、-1 は除外しています)

さて、求める答えは、最小値と最大値の間にあるので、その中間値でテストし、それより大きいようなら最小値、小さいようなら最大値を中間値に更新していくという方法でコーディングしました。
ただし、組んだアルゴリズムだと、初期値が最小値か最大値と同じ(境界値)の場合、結果を見落としてしまうため、初期値は (最小値 - 1) と (最大値 + 1) にしました。(テストケースに境界値はなかったので通りはしましたが)

» 続きを読む

| | コメント (0) | トラックバック (0)

2016年3月10日 (木)

『電脳体「キュラゲタム」を討伐せよ』の高度じゃないコード

「高度じゃないコード」シリーズその8はモンハンコラボ問題『電脳体「キュラゲタム」を討伐せよ』です。激ムズ問題のため協力プレイ可ということでしたが、何とか独力で解くことができました。挑戦期間が終了していて問題を見ることができませんが、挑戦の履歴から問題を転載させていただきます。(もし問題があるようでしたらご連絡ください)

クエスト:激ムズ!頭脳を【上限解放】~電脳体キュラゲタムを討伐せよ

★この問題は「激ムズ」のため、モンハンと同じく「協力プレイ」を可とします。挑戦受付中の相談はOKです。ぜひ協力して正解をめざしてください!

【二つ名持ちモンスター、電脳体「キュラゲタム」を討伐せよ!】
キュラゲタムは、キュラゲの中でも非常に珍しく周囲が見渡せるような高い場所でしか見られません。
このキュラゲタムを、最速で討伐して無事帰還してください!

【問題詳細】
マップ上を移動し、キュラゲタムの生息エリア(マップ上で最も高度の大きい場所)に向かいます。
マップ上のキュラゲタム生息エリアをすべて通りキャンプ(スタート地点)に戻るまでの最短時間を求めてください。

◎マップ
H×Wの格子状になっている文字列が与えられます。各地点には、0~9のレベルでその地点の高度情報が与えられ、移動方法・移動にかかる時間は次のように決まっています。

◎移動ルール
●隣り合う上下左右のマスのみ移動できます。
●高低差が無い場合: 1マス移動するのに3分かかります。
●高低差が「1」の上りの場合: 1マス移動するのに11分かかります。
●高低差が「1」の下りの場合: 1マス移動するのに2分かかります。
●高低差が「2」以上の場合: 上り・下り問わず移動することはできません。

例えば、2×3のマップ

    
   
   

で、左上から右上まで移動する場合、単純に右に進むと11+2で13分かかります。

  

しかし以下のように高低差を避けて回り込めば、3+3+3+3で12分になります。

  

◎注意点
●キャンプ(スタート地点)はマップ上の左上とします。
●キャンプ(スタート地点)からキュラゲタムの生息エリアまでのルートは必ず存在する入力データとなっています。
●マップ上の同じエリアを何回通ってもかまいません。
●キュラゲタムの生息地点数は最大15です。

【入力】
標準入力の1行目は、マップの縦サイズH・横サイズWが半角スペース区切り、2行目以降のH行分にマップデータとなる文字列が与えられます。

【出力】
標準出力に、最短時間を表す整数値を出力してください。

【入出力サンプル】
Input
4 5
32445
33434
21153
12343

Output
96

【入出力サンプルの説明】

↑↓
↓↑

マップ上での最高高度は「5」です。したがって、キュラゲタムは「5」の位置に生息すると判断します。
左上がキャンプ(スタート地点)ですので、上図のように移動すると96分で帰ってくることができます。

※問題内のモンスター、武器、アイテムなどは『モンスターハンタークロス』のゲーム内には登場しません。

この問題は2つの問題が合体したものと考えられます。1つは、与えられた条件における最短移動時間を求める問題、もう1つは、全ての目的地を最短コスト(この問題の場合は時間)で回る「巡回セールスマン問題」と呼ばれる問題です。

問題には書かれていないので、挑戦してみないとマップの最大サイズがわかりません。とりあえず、200×200 でコーディングしてみて最初の挑戦をしてみました。結果は、4問目でタイムアウトして、しかも、最後の2問は 250×250 であることが判明しました。

そこで、どこに時間がかかっているかを調べてみると、前半の最大16拠点(スタート地点とモンスターがいる最大15拠点の合計)間の移動にかかる時間の計算でした。後半は、短い時間で行けるベスト3を順次調べていくという最初に作った不完全な方法で時間的には問題ないです。そこで、後半の処理はそのままで、前半のアルゴリズムの見直しからすることにしました。それでもし、タイムアウトは回避できて不正解になるようなら、その時点で後半を考え直すようにしようと・・・。

そして、グッドなアルゴリズムを思いつきました。大きな流れとしては、1分で行ける場所を探し、2分で行ける場所を探し、3分で行ける場所・・・というように順番に探して行きます。(実際には1分で行ける場所はないので、2分からスタートさせていますが・・・)

さて、n分で行ける場所ですが、次の3つの条件のどれかを満たす場所となります。

1.n-2分で行ける場所に隣接していて高さが1下りとなる場所
2.n-3分で行ける場所に隣接していて高さが同じ場所
3.n-11分で行ける場所に隣接していて高さが1上りとなる場所

ただし、最大250×250のマップを全て調べていては時間がかかるので、過去11分間(n-11分~n-1分)に行けた場所と、今(n分で)行ける場所を書き込む、合計12分間の行ける場所リストを作成すれば高速チェックが可能です。

最初は、0分で行ける場所リストにスタート地点が1つあるだけですが、隣接地点で高さが1低い場所があれば2分で行けるリストに入り、高さが同じ場所があれば3分で行けるリストに入り、高さが1高い場所があれば11分で行けるリストに入ります。問題に出ている2×3のマップだと、スタート地点の下の地点が3分のリストに入り、その右が6分のリストに入り、さらにその右が9分のリストに入り、最後にその上が12分のリストに入ることになります。スタート地点の右の地点は11分のリストに入りますが、その右の地点はそこ経由だと13分となり、すでに回り込むことで12分で到着しているのでこのルートは評価されません。

そして、チェックの終了条件は、次のどちらかです。

1.12分間連続して行ける場所リストがなくなった
 (それ以降には行ける場所は増えない)
2.調べている拠点以外の最大15拠点への最短移動時間が全て埋まった
 (目的を果たした)

処理時間もほとんど変わらないので、私は終了判定が簡単にできる1を採用しました。

しかも、この方法は、目的地を定めずに行ける場所を広げていくだけなので、他の拠点全てへの最短移動時間を一度に求めることができます。
この処理を、スタート/ゴール地点とモンスターがいる地点の最大16箇所それぞれにつき1回づつ実行すれば、全拠点間の最短移動時間を求めることができるわけです。

こうしてコーディングして2回目の挑戦をしてみました。1問目~6問目までは「00.0秒 ○ 正解」でした。これは、勝ったなと思いましたが、7問目は「00.1秒 × 不正解」、さらに、8問目で「実行エラーです。 ソースコードに不備があります。」という初めて見るメッセージが出て、そこで挑戦終了となりました。で、ソースを調べてみて、毎分の行ける場所リスト用に確保していた配列が小さすぎたことが判明し、それを修正して3度目の挑戦をしました。7問目~8問目「00.1秒 ○ 正解」、9問目「00.2秒 ○ 正解」となり、「クエスト達成!」画面を拝むことができました。

» 続きを読む

| | コメント (0) | トラックバック (0)

«「平方コピペ数問題」の高度じゃないコード