きり@kiri8128 さん出題の問題 https://twitter.com/kiri8128/status/1297582612668538882午前零時がどの日に属しているかは曖昧なので、スイッチをオン/オフにした日の夜に、それに応じた照明の点灯が行われると考えることにする。 0° 基本的なアイデア 囚…
@riverplus さん出題の問題。 問題: http://riverplus.hatenablog.com/entry/2018/02/25/143351 解説: http://riverplus.hatenablog.com/entry/2018/03/19/220532下から k 番目 (0≦k＜h) のメダルを 、C(n,k) を2項係数として、 スタートから の下の点までの…
@Nabetani さんの問題 http://nabetani.sakura.ne.jp/hena/orde22numord/ を解いてみた。 m 以上 n 以下の自然数を b 進表記して辞書順に並べたとき、x 番目の数を求めよという問題。 他の方の実装が http://qiita.com/Nabetani/items/99e38a39165e1905b415 …
Ruby だと1行のメソッドで書ける気がしたので書いてみた。 効率は悪いけど、大体数秒から数分で解ける。 問題は1行の文字列で与える。'0' が空白。 解答は可能な解を配列に並べたもの(解が複数あるときは全部求める)。例題は Dr. Arto Inkala 作の世界一難し…
線形の漸化式(整数係数で最高次の係数は 1 とする)に従う数列が与えられたとき、もとの漸化式の特性方程式を見つける方法があるというのを某所で知った。 例えば、フィボナッチ数列の何項か(例えば 1, 2, 3, 5, 8)が与えられたとき、特性方程式 を求めるとか…
CodeIQ の @riverplus さん出題の問題。 の有理数の項を求めよというもの。 他の方のコードが http://togetter.com/li/911507 にある。 とすると、求める数 F(n) は を解に持つ方程式 を頑張って展開すると になるから、F(n) は差分方程式 を満たす。 なので…
最近 Project Euler の問題を解いているのだけど、使い回せるコードを探すのが大変になってきたのでここにまとめておくことにする。 前に他のプログラム中で使ったものだが、とりあえず Miller-Rabin 素数判定と Pollard のρ法(またはモンテカルロ法)による…
CodeIQ の Kawazoe さん出題の問題。 問題と他の方の解答が http://togetter.com/li/875421 にある。とりあえず項数 1 の数列を許すとして考える。項数が奇数のとき、m を項数とすると、(m によって定まる)初項 a(m) は 数列が整数列であるための必要十分条…
CodeIQ の Kawazoe さん出題の問題。 問題と他の方のコードが http://togetter.com/li/866620 にある。 をそれぞれ 0〜9 の数字の出現回数とする。 の10個の数を昇順に並べ替えたものを とする。 例えば n=4 のとき の組は次のいずれかになる。 0, 0, 0, 0, …
CodeIQ の Kawazoe さん出題の問題。 問題と他の方のコードが CodeIQ「カット・アンド・スクエア」問題 みんなのコード にまとまっている。 とする。 求める n 桁の整数の上下 n/2 桁をそれぞれ x, y とすると が成り立つ。 変形して として つまり を2平方…
CodeIQ の Kawazoe さん出題の問題。 他の方のコードが CodeIQ「フィズ・バズ・エクストリーム」問題 みんなのコード にまとまっている。 を互いに素な2以上の整数とし、f(n,k) を n 以下の正整数のうち のいずれかの倍数となるものの和とする。このとき と…
点集合の最小抱合円(点集合を周を含む内部に持つ最小の円)を O(N) の時間で求める Welzl のアルゴリズムというのがある。 論文が http://www.inf.ethz.ch/personal/emo/PublFiles/SmallEnclDisk_LNCS555_91.pdf で読める。 論文通りに実装すると、点の数が多…
前に書いたトリボナッチ数と同じようなやり方でフィボナッチ数を計算する方法。 自分が調べた範囲では、フィボナッチ数を計算する一番速いアルゴリズムだと思う。フィボナッチ数 とリュカ数 を で定義する。リュカ数を次の漸化式から計算して 、 フィボナッ…
CodeIQ の鍋谷武典さん出題の問題。 問題と解説はこちら。 CodeIQ に出した「中学入試から：対称軸の本数を数えよう」の 解説・解題下が解答に添えた説明。 円周が n 等分されているとして、図形を F とする。F を構成する線は2本以上とする。 円の中心と n …
CodeIQ の鍋谷武典さん出題の問題。 問題と解説はこちら。 CodeIQ に出した「中学入試から：概数と計算」の 解説解題下が提出したコード。言語は Ruby。浮動小数点で計算するとまずそうなので、有理数で計算するようにした。 コメントで '下限' を次の意味で…
CodeIQ のマシューさんの出題で、129桁の整数 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541 を素因数分解する問題が出た。 まともに計算すると、高速な素因数分解…
遠い世界の数式 http://nabetani.sakura.ne.jp/kanagawa.rb/evalex/ 解いてみた。まず最初に考えたもの。結構強引。 問題は最後の5問だけ。 class Fixnum def -(x) self | x end def ^(x) self + x end def >(x) self * x end end DATA.each do |expr| p eva…
CodeIQ の鍋谷武典さん出題の問題。 問題と解説はこちら。 「中学入試から：図形と場合の数」の 解説・解題下が提出したコード。言語は Ruby。 問題データをつけてすぐに実行できるものを http://ideone.com/cvjXrT に置いておいた。今回力尽くな方法しか思…
某所に を計算しろという問題があったので、前に書いた円周率のプログラムをいじって書いてみた。 として √ のところをテーラー展開して これで10進2桁ずつ求めていくというやり方。 速くはないけど、プログラムは簡単に書ける。平方根をこの方法で計算する…
CodeIQ の鍋谷武典さん出題の問題。 問題と解説はこちら。 「中学入試から：数字の個数」の 解説・解題プログラムは x 未満(x 自身を含まないのが自分でも混乱するけど、x 以下とやるより綺麗になるので)の数字を数える関数 count を作って、不定積分から定…
ちょうど1年前 Ruby を覚えたての頃書いたコードを発見した。 Ruby をインストールした直後で、何か書いてみたくてネットで例題を探していた記憶がある。問題はこれ。 http://okajima.air-nifty.com/b/2011/01/2011-ffac.html ゲーム「ぷよぷよ」で、フィー…
CodeIQ の鍋谷武典さん出題の問題を解いてみた。 問題と解説はこちら。 「中学入試から：正三角形？二等辺？」の、解説・解題解説を読んでから気づいたんだけど、ちょっと今回は力尽くなコードを書いてしまった。 言語は Ruby。 v.values - [nil] のところは…
CodeIQ の masuipeo さん出題の問題に解答してみた。 提出時は結構速いコードが書けたと思っていたのだが、 第47回「今週のアルゴリズム：クロスワードを作成して！」優秀解答例 を見たらずっと高速なものが紹介されていたので、自分が書いたものを少しいじ…
CodeIQ の鍋谷武典さん出題の問題「中学入試から：単位のある計算」を解いてみた。 問題と解説は http://nabetani.hatenablog.com/entry/codeiq_unit_q1058 にある。下が提出したコード。言語は Ruby。 不正な入力にはほとんど対処していないが、次元が揃っ…
CodeIQの七夕問題で提出したコードを貼っておく。問題と解説はこちら。 給料UPを目指す彦星の解答は？「七夕問題☆牽牛 彦星 牛をもっと飼う」解説 #CodeIQ言語は C。 64ビットの整数型 long long int と立方根 cbrt() が使える処理系が必要。 実行時間は Ide…
CodeIQ で出題された問題に解答してみた。 問題は 「長くなるように、増え続けるように」の 解説・解題 で読める。数列の列 b を以下のように構成する。 b_1 は s の最初の数字1項だけの列。 b_i (i≧2) は次のようにして決める。 「s の最初の i 文字を区切…
(修正完了。添え字をずらして標準的な定義に合わせた) で定義されるトリボナッチ数(Tribonacci Number)というものがある。 これを効率よく計算する方法を某所で訊いている方がいたので、ちょっと考えてみた。 以下は自分で考えたものなので、もっといい方法…
CodeIQ で覆面算の問題が出題されたときに書いたもの。 という形限定。 permutation で数字の順列を生成して、数字を割り当てた式を eval で評価すれば短く書けるが、それだと結構遅いから、下から一桁ずつ調べるようにした。言語は Ruby。 最後の行の 'SEND…
前回、テトロミノビンゴの問題を解いたが、今回は テトロミノ＋ビンゴ！ の未解決問題 を解いてみた。 一見膨大な計算のように見えるが、まず、カードに書かれていない数字の出方はどうでもいいので、99!通りではなくて、25!通りの計算で十分なのは明らか。 …
テトロミノビンゴ CodeIQ に出した「テトロミノ＋ビンゴ！」の解説・解題 にあった問題を解いてみた。 言語は Ruby。 リンク先にある data.txt が入力データとして必要。 手元の環境での実行時間は1.1秒程度。Ideone.com 程度の処理速度なら1秒未満のはず。…
