こわくないbit全探索1 入門編: bit全探索ってなに？【競プロ解説】 - Qiita
競技プログラミング（AtCoder）初心者が、最初に突き当たる壁になることが多いアルゴリズムのひとつに『bit全探索』があります。 この記事では、その『bit全探索』についてできる限り丁寧に解説をしていきます。 記事リンク 1. 入門編 bit全探索ってなに？ : bit全探索はどんなことをするアルゴリズムなのか解説します。 2. 基本編1 簡単な例題でbit全探索をやってみよう！ : 簡単な例題（部分和問題）で実際にbit全探索を実装してみます。 3. 基本編2 2進法を使って実装してみよう！ : 2進法を使ったbit全探索の実装をしてみます。 4. 実践編 AtCoderの問題を解いてみよう！ : AtCoderのbit全探索を使う問題のヒントとコード（Python・C++）を載せています。 5. 応用編 3つ以上の選択肢は再帰関数で書こう！ : 再帰関数を使ってbit全探索に似た問題
桁DPの痒いところに手が届く解説 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに 本記事は、アルゴリズムの一つである桁DPについて、入門者が疑問に感じる（というか筆者が実際疑問に感じた）ポイントに重点を置いて解説するものです。 筆者自身そこまで桁DPに詳しいわけではなく、むしろ最近覚えたぐらいなので、何かまずい部分があれば優しくご指摘いただけると嬉しいです。 この記事で特に重点を置くポイントは、次の通りです。 何故これでうまくいくのか 桁DPで数えているものは何か 初期条件はなぜこうなるのか 桁DPそのものの入門的解説としては、他にもけんちょんさん達の優れた記事がありますので、そちらも合わせてご覧ください。
桁DP(Digit DP) を考え方から問題例まで徹底解説！ | アルゴリズムロジック
桁DPとは 桁ごとに分けて考える動的計画法です。 「1からNまでの整数について、条件を満たす数はいくつあるか？」「1からNまでの整数について、条件を満たす最大値は何か？」 というような問題で主に使えます。 Nについての制約が非常に大きくなるのが特徴で、O(logN)やO(1)でないと計算時間が間に合わない問題で使用されます。 桁DPの前に知っておくと良いこと 桁DPでは、「N以下の数を全て走査する」ことになりますが、以下のような場合分けを考慮しておくと分かりやすくなります。 例えば、N=63435 のような数であれば、 00000 ~ 59999 (\(6\cdot 10^4\) 通り)60000 ~ 62999 (\(3\cdot 10^3\) 通り)63000 ~ 63399 (\(4\cdot 10^2\) 通り)63400 ~ 63429 (\(3\cdot 10^1\) 通り)6
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita
0. はじめに 二分探索法は単純ながらも効果が大きく印象に残りやすいもので、アルゴリズム学習のスタート地点に彩られた花という感じです。二分探索というと「ソート済み配列の中から目的のものを高速に探索する」アルゴリズムを思い浮かべる方が多いと思います。巨大なサイズのデータを扱う場面の多い現代ではそれだけでも十分実用的ですが、二分探索法はもっとずっと広い適用範囲を持っています。 本記事では、二分探索法のエッセンスを抽象化して、適用範囲の広い「二分探索法の一般形」を紹介します。同時に無数にある二分探索の実装方法の中でも「めぐる式二分探索」がバグりにくいと感じているので、紹介したいと思います。 注意 1: 二分探索の計算時間について 二分探索の計算時間について簡単に触れておきたいと思います。例えば「$n$ 個の要素からなるソート済み配列から目的の値を探索する」というよく知られた設定であれば、 単純な
アルゴリズムと数学的思考力 - 怠惰を求めて勤勉に行き着く
厳しい。年始早々厳しさを感じている。自分のプログラミング力にだ。伸び悩んでいる。 端的に言って、数学力のなさが自分のプログラミング能力に制限をかけている。例えばこの問題。 560. Subarray Sum Equals K 入力として与えられる配列 nums のうち、合計が k となる部分配列の個数を数え上げよ。どうも有名な問題らしいが… まず大前提として、部分配列なので i, j の2重ループで始点・終点を定めて sum(nums[i, j]) = k になるものを数え上げれば必ず答えが得られる。最悪計算量は O(N^3) ただし i < nums.length < 20000 という制約があるので N^3 では遅すぎるから何か考えてくださいというのがスタート地点。 ここで、結果の変わらない累積和を何度も求めているので nums[i, j] = k を求めたい場合、 nums[0, j
赤黒木の本質 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事はデータ構造とアルゴリズム Advent Calendar 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思い
よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
1. 典型的な二項係数の求め方 競プロをしていると、「 mod 」を計算する場面にしばしば出くわします。最近では、 であることが多いですね。 mod の計算方法は、時と場合によって色んな方法が考えられますが、すぐ下で紹介する方法が最も頻繁に使用されています。多くの AtCoder のトッププレイヤーたちも使用している形式で、高速です。 使い方としては、最初に一度前処理として COMinit() を呼び出します。その後は、毎回 COM(n, k) 関数を呼べばよいです。 前処理 COMinit()：計算量 クエリ処理 COM(n, k)：計算量 1-1. mod の実装 この実装では、ACL (AtCoder Library) の modint を用いています。さらに下に、modint を使わない実装も載せています。 #include <iostream> using namespace s
競技プログラマのための抽象セグメント木実装のすすめ - beet's soil
午前起床！（素振り） はじめに 先にこっちを見て beet-aizu.hatenablog.com うし木（一点更新区間取得）について書きます おまけ なんだこれはたまげたなあ（わかる人にはわかる記事、わからない人にはわからない） beet-aizu.hatenablog.com 前提知識(C++) 厳密性や歴史的背景をガン無視しています。あんまりあてにしないでください。 雰囲気を掴むためと割り切って読んでもらえるといいと思います。 C++のバージョンは14を前提にしていますがそのうち17に上がりそう？ struct is 何 競技プログラマならpairやtupleくらいは使ったことがあると思いますが、自分でそういうのを作るための機能です。 たとえば struct Node{ int fi,se; }; Node v; v.fi=0;v.se=1; みたいな感じで使えます。 つまり、大きな
atcoderでよく使う手法python版 - Qiita
はじめに 1年前に機械学習をやりたい、それならpythonだ！ってなったものの、別に情報系卒でもないし、プログラミングをやった経験もないので始めようと思いながら何も動かすことができませんでした。 「何か、なにかプログラミングやってみたい、でも何をやればいいの?」ってときに見つけたのが競技プログラミングです。これをやることで、いろんなアルゴリズムの考え方や、プログラミングでできることをいろいろと学べました。そして、普通に競技プログラミングにハマって今日まで続けています。 そんなところで競技プログラミングでよく使う技術のメモと、もっと使ってほしい技術の紹介です。もっとpython勢増えてほしい。特に短い、早い、わかりやすいコードの人が増えてほしい。いつも短い順、早い順で探して参考にしてるので。 ※githubにjupyterのコードをアップしました。 基本入力、出力、format関数 他の人が
Pythonで幅優先探索を実装する - りんごとバナナ
アルゴリズムの勉強のために、幅優先探索を書いてみた。 使ったのはAtCoder Beginers Contest 007Cの問題。この頃はアルゴリズムがそのまま出題されてたようだ。 特殊事項として、この問題ではスタートからゴールまでは必ず行くことができる前提がある。さらに周り中が壁で囲まれているので、盤面からはみ出すのを考慮する必要がない。 実装 from collections import deque def bfs(maze, visited, sy, sx, gy, gx): queue = deque([[sy, sx]]) visited[sy][sx] = 0 while queue: y, x = queue.popleft() if [y, x] == [gy, gx]: return visited[y][x] for j, k in ([1, 0], [-1, 0],
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
