クラスカル法など、他ライブラリから呼ばれることがあるので実装を置いておく。 前提 グループの管理を高速で行うことができるデータ構造 実態は木(森)になっている ある状態から、グループを併合することができ、分割することはできない UnionFind木の機…
前提 いずれも発想は貪欲法である。 クラスカル法 実装内容の理解についてはクラスカル法の方が楽 頂点数に対応する大きさのUnionFind木を用意する グラフの辺を、重みの小さい順に見ていき、(u, v)がまだ同じグループに属していないならばその辺を採用する…
前提 ダブリング手順 dp[i][j]:=頂点iの2j個上の頂点 iは頂点数nに対して、log_n 初期化: まずdpを-1で初期化したのち、dp[0][j]、つまり1個上のノードを登録する 以降、dp[i+1][j]=dp[i][dp[i][j]] で更新 ダブリングのわかりやすい解説 satanic0258.hatena…
セグメント木を抽象化したライブラリ(C++)を作成したのでまとめておく。 前提 セグメント木の実態は完全二分木 要素数nを扱いたいならn以上の2冪を葉の数とし、その数をwとすると、全体の要素数は2*w-1個となる 完全二分木において、要素i(>0)の親は(i-1)/2…
atcoder.jp 解説 想定解は包除原理だが、Nが小さいので動的計画法でも間に合う。 dp[i][j][k] := i桁目まで確定していて、0を使ったかがj、9を使ったかがkである状態のときの通り数 dpテーブルをこのように定義すると、テーブル更新にかかる計算量は、O(N * …
atcoder.jp bit全探索について、まさに典型と思える問題だったのでメモとして残す。 前回のABC146 Cは二分探索で、今回はbit全探索。まさに入門アルゴリズムの典型がCに配置されてると感じた。 #include <bits/stdc++.h> using namespace std; template<class T> inline bool chmax(T</class></bits/stdc++.h>…
atcoder.jp 期待値DPの問題 難しかったので、要復習としてメモ. 実装は以下の記事を参考にほぼ写経させていただきました. www.hamayanhamayan.com qiita.com 実装 #include <bits/stdc++.h> using namespace std; #define rep(i, m, n) for (int i = (int)(m); i < (int)(</bits/stdc++.h>…
codeforces.com DPに関して学びになる問題だったので、メモとして残す. 漸化式 dp[i] := s[i]まででn or uが連続する区間においていたずらできる回数 この問題で漸化式を上記の様に定義すると、dpテーブルの遷移はフィボナッチ数列と同じになることに気付く…
atcoder.jp DPについて学びになる問題だったので、メモとして残す. 考えたこと DPで解く 実装 参考にさせていただいた実装 考えたこと 最初考えたのは、各拠点のモンスターは、自身が攻撃できる街の中で勇者の撃退可能数が最も少ない街を貪欲的に選んでいけ…
atcoder.jp 制約 考えたこと 実装 制約 1 ≤ | S | ≤ 100 1 ≤ K ≤ 109 考えたこと SとKの制約から、文字列を連結させてから操作回数を数えようとすると、O( | S | * K ) となり間に合いません. そのため、Sに対して、どの隣り合う2文字も相異なるような操作…
仕事でIntelliJを使い始めたのでショートカットなどをまとめてみました。 ソースはこれです↓ IntelliJ IDEAハンズオン――基本操作からプロジェクト管理までマスター作者:山本 裕介,今井 勝信出版社/メーカー: 技術評論社発売日: 2017/11/08メディア: 大型本 J…
atcoder.jp 題意 制約 考えたこと 実装 感想 題意 2つの正整数A、Bが与えられるので、その公約数のうちいくつかを選ぶ。 このとき選んだ値は、それぞれが互いに素である必要がある。 選べる公約数の最大の個数はいくつか? 制約 1 <= A, B <= 1012 考えたこ…
FORCIAさん主催の競技プログラミングオンサイトコンテストに参加してきました。 forcia.connpass.com ちなみに、今回がオンサイトコンテスト初参加です。 オンサイトイベントへの参加は初めてなのですが、明日はFORCIAさん主催のゆるふわオンサイトに参加し…