atcoder.jp 問題 消費税T%のとき課税後の整数値として現れないN番目のものを出力せよ。 制約 解説 ある自然数Aがあって、T*A の結果、100の位へ繰り上げがあるなら、(100+T)*A/100-1 は登場しない整数値である。 なぜなら、T*A で100の位への繰り上げが生じ…

atcoder.jp 問題 以下の条件を満たす長さNの数列Aを構築せよ。 数列のどの2つの要素も互いに素ではない 解説 まず、どの2つの要素も互いに素ではなく、一方で全体のgcd は1である、という点に着眼し、数列の要素を3つのグループに分けることを考える。 グル…

atcoder.jp 問題 Nが のようにK分割されている。Mが与えられるので同様にK分割し、その結果を整数列Bとしたとき、 が最小となるようなものを1つ出力せよ。 制約 解説 数列Bの要素として実数を許すなら、 とすることで、 を全て0にすることができる。 しかし…

atcoder.jp 問題 N個の要素からなる集合A の2つの異なる部分集合で和の mod 200 の値が等しいものが存在するかを判定し、存在する場合はその2つの集合を出力せよ。 制約 公式解説 公式解説は、鳩ノ巣原理により の場合は必ず解が存在することから、 の範囲に…

高難度帯の部分問題として出てくるので実装を置いておく。 実装 以下の実装は、訪れた順に頂点を採番していく。 /// オイラーツアー struct EulerianTrail{ vector<int> order; EulerianTrail(vector<vector<int>>& G, int root=0){ int n=G.size(); order.resize(n); int cur</vector<int></int>…

過去問埋めしてて、トポロジカルソートで解く問題に当たって面白かった↓。 atcoder.jp 良い機会なので、改めて実装についてまとめておこうと思う。 前提 トポロジカルソートとは、閉路無し有向グラフ(DAG)において、どの頂点もその出力辺の先の頂点より前に…

エラトステネスの篩と、それを利用した素因数の高速列挙の実装をライブラリ化した。（どちらかというと後者の実装を残す目的で作った） 前提 整数nまでの素数の列挙を高速に行うアルゴリズム O(nloglogn) https://mathtrain.jp/eratosthenes https://detail.…

前提 Trie木は、複数の単語（文字列）を登録でき、ある文字列（またはそのprefix）が登録済みであるかを高速に検索できるデータ構造 基本的な機能はシンプルに、insert / searchの2つだけ 実態は有向木 基本的な動作は、単語のprefixが同じならNodeを共有し…

二分探索と比べて、区間の内分点の取り方やら、下に凸か上に凸かやら、地味に考えることが多いので汎用性を目指してライブラリ化してみた。 前提 三分探索とは、ある区間[l, r]において、極値がただ一つだけ存在するとき、その極値の近似値を区間の長さをnと…

これは何 最近コンテストで、入力値が小数第4位程度まで与えられ、その入力値を素直にdoubleで受け取って計算すると丸め誤差で WA となるような問題が散見されるようになった。 （直近の問題だと ABC 191 D Circle Lattice Points がそう） atcoder.jp この…

要求される度に、uniqueやらeraseやら、1-indexやらの箇所で微妙に考えてしまうので、この際ライブラリ化しておく。 ※ 転倒数には、i < j でかつ、a_i > a_j であるとき転倒とする場合と、a_i >= a_j であるとき転倒とする場合の2種類があり、以下の実装は前…

他ライブラリ（転倒数等）で活用されることがあるので置いておく。 前提 Fenwick Treeとも 競プロにおいては、BITでできることは以下の2点であると抑えておこう。 累積和テーブルの更新: add 指定した区間の累積和の計算: sum 機能を限定することで扱いやす…

今まで文字列照合系問題は、DP(LCS)で頑張っていたけど、持っていたら便利そうだと思ったのでライブラリを用意してみた。 前提 Z-Algorithmとは、最長共通接頭辞の長さを線形時間で求めるアルゴリズム。 文字列の長さをnとして、O(n2)を、O(n)に改善できる …

クラスカル法など、他ライブラリから呼ばれることがあるので実装を置いておく。 前提 グループの管理を高速で行うことができるデータ構造 実態は木（森）になっている ある状態から、グループを併合することができ、分割することはできない 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 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>…

atcoder.jp DPについて学びになる問題だったので、メモとして残す． 考えたこと DPで解く 実装 参考にさせていただいた実装 考えたこと 最初考えたのは、各拠点のモンスターは、自身が攻撃できる街の中で勇者の撃退可能数が最も少ない街を貪欲的に選んでいけ…

atcoder.jp 制約 考えたこと 実装 制約 1 ≤ | S | ≤ 100 1 ≤ K ≤ 109 考えたこと SとKの制約から、文字列を連結させてから操作回数を数えようとすると、O( | S | * K ) となり間に合いません． そのため、Sに対して、どの隣り合う2文字も相異なるような操作…

atcoder.jp 題意 制約 考えたこと 実装 感想 題意 2つの正整数A、Bが与えられるので、その公約数のうちいくつかを選ぶ。 このとき選んだ値は、それぞれが互いに素である必要がある。 選べる公約数の最大の個数はいくつか？ 制約 1 <= A, B <= 1012 考えたこ…