ポラード・ロー素因数分解法 - Wikipedia
ポラード・ロー素因数分解法（英: Pollard's rho algorithm）は、特殊用途の素因数分解アルゴリズム。1975年、ジョン・ポラード（英語: John Pollard）が発明した。合成数を素因数に効率的に分解する。 概念[編集] 一般に素因数分解は、対象の数 n について、その平方根以下の全ての素数について n を割ってみる。しかし、これは n が大きい場合に対象となる全ての素数が明らかでないという問題が生じる。ポラード・ロー素因数分解法は、そのような場合に大きな素因数を確率的に探す乱択アルゴリズムである。 このアルゴリズムはフロイドの循環検出法に基づいており、また2つの数 x と y が p で割り切れるには、ランダムに 個の数を選んだとき半分以上の確率で共に割り切れるという観測結果に基づいている（誕生日のパラドックスを参照）。p が素因数分解したい n の素因数であると
TopCoder SRM464 Div2 - Algorithmer’s note
はじめてTopCoderに参加しました。 250 赤球と青球と赤箱と青箱があって、球を箱に入れる。やるだけ、でも8分ぐらいかかった。表を書いたら一発だった… 焦ってたのかな。 500 文字列の桁数nが与えられたとき、辞書順に並べたときにm番目にくるカラフルな文字列を求める。全探索。 1000 罠があるかもしれない床がある迷路。全通り探索とDFSで余裕。 これを解き終わったら、45分間暇だった。 Challenge 500を２回Challengeされたけど大丈夫だった。 他の人の500のコードで、サンプルケースにしか対応してないコードがあったので即撃墜。TLEしそうなコードもあったので撃墜。 結果 230.12、456.40、862.69。全部System Test通った。撃墜点で+100点。 Rating: not rated -> 1934
SRM 464 - hosの日記です
writerをやっていました。いかがだったでしょうか？ Editorialを執筆中なので詳しい解説は後日そちらを参照してください。また Practice Room にofficialな解答を上げています。 以下に出題した5問について簡単なコメントを。 ColorfulBoxesAndBalls (Div 2 250) 赤箱青ボールと青箱赤ボールが必ず同じ個数なので、それについて [0, min(numRed, numBlue)] でループを回せば十分です。単調性から、端2つを比較するだけでもOKです。 ColorfulStrings (Div 2 500 / Div 1 250) 同じ数字は二度使えない・ n <= 8 にしか解がないので全探索で十分間に合います。効率が良いのはDFSですが、next_permutationでも大丈夫です。偶然生まれた n = 1 というコーナーケースに注意
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
Top-k文書列挙問題 - DO++
いろいろとありまして去年読んだ論文で面白かったものランキングとか書けなかったのが残念ですが、もしあげるとしたら次の論文は入れると思います（知ったのは年明けだったけど）。 "Space-Efficient Framework for Top-k String Retrieval Problems", FOCS 2009, Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter (pdf) 扱っているのは次のような問題です（説明のため本来のと言い換えています） n個の葉からなる木が入力として与えられ，各葉には色（1以上d以下の整数とします）が与えられています． この時、木中の任意の節点と正整数kがクエリとして与えられたときに、その節点の子孫の中で出現回数が大きい色を順にk個答えよという問題です。 簡単に思いつくのは，各節点に適当な個数(d)の答えをあ
PKU Wiki*
POJとは何？ 北京大学(PKU)の運営しているプログラミングの問題のジャッジシステムです。具体的に言うと、問題に対する答えとなるプログラムのソースコードを送信すると、それが正解かどうかを判定するものです。POJを通して、プログラムにおけるアルゴリズムを組む練習ができ、またTopCoder,ICPC,情報オリンピックなどのプログラミングコンテストの対策ともなります。 POJの公式サイトで登録した後は、まずこの下のFAQを読み、1000番を解いてみるといいでしょう。 翻訳された何か FAQ 翻訳された問題 1000～1999 2000～2999 3000～3999 4000～ 翻訳された問題数：143/4021(2012/2/10 現在) 編集ルール ひとつのページにひとつの問題の訳を載せてください。 問題のページ名は、[問題番号をあらわす四桁の番号]+[半角空白]+[問題の名前（原文）]と
実数探索三種類解説 - nodchipの日記
自分がよく使う実数上の探索アルゴリズム「三分探索」「黄金分割探索」「二分探索」のメモです。 三分探索 三分探索は凸関数の極値を求めるために使うアルゴリズムです。このアルゴリズムは関数が微分不可能な場合にも使えます。やり方は探索領域を三分割し、真ん中二本の境界のうちどちらの値が大きいかを調べ、それとは逆の方の境界を新たな探索領域の端にするというものです。一回のイテレーションで関数の計算を2回行い、探索領域が2/3になります。 double search(double left, double right) { for (int loop = 0; loop < maxLoop; ++loop){ if (f((left * 2 + right) / 3) > f((left + right * 2) / 3)){ right = (left + right * 2) / 3; } else
3分探索 - ICPC突破専用ザク
凸関数の極値を求める方法を知りたくなってググってみたところid:nodchipさんのエントリがヒットした． 以下，個人的なまとめ． 実数探索三種類解説 - nodchipの日記 http://d.hatena.ne.jp/nodchip/20090303/1236058357 単調関数の零点を求めるのには2分探索が使われるけど，凸関数の極値を求めるのには3分探索が使われるらしい． 三分探索は凸関数の極値を求めるために使うアルゴリズムです。このアルゴリズムは関数が微分不可能な場合にも使えます。やり方は探索領域を三分割し、真ん中二本の境界のうちどちらの値が大きいかを調べ、それとは逆の方の境界を新たな探索領域の端にするというものです。一回のイテレーションで関数の計算を2回行い、探索領域が2/3になります。 3分探索がうまくいく理由は以下のとおり． f : [a,b]→R : 上に凸な関数とし，区
Ｐｅｔｒ伝説＠ＴｏｐＣｏｄｅｒ - 超だめぽ日記
3完1700点は当たり前、5完3200点も Ｐｅｔｒにとっての１０００通過はＤｉｖ１昇格くらい ＳＲＭ始まる前に撃墜も日常茶飯 一回のサブミットで三問通す パソコンの前に座っただけでサーバーが落ちた。心臓発作を起こす管理者も。 あまりに解き過ぎるからコンパイルエラーしてても一サブミット扱い そのエラーコードもシステムテストを通す 画面を一睨みしただけでコードがコンパイルされる ＳＲＭの無い日でも1位通過 一位をとってもレートが下がる パソコン使わずに携帯で解いていたことも 自分のコードを自分で撃墜してシステムテストもちゃんと通す 1000点10分以内正答なんてザラ、別解を作ることも 座っているだけでレートが上がった 参加者の韓国人の野次に流暢な韓国語で反論しながら500通過 グッとガッツポーズしただけで700点くらいとった あまりに解きすぎるので最初から1位だったことも 全力でコーディング
引退＆これから参加する人へ - てきとーな日記
今回のが２回目の世界大会だったので、もうこれで引退となります 自分は大学に入ってICPCに出会ったのがプログラミングコンテストに参加し始めたきっかけとなったこともあり、数あるコンテストの中でも一番気合を入れていました 今年こそは金メダルを取りたいと思っていましたが、最後の最後でミスをしてまたしてもメダルなしに終わってしまい、期待に応えられずとても申し訳なく思います 非常に悔しいので、敗因を分析して、これから参加する人たちの役に立てればと思います まず、今年の自分たちの戦略について うちのチームは自分ときたまさの二人コーダー体制で、それぞれ得意分野の問題を担当します 解法の分からない問題は、相談しあって考えます 解法が分かった問題は適切なコーダーに割り振ります(１問を解くにあたってもこの部分は任せた、みたいなことをします) コーディングはこまめに交代しながら行い、ちょっとでも考えたくなった瞬
Leftist tree - Wikipedia
In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s-value which is the distance to the nearest leaf in subtree rooted at x.[1] In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the l
YUHA - YUHA
C88でYUHAのブースに来ていただいたみなさま、ありがとうございました。 今回、いつもより多い部数を作って持って行ったのですが、14:00には頒布終了となってしまいました。 午後の遅い時刻に訪れていただいたみなさま、申し訳ありません。 「第1回 アーケード版ぷよぷよ通 人類 vs AI 実装方法とアルゴリズム」は、8月30日に予定している ぷよぷよAI勉強会に少量お持ちしますので、そちらでも ご覧になることができます。 それ以外の予定は、現在のところありません。 誤りの訂正 「第1回 アーケード版ぷよぷよ通 人類 vs AI 実装方法とアルゴリズム」で内容の誤りが見つかっておりますので、 ここで訂正します。 13ページ 「xは位置(4, 2)であり、ビットが立っているのは位置(2, 1), (3, 1), (4, 1), (4, 2)の4つである。」 を、 「xは位置(4, 1)て
SRM 459 - hosの日記です
Room Room 22 普通。 250 -1/2から2001/2まで全部調べる 500 冷静に考えれば1次方程式の自然数解数えるだけのDPなのに計算量が駄目なのを組んで時間ロス 1000 フローじゃね？と思ったがさっぱり Challenge 250で X > 1000 で落とせた System Test 通った 部屋で2つ250が落ちていた Result 242.19 + 413.72 + 0.00 + 50.00 = 705.91 5位 (部屋1位) 2961→3024 ここ最近妙に好調だなあ、とか思っていたらいつの間にか3000超えてしまいました。不思議。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Proudly organised by the Australian Mathematics Trust and The University of Queensland
DMM FX 口座開設キャンペーン ｜ 269g.jp
チームライブラリ - てきとーな日記
http://acikelabo.org/maze-js/
Asia-Pacific Informatics Olympiad
イベント詳細
Home