Binary Indexed Tree のはなし
Binary Indexed Tree のはなし 保坂 和宏 (東京大学理学部数学科) 第 13 回 JOI 春合宿 2014/03/19 概要 Binary Indexed Tree とは 何ができる？ 何が嬉しい？ 具体的な実装 応用範囲 区間に足す問題 多次元 二分探索 目標 実装できるようにする 「普通に Binary Indexed Tree を使うだけ」の部 分で詰まらないようになる 補助的な道具としてぱっと使えるように Binary Indexed Tree とは Binary Indexed Tree Binary Indexed Tree (Fenwick Tree) Peter M. Fenwick, "A New Data Structure for Cumulative Frequency Tables" (199
競技プログラミングで使う有名グラフアルゴリズムまとめ
0. はじめに AtCoderなどでは、グラフを扱った問題が多く出るが、その度に一から実装していると時間が掛かりすぎてしまうため、有名なものをあらかじめ持っておく必要がありそう。そこで、Pythonを用いて、ダイクストラ法、ベルマンフォード法、プリム法、クラスカル法、ワーシャルフロイド法を実装した。 コメント、意見等ある方は是非! お待ちしてます! 1. ダイクストラ法 1.1. ダイクストラ法(defaultdictで実装) defaultdictで実装すると、リストで実装するよりも、ノード数$N$が大きい際には高速に動作する。ただし、経路復元の関数は、うまく書けなかった......。 (2019/7/6 追記)結局できました。1.1.1. を参照してください。 import collections import heapq class Dijkstra: def __init__(se
AtCoder橙になりました - ARMERIA
5月4日のAGCで、ついに橙になることができました！！！ 初めてratedに参加したのが昨年の4月上旬なので、およそ1年と1ヶ月での到達となりました。今年中には橙になりたいと思っていたので、予想より遥かに早くてびっくりしています。 ということで記事を書きます。ここまで来ると体系的に書けることがなくなってきたので、全体的にポエム成分が多めです。 解いた問題 AtCoder ProblemsのAC数と、AtCoder Scoresの精進グラフです。何だかんだでStreakをずっと繋いでいます。 全て埋めたのはABC全部と、ARCのE（昔のC）まで、AGCのDまで（今回のやつ解いていませんが）。最近はARC/AGCで残っている問題がかなり難しくなってきたので、JOIとか過去の企業コンとかを細々とやっています。 このゴールデンウィークは、コンテストに出る他はCodeforcesでDifficult
「写像12相」を総整理！ 〜 数え上げ問題の学びの宝庫 〜 - Qiita
0. はじめに: 「数え上げ」という分野について 「条件を満たすものを数え上げる」タイプの問題にはパズルのような楽しさがあります。そのような問題のうち簡単なものは高校数学の「個数の処理・確率」で学ぶのですが、その先にも奥深い世界が待っています。 例: 数え上げテクニック集 (DEGwer さん) 例: 数え上げおねえさん (ERATO 湊離散構造処理系プロジェクト) 本記事では数え上げ問題を解くと度々登場する「写像12相」について整理します。写像12相の中でも特に高度なスターリング数と分割数をメインに取り上げます。これらのテーマが直接的に登場する問題はあまり多くはないですが、包除原理や動的計画法といった技法を学べる格好の題材です。簡単な部分についても重複組合せなどの教育的要素を多く含んでいます。 そんな事情もあって、chokudai さんも「競プロで使う基礎的な数学は写像12相がわかればと
ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary
はじめに この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の1日目の記事です。 この記事ではビット演算を使って有限集合の部分集合を表現、操作するテクニックを紹介します。 本文中で説明を省略した部分については、詳しい説明のある参考文献を紹介しておきます。 2021/01/03: 高速ゼータ変換/メビウス変換/畳み込みに関する部分を全面的に書き換えました。 表現方法 S={A,B,C,D}という4要素の集合があったとします。 各要素を次のように2進数の数字と対応付けます。 A: 0001 B: 0010 C: 0100 D: 1000 こうすると、Sの部分集合は存在する要素のビットごとの論理和を取ることで4ビットのビット列として一意に表すことができ、例えば {A,B,C}: 0111 {B,D}: 1010 のようになります。 以後、
競技プログラミング練習問題集 - はまやんはまやんはまやん
他 競技プログラミングにおける細かな話題まとめ - はまやんはまやんはまやん DEGwerさんの数え上げテクニック集問題まとめ - はまやんはまやんはまやん セグメントツリーにセグメントツリーを乗せる手法（2Dセグメントツリー） - はまやんはまやんはまやん HackerRank Game Theory の勧め - はまやんはまやんはまやん Educational DP Contestの勧め - はまやんはまやんはまやん 今年中に理解する！多項式、母関数、形式的べき級数の競プロでの実践的使い方 - はまやんはまやんはまやん パソコン甲子園 プログラミング部門 解説まとめ - はまやんはまやんはまやん 日本情報オリンピック 解説まとめ - はまやんはまやんはまやん アルゴリズム実技検定解説まとめ - はまやんはまやんはまやん フロー 競技プログラミングにおける最小費用流問題まとめ - はまや
水色になりましたので学びを整理します - 地下ハウス
はじめまして、ねてるくんと申します。 AtCoderを初めて約3ヶ月、ABC123で水色になれましたので今までの勉強内容を整理します。 使用言語はPython3です。C++を勉強する予定は当面のところないです。 覚えたアルゴリズム 取り組んだこと 取り組まなかったこと 最後に 覚えたアルゴリズム ・深さ/幅優先探索（DFS/BFS） グラフや2次元グリッド上を全探索したいときに利用します。実装には両端キューdequeによるスタック/キューを使います。再帰関数を用いた深さ優先探索もありますがコンテスト本番では実装できた記憶がないです（再帰関数が苦手です…）。 ・貪欲法 ソートして前から/後ろから順番に考えていきます。難しい問題では、何を基準にソートすれば貪欲に解けるか分からなくなります。貪欲法のための勉強はあまりしませんでしたが、区間スケジューリング問題は知っておくと様々な問題で応用が効きま
半年以上かかってAtCoderでやっと緑になった話 - Zono_0317’s blog
AtCoderを始めて(というか競プロを始めて)7か月経ってやっと緑になることができたので、緑までの道のりをぐだぐだ書きます。 とりあえず レートの推移はこんな感じです。 灰色前期はB問題安定なんて程遠いくらいの実力でした。 緑になるまで24回もかかっています...遅いですね。 緑になるまでに具体的になにをしたのか 灰色～茶色になるまで この時期は、ひたすら簡単な問題を解きました。 具体的には、ABC-A,Bを全部埋めました。 これは、今まで、どのレベルの問題をどれだけ解いてきたかを表す円グラフです。 ABC-A,Bは灰色の終わりごろにはすべて埋めていました。 (kenkooooさん(Twitter:kenkoooo)が作ったAtCoder Problemsというサイト(上のグラフもそのサイトのもの)で自分がどれだけACしたか、ライバルがどこをACしているかなどがわかります。便利です。使い
AtCoder 緑色になるまでにやったこと - たのしい競プロブログ
先日(2019/03/03)のコンテスト（AtCoder Beginner Contest 120）で、レーテイングが809に到達し、緑コーダーになることができたので、今までにやってきたことを振り返ってみたいと思います。 目次 １．AtCoderデビュー～緑到達までの流れ ２．緑に到達するためにやるべきことは何か？ ３．今後の課題 ※実は緑色になるのは今回が2回目なのですが、1回目に緑色になったときは運の要素が強かったため、このような記事を書くのを見送っていました。 １．AtCoderデビュー～緑到達までの流れ １．１ 2018年3月（デビュー）～2018年8月ごろ 僕は2018年3月にAtCoderを始めました。まず初めは、practice contestで入出力の方法学び、次にdrken氏の「AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問
AtCoderで水色になるまでにやったこと - naoppyの日記
naoppyです。4/21にAtCoderで水色になることが出来ました。 一つの節目として、やってきたこととかをまとめます。 レート変移 水色時点での自分 使えるアルゴリズムとテク Twitterがやめられない 精進方法 AtCoderProblemsで過去問を解く TwitterのDMで優しい人に聞きまくる チーター本を読む スライドやQiitaの記事を読む 解くときのテク まとめ レート変移 これを見てわかるのは、まあ僕に特別な才能や強い考察力がないことぐらいでしょう。 31回も参加してます。 水色時点での自分 実力と言っても色々パラメーターがあるので、難しいですが、僕のスペックを並べます。 プログラミング歴1年、Java使い 競プロ歴は始めたのが去年(2017)の7月中旬、それなりに本気でやり始めたのが12月ぐらいです 1月ごろに300点問題は完全に安定、水色になった時点で400点が
「これがわからなかったから解けなかった…」みたいな情報まとめ（Topcoder SRM Easy 600番台） - はむこの勉強記録
Topcoder SRM Easyを100ACしたので、Topcoder SRM 600番台で勉強したことをまとめます。 僕の解説リストから、特に勉強したこと、新しい発想方法だけ抽出します。 docs.google.com 目次 目次 二分探索と全探索の順序は、全探索→二分探索のほうが枝刈りできて速い 成り立たないってことは…つまりどういうことだってばよ… DP書こうとしたらこれループするんですけど 「事前に分からない」場合分け その変数、探索する必要ありますか 整数計画に落とすしてもあまり意味ないので、sumなどを使ってうまく緩和する おいおい、辺を忘れてもらっちゃ困るぜ 可逆な状態変化とDFS 制限付きDPでは、制限ベースに一個ずつ殺していく 範囲素因数分解はけっこう速い DAGの考察は横一列にならべて、トポロジカルソート的に ハミルトン路（全頂点一筆書き）は閉路だろうがなんだろうがN
エンジニアのスポーツ「競技プログラミング」を実際に体験してみた
「競技プログラミング」とは、出題される問題を制限時間内に解くプログラムを作成するスピードを争う競技で、プログラミングを使ってパズルを解くスポーツと表現されることもある競技です。今回は競技プログラミングに参加するための環境を構築し、コンテストの過去問を解いてみました。 AtCoder http://atcoder.jp/ 今回はAtCoderというサイトを使います。トップページへアクセスし、右上の「新規登録」をクリック。 ユーザーID、メールアドレス、パスワードなどを記入し、「個人情報の取り扱いについて確認しました」にチェックを入れて「新規登録」をクリックします。 登録が完了したら「practice contestに参加する」というボタンが表示されるのでクリックします。 画面上部に「Joined in～」という文字が出たのを確認し、上のタブから「問題」をクリックします。 つづいて「はじめての
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Binary indexed tree