next_combinationを実装してみた - Qiita
前置き next_permutationがあるならnext_combinationがあってもいいじゃないか、というわけでnext_combinationです。 next_combinationでググると、実装されたものもたくさん見つかるのですが、どれもなかなか理解するのが大変で、そんな中でも比較的私の頭でも理解できそうだったものを参考に、勉強のために改めて自分で実装し直してみました。 なお、参考にさせていただいた記事はこちらです。C++でnCkやnPkを全列挙する関数 ありがとうございます。 実装 template <typename T> bool next_combination(const T first, const T last, int k) { const T subset = first + k; // empty container | k = 0 | k == n if
Red Blob Games: Hexagonal Grids
Mar 2013, updated in Mar 2015, Apr 2018, Feb 2019, May 2020, Oct 2021, Dec 2022, Feb 2023, Oct 2024, Mar 2025 This guide will cover various ways to make hexagonal grids, the relationships between different approaches, and common formulas and algorithms. I've been collecting hex grid resources[1] for over 25 years. I wrote this guide to the most elegant approaches that lead to the simplest code, st
ゼータ変換・メビウス変換を理解する - Qiita
要約 本記事では、競技プログラミングに頻出のゼータ変換・メビウス変換についてまとめました。 記事中のコードはpythonで記述されています。 1次元のゼータ変換 定義 $f[0], \dots, f[N-1]$が与えられている。 このとき、$\displaystyle g[x] = \sum_{i \le x}f[i]$となる$g$を、$f$のゼータ変換という。 また、逆に$f$を$g$のメビウス変換という。 アルゴリズム 上の定義を落ち着いて読むと、$f$のゼータ変換$g$は$f$の累積和そのものだとわかります。 図で見ると上図のようになります。 累積和を知らない方はdrkenさんの記事を見てください。 念のため累積和の計算を復習しよう。 配列$f$が与えられているとき、$f$のゼータ変換はlist(itertools.accumulate(f))となる。 もしくは、in place に
高速ゼータ変換 - とどの日記
id:iwiwiさんの高速ゼータ変換に関する記事 http://topcoder.g.hatena.ne.jp/iwiwi/20120422/1335065228 が恥ずかしながら分からなかったので，自分なりに解釈した． やりたいこと 集合に関する関数があり，全集合について， を求めたい． コード for(int i=0; i<n; i++) for(int s=0; s<1<<n; s++) if ((s>>i&1)==0) a[s]+=a[s|(1<<i)]; ただし，a[s]には予めが入っている． 実行の様子 n=3としてi=0の時の処理が終わった後のaの中身は以下のようになっている． 000：000, 001 001：001 010：010, 011 011：011 100：100, 101 101：101 110：110, 111 111：111 左はインデックス集合，右は（その
全方位木DP [いかたこのたこつぼ]
詳細なアルゴリズムは、他の記事が多く出てくるのでそちら参照。 「木で、ある頂点を中心に考えたときの何らかの値」を「全ての頂点について」求めたいときに使うことがある。 ①を根として木DPを行うことで、①を中心に考えたときの値を求められるような問題があったとする。 このとき、頂点②を中心に考えたいとき、最初からまた木DPを行うのでなく、 ①を計算したときの結果を上手くずらして使うことで、計算量を削減できる。 ① ② ／ ＼ ⇙⇓＼ ②から④,⑤方向への部分木 および ② ③ → ④ ⑤ ① ①から③方向への部分木は /\ /\ ⇓ ①を根としたDPで求まっている（二重矢印） ④⑤ ⑥⑦ ③ ⇙⇘ あとは、親子関係を①→②から②→①に ⑥ ⑦ 付け替えたときの差分を計算すればよい。 （DP[1] から DP[2] に相当する分を除き、 DP[2] にはその除いた分を加える） 1つ頂点を遷移するた
いろんな人のテンプレートを観察 - memo
この記事はCompetitive Programming Advent Calender(その2) 23日目の記事です。 はじめに 競技プログラミングでいろんな人のコードを読んでみると、前半部分には人によって色々なマクロや関数が定義されていたりいなかったりします。(参考: Quora) この部分にはその人が快適にコーディングするための工夫が見られて面白いので、今回いろんな人のテンプレートを眺めてみることにしました。 実際に見たテンプレートはここ(Codeforces)とここ(KUPC)にまとめました。時間の都合上、それぞれ約50人、約30人しか見ていません。しかも途中で疲れてコメントがかなり雑です。すいません。 これらを見てどのような機能がテンプレートにあったか挙げていきたいと思います。 ※この記事は競技プログラミングにある程度参加している人が読者であることを想定しています。そうではなくて
【図解】線形時間の文字列アルゴリズム「Z algorithm」をイラストとアニメーションでかみ砕く - Qiita
この記事では文字列を $S$，その $i$ $(0 \leq i < |S|)$ 文字目を $S[i]$ と表記します．文字列の結合は $+$ で表現します． また，Z 配列を $Z$，その $i$ $(0 \leq i < |S|)$ 番目の要素を $Z[i]$ と表記します． 1. Z algorithm で求める Z 配列とは 難しく厳密に表現すると，$Z[i]$ は 文字列 $S=S[0]+S[1]+\cdots+S[|S|-1]$ 文字列 $S[i]+S[i+1]+\cdots+S[|S|-1]$ の 最長共通接頭辞の長さ と定義されます． もう少しざっくり表現すると， 文字列 $S=S[0]+S[1]+\cdots+S[|S|-1]$ 文字列 $S[i]+S[i+1]+\cdots+S[|S|-1]$ の 先頭何文字が一致してるの？ という値が $Z[i]$ です． 図解 図で
二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆を総整理！ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに、二部マッチングに関してこちらの記事を読んでいただければと思います。 実世界で超頻出！二部マッチング（輸送問題、ネットワークフロー問題）の解法を総整理！ 早見表 二部グラフの最大マッチング、最小点被覆、最大安定集合、最小辺被覆についての結論を最初にまとめます。$|V|$ はグラフの頂点数、$|M|$ は最大マッチングのサイズです。 なお、本記事の内容のあらすじは簡単に以下のスライドにまとめました。 https://www.slideshare.net/drken1215/ss-86894312 1. はじめに グラフ上の最適化問
三角形の外接円の半径と中心座標(外心)を求める - Qiita
出典 Aizu Online Judge 0010 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0010&lang=jp 平面上の点$(x_1, y_1),(x_2, y_2), (x_3, y_3)$ を頂点とした三角形の外接円の中心座標$(p_x, p_y)$と半径rを出力するプログラムを作成して下さい。 ※問題文では三角形の頂点の座標を$(x_1, y_1),(x_2, y_2), (x_3, y_3)$と定義していますが、式変形する時に訳がわからなくなるので$(a, b), (c, d), (e, f)$と読み替えます。 外心座標の計算 Wikipediaに「外心の位置」という項目がありますのでこちらが理解できる方はそのほうがたぶん早いです。私は理解できなかったので別の方法を取りました。 まず、3つの頂点からまで
Python で std::set の代替物を作った - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? Pythonista の皆様、こんにちは。競技プログラミングをしている tatyam と申します。 Python で競技プログラミングをしていると、std::set が欲しいな〜ってとき、ありますよね？ 例えばそう、 Cutting Woods (ABC217-D) を見てみましょう。これは以下のような問題です。 長さ $L$ の定規がある。以下のクエリが $Q$ 回与えられるので、順に処理せよ。 1 x：目盛 $x$ で定規を切る。 2 x：目盛 $x$ を含む部分の長さを出力する。 $L ≤ 10^9,\ N ≤ 2 \times
Red-Black Tree by Java & Python - これで分かった赤黒木
【これで分かった赤黒木】 このページは、 マップ(連想配列)と呼ばれるデータ構造の実装の１つである赤黒木(２色木、red-black tree)について解説するページです。 赤黒木は、要素の挿入・削除・検索などの操作が、 いかなる場合でも O(log n) の計算量で実行出来る平衡２分探索木です(n は要素数)。 何の工夫もしない単なる２分探索木では、 挿入や削除のパターンによっては木の茂り方のバランスが崩れてしまい、 各種操作に O(n) の計算量が必要になる場合があります。 赤黒木はやっていることは単純なのですが、 とにかく場合分けがたくさんあって、 習得しようとしながらもくじけてしまった人も多いのではないでしょうか？ しかし、ご安心ください。このページは場合分けを出来るだけ減らし、 挿入操作で４パターン、 削除操作で８パターンさえ理解すれば赤黒木が分かるように書かれています。 削除操
石取りゲーム(Nim) [いかたこのたこつぼ]
（例）$[5, 9, 11]$ ⇒ 2進数表現で $[101, 1001, 1011]$ ⇒ $0101 \hat{} 1001 \hat{} 1011 = 0111$ となり、$X = 111$
AtCoder 版！蟻本 (中級編) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0 はじめに 前回の初級編に続いて、今度は中級編です。 プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です: POJ が国内ではあまり使用されなくなった (計算速度が遅いなど) AtCoder 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。具
アルゴリズムの世界地図 - Qiita
こんにちは、square1001 です。 現在は東京大学の学部 1 年生をしています。私は中学 1 年の頃からプログラミングをやっていて、特にアルゴリズムが大好きです。AtCoder をはじめとする 競技プログラミング にも取り組んでいて、中高生のときは 情報オリンピック にも参加していました。 本記事では、アルゴリズムや競技プログラミングに興味がある方、あるいはプログラミングをやっているけどアルゴリズムをよく知らない方に アルゴリズムはどんなもので アルゴリズムを使うとどんな問題が解けて アルゴリズムが地球のように広く、多様で、奥深く、そして楽しいこと を知ってもらおうと思っています。 アルゴリズムの世界へようこそ 時代は 2020 年代に突入し、急速に IT 化 や DX が進んでいく中で、問題を効率的に解くアルゴリズム技術の重要性が、ますます高まっています。そして、アルゴリズムは、世
青から黄になるために学んだアルゴリズムたち - クマーの競プロ精進日記
色変記事でも書いたように、私が一番アルゴリズムを学んだのは青になってからです。青以降の期間が競プロ歴の7割くらいなので、当たり前かもしれませんが。 chokudaiさんのブログには 水色や青あたりで、競技プログラミングで必要な知識はほぼ揃ってしまうので、そこから先は応用力の違いになってきてしまいます。 と書いてあるのですが、個人的な感覚だと青になってからの方が学んだアルゴリズムが圧倒的に多いです。ABCは茶や緑くらいの人でも理解できるアルゴリズムを組み合わせて解く問題が多いので、高度なアルゴリズムを知らなくても青になれてしまうというのはあると思います。 しかし黄色になる、あるいはそれ以降のレベルで戦うには知識が足りないことは自覚していたので、夏休みに入ってからはひたすらアルゴリズムを勉強しました。 せっかくなので自分が何を勉強したか振り返ってみたいと思います。アルゴリズムを解説できる腕はな
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
確率 DP を極めよう - 確率と期待値の問題解説
Bernoulli's triangle - OeisWiki
高速ゼータ・メビウス変換 - Mister雑記
TopCoder の始め方 (macOS)
Dropbox - Error - Simplify your life
