行列演算を活用した高速冪乗法の実装と応用
行列の構造と基本演算
行列は \(m\) 行 \(n\) 列の数値配置として定義され、各成分を \(a_{i,j}\) で表すとき、行列 \(\mathbf{A}\) は以下の形式で記述される。
\[
\mathbf{A} = \begin{pmatrix}
a_{1,1} & \cdots & a_{1,n} \\
\vdots & \ddots & \vdots \\
a_{m,1} & \cdots & a_{m,n}
\end{pmatrix}
\]
特殊な行列として「単位行列」が存在する。これは正方行列で ...
5月16日 17:00 投稿
POI2009 PRZ：配列の等価性を判定する階層化ハッシュ手法
問題の定義
本問題は、2つの正整数列 X と Y に対して、再帰的に定義された関数 F(X, Y) の真偽を判定することを目的としています。与えられた関数の構造は以下の通りです。
bool Evaluate(const std::vector<int>& X, const std::vector<int>& Y) {
if (GetUniqueSet(X).size() != GetUniqueSet(Y).size()) return false;
if (GetUniqueSet(X).si ...
5月14日 14:29 投稿
Codeforces Round 938 Div.3 問題セット解説とアルゴリズム実装
問題A：ヨーグルト購入の最適化（貪欲法）
課題の概要
1本あたりの価格が single 円、2本セットの価格が pair_cost 円のヨーグルトが販売されている。合計 n 本を購入する際、最小の総支出額を求める。
実装アプローチ
セット購入の単価（pair_cost / 2）と通常価格を比較する。セット単価が通常価格より安価な場合は、可能な限りセットで購入し、余った分を単品で処理する ...
5月14日 06:06 投稿
Codeforces Round 859 Div.4 のアルゴリズム解法と実装解説
問題 A: Plus or Minus
問題概要
3つの整数 a, b, c が与えられます。演算子として + または - のいずれかを用いて a と b を結合した結果が c と一致する場合、該当する演算子を出力してください。必ずいずれか一方のみが成立することが保証されています。
解法のアプローチ
単純な条件分岐で対応可能です。和 a + b が c と等しければ + を、等号が成立しなければ必然的 ...
5月13日 22:32 投稿
AtCoder Beginner Contest 363 解説：アルゴリズム設計と実装
問題A：数値間隔の算出
入力値 $R$ が属する百の位区間を特定し、その区間の上限値との差分を出力する問題です。条件分岐を用いる代わりに、整数除算による切り上げ演算の特性を活用することで、簡潔な式に変換可能です。
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int current_rat ...
5月13日 15:46 投稿