グリッド迷路での最適経路探索
問題概要
n×m のグリッドからなる迷路を考えます。各セル (i, j) には方向指示 di,j と重み vi,j が設定されています。プレイヤーは初期位置 (sx, sy) から左足で踏み込み、その時点で vsx,sy を加算し、セルの重みを -vsx,sy に反転させます。
その後、各ステップで以下の選択肢があります：
ゲームを終了し、現在のスコアを最終スコアとする
現在のセルの方向指示に従 ...
8月31日 20:47 投稿
LeetCode | 面試問題 08.01. 三步問題
関連タグ
動的計画法、C言語
問題の説明
三段階の階段を登る問題です。ある子供が階段を登っているとします。階段はn段あり、その子供は一度に1段、2段、または3段を登ることができます。このとき、子供が階段を登る方法の総数を計算するアルゴリズムを実装してください。結果は非常に大きくなる可能性があるため、1000000007で剰余を取ってください。
解法の考察
これは基 ...
8月23日 07:43 投稿
街路灯の消灯順序最適化 - 区間DPによる解法
街路灯の消灯問題
問題の概要
ある村では、一本の道に \(n\) 基の街路灯が設置されています。各街路灯には異なる消費電力があります（つまり、同じ時間あたりに消費する電力量が異なります）。張さんはこの道の途中にある街路灯のそばに住んでおり、毎朝夜明けになると一つずつこれらの街路灯を消す仕事をしています。
村の電気代を節約するため、張さんは各街路灯の位置と ...
8月22日 01:37 投稿
競技プログラミング・アルゴリズム問題解説：動的計画法、単調スタック、貪欲法の実装
問題概要と考察
本稿では3つのアルゴリズム問題を解くための手法について説明します。各問題で異なる技術が要求されています。
第1問：骨牌配置の最適化
n枚の骨牌を並べるとき、ある位置から倒すことで連続して倒れる骨牌の数を最小化する問題です。
考え方
最終的な回答は、末尾のいくつかの骨牌を削除した後の状態から計算できます。任意の位置まで考えた時の最適値を ...
8月21日 23:21 投稿
文字列のパリンドローム分割におけるバックトラッキング手法と動的計画法による高速化
問題定義
特定の入力文字列を受け取り、それを複数の部分文字列に分割する際、各部分文字列が必ずパリンドローム（読み返しても同一になる列）となるようなすべての組み合わせを求めるタスクです。
探索アプローチの設計
この種の分割問題は、標準的なループ制御のみで実装しようとすると境界条件や重複チェックが複雑化しやすくなります。代わりに、選択枝を並木道のよう ...
8月21日 12:55 投稿
2022 ICPC アジア西安地区大会 問題解説と実装アプローチ
C. Clone Ranran
本問題は、自身のクローンを作成する時間と、問題を作成する時間のバランスを取って最小の総時間を求めるものです。
クローンを作成する回数を全探索します。クローンを作成するたびに人数は2倍になるため、対数オーダーの探索で済みます。各ステップにおいて、必要な問題数を現在の人数で割ったもの（切り上げ）を作成時間に乗算し、クローン作成時間と合 ...
8月18日 14:40 投稿
USACO13OPEN Photo G の解説
序文
問題のリンク：洛谷。
問題概要
長さが \(n\) の配列があり、一部の要素はすでに色が塗られています。\(m\) 個の制約が与えられ、それぞれ \(l_i \sim r_i\) の範囲内にちょうど1つの要素が色付きであることを示します。この制約をすべて満たすように、最大で何個の要素を色付けできるかを求めます。
\(n \leq 2 \times 10^5\)，\(m \leq 10^5\)。
問題解析
解法 \(1\ ...
8月15日 23:59 投稿
等比数列の効率的計算と木構造処理
T1: 等比数列の合計計算
数列$ \sum_{i=1}^n x^i $を効率的に求めます。この問題ではx進法の特性を利用した新しいアプローチを採用しました。
変数Pを$x^1 + x^2 + ... + x^n$と定義すると、x進法で表現する際は連続する1の並びになります。この性質を活かし、$Q = x^{m+1}$のx進法表現から$Q-1$を導出し、$(x-1)$で割ることで最終的な合計値を得ます。
以下に数式を示し ...
8月15日 17:07 投稿
探索と最適化アルゴリズムによる競技プログラミング問題の解法
マトリックス操作と深さ優先探索（DFS）
最初の問題は、与えられたバイナリ行列を行の反転と列の置換によって目標の行列に一致させられるかを判定するものです。行の反転は同一の行に対して2回行うと無効になるため、各行に対する操作は「行う」か「行わないか」の二択です。
まず、各行の要素の合計値を見て、反転することが確定している行を処理します。特定の行において ...
8月15日 00:33 投稿
2026年NOI問題解決記録（十五）
コンテストリンク
\(\text{著者：DaiRuiChen007}\)
A. [UOJ702] 張飛の精鋭兵団 (3.5)
問題リンク
コンテストの過程を木として捉え、値を大きい順に埋めていく。制約は親子のトポロジカル順序であり、係数が\(-1\)の層を優先的に埋める。もし埋められない場合は、子ノードが最も多く、勝利回数が最も多いノードを選ぶ。
コードに落とし込むと複雑度を効率的に改善できる。
...
8月12日 06:48 投稿