競プロのための高速フーリエ変換
■「フーリエ変換って知ってる？」 ●「フーリエ変換ですか？ 信号処理でもするんですか、先輩」 ■「いや、競プロで使えるようになりたいなって」 ●「ああ、畳み込みの高速化ですか。あれは高速フーリエ変換をそのまま使うだけですからね」 ■「勉強しようと思って色々調べたんだけど、なかなか理解できなくて」 ●「私もうまく説明できるかわかりませんが、お話しましょうか」 離散フーリエ変換（DFT） フーリエ変換の仲間たち ●「フーリエ変換の仲間には色々種類があるんですけど、競プロで使うのは離散フーリエ変換（DFT: Discrete Fourier Transform）ですね」 ■「離散ってことは、連続もあるんだよね」 ●「はい。ざっくり 4 種類あります。フーリエ変換では元の信号を別の信号に変換するんですが、元の信号が周期信号だと変換後は離散信号（数列）になります」 ■「周期信号っていうのは、決まった
アルゴリズムの世界地図 - Qiita
0. アルゴリズムとは？ まず、アルゴリズムとは何かを説明します。（0 節の説明はスライド「50 分で学ぶアルゴリズム」 の説明を参考にして書きました） さて、次の問題を考えてみましょう。 問題： 1 + 2 + 3 + … + 100 の値を計算してください。 単純な方法として、式の通りに 1 つずつ足していく方法が考えられます。すると、以下の図のように答えが計算されることになります。 これで答え 5050 が正しく求まりました。これはれっきとした アルゴリズム であり、この問題を 99 回の足し算 で解いています。しかし、計算回数が多く、計算に時間がかかるのではないかと思った方もいると思います。 ここで、方法を変えて、「1 + 100」「2 + 99」「3 + 98」…「50 + 51」の合計を求めることで、1 + 2 + 3 + … + 100 の値を計算してみましょう。 50 個の
AHC006初心者向け解説 ～貪欲だけで順位表2ページ目を目指す～ - TERRYのブログ
ヒューリスティックコンテスト、楽しんでますか？私は楽しんでいます。最近企業AHCなんかも続々と出てきて、これからどんどん盛り上がってくれるんじゃないかと期待しています。 とはいえ、ヒューリスティックコンテスト特有の取っつきづらさがあるのも確かです。「どこから手を付けていいか分からない……」「AHC後のTLに焼きなましとか2-optとか流れてきたけど何が何だか……」と思われた方も多くいらっしゃるのではないでしょうか？ AHC006は巡回セールスマン問題を発展させた問題なので、確かに2-optを使った焼きなましができると有利ではあります。しかし、専門知識がないと戦えないかというと全くそんなことはありません。 この記事では、AtCoder Heuristic Contest 006 (AHC006)を題材として、 焼きなまし → 使いません ビームサーチ → 使いません 2-opt → もちろん
アルゴリズムロジック
問題へのリンク 問題概要座標 \((0,0)\) からスタートして \(N\) 回の移動で \((X,Y)\) に到達する確率を求めたい。 1回の移動では、上下左右それぞれの方向に確率 \(\frac{1}{4}\ ...
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ - Qiita
基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。 基本的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれか。 始点を固定して他のすべての頂点との対について最短経路問題を解く場合や、任意の2頂点の対について解く場合などが実際には多いです。 実社会とも強く密着した問題のため、古くからたくさん効率的な解法が考えられてきました。 今回はそれらを紹介しつつ、細かいテクニ
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita
本記事を終えた次は？ AtCoder Beginners Selection を終えたら、AtCoder 上の過去問が AtCoder Problems に集大成されていますので、片っ端から埋めるような気持ちで精進していきましょう。本記事の続編として AtCoder 版！蟻本 (初級編) AtCoder 版！蟻本 (中級編) AtCoder 版！蟻本 (上級編) AtCoder 版！蟻本 (発展的トピック編) も執筆しましたので参考にしていただけたらと思います。また、アルゴリズムとデータ構造に関するトピックを集大成した書籍として、 問題解決力を鍛える！アルゴリズムとデータ構造 (通称、けんちょん本) を上梓しました。ぜひ読んでみてください。 1. AtCoder とは AtCoder は以下のコンテストサイトを運営しています。今後常に訪れることになるサイトです: AtCoder コンテスト
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
AtCoder灰・茶・緑色の方必見！二分探索を絶対にバグらせないで書く方法