ange1のブログスマートフォン用の表示で見るange1のブログこの広告は、90日以上更新していないブログに表示しています。CodeIQCodeIQの出題者だった@riverplusさんの「数学プログラミング・チャレンジ」に挑戦しましたので、ネタバレです。riverplus.hatenablog.com問題と解説これまでのCodeIQのプログラミング問題サービス終了に伴い、未出題のネタ5問が一挙に出題されました。以下、1問ずつ見ていきます。左下の点から右上のゴールまで最短距離で向かう。この時、取り得る経路を等しい確率で選ぶ場合の、道中にあるメダルの個数の期待値を$F(w,h,m)$とする。$F(10,10,3)$の値を、小数点以下が7桁になるように四捨五入して求めよ。0.9090909解説これは素直に数式一発です。$$適度に階乗に直して総和を求めれば答えが出ます。計算するRubyコードは次のようになります。nに対し、その総和が平方数となる、連続する幾つか(1つ以上)の奇数の組み合わせで、その最大値がn以下のものの組数を$F(n)$とする。$F(10^7)$の値を求めよ。27368012解説1から連続する奇数の和というのが平方数になるのは良く知られていることかと思います。いうことは、連続する幾つかの奇数の和は、平方数の差になることが分かります。満たす整数$(a,b,c)$の組の数を求めよという問題に還元することができます。組み合わせを数えることにしました。足し合わせればそれで計算できます。なるケースだけは別にカウントしておきます。Rubyでの実装は次のようになります。kに対し、数列$F_k(n)$を次のように定義する。大きくなるとその手は使えません。$$と整理すれば、バイナリ法は使えないものの、項数を大幅に減らして計算できます。大きさに合わせて2種類の計算をハイブリッドしたRubyでの実装です。10^6)$の値を求めよ。素因数分解して、各素因数の積を計算すれば良いわけですが、都度素因数分解していたらどれだけ時間がかかるか分かりません。)そこで、素因数が現れる周期を管理することにします。5周期で現れていくわけです。タイマーとしてセットしておくような感覚で管理するわけです。queueが使えます。新しい素因数が現れたら、新しい周期を更に管理に組み込んでいく感じです。いうことで、C++の実装は次のようになります。使うためにしかC++使ってない気もしますがキニシナイ。次の条件を満たす自然数を10/16数と定義する。その数の10進表記をそのまま16進表記と見做した数が、元の数の整数倍である100番目に小さな10/16数を求めよ。各桁の満たす条件を探る方針では巧く行く気がしなかったので、それなりに効率よく探索できるように、という観点で攻めました。対象とした場合を考えてみます。した場合で見積もることができます。する時が倍率は最小です。いうことが分かります。...ということを、上位の桁から次々見て行けば、ダメな候補をある程度早い段階で捨てることができるはずです。実際にRubyで実装したのが次のコードになります。最終的な答えは12桁ですが、1秒もかかっていないので、まあなんとかなっているようです。少々手抜き感が否めませんがご容赦を。最初は問4から入って、最後問5で締めたのですが、この2問が方針決定的にもコード的にも苦しみました。これで本当に終わりかと思うと寂しいところではありますが...。最後まで面白い問題を有難うございました。)月別アーカイブはてなブログをはじめよう!ange1さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。