« 2016年2月 | トップページ | 2016年4月 »

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)

2016年3月 8日 (火)

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

「高度じゃないコード」シリーズその7は「平方コピペ数問題」です。

桁数が偶数の自然数であって、前半分と後ろ半分の桁の数字の並びが同じである数を「コピペ数」と定義します。

例えば、11、100100、123123、666666 はコピペ数です。
12、333、1001、124421、202020 はコピペ数ではありません。

また、整数の二乗で表される数(16、25、49 など)を平方数と呼びます。

コピペ数かつ平方数である、最も小さい数を求めて下さい。

(下記の問題ページよりコピペさせていただきました)


【平方コピペ数問題】

今日の午前中になって問題を初めて知りましたが、今朝の朝8時にブログ等での解答などの発表が解禁になったということであわてて考え、お昼過ぎに何とか解けて足跡を残しましたが、その時点で既に解答を公開している人もおられたようです。ですが、カンニングはしておりませんので念のため・・・。

数字の前半と後半が等しいということは、その数字は、11・101・1001・10001・・・という最上位と最下位の桁が1で後は0の数字(これ以降は101数字と書きます)の倍数です。101数字に掛ける数字はそれより1桁小さな数字でなくてはならないので、全体が自然数の二乗であるためには、101数字自身が2以上の自然数の二乗で割り切れなくてはなりません。

これを式として考えてみます。求める答えが3つの自然数 i, j, k を掛けたものの二乗だとします。
(i*j*k)2 = i*i * j*j * k*k = (i*i*j) * (j*k*k)
今回の問題の条件を満たすためには、この積となっている2つの括弧の中身のどちらかが101数字、もう片方がコピペされる数字でなければなりません。ここでは前者が101数字だとします。

さて、101数字は奇数なので2で割り切れません。また、全ての桁を足すと2となることから3でも割り切れません。1の桁が1なので5でも割り切れません。ということで、最初の候補は上の式の i = 7 の場合となり、i*i = 49 となります。

そこで、まずは、101数字で49で割り切れるものを探してみました。そうして、1000000000000000000001 = 7*7*20408163265306122449 を見つけました。j = 20408163265306122449 ということになりますが、このままだと1桁足りなくてコピペ数字にならないので、k*k を掛けて1桁増える最小値の k = 3 を適用させ 9倍します。ということで、(7*7*20408163265306122449)*(20408163265306122449*3*3) = 183673469387755102041183673469387755102041 という答えが出ました。

ところが、その答えを入力しても、Not Found となります。どうやら、条件を満たす数字でもっと小さいものがあるようです。そこで、i = 7 以外の、i = 11 や i = 13 や i = 17 や i = 19 などの各二乗で、上記より小さい101数字が割り切れないかを調べてみました。そしたら、i = 11 で 100000000001 = 11*11*826446281 となりました。上の例と比べてむっちゃ小さいですね。で、上と同じ方法で答えを出しました。(11*11*826446281)*(826446281*4*4) = 1322314049613223140496 となり、今度は、ちゃんと正解のページに飛ぶことができました。

続きを読む "「平方コピペ数問題」の高度じゃないコード"

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

2016年3月 3日 (木)

「デスコロC #2」の高度じゃないコード

高度じゃないコードシリーズその6は「デスコロC #2」です。

aBcdEfGhijKlmnopQrStuvwxyzabCdefghijklmnOpqrstUvwxyzabcdefGhIjklmnOpqrStuvwxyzAbcdefghijKlmnopqrStuvWxyzabCdEfghijklmnopqrstuvWxyzabcdefghijklmnopqrStUvwxyzAbcdefghijKlmnopqrstuvWxYzabcdefghIjklmnOpQrstuvwxyzabCdefghijklmnopqrStUvwxyzabcdefGhijklmnopQrstuvWxyzabcdefghIjKlmnopQrstUvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijKlmnopqrStuvwxyzabCdEfghijklmnopqrstuvwxyzabcdefGhijklmnOpqrStuvwxYzabcdefghijKlmnopqrStuvWxyzabcdEfghijklmnOpqrstuvwxyzAbcdefghijklmnopqrstUvwxyzAbcdefghijKlmnopqrstuvWxYzabcdEfghijklmnOpqrstuvwxyzAbCdefghIjklmnopqrStUvwxyzabcdefghijklmnopQrstuvWxyzabcdefghIjKlmnopqrstuvwxyzAbcdefghijklmnOpqrstuvwxYzabcdefGhijklmnopQrstuvwxYzabcdefghijklmnopqrstuvWxyzabCdefGhijklmnOpqrstuvwxyzabcdefGhijklmnopQrstuvwxyzabCdEfghijklmnOpqrstUvWxyzabcdefghijklmnopqrstuvwxYzAbcdefghijklmnopqrStuvWxyzabCdefghijklmnopqrstuvWxyzAbcdefghIjklmnopqrStuvwxyzabcdEfghijKlmnopqrstuvwxyzabcdEfghIjklmnOpqrstuvwxyzabCdefghIjklmnopqrstUvwxyzabcdEfGhijklmnopqrstuvwxyzabcdefghIjKlmnopqrstUvwxyzabCdefghijklmnopqrstUvwxYzabcdEfghijklmnopQrstuvwxYzabcdefghijKlmnopqrstuvwxyzabcdefGhijklmnopqrstuvwxyzAbcdefghijKlmnopQrstuvwxyzabcdEfghijklmnopqrstUvwxyzabcdefGhijklmnopqrstuvwxyzAbcdefghijKlmnopqrstuvwxyzabCdEfghijklmnOpQrstuvWxyz

を標準出力してください。

「デスコロC #2」問題のトーナメント結果発表です!~優勝者は…!

アルファベット a~z の26文字が50回繰り返されていますが、所々大文字になっています。まずは、その大文字になる法則を見つけることが定石です。ところが、どうしても私には最後まで法則が見つけられませんでした。終了後公開された解説記事を読むと「素数かつ3なし番目を大文字化」だったらしいです。一応、素数は調べましたが、アホになる数字を除くことまでは残念ながら思いつきませんでした。道理で1箇所だけ間が119も飛んでいるわけだ。300番台の素数が全て除かれていたからってことね・・・。

でも、法則はわからなくても諦めません。テーブルを持たせて大文字に変えることにしました。大文字に挟まれた小文字の数でテーブルを作ります。それが、1~119まであったので、キャラクターコードの127からその数字を引いた文字を並べた文字列テーブルを作ることにしました。ちなみに、119は8になるので '\b' となり、そこだけ2文字になってしまいますが、1つだけなのでよしとします。ただし、テーブルは前から使うか後ろから使うかを変えることでコード短縮に繋がる可能性もあるので、とりあえず、両方の文字列を作りました。

正方向
~}~|z~vtzt~z|xvx|z~nj~zvt~vz~tp~tvzt~z|\bxv~dx|ztx|xvtlzvt~zvt~zv~jzt~prvxvxhz|xnvt~vz~d~n|zl|xvtzl|zrztv~d~vxn|ztxtjlvzrptlvn~v~z|
逆方向
|z~v~nvltprzvljtxtz|nxv~d~vtzrz|lztvx|lz|n~d~zv~tvnx|zhxvxvrp~tzj~vz~tvz~tvzltvx|xtz|xd~vx\b|z~tzvt~pt~zv~tvz~jn~z|xvx|z~tztv~z|~}~

続きを読む "「デスコロC #2」の高度じゃないコード"

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

« 2016年2月 | トップページ | 2016年4月 »