アルゴリズムとデータ構造8 - 線形篩による一般乗法関数の計算
概要
競技プログラミングの問題を解く中で、線形篩を用いた一般乗法関数の計算方法を学んだので、その説明を行う。
前提知識
乗法的関数：任意の互いに素な整数p,qについてf(p)×f(q)=f(pq)を満たす関数。
完全乗法的関数：任意の整数p,qについてf(p)×f(q)=f(pq)を満たす関数。
線形篩：O(n)でn以下の素数を列挙するアルゴリズム。
適用範囲
任意の素数pに対して、f(p)およ ...
6月10日 19:05 投稿
2023年伝智杯プログラミング競技予選ソリューション
文字列連結
2つの文字列を入力として受け取り、連結して出力します。空白を含む可能性があるため、getline関数を使用します。
#include <iostream>
#include <string>
using namespace std;
int main() {
string a, b;
getline(cin, a);
getline(cin, b);
cout << a + b;
return 0;
}
最小差分値
整数配列内の隣接要素間の最小差 ...
6月4日 19:44 投稿
AtCoder初心者コンテスト443 解説
D - パンライン問題
この問題は数学的に抽象化することで簡単に解くことができます。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll t;
cin >> t;
while (t--) {
ll n, sum = 0;
cin >> n;
vector<ll> arr(n);
for (auto &x : arr) {
cin >> x;
sum += x; ...
6月1日 19:15 投稿
競技プログラミング問題集 SMU Spring 2023
A. 重複要素の削除
与えられた数列から重複要素を削除し、最初に出現した要素のみを保持するアルゴリズム。
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> removeDuplicates(const vector<int>& nums) {
unordered_map<int, int> countMap;
vector<int> result ...
5月29日 14:24 投稿
AtCoder Beginner Contest 389 解法解説
A - 9x9
問題概要
1桁の数字同士の乗算結果を求める。
解法
入力文字列から数値を抽出して掛け算する実装を行えばよい。
実装コード
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve() {
string input;
cin >> input;
int a = input[0] - '0';
...
5月28日 14:34 投稿
配列操作と木構造上の色付け問題の解法
配列内要素の隣接関係判定
与えられた配列において、特定の2つの要素xとyが隣接しているかどうかを判定する問題です。
#include<iostream>
#include<vector>
using namespace std;
bool checkAdjacent(vector<int>& arr, int target1, int target2) {
int n = arr.size();
for(int i = 0; i < n; i++) {
if(arr[i] == target1) {
...
5月26日 06:39 投稿
競技プログラミング問題集：幾何、貪欲法、データ構造
円の面積計算
円の面積を計算する際にはπの精度に注意が必要である。以下のコードは入力値nを用いて円の面積を計算する。ここで円の半径はnに関係する（n*n*0.5をπで割る）。
#include<iostream>
#include<cmath>
using namespace std;
int main() {
double input;
cin >> input;
double area = input * input * 0.5 / M_PI;
printf("% ...
5月23日 22:12 投稿
Codeforces ラウンド 970 (Div. 3)
A. サクラコの試験
解法
全探索で解く。
コード
#include <iostream>
using namespace std;
void solve() {
int a, b;
cin >> a >> b;
for (int i = 0; i n;
string s;
cin >> s;
int m = sqrt(n);
if (m * m != n) {
cout a >> b;
long long l = 1, r = 2e9, ans = 0;
while (l
5月22日 19:19 投稿
プレフィックス和と差分アルゴリズムの理解とC++実装
プレフィックス和アルゴリズム
基本概念
プレフィックス和は配列処理技術の一種で、事前計算により部分区間の和をO(1)で取得可能にします。入力配列をdataとすると、プレフィックス配列prefは次のように定義されます：
pref[i] = data[0] + data[1] + ... + data[i]
pref[0] = data[0]
構築方法
C++による実装例：
vector<int> constructPrefixArray(const vector& ...
5月21日 01:20 投稿
アルゴリズム競技プログラミング問題集
基本的なアルゴリズム問題集
1. 立方体の体積計算
辺の長さa, b, cが与えられた時、立方体の体積を計算します。
#include <iostream>
using namespace std;
int main() {
int length, width, height;
cin >> length >> width >> height;
cout > exponent;
cout countB;
for(int i=0; i<countA+countB; i++) {
cout > n;
whil ...
5月20日 03:45 投稿