アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 - Qiita
こんにちは、大学 1 年生になったばかりの E869120 です。 私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどに出場しています。ちなみに、2021 年 4 月 7 日現在、AtCoder では赤（レッドコーダー）です。 本記事では、アルゴリズムの学習や競技プログラミングで使える数学的な部分を総整理し、それらについて解説したいと思います。前編・中編では数学的知識、後編（2021/4/26 公開予定）では数学的考察の側面から書いていきます。 【シリーズ】 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 ← 本記事 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 アルゴリズム・AtCoder のための数学【後編：数学的考察編】 1. はじめに 21 世紀も中盤に入り、情報化社会（いわゆる「IT 化」）が急激に進行していく中、
HackerRankのアルゴリズム厳選20問でコーディング面接を対策する【Pythonコード付き】 - honawork
HackerRankのCracking the Coding Interview https://www.hackerrank.com/domains/tutorials/cracking-the-coding-interviewwww.hackerrank.com HackerRankという、世界中のハッカー（＝ソフトウェアエンジニア・機械学習エンジニアなど）が、プログラミング課題を解決するサイトがあります。 そこに「Cracking the Coding Interview」といういかにもコーディング面接対策といった風情のチュートリアルがあるのですが、初心者がプログラミングのためのアルゴリズムを学ぶのに素晴らしい教材だと感じたので紹介します💁♂️ HackerRankのCracking the Coding Interview Cracking the Coding Intervi
【連載記事】JavaScriptでプログラミングを学ぶ その5：データ構造とアルゴリズム
プログラミングにおいて、値（データ）の扱いはとても重要です。今度は、値をどう管理すべきか、値をどう処理すべきかについて学んでみましょう。 連載目次 基礎と文法 関数 配列とオブジェクト オブジェクト指向 データ構造とアルゴリズム（この記事） HTMLとDOM（予定） 未定 今回学ぶ内容 プログラミングというのものは、極端なことを言うと、値の操作の集まりです。なので、値をどう上手に扱うか、という一点が重要になってきます。値の扱いが上手ければ、処理が高速に終わるかもしれません。また、少ないメモリ消費で動くかもしれません。 今回はそういった「処理効率」に焦点を当てていきます。そして高い処理効率を実現するには、データ構造とアルゴリズムの知識は必要不可欠です。 値を保持するデータ構造は様々存在します。データ構造が違うと何が違うのか、それぞれどんなメリットがあるのか、どんなデメリットがあるのか、いくつ
みんなのデータ構造 - ohbarye
C++のstd::copyのような、resize時に各要素を新しい配列にfor loopでcopyするのではなく、高速にコピー可能な機械語の命令に変換される機能を使うことで高速化される
本当は遅い「似非エラトステネスの篩」の罠
この記事は？ インターネット上でエラトステネスの篩の実装を検索すると、かなりの割合で、エラトステネスの篩とよんでいいのか怪しい「似非エラトステネスの篩」とでも称すべきものがみられます。 この記事では、「試し割り」「似非エラトステネスの篩」「エラトステネスの篩」の3つのアルゴリズムを比較して、その違いを解説します。 3つのアルゴリズムの比較 1. 試し割り 実装 まず他のアルゴリズムに対する評価基準として、試し割りのアルゴリズムを示します。 試し割りは、nが素数であるかを判定するために\sqrt{n}以下の全ての素数で割って確認するアルゴリズムです。 import sys # limit 以下の全ての素数を返す def list_primes(limit): primes = [] for i in range(2, limit + 1): is_prime = True for p in
N番目の素数を求める - すぎゃーんメモ
SNSなどで話題になっていたので調べてみたら勉強になったのでメモ。 環境 Pythonでの実装例 例1 例2 例3 エラトステネスの篩 Rustでの実装例 試し割り法 エラトステネスの篩 アトキンの篩 おまけ: GMP Benchmark 高速化のテクニック 上限個数を見積もる Wheel factorization オチ Repository References 環境 手元のMacBook Pro 13-inchの開発機で実験した。 2.8 GHz Intel Core i7 16 GB 2133 MHz LPDDR3 Pythonでの実装例 例1 最も単純に「2以上p未満のすべての数で割ってみて余りが0にならなかったら素数」とする、brute force 的なアプローチ。 import cProfile import io import pstats import sys def m
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
さるでもわかるアルゴリズム — DEV Community Profile
Four Year Club This badge celebrates the longevity of those who have been a registered member of the DEV Community for at least four years. Got it Writing Debut Awarded for writing and sharing your first DEV post! Continue sharing your work to earn the 4 Week Writing Streak Badge. Got it Three Year Club This badge celebrates the longevity of those who have been a registered member of the DEV Commu
JavaScriptによる小数計算の誤差を無くす
ファッ！？ 0.1kg痩せたはずが、0kgと表示されてしまいました。 たかだか100gとはいえ、こんな表示になったらガックリきますね。 一行ずつ値を追っていくとわかるのですが、4行目で減算した時点でdiffの値が "0.09999999999999432" とズレてしまっています。 これはJavaScriptがIEEE 754という規格に従って実装されているためです。 つまり、この計算結果はJavaScriptの仕様なのでJavaScript的には正しい値であり、避けようがありません。 このIEEE 754と小数計算の誤差についての関係は下記のURLの解説が分かりやすくオススメです。 http://pc.nikkeibp.co.jp/pc21/special/gosa/eg4.shtml これの対処法として、小数値に10^Nの数値をかけて整数値にしてから計算してしまおう！ といった対処法を
数学的知識
となりますね。 ■ 逆元 かけ算をするときは 3 にをかけると 1 となります。このようにある数字に対してかけ算すると 1 になるような数字のことを逆元といいます（かけ算の場合は逆数という呼び方が一般的です）。13 を法としたとき，5 の逆元を求めてみましょう。 となることより，5 の逆元は 8 となります。ユークリッドの互除法という計算を行うことで逆元は容易に計算が可能です。 ■ 繰り返し二乗法 繰り返し二乗法は のような計算を効率的に計算する計算法です。そのままかけ算すると 9 回のかけ算をしなくてはなりませんが，次のようにするとかけ算の回数を減らすことが出来ます。
AtCoder ABC 129 C - Typical Stairs (茶色, 300 点) - けんちょんの競プロ精進記録
いわゆる本当に最初の入門という感じの DP だね。 問題へのリンク 問題概要 段の階段があって、現在は 0 段目にいる。 高橋君は一歩で 1 段か 2 段上がることができる。ただし 段目は壊れていて、そこに足を踏み入れることはできない。 高橋君が 0 段目から 段目までたどり着くまでの移動方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 壊れているところがなかったら もしかしたら高校時代に似たような問題を解いたことのある方も多いかもしれない。すなわち「どこも壊れていないバージョン」なら解いたことある方も多いかもしれない。 下図のように 0 段目は「なにもしない」という 1 通り 1 段目は「0 段目から 1 段のぼり」という 1 通り 2 段目は、その直前がどうだったかが以下の 2 つの場合があって、それらを合計して 2 通り 直前が 0 段目：1 通り 直前が 1
[AtCoder] ABC023 D – 射撃王 | アルゴリズムロジック
問題概要 問題へのリンク 風船に 1 から N までの番号が付けられていて、風船 i (1≦i≦N) は競技開始時に高度 \(H_i\) のところにあり、1 秒経過するにつれて高度が \(S_i\) だけ増加する。 はじめ1つ風船を割り、その後は一秒ごとに一つ風船を割ることができる。 割られた時の風船の高度について最大値を得点とする。得点がもっとも小さくなるような割り方を考えるとき、このときの得点を答えよ。 制約 \(1 \leq N \leq 10^5\)\(1 \leq H_i \leq 10^9\)\(1 \leq S_i \leq 10^9\) 考え方 N が \(10^5\) までなので、風船を割る順番を決めたりして全探索するのは間に合いません。 また、貪欲的に1秒ごとにどの風船を割るのかを決めるのも難しそうです。その時の最大の高度となる風船を割ることにしても、その風船を見つける
アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～ - Qiita
今の場合は A さんが 31 歳の場合のストーリーでしたが、A さんが 20 歳～ 35 歳のうちのどの年齢であったとしても、似たようなストーリーで必ず 4 回の質問で当てることができます！(他の例も是非考えてみてください。) ちなみに、このような「真ん中で切ってどちらかに絞って行く」タイプのアルゴリズムには二分探索法という名前がついています。応用情報技術者試験でも頻出のテーマですので馴染みのある方も多いと思います。 1-2. つまり、アルゴリズムとは 上の年齢当てゲームという問題では、相手の年齢を当てる「方法・手順」を二分探索法に基づいて導きました。このようにアルゴリズムとは、 問題を解くための方法・手順 のことです。さて、アルゴリズムと聞くと「コンピュータ上で実装されたプログラム」のことを思い浮かべる方も多いと思いますが、必ずしもコンピュータと関係がある必要はなく、日常生活でも多々登場
グラフ理論の基礎 - Qiita
グラフ理論の基礎 - Basics of Graph Theory - ねらい グラフ理論の基礎を学ぶ グラフ (graph)、頂点 (vertex, node) 、辺 (edge) 連結リスト (linked list)、次数 (degree) 深さ優先探索 (depth-first search) 、幅優先探索 (width-first search) 連結成分 (connected components, connected subgraph, cluster) 、シングルトン (singleton) 切断点 (cut vertices) 、切断辺 (cut edges) 経路 (path) 、閉路 (cycle) 最小木 (minimum spanning tree)、最短経路 (shortest path) 巡回セールスマン問題 (traveling salesman probl
JavaScript/TypeScriptで競技プログラミングをするには 後編 | わたしろぐ
JavaScript/TypeScriptで競技プログラミングをするには 後編 2018-02-09 19:30:00 Category: dev Tag: competitive-programming javascript 主要コンテストサイトのJavaScript対応状況、および私がJavaScript/TypeScriptで競技プログラミングをする時に気をつけていることなどを書きます。 今回は後者についてです。 前回の記事ではコンテストサイトのJavaScript対応状況をメインに書きました。 この記事では、実際にJavaScript/TypeScriptで競技プログラミングをする際に気をつけている点について書いていきます。 競技プログラミングにおけるJavaScriptの致命的な問題点 残念ながら、JavaScriptが競技プログラミングに向いていない理由となる仕様がいくつか存在
素数にまつわる覚えておくべき性質まとめ | 高校数学の美しい物語
・ ppp が素数，m,nm, nm,n が整数で，mn=pmn=pmn=p なら mmm か nnn のどちらかの絶対値が 111 。これは素数の定義から当たり前の事実ですが不定方程式を解くときなどに使う基本的な性質です。 ・素数 ppp と任意の自然数 aaa に対して ap≡a(modp)a^p\equiv a\pmod{p}ap≡a(modp) →フェルマーの小定理の証明と例題 ・その他，受験で役立つ機会は少ないですがマニアックな定理として，ウィルソンの定理やアイゼンシュタインの定理など。 →ウィルソンの定理とその2通りの証明 →アイゼンシュタインの定理 ・ ab≡ac(modp)ab\equiv ac\pmod{p}ab≡ac(modp) で aaa と ppp が互いに素なら b≡c(modp)b\equiv c\pmod{p}b≡c(modp) →合同式の意味とよく使う6つの
Python (SymPy) で方程式・連立方程式を解く、数列を求める - pianofisica
今回はプログラミング言語Pythonを使って方程式・連立方程式を解いてみたいと思います。数式処理ライブラリSymPyを使って代数的に厳密に解く方法をみていきます。また、漸化式から定まる数列について、その各項を求める方法もみていきます。 SymPyのごく基本的な使い方については以下の記事を参照してください： pianofisica.hatenablog.com 代数方程式 １次方程式 ２次方程式 ３次方程式 ４次方程式 ５次方程式 方程式の数値解 連立１次方程式 ２変数の場合 ３変数の場合 連立方程式 微分方程式 漸化式 代数方程式 多項式（変数と定数について有限回の和と積をとったもの）同士を等号で結んだ方程式を代数方程式といいます。代数方程式の解として表される数を代数的数といいます。したがって整数、有理数、そして などの無理数は代数的数です。 代数的数でない数は超越数と呼ばれます。同様に、
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Introduction to Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare
Microsoft PowerPoint - 05_2011_0519_A.pptx
アルゴリズムビジュアル大事典