CodeIQ「ルート・パワー」問題 みんなのコード

0
Kawazoe @riverplus

現在CodeIQで出題中の「ルート・パワー」問題、明日で公開終了です。今回はだいぶハードだった…! 今回もお願いです。期間終了後にみなさまのコードを公開してくださいませ! codeiq.jp/q/1563

2015-12-23 21:34:55
あんちもん2 @antimon2

@riverplus 提出解(コメント含め提出時のまま) ideone.com/d4R8Xq ちなみに新しいMac快適です♪ 「ルート・パワー」問題 codeiq.jp/q/1563 @codeiqさんから

2015-12-24 10:14:52
angel (as ㌵㌤の猫) @angel_p_57

@antimon2 @riverplus @codeiq やってること同じっぽい…。今回珍しくC++に挑戦してみました ideone.com/stvUKf 。コメントないんですが、…関数 f の見たまんまなので、という。

2015-12-24 11:33:23
nekoTheShadow@カフェイン中毒 @neko_the_shadow

@riverplus 「『ルート・パワー』問題」の提出コードを公開しました。今回は気合と根性で解きました。よろしくお願いします。 qiita.com/neko_the_shado…

2015-12-24 11:34:55
angel (as ㌵㌤の猫) @angel_p_57

@antimon2 @riverplus @codeiq なお、昨日CodeIQ忘年会で @g_m_k さんに「ゴルフしないんですか?」と聞かれてたのですが、行列計算以上の攻め口が見つからなくて断念してました。mod 10e9での固有値 ( 出せ ) なかったり…。

2015-12-24 11:36:15
angel (as ㌵㌤の猫) @angel_p_57

@antimon2 @riverplus @codeiq @g_m_k 訂正、10e9 じゃなくて 1e7 ですね。固有方程式だしてみたら、確かすでに mod 5 での解がなかったと思います。

2015-12-24 11:42:15
putStr @putStr

@riverplus 「ルート・パワー」問題提出分 (ideone.com/TXMVPe)。 今回は短く書けなかった…。

2015-12-24 12:41:18
masaki goto @g_m_k

@riverplus 1ツイート解を狙ったもののRuby(180)で諦めです…。golf的工夫ポイントは①他の方が行列で書かれているところをlcmやgcdで再現、②入力上限が示されているのでループ回数を決め打ち、あたりでしょうか。 ideone.com/PZleKn

2015-12-24 12:51:28
ザード@ @world_fantasia

@riverplus こんばんは。ルートパワー問題、方針は20分で思いついたんですが計算時間が全然足りず苦労しました。リンク先は私なりの解き方の記事です。次の問題も楽しみにしています bit.ly/1PmuO9c

2015-12-24 21:59:26
Kawazoe @riverplus

@world_fantasia 解説記事ありがとうございました!想定した方針は、書いておられる内容とほぼ同じです。行列のべき乗は実装むずいですよね。整数をべき乗するのと原理的には変わらないのですが。(整数のべき乗は、以前Lala*先生の問題で出た気がします。)

2015-12-25 00:41:26
Kawazoe @riverplus

CodeIQ「ルート・パワー」問題、コードを公開して下さった方ありがとうございました。これまでのをまとめました。togetter.com/li/911507 行列のべき乗に帰着させるやり方一択かなと思います。同類の問題をやった経験がないとかなりキツイですよねこれ

2015-12-25 00:17:40
Kawazoe @riverplus

やっぱり (1+√2+√3)^n の有理数の項を求める問題にした方がとっつきやすかったかもしれません。手計算けっこうハードだし。しかしこの問題でもゴルフを試みる諸兄は流石です。

2015-12-25 00:24:05
Kawazoe @riverplus

あと行列のべき乗の実装って、言語により得手不得手があったりするのかしら。クラスが定義できる言語ならそれなりにすっきり書けるのですが。

2015-12-25 00:25:51
angel (as ㌵㌤の猫) @angel_p_57

@riverplus 結城さんの数学ガール ( ガロア理論 ) に、「√2等を添加した体」の話が出てくるので、読んでいればモロですね。

2015-12-25 00:25:18
しえる@codefes2016::002 @cielavenir

実はビット積と排他的ビット和を使った私は少数派…? github.com/cielavenir/cod… @riverplus 「ルート・パワー」問題 codeiq.jp/q/1563 @codeiqさんから

2015-12-25 00:56:17
idiotton @idiotton

フィボナッチ数列を行列で求める方法を知っていれば、比較的容易だと思うけど、そうでもないのかな。自分的には、このひとつ前の直角三角形の外接円を内接円とする相似三角形の方が、ずっと難しかった印象が。

2015-12-25 00:36:28
angel (as ㌵㌤の猫) @angel_p_57

@idiotton 行列に慣れているかどうか、ってのはありそうです。高校レベルと大学レベルとの一つの壁ですし。

2015-12-25 00:39:02
Kawazoe @riverplus

@idiotton この手のに慣れてる人には、なんだ定番か、ですよねえ。初見では結構きついんじゃないかなーっておもいました。難易度づけは毎度むずいす。

2015-12-25 00:49:32
idiotton @idiotton

@angel_p_57 確かに行列は知ってても、漸化式を行列で計算するのを初めて知った時は、「え?」って感じではありましたけどね。

2015-12-25 00:49:41
angel (as ㌵㌤の猫) @angel_p_57

@idiotton 本当は高校でやっても良かったと思うんですけどね。高校の教科書だと数列の漸化式と行列との関連を徹底的に無視しますから…。

2015-12-25 00:53:17
idiotton @idiotton

@riverplus と言うか、正統的に数学やってる人は、三角形の問題のような式が出て来ても、普通に解けるんですよね。自分、適当に我流で遊んでるだけだから、式がめんどくさくなると、うわぁって感じで難しく。

2015-12-25 00:53:26
Kawazoe @riverplus

@idiotton 幅広い分野から出題するのが面白そうですね。確率の問題とかもいずれ…

2015-12-25 01:20:09