凸多角形の構成問題とサボテングラフ上の期待値計算、幾何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 投稿
JOI 2013 国内予選最終ラウンド解説
問題1：交互配列の最長連結区間
与えられた 0-1 列において、隣接要素が交互に変化する（例：01010）最大長の連続部分列を求める。ただし、1つの「交互セグメント」を反転することで、より長い連続交互列を得られる可能性がある。
まず、入力列を交互性に基づいて分割し、各セグメントの左右端点を記録。その後、隣接する3つのセグメント（左・中・右）を結合した長さを評 ...
7月14日 01:06 投稿
Codeforces 909 問題A〜Fの解説
Codeforces 909 問題解説
問題URL
A B C D E F
難易度：赤 黄 緑 青 緑 紫
解説
A
問題概要：2つの文字列が与えられる。非空の接頭辞を連結した文字列の中で辞書順最小のものを求める。
アルゴリズムラベル：貪欲
解法分析：
辞書順比較は左から順に文字を比較し、どちらかが終了するか異なる文字が見つかるまで続ける。このため、貪欲法が有効。前後の文字列の接頭辞を比 ...
6月26日 19:39 投稿
競技プログラミング問題解説：貪欲法から動的計画法まで
問題 1：目標値への到達ステップ数
この問題は貪欲法の適用例です。目標値 50 に対して、現在の値が不足している場合と超過している場合で戦略が異なります。不足時には 2 で割った余り、超過時には 3 で割った余りを考慮し、必要な操作回数を計算します。
具体的には、差額が偶数であれば単純に除算し、奇数であれば調整値を加えてから計算します。超過時についても同様に ...
6月22日 23:05 投稿
障害物のある格子路の問題解法：動的最適化による経路カウント
m 行 n 列の二次元グリッドが与えられた場合、左上隅の座標から右下隅の座標まで移動するシナリオを考慮します。移動ルールとして、一歩ごとに「下」または「右」へ進むことが許容されています。
この環境には障害物が混在しており、特定のセルは通ることが不可能です。データ構造上、障害物は整数 1、空席は 0 によって定義されます。これらの条件を満たしながら、スタ ...
6月17日 20:42 投稿