競技プログラミングにおける数論と DP による最適化戦略
問題 1：数値変換プロセスと剰余定理
この問題では、巨大な数値 $n$ に対して特定の減算操作を繰り返す際の最終状態を求めます。操作の規則は、$n$ を $s$ で割った商と余りの和を次の $n$ とするものです。入力値が非常に大きくなる可能性があるため、単純なシミュレーションでは時間制限を超えてしまいます。
部分点対策：桁ごとのシミュレーション
まず、数値を文字列 ...
10月13日 15:03 投稿
ICPC 2025 Yokohama R「Seagull Population」問題解説
(M) の処理については公式解説を参照されたい。
まず，海鸥の全总数的明显な下界は (b_i) の最大值であり，(D_{\mathrm{max}} = \max(b_1, \ldots, b_n)) である。これは，いずれかの日に观察到的海鸥数が海鸥の総数をを超えることはできないためである。同様に，增加分の合計も
[S_{\mathrm{inc}} = \sum_{i = 1, \ldots, n} \max(b_i - b_{i - 1}, 0) \quad (\text{where ...
8月17日 01:54 投稿
企業推薦の最適化アルゴリズム
プログラミングコンテスト終了後、企業の採用担当は成績優秀者を推薦する必要がある。推薦条件は以下の通り：
コンテスト得点が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 投稿