アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 - Qiita
こんにちは、大学 1 年生になったばかりの E869120 です。 私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどに出場しています。ちなみに、2021 年 4 月 7 日現在、AtCoder では赤（レッドコーダー）です。 本記事では、アルゴリズムの学習や競技プログラミングで使える数学的な部分を総整理し、それらについて解説したいと思います。前編・中編では数学的知識、後編（2021/4/26 公開予定）では数学的考察の側面から書いていきます。 【シリーズ】 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 ← 本記事 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 アルゴリズム・AtCoder のための数学【後編：数学的考察編】 1. はじめに 21 世紀も中盤に入り、情報化社会（いわゆる「IT 化」）が急激に進行していく中、
競技プログラミングの在り方 ～「競技プログラミングを我々が終わらせる」を受けて～ - chokudaiのブログ
nuc.hatenadiary.org 競技プログラミングについての言及があったのですが、バズってる＋競技プログラミングについて、納得がいかない記述がかなり多く見受けられたので、反論記事を書きました。 自己紹介 競技プログラミングの日本最大企業「AtCoder」の社長を9年間続けています。競技プログラマとして、2010年から毎年1つは世界大会で入賞しています。 完全に競技プログラミング支持側の意見なので、ポジショントークを出来るだけ排除しようと心がけているものの、完全に排除することは多分出来ていないため、多数の意見と比較してもらえると幸いです。 競技プログラミングとGoogle まずは肯定的な所から。 Googleに入るためには、競技プログラミングではなく、Googleに入るための勉強をするべき、という点に関しては、間違いなく正しいです。特にAtCoderの競技プログラミングは、常日頃から
本当は遅い「似非エラトステネスの篩」の罠
この記事は？ インターネット上でエラトステネスの篩の実装を検索すると、かなりの割合で、エラトステネスの篩とよんでいいのか怪しい「似非エラトステネスの篩」とでも称すべきものがみられます。 この記事では、「試し割り」「似非エラトステネスの篩」「エラトステネスの篩」の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
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 Community for at least three years. Got it Two Year Club This badge celebrates the longevity of those who have been a registered member of the DEV Commu
数学的知識
となりますね。 ■ 逆元 かけ算をするときは 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が競技プログラミングに向いていない理由となる仕様がいくつか存在
Pythonで実装する素数判定アルゴリズムと実行効率の比較 - Szarny.io
はじめに ごり押し判定法 説明 ソースコード ちょっと改善した判定法 説明 ソースコード 素数の性質を利用した判定法 説明 ソースコード フェルマーの小定理を利用した判定法 説明 ソースコード エラトステネスの篩 説明 ソースコード 実行時間の比較 説明 実験用のソースコード 実行結果 はじめに Pythonで5種の素数判定アルゴリズムを実装します． 後で効率を比較するために，各関数は の範囲において，各数が素数であるかを計算します．そして，その範囲における素数の総数を戻り値として設定します． ごり押し判定法 説明 ある数 が素数かどうか判定するために，の範囲において約数が存在するかどうか調べます． もし，その範囲内に約数が存在しないなら，素数であると判断します． ソースコード def normal(limit): n = 0 for k in range(2, limit+1): fac
フィボナッチ数絡みの競プロの問題を解いてみた（Typical DP Contest T） | 雑記帳
この間、フィボナッチ数を計算する記事を書いていたら、@fetburner氏にこういう問題を教えて頂いた： T: フィボナッチ – Typical DP Contest | AtCoder フィボナッチ数列の各項は直前の2項（隣接3項間の漸化式）によって定まる\[a_{n+2}=a_n+a_{n+1}\]が、それを「直前の\(K\)項」に一般化したものを高速に計算しなさい、ということだそうだ。\begin{align*}a_1&=a_2=\cdots=a_K=1,\\a_i&=\underbrace{a_{i-1}+\cdots+a_{i-K}}_{K\text{項}}\quad(i>K)\end{align*} 競技プログラミングにはあまり興味はない（制限時間があって他の人と競って〜という形式は好きではない）が、フィボナッチ数列の計算について熱弁した後に「わからん！w」と言って逃げるわけに
DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita
0. はじめに --- グラフ探索の動機 現代ではコンピュータはとても身近なものになりました。コンピュータの用途としては シミュレーションなどの大規模計算を行う 人工知能をつくる アプリを開発する などなど多様なものが考えられますが、「探索」もまた、コンピュータを用いるモチベーションとして、最も基本的かつ重要なものの一つだと思います。探索とは、与えられた対象の中から、目的に合うものを見つけ出したり、最良のものを見つけ出したり、条件を満たすものを列挙したりする営みです。 世の中における様々な問題は、探索によって、考えられる場合を調べ尽くすことによって原理的には解決できるものが多いです。例えば、現在地から目的地まで最速でたどり着く方法を求める問題は、原理的には、現在地から目的地へ到達する経路をすべて列挙することで解決できます1。将棋やオセロの必勝法を求める問題は、原理的には、考えられる局面と
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムビジュアル大事典