C++文字列操作マスタリ
基本操作
str.size(); || str.length();//文字列の長さを返す
str1.swap(str2); || swap(str1, str2);//str1とstr2を交換（前者推奨）
str.substr(pos, len);//pos位置からlen文字の部分文字列を取得
reverse(str.begin(), str.end());//文字列を反転
string str(count, ch);//ch文字をcount回繰り返した文字列を生成
sort(str.begin(), str.end());//文字列をソート
代入 ...
7月18日 19:48 投稿
動的計画法における最長増加部分列モデル
動的計画法を用いた最長増加部分列（LIS）のアルゴリズムとその応用について解説します。最長増加部分列は、与えられた数列の中から単調に増加する部分列の中で最も長いものを求める問題です。このモデルは、様々な最適化問題に応用可能です。
最長増加部分列の基本概念
最長増加部分列問題は、与えられた数列において、各要素が前の要素よりも大きくなるように選んだ部分 ...
7月18日 19:13 投稿
C++における例外処理の基本とベストプラクティス
例外処理の概要
例外処理は、C++プログラミングにおける重要なエラーハンドリングメカニズムです。戻り値をチェックする従来の方法に比べ、例外はエラーを自動的に伝播させ、メインロジックからエラーハンドリングコードを分離し、複数の関数にまたがる制御フローを処理できます。これにより、各関数で戻り値を繰り返しチェックし、エラーステータスを渡す必要がなくなりま ...
7月18日 01:06 投稿
HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）解説
A - Yay!
長さが3以上の文字列中に2種類の文字が含まれており、そのうち1つはちょうど1回だけ出現する。その位置を1-indexedで出力せよ。
最初の文字が一意であれば、残りにその文字は存在しない。そうでなければ、最初の文字とは異なる最初の文字を探せばよい。
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
...
7月18日 00:29 投稿
プログラミングコンテスト初級：典型問題の実装パターン
問題1：文字列の反復生成
文字 'L'、'o' を N 回繰り返した文字列、そして "ng" を連結して出力する問題です。ループを使用せず、文字列コンストラクタを活用することで簡潔に記述できます。
#include <iostream>
#include <string>
int main() {
int repeat;
std::cin >> repeat;
std::string result = "L" + std::string(repeat, 'o') + ...
7月17日 16:04 投稿
ABC356コンテスト問題解説
問題A
問題の指示に従ってシミュレーションを行います。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int size, left, right;
cin >> size >> left >> right;
vector<int> sequence(size);
for (int i = 0; i < size; ++i) {
sequence[i] = i + 1;
} ...
7月17日 03:05 投稿
C++の定数最適化テクニック ─ 高速化のための実践的手法
C++プログラムにおいて、関数呼叫やループ、回路上的の最適化だけでなく、定数レベルでコードを高速化する手法があります。以下では、実際に効果が期待できる定数最適化の手法を解説します。
共用体（union）の活用
基本的な定義
共用体は複数のメンバーが同一のメモリ領域を共有する特殊なクラスです。定義は以下のようになります（関数内 maupun 関数外どちらでも定義可 ...
7月16日 23:36 投稿
洛谷100題チャレンジ (5/100)
洛谷100題チャレンジ (5/100)
P1002 [NOIP2002 普及組] 馬避け - 洛谷 | コンピュータ科学教育新生態
long long型を使用しないと問題発生注意!!!
馬の制御点を全てマークし、残りは通常通り转移すればよい
\(dp[i][j] += dp[i - 1][j] + dp[i][j - 1]\)
\(i=0||j=0\)の場合、左または上からのみ转移可能
using i64 = long long;
using namespace std;
typedef pair Pair ...
7月16日 23:20 投稿
バックトラックアルゴリズムの理論と組み合わせ問題の実装
バックトラック法の基本概念
バックトラック法は探索手法の一種で、再帰処理と密接に関連しています。再帰処理を行う際には必ずバックトラックが発生するため、バックトラックは再帰の副産物と言えます。
バックトラック法の効率性
バックトラック法は本質的に全探索アルゴリズムであり、効率的とは言えません。ただし、枝刈り(pruning)を適用することで多少の効率改善 ...
7月16日 16:50 投稿
プログラミング問題の解法メモ
P2671 [NOIP2015 初級者部門] 和の計算
この問題では、xとzの色が同じで偶奇が一致する条件を満たす要素の組み合わせで和を計算する必要がある。単純なO(n²)の解法では時間制限に間に合わないため、色と偶奇で分類する方法を採用。
色ごとに偶数・奇数グループを分けて集計し、各グループ内で次の式を適用：
ans += 要素番号 × (該当色グループ内の要素数 - 1) × 値 + 要素 ...
7月15日 23:21 投稿