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 投稿
深さ優先探索（DFS）の実装と応用
基本原理：
深さ優先探索は、開始ノードから出発し、一つの分岐を深く進み続けます。葉ノードまたは進めなくなったノードに到達するまで探索を続けます。
探索が葉ノードまたは進めなくなったノードに到達した場合、未探索の前のノードに戻り、他の分岐の探索を続けます。
既に訪問したノードをマークすることで、同じ経路での重複訪問を避けます。
DFSアルゴリズムのス ...
5月31日 11:33 投稿
配列操作と木構造上の色付け問題の解法
配列内要素の隣接関係判定
与えられた配列において、特定の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面ダイスとコインを使用するゲームの勝率を求める。初期値としてダイスを振り、値が1～K-1の場合コインを繰り返し振る。表が出れば値が倍増、裏が出れば0になり、0で敗北またはK以上で勝利となる。
解法
初期値1～nについて、勝利条件は値が2^x倍されてK以上になることである。各初期値の勝率は1/2^xで、n個の初期値の勝率を合計後nで除算する。
#includ ...
5月26日 00:39 投稿
アルゴリズム競技プログラミング問題集
基本的なアルゴリズム問題集
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 投稿
Kruskal再構築木の学習メモ
前提知識
Kruskal最小/最大全域木アルゴリズム、ダブリング（Binary Lifting）の知識を前提とします。
Kruskal再構築木を構築すると、最小全域木上の2点間のパスの最大重み、および重み ≤ w の辺のみを通って到達可能な点の集合を O(log N) で求めることができます。
近年の競技プログラミングでは出題頻度は控えめですが、該当する問題に遭遇した際に非常に強力なツ ...
5月19日 05:15 投稿
最小生成木の実装：Prim法とKruskal法の比較と実装例
グラフ理論における最小生成木を求める主要なアルゴリズムとして、Prim法とKruskal法がある。n個の頂点とm個の辺を持つグラフを対象とする。
アルゴリズムの特性
Prim法は隣接行列で表現された密グラフに適しており、基本実装の時間計算量はO(n²)である。優先度付きキューを用いてO(n log n)に改善可能である。
Kruskal法は疎グラフに向いており、辺の数mに対してO(m log ...
5月16日 03:06 投稿
グラフ理論における第二最短経路
前提知識
グラフの表現方法、最短経路探索アルゴリズム、幅優先探索(BFS)の理解が必要です。
第二最短経路の分類
一般第二経路（同一辺の重複利用可能）
単純第二経路（同一辺の重複利用不可）
厳密/非厳密第二経路（最短経路と等価/非等価）
一般第二経路
配列の最大値・次大値探索と類似した手法を用います。各頂点について最短距離と第二短距離を同時に管理します。 ...
5月14日 18:44 投稿