ウェーブレット行列(wavelet matrix) - Eating Your Own Cat Food
ウェーブレット行列(wavelet matrix)の話です ウェーブレット行列 ウェーブレット行列で可能な操作 索引の構築 操作 access rank select quantile topk sum intersect ソース いろいろな人の実装 参考 ウェーブレット行列 例えば，T = [5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0] という配列があったとき，この配列の中で 7 番目に小さい値を求めたいとします． 最も単純なやり方は値をソートしてから T[7] にアクセスすることです（1-origin）． このような操作をいちいち行うことは，同様の操作を何回も繰り返し行いたいときには非効率です． ウェーブレット行列では，あらかじめ索引を作っておくことで，配列に対する様々な操作を効率的に行うことができます． ウェーブレット行列は内部で完備辞書(簡潔ビットベクトル
セグメントツリーの抽象化（C++）
※注 終盤に「ARC008-D タコヤキオイシクナール」の解法のネタバレが存在します ■「セグメントツリーの抽象化ってしてる？」 ●「抽象化…… セクハラですか、先輩」 ■「ええっ」 ●「冗談はさておいて…… 抽象化というのは、セグ木自身に “区間和” や “指定要素を上書きして更新” などの具体的な情報を書かずに、それらを外部から与えることで、目的が変わっても同じコードを使えるようにすることですよね。はい、ある程度はしてますよ」 ■「そうなんだ。いまいちやり方が分からないから、参考にしたいなと思って」 ●「いいですよ、こんな感じです。”long long 型の値を持って区間minと一点上書きのクエリが与えられる” という場合、 “long long”、”区間min”、”一点上書き” という情報を外部から与えます」 template <class T> class SegTree { in
（これは AtCoder関連サービス Advent Calendar 2018 の25日目の記事です） AtCoder Unit Test という、ブラウザの拡張機能を作りました。 これは、どういうものかというと「AtCoder の問題ページから、自動でテストケースを生成するツール」です。 AtCoder Unit Test – Get this Extension for 🦊 Firefox (ja) AtCoder Unit Test - Chrome ウェブストア 現在の対応言語は、Java, Kotlin, C#, Python 31 です。 その他の言語については Pull Request をお待ちしています。 動作確認を手動でやってますか？ AtCoder にコードを提出する前に、たいていの場合は動作確認をします。その時に、以下の手順でやるのが一般的です。 プログラムを実行
AtCoder Heuristic Contest 001 AtCoder Ad - びったんびったん
AtCoder Heuristic Contest 001 - AtCoder Heuristic Contest の初開催おめでとうございます。 楽しませていただきました。 seed: 1 方針 greedy に初期解を求め、少し山登り法をします 実行時間の前半、 1. を繰り返しそのうちの最良解を後半の初期解とします（多スタート） 後半、「キック近傍+少しの山登り」を近傍とした山登り（これは少しではない）をします 山登り法 広告の位置サイズを変更して良くなっていたら遷移する、ができるので焼きなまし法系だなあと思います。 近傍 1: 広告 1 つを最適化 要素を 1 つ 2 つ変えるというのは頻出なのでします。 広告を 1 つ選び、それ以外すべての広告の位置サイズを不変としたときの（ありうる矩形すべてのうちの）最適な位置サイズに選んだ 1 つの広告を変えます。これが平均 O(N) ででき
AtCoder Companions | AC のヒントを見つけよう
はじめに 先月の記事「AtCoderで年齢(誕生年)とレーティングや得点の相関について調べてみた」にて、タイトルの通り、AtCoderにおける年齢とレーティングの相関を調べてみました。 その記事にて年齢とプログラミング言語に相関があるのではというコメントをいただきました。ありがとうございます！！ 実際に年齢と使用言語の相関を調べたみたところ、個人的には予想外な結果が出ました。 年齢が高いほどにC++の使用率が高く、低いほどにPythonの使用率が高いのだろうと予想していたのです。 対象ユーザ AtCoderのランキングのアクティブユーザのみ(2023年4月2日6時付)を元とする。そのため、本記事でユーザという単語が用いられた場合はアクティブユーザを示すとお考えください。アクティブユーザは過去2年以内にRatedコンテストに一度でも参加したユーザと定義されています。 各ユーザの使用言語はAt
AtCoder ABC 163 D - Sum of Large Numbers (緑色, 400 点) - けんちょんの競プロ精進記録
「作れる数が連続する整数になる」というの、実は結構よくある！！ 問題へのリンク 問題概要 個の整数 がある。 これらから 個以上の整数を選んで合計して得られる整数としてありうるものの個数を 1000000007 で割ったあまりを求めよ。 制約 考えたこと まず、 「この ってなんだよ！！！！！」 となるかもしれない。でも、よくよく考えると、これはそんなに恐れる必要はなくて...。 だとでかすぎるので、試しに として、 の代わりに くらいにしてみよう。そうすると 個の整数は 10000, 10001, 10002, 10003, 10004, 10005 になる。これらの整数から、いくつか選んで足してみる。このとき、 1 個選んで足したときは、どのように選んでも、最上位の値が 1 2 個選んで足したときは、どのように選んでも、最上位の値が 2 3 個選んで足したときは、どのように選んでも、最
はじめに 最近、競技プログラミングの勉強をはじめました。仕事で求められるものとはまた違った知識・経験が要求され、なかなか難しさを感じています。 この記事では競技プログラミングを通して学んだ、Rubyを用いたbit演算の基礎をまとめたいと思います。 bit演算の基礎 表示 0b を先頭につけることで2進数表示にできます。 irb(main):> bit = 0b101 irb(main):> bit => 5 論理回路 & は積(AND)、| は和(OR)、~は否定(NOT)、 ^ は排他的論理和(XOR)を示します。 irb(main):> bit = 0b101 # 10進数では5 irb(main):> another_bit = 0b111 # 10進数では7 irb(main):> bit & another_bit => 5 # 0b101 irb(main):> bit | a
標準入力を1行ずつ処理する
Ruby の while line = gets puts line end は、コマンドライン引数で与えられたファイルを一つずつ開いて1行ずつ読み込み、出力するループである。コマンドライン引数でファイルを指定しなければ、標準入力から1行ずつ読み込む。 これと同じことをするための仕組みが Python の標準ライブラリの fileinput モジュールで提供されている： import fileinput for line in fileinput.input(): print(line, end="") # または print(line.rstrip()) fileinput.input() に引数でファイル名（のリスト）を与えれば、それが優先される。 Ruby の gets と違い、ループの中で余分に行を読み込むことはできない。 標準入力だけ読めばよいなら、次のようにできる： impor
この記事は競プロ Advent Calendar 2021 8日目の記事です。 概要 AtCoderの復習を手助けするAtCoder-Ebbingというサイトを作成しました。 レートや解いた回数、前に解いたときからの期間等を考慮して解くべき問題を一問ずつ出題してくれます。 名前の由来は忘却曲線のエビングハウス氏です。 https://atcoder-ebbing.web.app https://atcoder-ebbing.firebaseapp.com （キャッシュのせいか片方見れないことがあります。見れない時はもう片方にアクセスすると良いかもしれません） 背景 皆さんAtCoderのレート上がってますか？ 僕のレートはずいぶん長いことX軸に平行です😢。 一度解いた問題をちゃんと身につけるために復習が大切だというのは分かっていますが、復習をするため問題を管理するのはやや面倒です。 特に
上の例では頂点1がまだ未探索なので、再び頂点1から深さ優先探索を始めれば良いです。その際は既に探索した頂点は探索しないようにしましょう。 計算量 幅優先探索：\(O(|V|+|E|)\)深さ優先探索：\(O(|V|+|E|)\) 未探索の頂点ごとに深さ優先探索や幅優先探索を行うので、計算量はどちらも \(O(|V|+|E|)\) となります。 C++での実装例 幅優先探索でのアルゴリズム グラフを受け取って、トポロジカルソートをした頂点のvectorを返す関数です。 #include <bits/stdc++.h> using namespace std; struct Edge { int to; }; using Graph = vector<vector<Edge>>; /* topo_sort(G): グラフG をトポロジカルソート 返り値: トポロジカルソートされた頂点番号 計算
前にAtCoderのレーティングの分布について調べて記事を書きました sucrose.hatenablog.com Twitterで「AtCoderにたくさん参加すればレーティングが上がる」という話を見かけて気になったので、ユーザーの参加回数とレーティングの関係を雑にグラフにしたりレーティングの分布のグラフを書いたりしてみました 調べるのが簡単なAtCoderのランキングに書いてある現在のレーティングと参加回数の表のデータを使いました https://atcoder.jp/ranking?p=1 AtCoderのレーティングの分布 レーティングの色分けについてはこちら↓ https://atcoder.jp/post/14 1回しか参加していないユーザーも数えているので灰色が全体の半分近くを占めています レーティング レーティング上位何%か 2800(赤) 1% 2400(オレンジ) 2%
これは品川 Advent Calendar 2019の17日目の記事です。 私は競技プログラミングにGo言語で参加することが多いのですが、その際に役立つ（かもしれない）小ネタをいくつか紹介したいと思います。 なお、本記事では次のような方を読者として想定しており、競技プログラミングそのもにについては解説しません。 競技プログラミングにGoで参加しはじめた人 競技プログラミングに興味があってGoで参加したいと思っている人 競技プログラミングそのものについて知りたい場合は drken さんの AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ を見ると雰囲気がわかると思います。また、これらの問題の Go によるACコードについては AtCoder に登録したら解くべき精選過去問 10 問 を Go で解いてみた をご覧ください。 0. C++での参戦
激ムズ数え上げパズルと驚きの解法
この動画は3Blue1Brownの動画を東京大学の学生有志団体が翻訳・再編集し公式ライセンスのもと公開しているものです。 チャンネル登録と高評価をよろしくお願いいたします。 関連するこちらの動画もどうぞ 畳み込みの仕組み | Convolution https://youtu.be/CHx6uHnWErY 日本語版Twitter https://twitter.com/3B1BJP 元チャンネル（英語） https://www.youtube.com/c/3blue1brown 元動画（英語） https://youtu.be/bOXCLR3Wric ゼータ関数の見た目【解析接続】 https://youtu.be/Xjja6Cc7lio 【視覚的に理解する】フーリエ変換 https://youtu.be/fGos3wrKeHY 最後の問題の解説 https://benjamin-
AtCoderのレーティングとパフォーマンスの関係を計算しグラフに描画するサイト
素人によるワーシャルフロイド法 - Qiita
最短経路問題で使われるアルゴリズムの１つ。負の閉路がない限り、負の辺があっても使える。グラフ上の全ての頂点間の最短経路を探すので、計算量は$O(V^3)$となる。 ワーシャルフロイド法はその名前から難しそうな印象があって避けていた。しかし、最近競プロの精進中に実装する機会がチラホラあり、実装してみると思ったよりも簡単だったのでびっくりした。ワーシャルフロイド法が必要となった方は簡単な実装なので恐れず調べてみてほしい。 今回すること ワーシャルフロイド法は実装が簡単だが、その裏でどんな振る舞いをしているのかイマイチ掴めなかった。簡単に最短経路を求められるといっても、裏の仕組みを知らずに使うのは自分としてはどうも気持ちが悪い。今回はいろいろ手を動かしてみながら、仕組みの理解を試みる。 C++によるコード まずはワーシャルフロイド法のコードを見てみる。 void warshall_floyd(i
maspyのHP
・Twitter：@maspy_stars ・ProjectEuler → maspy ・AtCoder → maspy ・codeforces → maspy ・(2019/04）pythonで競技プログラミングを始めました。 ・感想や、発見した知見を書き残していこうと思います。よろしくお願いします。 maspy の記事執筆等を支援する → https://github.com/sponsors/maspypy ★最新記事一覧 FPS Composition and Compositional Inverse (Part 2) FPS Composition and Compositional Inverse (Part 1) FPS 合成・逆関数の解説（2）転置原理による合成アルゴリズムの導出 FPS 合成・逆関数の解説（１）逆関数と Power Projection [yukicod
はじめに 本記事は三重大学 計算研 Advent Calendar 201916日目です。 少し前までAtCoderに参加していましたが、最近やる気が出なかったのでやる気を出すためかつストレスフリーになるように自動提出やテストケースのチェック等をできるプログラムを書きました。ソースコードはhttps://github.com/flow6852/atsubmit に置いてあります。 本記事はその時に使った様々なモジュール内で定義された関数の使い方や設計のメモを残すこと、筆者が初めて知ったことを書いておくことが目的です。 おことわり 本記事はHaskellを使ってAtCoderのパフォーマンスを向上させる内容ではなくコンテストに快適に参加するためのツールを作成したという内容です。 汚い実装(モナドの恩恵を感じられない...)です 参考文献が結構多いので必要な部分で適宜参考文献を載せていき、最後
この記事ではRustのproconio::input! macroについて書きます。 documentやtest caseで想定されているユースケースをどうやって実現しているのかを追っていきます。 versionは記事を書いている時点で最新のp-v0.4.3 を対象にしています。 proconio::input! とはproconio とは以下のREADME にあるように競技プログラミングで利用されることを意図したIO libraryです。 Easy IO library for competitive programming. proconio provides an easy way to read values from stdin (or other source). The main is input! macro. input! は出題としてstdinからあたえられる入力を読み
この記事は、競プロ Advent Calendar 2021 3 日目の記事です。 飛ばしていい雑談 現在水色コーダーのH20と申します。 2020年の5月よりAtcoderのコンテストに参加してから、競技プログラミングという沼にハマり続け、参加回数はすでに80回を超えました。 沼にハマり続けるのは何も競技プログラミングだけに限りません。WA(不正解)とTLE (実行時間超過)の沼にもハマり続けました。 何度「解法は合ってた、解けてたはずなのに！」という後悔と、「ぎりぎりバグを見つけて通せた！」という喜びがあったでしょうか1。 実装ミスは特にこの半年の上がっては下がりを繰り返す気にくわないほど横ばいなレート推移となる一因です2。 とにかく今悩んでいる問題の AC (正解)を目指す。 解法は合ってるはずなのに何故か提出するとWAになってしまう状況や、ペナの数はもう気にしないとにかくこの一問を
ゴールデンウィークの有志コンテストなどで多く出題され、話題になったので記事を書こうと思います。 対象レートはだいたい緑～水色（最後のほうは青くらいまで）です。実際のAtCoderの問題を使って説明していくので、ネタバレになる点はご了承ください。 「答えを決め打つ」タイプの二分探索とは この記事で扱うのは、以下のような問題＆解法です。 「○○という条件を満たす の最小値を求めよ」という問題において、 「ある値 が与えられたとき、○○を満たすことはできるか？」という判定問題を考え、 その判定問題を繰り返し解くことでYesになる とNoになる の間の境界を特定し、元の問題の答えを求める解法。 もちろん最小値ではなく最大値である場合もあります。実際にいくつか問題を見ていきましょう。 問題例1：花束（ARC050-B） B - 花束 解法 持っている花から2種類の花束を作り、その合計数を最大化する問
ac-predictor-minimal は古いっぽいので、 ac-predictor を使ったほうがよいかも
VSCodeとdevcontainerを使い、RustでAtCoderのコンテストに参加するための環境を整えました。 その際の手順メモです。 Dockerfileを用意する VSCodeとDockerを使える状態から始めます。 まずは、devcontainer用のDockerfileを作ります。 rust.Dockerfileというファイル名で、プロジェクト直下に置きます。 ファイルの内容は以下のようにしました。 cargo-compete は、競技プログラミング用のcargoのツールです。 1.42.0 は、2023年2月18日現在AtCoderが対応しているRustのバージョンです。 「最初から rust:1.42.0 系のイメージを使えばよいのでは？」→ そのバージョンでは cargo-compete のインストールが困難でした。 devcontainerを用意する VSCodeにD
VSCodeで競技プログラミング 〜インストールからショートカットで自動サンプルテスト&提出まで〜 • knshnbのブログ
はじめに この記事はCompetitive Programming (1) Advent Calendar 2019の20日目として書かれました。 競技プログラミング勢は、コーディングの際のツールを使いこなしている人とそうでない人の差が大きいイメージがあります。 昔ICPCのチームメイトがメモ帳でプログラミングをしていた話を思い出し、そういった人の助けに少しでもなればいいなと思いこの記事を書きました。 なお、競プロには様々な向き合い方があり、こういうツールを必ず導入するべきだとはもちろん思っていません。 強い人でも全く使っていない人もいるので自分の好きなスタイルでやっていくのが一番だと思います。 今回の記事のメインターゲットは、 コンパイル (→ 実行 → サンプルをコピー → サンプルをペースト → 目で出力があっているか確認) *3~4回 → ソースコードをコピー → ソースコードをペ
ABC237のA,B,C,D,E,F問題を、Python3でなるべく丁寧に解説していきます。 ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。 シンプル：余計なことを考えずに済む 実装が楽：ミスやバグが減ってうれしい 時間がかからない：パフォが上がって、後の問題に残せる時間が増える ご質問・ご指摘はコメントかツイッター、マシュマロ、Discordサーバーまでお気軽にどうぞ！ Twitter: u2dayo マシュマロ： https://marshmallow-qa.com/u2dayo ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share Discordサーバー（質問や記事の感想・リクエストなどどうぞ！） : https://discord.gg/jZ
GitHub - E869120/kyopro_educational_90: 2021/3/30 ～ 2021/7/12 に行われる企画「競プロ典型 90 問」の問題・解説・ソースコードなどの資料をアップロードしています。
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
「ゲームで学ぶ探索アルゴリズム実践入門」のサンプルコードでAtCoderの問題を解いてみた はじめに どうもこんにちは、thunderです。 私事ではありますが、2023/2/18に「ゲームで学ぶ探索アルゴリズム実践入門～木探索とメタヒューリスティクス」という技術書を出版しました！ amazon https://www.amazon.co.jp/dp/4297133601/ 技術評論社 https://gihyo.jp/book/2023/978-4-297-13360-3 本書の魅力はspeakerdeckにアップロードしたスライドにまとめているので、御覧いただけると幸いです。 さて、本書のサンプルコードはサポートページからダウンロードできるのですが、学んだ内容を活かして何かプログラムを書きたい！という方もいらっしゃるのではないかと思います。 本記事では、このサンプルコードを用いて実際に
PyCon JP 2019 プロポーザル採択速報/Proposal selection bulletin PyCon JP 2019 へ多くのプロポーザル応募ありがとうございました。そして、おまたせしました。採択会議の結果を発表します。 全体のトーク応募数は260件でした. 全体で47本受け入れをしました。採択率は18.1%でした。 今回、採択できなかったトークの応募者の皆様、 今年は多くの応募がありトークの採択は非常に悩みました。LT、ポスター、ビギナーセッションの応募をお待ちしています。 Thank you for all your proposal submissions to PyCon JP 2019. We're excited to announce the results of our proposal review meeting. In total number, we
【2021/10/27追記】本記事のテーマについては，次のpaizaのページが参考となるかもしれません．値取得・出力サンプルコード：https://paiza.jp/guide/samplecode いやもう，FizzBuzz問題の代わりに『コードが書けないプログラマ志願者を見分ける手法』にしてもいいほどに（それは言い過ぎ）． 以前，『サンプルコードは入力と出力をセットにして作成してから実行を確かめる』といったことを述べている記事を書き，また，その趣旨に基づく『最初のサンプルプログラム』集みたいな記事も作成しました．これらを踏まえ，AtCoderあたりでは定番の，値入力部分のサンプルプログラムをいろんな言語で書き始めてみたのですが…いやあ，めんどくさい．入力スタイルに合わせるのはもちろん，言語固有の工夫が必要だったり，入力後の処理によってケースバイケースとなったり．"Hello, Worl
oj/docs/getting-started.ja.md at master · online-judge-tools/oj
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
Ruby Junk Scripts
トライ トライは文字列の集合を表すのに都合のよいデータ構造です。トライの語源は、「検索 (retrieval) 」という言葉の真ん中 (trie) に由来しています。トライは木構造の一種であり、根から葉までの経路がひとつの単語に対応します。次の図を見てください。 図 : 文字列の集合を表したトライ 上図は文字列の集合をトライで表現したものです。ここでは葉を $ で表しています。たとえば、葉 $7 までたどると、それは "THEN" という文字列を表しています。また、文字列 "THE" をトライから探す場合は、節を順番にたどっていって、葉 $6 に達した時点で "THE" を見つけることができます。もし、節 E の子に葉 $6 がなければ、THE はトライに存在しないことになります。 ●参考文献 A.V. Aho, J.E. Hopcroft, J.D. Ullman, 『データ構造とアルゴ
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
AtCoder Unit Test を使って、動作確認を簡単に！ - Qiita
AtCoder Companions
AtCoderで年齢と使用プログラミング言語の相関を調べてみた - Qiita
Rubyで競技プログラミング bit演算の基礎まとめ - ls /asapon/blog
AtCoderの復習を手助けするWebサイトを作った（AtCoder-Ebbing） - Qiita
トポロジカルソートのアルゴリズム（閉路のない有向グラフDAGのソート） | アルゴリズムロジック
AtCoderの参加回数が多い人ほどレーティングが高い？ - 唯物是真 @Scaled_Wurm
Goで競技プログラミングするときのテクニック - Qiita
AtCoder Rating Simulator
(なるべく)HaskellでAtCoderに参加したい - Qiita
⚙️ proconio::input!の仕組みを追ってみる | Happy developing
【Python版】AtCoderのコンテスト中に「問題が解けない！」となった時に読む記事 - Qiita
「答えを決め打つ」タイプの二分探索を使いこなそう - ARMERIA
AtCoderをするとき、入れておくといい拡張機能など - ま
RustのAtCoder環境構築手順（devcontainer編）
【AtCoder解説】PythonでABC237のA,B,C,D,E,F問題を制する！ - Qiita
# 「ゲームで学ぶ探索アルゴリズム実践入門」のサンプルコードでAtCoderの問題を解いてみた - Qiita
PyCon JP2019 プロポーザル採択速報/Proposal selection bulletin
『N個の値を入力するプログラム』が意外とめんどくさい