前回の記事では方法 1 について記述しました。 今回はそれを発展させた方法 2 について記述します。 方針 方法 2 では、方法 1 の状態からさらに、子ノードが 1 個のノードを省略します。 下図は、クエリ (1) によりインデックス の値が更新されたときの例で…
概要 通常のセグメント木では、管理対象の列の項数 を固定して完全二分木を構築するため、初期化に時間計算量および空間計算量 を要し、1 回のクエリあたり時間計算量 を要する。 したがって、 として利用できる値には計算機資源上の制限があり、列のインデ…
重み平衡二分木 (weight-balanced binary trees) を C# で実装したライブラリ WBTrees (GitHub) の初版 v1.0 をリリースしました。 主な機能は次の通りです: (1) インデックスによる操作 (取得・更新・挿入・削除) をすべて 時間でできる List WBList<T> クラ</t>…
第6回 アルゴリズム実技検定 (PAST) の問題 M - 等しい数 の解説です。 この記事では、範囲更新クエリ (RUQ) または平衡二分探索木を利用した解法を紹介します。 問題文はリンク先を参照してください。 atcoder.jp 解法の全体構成 まず、解法の全体構成は次…
// Competitive Programming (1) Advent Calendar 2020 および C# その2 Advent Calendar 2020 の 12 日目の記事です。 このシリーズでは、C#、とくに LINQ で簡潔に書ける競技プログラミングの問題を集めて記事にしています。 Advent Calendar ということで…
2020年3月の AtCoder の問題を、LINQ (C#) を使って解いていきます。全11問。 問題文はそれぞれのリンク先を参照してください。 ABC 157 B - Bingo 選ばれた数をハッシュセット HashSet<int> に格納しておきます。 縦 (3種類) ・横 (3種類) ・斜め (2種類) のいず</int>…
2020年2月の AtCoder の問題を、LINQ (C#) を使って解いていきます。全8問。 今回は Rated コンテストのほか、JOI 2019/2020 本選も対象としています。 問題文はそれぞれのリンク先を参照してください。 JOI 2019/2020 本選 A - 長いだけのネクタイ (Just Lo…
2020年1月の AtCoder の問題を、LINQ (C#) を使って解いていきます。全8問。 問題文はそれぞれのリンク先を参照してください。 第6回 ドワンゴからの挑戦状 予選 A - Falling Asleep 曲のリストを列挙し、曲名が X に一致するまでスキップします。 その一致…
競技プログラミングにおける典型問題は、新たに学習したアルゴリズムを実装して試すとき、 あるいはライブラリを作成して試すときなどに利用すると最適です。 これまでに経験した範囲で、分野ごとに典型問題と思われるものを以下にまとめました。 AtCoder の…
しかし、アルゴリズム実技検定 (PAST) では「1からプログラムを作成する能力を問う」と標榜しているわけですから、そんな飛び道具に頼った実装は許されないと容易に想像できます。すなわち、ビット演算を駆使してこの問題に取り組むのです。
しかし、アルゴリズム実技検定のキャッチフレーズは「1からプログラムを作成する能力を問う」です。したがって、そんな単純な実装で許されるはずはなく、出題者の想定解法は「ビット演算を使って四則演算を実装する」です (断言)。
This Blog's Concept In programming, the solution is not always unique for something you want to achieve. I usually try multiple implementations when I find them. In competitive programming such as Codeforces and AtCoder, I think that submi…
このブログのコンセプト プログラミングにおいては、何か実現したい対象があったとして、それを実現する方法は一つだけとは限りません。 筆者は普段から、複数の実装方法を見つけた場合には試すようにしています。 AtCoder や Codeforces のような競技プログ…