競技プログラミングにおける数論と DP による最適化戦略
問題 1：数値変換プロセスと剰余定理
この問題では、巨大な数値 $n$ に対して特定の減算操作を繰り返す際の最終状態を求めます。操作の規則は、$n$ を $s$ で割った商と余りの和を次の $n$ とするものです。入力値が非常に大きくなる可能性があるため、単純なシミュレーションでは時間制限を超えてしまいます。
部分点対策：桁ごとのシミュレーション
まず、数値を文字列 ...
10月13日 15:03 投稿
数論的関数とデータ構造を用いた競技プログラミングのアルゴリズム最適化
アルゴリズム最適化の基本概念
競技プログラミングにおいて、問題の制約を満たすためには、単純な全探索から数学的な性質や効率的なデータ構造への転換が不可欠です。本記事では、約数とオイラー関数を用いた数論的問題、最長増加部分列（LIS）の個数計算におけるセグメント木の応用、そしてフィボナッチ数列に基づく木構造の動的計画法（DP）について、その数学的背景と計 ...
10月5日 20:47 投稿
Educational Codeforces Round 181 (Div. 2) の A〜D 問題の解法
問題リンク: https://codeforces.com/contest/2125
A. Difficult Contest
解法
「NTT」と「FFT」はどちらも部分列として T が後ろに来る必要がある。したがって、まず F と N 以外の文字をすべて出力し、その後で F と N を出力すればよい。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
...
10月5日 11:00 投稿
中国鉱業大学大学院入試プログラミング課題：最長共通部分列とシーザー暗号の解法
課題1：最長共通部分列（LCS）の算出
技術概要
2つの文字列が与えられた際、順序を維持したまま両者に共通して現れる部分列のうち、最長のものを特定しその長さを返すアルゴリズムを実装する。入力ストリームには複数のテストケースが連続して含まれており、各文字列の最大長は1000文字に制限される。元の試験仕様では文字列長が等しく重複文字を含まない条件が付されてい ...
9月14日 01:26 投稿
凸多角形の構成問題とサボテングラフ上の期待値計算、幾何DPの最適化
凸多角形の構成と桁DP：ベクトル選択の数え上げ
凸多角形を構成する際、同一のベクトルは連続して現れる必要があります。この問題は、与えられた $n$ 個のベクトル $(x_i, y_i)$ をそれぞれ $c_i$ 個選択し、閉路を形成しつつ、全ての座標が指定された範囲 $m$ に収まる組み合わせを求める問題に帰着できます。
条件は、正の方向の総和と負の方向の総和が等しく、かつその ...
8月16日 03:46 投稿
七夕祭プログラミングコンテスト問題
A. 神話キャラクター
解決アプローチ：各要素についてソート後の隣接要素を確認します。二分探索により位置を特定し、左右の値が条件を満たすか判定します。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define YES(x) (x ? "Yes" : "No")
const int MOD = 1e9 + 7;
int main_val[100005], backup_val[100005];
vo ...
8月10日 05:07 投稿
K差分構成問題の解法
問題概要
長さ n の 01 文字列 s が与えられる。一部の文字は ? となっており、これらを 0 または 1 に置き換える必要がある。
良い配置とは、1 ≤ i < n を満たす異なる i がちょうど m 個存在し、かつ s[i] ≠ s[i+1] となるものをいう。
すべての良い配置の中で辞書順最小のものを求めよ。解が存在しない場合は Impossible を出力せよ。
解法
まず、現在の文字列におけ ...
7月25日 23:01 投稿
動的計画法：完全背包問題の主要パターンと実装ガイド
完全背包問題の基本概念
動的計画法（DP）における完全背包問題（Complete Knapsack Problem）は、各アイテムを無限に選択可能な状態での最適化問題を指します。0-1 背包問題との主な違いは、アイテムの再利用が許可されている点であり、これにより状態遷移の内側ループ順序が重要になります。具体的には、背包の容量を小さい方から大きい方へ順に更新することで、同一ア ...
7月23日 17:01 投稿
アルゴリズム問題の効率的な解法
本記事では、複数のアルゴリズム問題について考察し、それぞれの問題に対する効率的な解法を説明します。
避難所配置問題
この問題は、特定の範囲内で最も効率的な方法で避難所を配置する必要がある。具体的には、以下の関数を考える：
[ g(y, r) ] は、右境界が (r) の場合に、位置 (y) に避難所を設置したときのコストを表す。
我々が必要とするのは、[ \max_{j \geq mid ...
7月18日 01:21 投稿
UKIEPC 2017 プログラミングコンテスト問題解説
Problem A: Alien Sunset
各惑星の自転周期、日の出時刻、日の入り時刻を格納します。自転周期の最大値(max_period)を求め、0からmax_period×1825までの時間を列挙します。各時間について全ての惑星で夜間であることを確認し、条件を満たす最初の時刻を出力します。
#include <bits/stdc++.h>
using namespace std;
struct Planet {
int period, sunrise, sunse ...
7月15日 16:15 投稿