1. 約数の個数
2. 最大部分行列問題
総当たり法による解法
#include <iostream>
using namespace std;
// 部分行列の合計を計算
int grid[40][30];
long long maxSum;
int main() {
// 30x20のグリッドを読み込む
for(int row = 1; row <= 30; row++) {
for(int col = 1; col <= 20; col++) {
cin >> grid[row][col];
}
}
// 5x5の部分行列の合計を計算
for(int startRow = 1; startRow <= 26; startRow++) {
for(int startCol = 1; startCol <= 16; startCol++) {
long long currentSum = 0;
for(int offsetRow = 0; offsetRow < 5; offsetRow++) {
for(int offsetCol = 0; offsetCol < 5; offsetCol++) {
currentSum += grid[startRow + offsetRow][startCol + offsetCol];
}
}
maxSum = max(maxSum, currentSum);
}
}
cout << maxSum << endl;
return 0;
}
3. 奇数の出現回数
#include <iostream>
using namespace std;
int digitCount[100000+10];
int main() {
string inputStr;
cin >> inputStr;
// 文字列を数字配列に変換
for(int index = 0; index < inputStr.size(); index++) {
digitCount[index] = inputStr[index] - '0';
}
int oddCount = 0;
for(int index = 0; index < inputStr.size(); index++) {
if(digitCount[index] % 2 == 1) {
oddCount++;
}
}
cout << oddCount << endl;
return 0;
}
4. 最大のY字形
#include <iostream>
using namespace std;
char matrix[1000+10][1000+10];
int main() {
int rows, cols;
cin >> rows >> cols;
int maxSize = 0;
// 行列の読み込み
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
cin >> matrix[i][j];
}
}
// Y字形の探索
for(int centerY = 1; centerY < rows-1; centerY++) {
for(int centerX = 1; centerX < cols-1; centerX++) {
int currentSize = 0;
// 可能な最大サイズを計算
int maxPossibleSize = min(min(centerY, rows-centerY-1), min(centerX, cols-centerX-1));
for(int size = 1; size <= maxPossibleSize; size++) {
// Y字形の各部分が同じ文字かチェック
if(matrix[centerY][centerX] == matrix[centerY-size][centerX-size] &&
matrix[centerY][centerX] == matrix[centerY-size][centerX+size] &&
matrix[centerY][centerX] == matrix[centerY+size][centerX]) {
currentSize++;
} else {
break;
}
}
maxSize = max(maxSize, currentSize);
}
}
cout << maxSize << endl;
return 0;
}
5. 区間カウント
#include <iostream>
using namespace std;
int main() {
int validPairs = 0;
// 効率的な計算方法
for(int firstNum = 0; firstNum <= 90; firstNum++) {
for(int secondNum = firstNum + 10; secondNum <= 100; secondNum++) {
validPairs++;
}
}
cout << validPairs;
return 0;
}
6. 最小ステップ数
#include <iostream>
using namespace std;
int main() {
int targetValue;
cin >> targetValue;
int steps = 0;
// 3で割り切れる場合は割る、そうでなければ1ステップ余分に必要
if(targetValue % 3 == 0) {
steps = targetValue / 3;
} else {
steps = targetValue / 3 + 1;
}
cout << steps << endl;
return 0;
}
7. 階段の登り方
動的計画法による解法。dp[i] = dp[i-a] + dp[i-b] + dp[i-c]; i段目にはi-a段目からa段で登る、i-b段目からb段で登る、i-c段目からc段で登る方法がある。
#include <iostream>
#include <cstring>
using namespace std;
long long ways[1000000+10];
const int MOD = 1000000007;
int main() {
int totalSteps;
cin >> totalSteps;
int stepA, stepB, stepC;
cin >> stepA >> stepB >> stepC;
// 初期化：0段目にいる方法は1通り
ways[0] = 1;
for(int currentStep = 1; currentStep <= totalSteps; currentStep++) {
if(currentStep >= stepA) {
ways[currentStep] += ways[currentStep - stepA];
}
if(currentStep >= stepB) {
ways[currentStep] += ways[currentStep - stepB];
}
if(currentStep >= stepC) {
ways[currentStep] += ways[currentStep - stepC];
}
// オーバーフロー防止のためMODで割る
ways[currentStep] %= MOD;
}
cout << ways[totalSteps] << endl;
return 0;
}
8. 大きな数の剰余計算
大きな数の剰余を計算する効率的な方法
#include <iostream>
#include <string>
using namespace std;
int main() {
string bigNumber = "12345678901234567890123456789012345678901234567890";
long long remainder = 0;
int divisor = 2023;
// 文字列を左から右へ処理して剰余を計算
for(int digitIndex = 0; digitIndex < bigNumber.size(); digitIndex++) {
remainder = (remainder * 10 + (bigNumber[digitIndex] - '0')) % divisor;
}
cout << remainder << endl;
return 0;
}
9. 極大値と極小値
#include <iostream>
#include <vector>
using namespace std;
int main() {
int dataSize;
cin >> dataSize;
vector<int> numbers(dataSize);
// データの読み込み
for(int i = 0; i < dataSize; i++) {
cin >> numbers[i];
}
int maxLocalMin = 0;
int minLocalMax = 100000;
// 極値の探索
for(int i = 1; i < dataSize-1; i++) {
// 極小値のチェック
if(numbers[i] < numbers[i+1] && numbers[i] < numbers[i-1]) {
maxLocalMin = max(maxLocalMin, numbers[i]);
}
// 極大値のチェック
if(numbers[i] > numbers[i+1] && numbers[i] > numbers[i-1]) {
minLocalMax = min(minLocalMax, numbers[i]);
}
}
cout << maxLocalMin << " " << minLocalMax << endl;
return 0;
}
10. 左右の文字数が等しい位置
#include <iostream>
#include <string>
using namespace std;
int main() {
string input;
cin >> input;
int leftCount = 0, rightCount = 0;
long long equalPositions = 0;
// 左から右へ処理
for(int i = 0; i < input.size(); i++) {
// 左側の'L'の数をカウント
if(input[i] == 'L') {
leftCount++;
}
// 右側の'R'の数をカウント
if(input[input.size()-1-i] == 'R') {
rightCount++;
}
// 左側の'L'の数と右側の'R'の数が等しい位置をカウント
if(leftCount == rightCount) {
equalPositions++;
}
}
cout << equalPositions << endl;
return 0;
}
11. 桁の和が特定の値となる素数
#include <iostream>
using namespace std;
// 素数判定関数
bool isPrime(int number) {
if(number <= 1) return false;
if(number == 2) return true;
if(number % 2 == 0) return false;
for(int divisor = 3; divisor * divisor <= number; divisor += 2) {
if(number % divisor == 0) {
return false;
}
}
return true;
}
// 桁の和を計算する関数
int digitSum(int number) {
int sum = 0;
while(number > 0) {
sum += number % 10;
number /= 10;
}
return sum;
}
int main() {
int primeCount = 0;
// 100から1000000までの数をチェック
for(int num = 100; num < 1000000; num++) {
if(isPrime(num) && digitSum(num) == 23) {
primeCount++;
}
}
cout << primeCount << endl;
return 0;
}