企業推薦の最適化アルゴリズム
プログラミングコンテスト終了後、企業の採用担当は成績優秀者を推薦する必要がある。推薦条件は以下の通り：
コンテスト得点が175点以上であること
最大K回の推薦ラウンドが可能
各ラウンドでは得点が厳密に増加する順序で推薦
PAT試験の合格者（スコアが基準以上）は同点でも推薦可
入力形式
最初の行には3つの整数N（≤10⁵）、K（≤5×10³）、S（≤100）が与えられる。続 ...
7月31日 17:31 投稿
競技プログラミングにおける主要アルゴリズム実装テクニック集
高速入出力と座標圧縮
大量のデータ処理を行う際、標準的な入出力関数はボトルネックになることがあります。以下では、カスタム関数による高速化と、std ライブラリを使用した最適化の両方を示します。
#include <bits/stdc++.h>
using namespace std;
// カスタム関数による高速入力
inline int fastRead() {
int val = 0;
char ch = getchar();
bool ...
7月27日 18:41 投稿
K差分構成問題の解法
問題概要
長さ n の 01 文字列 s が与えられる。一部の文字は ? となっており、これらを 0 または 1 に置き換える必要がある。
良い配置とは、1 ≤ i < n を満たす異なる i がちょうど m 個存在し、かつ s[i] ≠ s[i+1] となるものをいう。
すべての良い配置の中で辞書順最小のものを求めよ。解が存在しない場合は Impossible を出力せよ。
解法
まず、現在の文字列におけ ...
7月25日 23:01 投稿
Codeforces ラウンド 996 (Div. 2) 問題解説
問題 A: 二匹のカエル
問題リンク：https://codeforces.com/contest/2055/problem/0
アプローチ:
アリスが先手で勝つ状況は、位置 a と b の距離が奇数の場合に限られます。
ACコード:
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 void process() {
5 long long n, p, q;
6 cin >> n >> p >> q;
7 if ((abs(p - q) % 2) ...
7月24日 17:10 投稿
動的計画法：完全背包問題の主要パターンと実装ガイド
完全背包問題の基本概念
動的計画法（DP）における完全背包問題（Complete Knapsack Problem）は、各アイテムを無限に選択可能な状態での最適化問題を指します。0-1 背包問題との主な違いは、アイテムの再利用が許可されている点であり、これにより状態遷移の内側ループ順序が重要になります。具体的には、背包の容量を小さい方から大きい方へ順に更新することで、同一ア ...
7月23日 17:01 投稿
Codeforces Round 1027 (Div. 3) 問題解説（A〜E）
概要
本稿では、Codeforces Round 1027（Div. 3）の問題AからEまでの解法を示す。
問題A：数値構築
問題内容
4桁の整数cが与えられる。整数a（0以上99以下）とb（0以上99以下）を用いて、(a+b)² = c を成立させられるか判定する。
解法
0から√nまでの範囲で遍历し、平方数になるかを判定すればよい。a+b = √c が成立する必要があり、a=0, b=√c で試すだけで十分である ...
7月19日 20:01 投稿
アルゴリズム問題の効率的な解法
本記事では、複数のアルゴリズム問題について考察し、それぞれの問題に対する効率的な解法を説明します。
避難所配置問題
この問題は、特定の範囲内で最も効率的な方法で避難所を配置する必要がある。具体的には、以下の関数を考える：
[ g(y, r) ] は、右境界が (r) の場合に、位置 (y) に避難所を設置したときのコストを表す。
我々が必要とするのは、[ \max_{j \geq mid ...
7月18日 01:21 投稿
JOI 2013 国内予選最終ラウンド解説
問題1：交互配列の最長連結区間
与えられた 0-1 列において、隣接要素が交互に変化する（例：01010）最大長の連続部分列を求める。ただし、1つの「交互セグメント」を反転することで、より長い連続交互列を得られる可能性がある。
まず、入力列を交互性に基づいて分割し、各セグメントの左右端点を記録。その後、隣接する3つのセグメント（左・中・右）を結合した長さを評 ...
7月14日 01:06 投稿
模擬退火アルゴリズムの原理と実装事例
模擬退火法の概要
模擬退火（Simulated Annealing, SA）は、大域的最適解近似アルゴリズムの一種であり、組み合わせ最適化問題などに広く適用される確率的探索手法です。解空間が非常に広大であり、かつ目的関数が単峰性を持たない場合などに有効です。
この手法は、金属加工における「焼きなまし（Annealing）」プロセスに由来します。金属を高温で加熱し、徐々に冷却する ...
7月12日 23:28 投稿
フェニック木（Binary Indexed Tree）の基礎と応用
フェニック木（Binary Indexed Tree, BIT）は、主に数列の prefix sum（接頭辞和）を効率的に管理・計算するために設計されたデータ構造です。セグメント木と比較して実装が簡潔であり、定数倍の計算コストが低いため、頻繁な更新とクエリが発生する箇所で広く利用されています。本記事では、基本的な1次元の構造から、差分を利用した区間更新、および2次元への拡張につい ...
7月11日 16:07 投稿