競プロ典型問題の解法パターンと実装テクニック
文字列の構成要素検証
与えられた3文字の文字列が"A"、"B"、"C"の3種類の文字のみで構成されているかを判定する問題。文字の順序は問わず、各文字が1回ずつ出現するかを確認する必要がある。
#include <iostream>
#include <array>
using namespace std;
int main() {
string input;
cin >> input;
array<int, 3> count = {0};
...
8月27日 22:31 投稿
AtCoder ABC369 のアルゴリズム解説
A. 369
整数 $C$ が存在して $A, B, C$ が等差数列となる条件は、$A+B$ が偶数であることです（$C = (A+B)/2$ が整数であることと同値）。特別な場合として、$A=B$ であれば数列の長さは1となるため、答えは1です。それ以外の場合、$A+B$ が偶数ならば $A$ と $B$ の間に整数が1つ、$A$ と $B$ の外側に整数が1つずつ存在するため、選択肢は3つになります。奇数の場合は $A ...
8月22日 09:01 投稿
AtCoder ABC336 演習：桁制約付き DP と双方向 BFS
E - 数字の和で割り切れる数
この問題では、与えられた正整数 \(N\) 以下の自然数のうち、その桁の和で割った余りが 0 となる数を求める必要があります。
通常の桁 DP では、剰余を状態として維持するのは容易ですが、今回のように「剰元の基準（桁の和）」自体が変化する場合、直接的な DP では困難になります。そこで、桁の和（モジュロ）を先に見積もるアプローチを取 ...
8月13日 02:59 投稿
2024年夏休み交流戦・練習編1
2024年夏休み交流戦・練習編1
A - 🐓
AtCoder - abc079_d
問題文
各頂点のコストが与えられ、それを1に変換するのに必要な最小コストを求める。
解法
すべての数を1にするには、直接1に変換するか、別の数に変換してからさらに変換する方法がある。
これは$floyd$アルゴリズムによる最短経路探索と似ているため、$floyd$を適用できる。
コード
#include<bits/stdc++.h&g ...
8月5日 02:59 投稿
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 投稿
AtCoderコンテスト445の解法解説
D - チョコレートの再構築
この問題は比較的単純な実装問題です。チョコレートの配置を再構築するアルゴリズムを示します。
struct Chocolate {
int height;
int width;
int id;
};
bool compareWidth(const Chocolate &a, const Chocolate &b) {
return a.width > b.width;
}
bool compareHeight(const Chocolate &a, const Chocolate &b) {
ret ...
7月17日 20:13 投稿
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 投稿
ABC351コンテスト問題解説
問題A: ゲームの点数計算
木青チームと高橋チームの点数をそれぞれ計算し、木青チームの総得点が高橋チームより1点多くなるようにします。
コード例
#include <iostream>
#include <vector>
int main() {
int score_gq = 0, score_mq = 0;
int input;
// 木青チームの9つの点数を入力
for (int i = 0; i < 9; ++i) {
std::cin >> i ...
7月14日 02:44 投稿
ビット列列挙の応用問題集
ビット列列挙は、組み合わせ問題を効率的に解決するための強力な手法です。具体的な応用例を通じてその実装方法を解説します。
問題1: ビットマスクとPopcountの総和
与えられた非負整数NとMについて、0からNまでの全ての整数iにおける (i & M) のビットカウント（popcount）の総和を求める。解法では加算処理を乗算に変換して効率化する。
例: N=22 (2進数:10110) ...
7月11日 21:10 投稿
AtCoder Beginner Contest 338 解説
A - Capitalized?
英字からなる文字列 $S$ が与えられる。先頭が大文字で、残りがすべて小文字であるかを判定する。
単純に先頭文字が 'A'～'Z' の範囲にあり、他の文字がすべて 'a'～'z' の範囲にあるかをチェックすればよい。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
bool ok = isupper(s[0]);
for (in ...
7月8日 19:49 投稿