GitHub - recuraki/cphb-ja: (JA)Competitive Programmer's HandbookYou signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
素人によるワーシャルフロイド法 - Qiita
最短経路問題で使われるアルゴリズムの１つ。負の閉路がない限り、負の辺があっても使える。グラフ上の全ての頂点間の最短経路を探すので、計算量は$O(V^3)$となる。 ワーシャルフロイド法はその名前から難しそうな印象があって避けていた。しかし、最近競プロの精進中に実装する機会がチラホラあり、実装してみると思ったよりも簡単だったのでびっくりした。ワーシャルフロイド法が必要となった方は簡単な実装なので恐れず調べてみてほしい。 今回すること ワーシャルフロイド法は実装が簡単だが、その裏でどんな振る舞いをしているのかイマイチ掴めなかった。簡単に最短経路を求められるといっても、裏の仕組みを知らずに使うのは自分としてはどうも気持ちが悪い。今回はいろいろ手を動かしてみながら、仕組みの理解を試みる。 C++によるコード まずはワーシャルフロイド法のコードを見てみる。 void warshall_floyd(i
問題解決のための「アルゴリズム × 数学」- Forkwell Library #1
📝 イベントレポートも発信しています 📝 コチラから：https://pr.forkwell.com/events/forkwell-library-01/ ⏳ プログラム 0:00 待ち時間 4:59 オープニング 9:08 基調講演「30 分でわかる！アルゴリズムの基本」『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』著者 米田 優峻 氏 45:12『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』プレゼント企画のご案内 52:41 視聴者Q&Aパネルトーク「アプリケーション開発で活かせること」shisamaさん × 米田 優峻さん 🐦 気づき・感想をシェアしてね 参加者全員で、この勉強会からの気づきを最大化しましょう！ 以下の Twitter ハッシュタグでツイートをお願いします。 #Forkwell_Library URL：htt
「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
1. なぜ 998244353 で割るのか？ 最初はこのような設問を見るとぎょっとしてしまいますが、実はとても自然な問題設定です。 $998244353$ で割らないと、答えの桁数がとてつもなく大きくなってしまうことがあります。このとき以下のような問題が生じます: 多倍長整数がサポートされている言語とされていない言語とで有利不利が生じる 10000 桁にも及ぶような巨大な整数を扱うとなると計算時間が膨大にかかってしまう 1 番目の事情はプログラミングコンテストに特有のものと思えなくもないですが、2 番目の事情は切実です。整数の足し算や掛け算などを実施するとき、桁数があまりにも大きくなると桁数に応じた計算時間がかかってしまいます。実用的にもそのような巨大な整数を扱うときは、いくつかの素数で割ったあまりを計算しておいて、最後に中国剰余定理を適用して復元することも多いです。 なぜ 9982443
アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 - Qiita
こんにちは、大学 1 年生になったばかりの E869120 です。 私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどに出場しています。ちなみに、2021 年 4 月 7 日現在、AtCoder では赤（レッドコーダー）です。 本記事では、アルゴリズムの学習や競技プログラミングで使える数学的な部分を総整理し、それらについて解説したいと思います。前編・中編では数学的知識、後編（2021/4/26 公開予定）では数学的考察の側面から書いていきます。 【シリーズ】 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 ← 本記事 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 アルゴリズム・AtCoder のための数学【後編：数学的考察編】 1. はじめに 21 世紀も中盤に入り、情報化社会（いわゆる「IT 化」）が急激に進行していく中、
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 - Qiita
このように、競技プログラミングはコーディングの正確性が問われるコンテストです。 どんな問題が出されるか（２） 競プロは正確性だけではありません。例えば、以下の問題を考えてみてください。 $N$ 枚のカードが一列に並べられています。 左から $i$ 番目のカードには、整数 $A_i$ が書かれています。 あなたは $N$ 枚のカードの中から $2$ 枚同時に選び、取ることができます。取った $2$ 枚に書かれた整数の合計がちょうど $101$ となるような、カードの選び方の通り数を求めてください。 テストデータの制約：$1 \leq N \leq 10^{6}, 1 \leq A_i \leq 10^{9}$ 一番最初に考えられる解法は、以下のように「何枚目と何枚目を選ぶか全探索する」という方法だと思います。つまり、$1 \leq i < j \leq N$ を満たすすべての $(i, j)
アルゴリズムロジック
問題へのリンク 問題概要座標 \((0,0)\) からスタートして \(N\) 回の移動で \((X,Y)\) に到達する確率を求めたい。 1回の移動では、上下左右それぞれの方向に確率 \(\frac{1}{4}\ ...
ABC217 D - Cutting Woods - かんプリンの学習記録
問題はこちら 問題概要 解説 Pythonでの解法 感想 問題概要長さの木材がある．以下の個のクエリを処理せよ．番目のクエリはで与えられる． のとき：木材の左端からの地点で木材を切る． のとき：木材の左端からの地点を含む木材の長さを出力する． 解説現在の木材の区間を管理します．を初期状態とし，の木材をの地点で切ると，との木材になります． C++のstd::setでおよび切れ目を管理することで，の地点を含む木材の値が両端が取得できます． 具体的にはそれぞれのクエリで以下の操作を行います． クエリ1：をsetに入れる． クエリ2：setの以上の最小の要素と以下の最大の要素を取得し，を出力する． Pythonでの解法C++にはstd::setというデータ構造があり，クエリ1がinsert，クエリ2がlower_boundで実現できるのですが，PythonにはSTLにsetのようなものがない(Py
Ruby Junk Scripts
トライ トライは文字列の集合を表すのに都合のよいデータ構造です。トライの語源は、「検索 (retrieval) 」という言葉の真ん中 (trie) に由来しています。トライは木構造の一種であり、根から葉までの経路がひとつの単語に対応します。次の図を見てください。 図 : 文字列の集合を表したトライ 上図は文字列の集合をトライで表現したものです。ここでは葉を $ で表しています。たとえば、葉 $7 までたどると、それは "THEN" という文字列を表しています。また、文字列 "THE" をトライから探す場合は、節を順番にたどっていって、葉 $6 に達した時点で "THE" を見つけることができます。もし、節 E の子に葉 $6 がなければ、THE はトライに存在しないことになります。 ●参考文献 A.V. Aho, J.E. Hopcroft, J.D. Ullman, 『データ構造とアルゴ
Rubyでlower_bound - Qiita
def lower_bound(array, value) left = -1; right = array.length; while left + 1 < right mid = left + (right - left) / 2; if array[mid] >= value right = mid else left = mid end end right end
めぐる式lower_bound, upper_bound in Ruby
今日のランチタイム、Rubyにlower_boundとupper_boundがないことに気づいた。 二分探索だとArray#bsearchはあるみたいだけど、これは値を返してしまうから情報量が少ない。C++にあるstd::lower_bound()とstd::upper_bound()が欲しい。 ということで、めぐる式にぶたんの考え方に則ってそれぞれ書いてみた。 lower_bound: 探索したい値以上の値が最初に現れる位置を返す def lower_bound(arr, n) ng = -1 ok = arr.size while (ok - ng).abs > 1 mid = (ok + ng) / 2 if n <= arr[mid] ok = mid else ng = mid end end ok end upper_bound: : 探索したい値より大きい値が最初に現れる位置
アルゴリズムとデータ構造
アルゴリズムとかデータ構造というのは、プログラミングの基礎中の基礎ですね。いまどきは、いろいろな言語において標準ライブラリで提供されていたりしますから、ただ使うだけならこれらを1から自分で書けるようになってもそんなにうれしくはないですが、必要な場面でよりよいアルゴリズムを選択できるように、概要くらいは知っておきたい物です。というわけで、ここではアルゴリズムとデータ構造についての話をしていこうかと思います。 説明やサンプルには、有無を言わせず C# を使います。 うちは C# 入門サイトですから。 ある意味、「C# によるプログラミング入門」のサンプルプログラムの延長みたいなページになってるかも。
優先度付き待ち行列(アルゴリズムとデータ構造)
概要 優先度付き待ち行列（priority queue）とは、 ある優先度（例えば、値の大きな物ほど優先度が高いとか）に従って、 優先度の高いものから順に取り出すことの出来るコレクションです。 挿入順序がどうであれ、優先度の高いものが必ず1番最初に取り出されます。 優先度付き待ち行列 名前に「待ち行列」という言葉が含まれていることから分かるように、 優先度付き待ち行列への値の挿入・取り出しはそれぞれエンキュー・デキューといいます。 「待ち行列」のときと同様に、 「スタック」と呼び名をそろえるために、 プッシュ・ポップという名前で実装する場合もあります。 このようなコレクションを実現するためには、 例えば、ソート済みの配列を使うといった方法も考えられますが、 優先度が1番高い要素1つだけが分かれば十分なのに、 ソートを行うのでは余分な労力を裂いていることになります。 これに対して、 優先度が
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ - Qiita
はじめに --- DP は役に立つ はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 巷ではよく「DP なんて実務では使わない」といった言説が定期的に流れますが、そんなことはないです。僕自身この 2 年間で DP が使える実務案件に 3 件くらい関わりました！ それはともかくとして、DP を学び立ての方がよく抱く悩みとして「バリエーションが多すぎて混乱するし、統一的なフレームワークがほしい」というのがあります。確かに DP のバリエーションは非常に多岐にわたるのですが、そのほとんどが以下の 3 つのフレームワークで説明できると思います: ナップサック DP 区間 DP bit DP 今回はこのうちのナップサック DP について、とにかく
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita
0. はじめに: 非常に素敵な DP の入門コンテンツ 待ちに待ったコンテストの到来です！！！！！ DP (動的計画法) はアルゴリズムの登竜門というべき難所ですが、いくつか問題を解いて行くとパターンのようなものが見えて来ます。まさに「習うより慣れろ」の世界で、たくさん問題を解いて行くうちに、DP な問題の解法を一言で言えるようになって来ます。 典型を学ぶ方法論として、その最も典型的なシンプルな形をした問題をそのまま吸収してしまうのは 1 つの有効な方法だと思います。それにふさわしいシンプルな問題たちを集めた DP コンテストが先日開かれました。DP 以外にもこういうのが欲しい気持ちになりますね。 Educational DP Contest / DP まとめコンテスト 全部で A 問題から Z 問題まで 26 問あります。今回はこれらの問題に対し 簡単なコメントや解説、その他の解説へのリ
資産1億達成したビットコイン投資手法を公開した - これからの「お金」の話をしよう
UKIです。 4月5日にビットコイン投資（投機）で資産1億を達成しました。 達成と同時にその手法をツイッターに投稿しています。 最終資産は1億255万。TLを振り返ると(元祖)ドテン君を初めて動かしたのは3/4、チャレンジの軍資金2000が着金したのが3/8である。ざっくり丸めて考えると、およそ1ヶ月弱で2000→1億(5倍)を達成することができた。多少悔いは残るが、引き際が肝心との判断。 pic.twitter.com/JUihRBzIKR — UKI (@blog_uki) 2018年4月5日 お待ちかねのロジックを公開。 (元祖)ドテン君はブレイクアウトだが通常のHLチャネルブレイクではない。その手法は「オープニングレンジ・ブレイクアウト」と呼ばれるものである。文章での説明は面倒なのでhohetoとの会議資料をそのまま添付する。ストラテジーに関する質問には応対できません。 pic.t
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
30 分でわかる！アルゴリズムの基本
Amazon.co.jp: プログラミングコンテスト攻略のためのアルゴリズムとデータ構造: 渡部有隆 (著), Ozy（協力） (その他), 秋葉拓哉（協力） (その他): Digital Ebook Purchas
Amazon.co.jp: 問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書): 大槻兼資 (著), 秋葉拓哉 (監修): 本
アルゴ式(beta)
