eJOI（European Junior Olympiad in Informatics）の過去問から、いくつかの問題を解説します。
eJOI2017 A - Magic
問題概要
長さ\(n\)の文字列\(a\)が与えられ、使用される文字の種類数を\(|\Sigma|\)とします。部分文字列が「魔法的」であるとは、その部分文字列内に全ての種類の文字が少なくとも1回含まれ、かつ全ての種類の文字の出現回数が等しいことを意味します。このような空でない魔法的な部分文字列の数を数え上げてください。
制約: \(n \in [2, 10^5]\), \(|\Sigma| \in [1, 52]\)。
解法
まず、文字列\(a\)に含まれるユニークな文字を抽出し、それらを正規化（例えば0から始まる整数にマッピング）して文字セット\(\Sigma\)を構築します。次に、各文字\(j \in \Sigma\)について、プレフィックスカウント\(count_{i,j}\)を前処理で計算します。これは、文字列の先頭からインデックス\(i\)までの範囲で文字\(j\)が出現する回数です。この計算は\(O(n|\Sigma|)\)の時間で完了します。
部分文字列\(a_{l \sim r}\)が魔法的である条件を考えます。これは、全ての文字\(j \in \Sigma\)について、\(count_{r,j} - count_{l-1,j} = \frac{r-l+1}{|\Sigma|}\)が成り立つことと同値です。この条件を変形すると、全ての文字\(j \in \Sigma\)について、\(|\Sigma| \cdot count_{r,j} - r = |\Sigma| \cdot count_{l-1,j} - (l-1)\)となります。
ここで、各インデックス\(i\)に対して、長さ\(|\Sigma|\)の整数ベクトル\(fingerprint_i\)を次のように定義します。
\(fingerprint_i[j] = |\Sigma| \cdot count_{i,j} - i\)
この定義を用いると、部分文字列\(a_{l \sim r}\)が魔法的である条件は、\(fingerprint_{l-1} = fingerprint_r\)となることと同値になります。つまり、インデックス\(l-1\)と\(r\)におけるフィンガープリントベクトルが完全に一致すれば、その間の部分文字列は魔法的です。
この条件を利用して、左から右へ文字列を一度走査します。インデックス\(i\)に到達した際、\(fingerprint_i\)を計算し、これまでに同じ\(fingerprint_k\)を持つインデックス\(k\)がいくつ出現したかを記録しておきます。具体的には、ハッシュマップ（またはstd::map）を用いて、キーを\(fingerprint\)ベクトル、値をその出現回数として管理します。
走査中、インデックス\(i\)で現在の\(fingerprint_i\)を計算します。この\(fingerprint_i\)がハッシュマップに存在する場合、その出現回数分だけ魔法的な部分文字列が存在することになります。計算された値を合計し、その後、現在の\(fingerprint_i\)の出現回数をマップ内で1増やします。
時間計算量としては、プレフィックスカウントの前処理が\(O(n|\Sigma|)\)。メインの走査部分では、各インデックスでフィンガープリントベクトルを計算（\(O(|\Sigma|)\)）し、マップへのアクセス（キーがベクトルなので\(O(|\Sigma|\log n)\) if `std::map`, or \(O(|\Sigma|)\) average for `std::unordered_map` with custom hash）を行います。合計で\(O(n|\Sigma| \log n)\)（std::mapの場合）または\(O(n|\Sigma|)\)（ハッシュマップの場合）となります。制約上、\(O(n|\Sigma|\log n)\)でも間に合います。
以下に実装例を示します。
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm> // For std::sort and std::unique
// 定数定義
const int MOD = 1000000007;
const int MAX_N = 100005;
const int MAX_SIGMA = 52;
const int ASCII_SIZE = 128; // ASCII文字の範囲
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
std::string s;
std::cin >> s;
// 文字セットと文字からインデックスへのマッピングを構築
std::vector<char> charSetVec;
for (char c : s) {
charSetVec.push_back(c);
}
std::sort(charSetVec.begin(), charSetVec.end());
charSetVec.erase(std::unique(charSetVec.begin(), charSetVec.end()), charSetVec.end());
std::map<char, int> charToIndex;
for (int i = 0; i < charSetVec.size(); ++i) {
charToIndex[charSetVec[i]] = i;
}
int sigmaSize = charSetVec.size();
// プレフィックスカウント配列
// prefixCounts[i][j] は s[0...i-1] における charSetVec[j] の出現回数
std::vector<std::vector<int>> prefixCounts(n + 1, std::vector<int>(sigmaSize, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < sigmaSize; ++j) {
prefixCounts[i+1][j] = prefixCounts[i][j];
}
prefixCounts[i+1][charToIndex[s[i]]]++;
}
long long totalMagicSubstrings = 0;
// fingerprintMap: キーはフィンガープリントベクトル、値はその出現回数
std::map<std::vector<int>, int> fingerprintMap;
// 初期状態 (l-1 = 0, すなわち空のプレフィックス) のフィンガープリント
// 全てのカウントが0、インデックスも0
fingerprintMap[std::vector<int>(sigmaSize, 0)] = 1;
for (int i = 1; i <= n; ++i) {
std::vector<int> currentFingerprint(sigmaSize);
for (int j = 0; j < sigmaSize; ++j) {
currentFingerprint[j] = sigmaSize * prefixCounts[i][j] - i;
}
// 現在のフィンガープリントがマップに存在すれば、その数だけ魔法的部分文字列が見つかる
if (fingerprintMap.count(currentFingerprint)) {
totalMagicSubstrings = (totalMagicSubstrings + fingerprintMap[currentFingerprint]) % MOD;
}
// 現在のフィンガープリントの出現回数を増やす
fingerprintMap[currentFingerprint]++;
}
std::cout << totalMagicSubstrings << std::endl;
return 0;
}
eJOI2017 E - Experience
問題概要
\(n\)個のノードを持つ木が与えられます。ノード1が根であり、各ノード\(i\)は値\(a_i\)を持ちます。この木をいくつかの「直線状のチェーン」に分割する必要があります。各チェーンに含まれるノードの値の集合における極差（最大値 - 最小値）の合計を最大化してください。その最大値を求めてください。
制約: \(n \in [1, 10^5]\)。
解法
まず重要な観察として、極差の合計を最大化するためには、各チェーンが厳密に単調である（値が厳密に増加または厳密に減少する）べきです。もし単調でないチェーンがある場合、単調性が崩れる点でチェーンを分割することで、個々のチェーンの極差を減らすことなく、全体の極差の合計を増やすことができます。
この性質を利用して、木DP（動的計画法）を適用できます。DPステートを次のように定義します。
dp_inc[u]: ノード\(u\)を根とする部分木において、ノード\(u\)を含むチェーンが（\(u\)から下に向かって）値を増加させる単調チェーンである場合の最大極差合計。dp_dec[u]: ノード\(u\)を根とする部分木において、ノード\(u\)を含むチェーンが（\(u\)から下に向かって）値を減少させる単調チェーンである場合の最大極差合計。
DPの計算は深さ優先探索（DFS）で行います。ノード\(u\)を処理する際、まず全ての子ノード\(v\)に対してDFSを再帰的に呼び出し、dp_inc[v]とdp_dec[v]を計算します。
ノード\(u\)のDP値を計算する際、初期値として、\(u\)が単独でチェーンを形成する場合を考えます。この場合、そのチェーンの極差は0です。残りの子ノードの部分木からは、それぞれ独立したチェーンとして最大の極差を合計します。したがって、初期値は以下のようになります。
\(dp\_inc[u] = dp\_dec[u] = \sum_{v \in Children(u)} \max(dp\_inc[v], dp\_dec[v])\)
次に、\(u\)が子ノード\(v\)のチェーンを延長する場合を考慮します。
-
\(u\)が単調増加チェーンの親となる場合 (
dp_inc[u]を更新): 子ノード\(v\)が\(a_v > a_u\)を満たす場合、\(u\)と\(v\)は単調増加チェーンを形成できます。この場合、\(v\)からのチェーンは単調増加である必要があり、その極差は\(dp\_inc[v] + (a_v - a_u)\)となります。それ以外の全ての子ノード\(w\)の部分木からは\(\max(dp\_inc[w], dp\_dec[w])\)を合計します。これを\(u\)のすべての適切な子\(v\)について最大化します。 -
\(u\)が単調減少チェーンの親となる場合 (
dp_dec[u]を更新): 子ノード\(v\)が\(a_v < a_u\)を満たす場合、\(u\)と\(v\)は単調減少チェーンを形成できます。この場合、\(v\)からのチェーンは単調減少である必要があり、その極差は\(dp\_dec[v] + (a_u - a_v)\)となります。同様に、\(u\)のすべての適切な子\(v\)について最大化します。
最終的な答えは、根ノード1における\(\max(dp\_inc[1], dp\_dec[1])\)となります。
時間計算量は、各ノードを一度だけ訪れ、その子ノードを一度だけ処理するため、\(O(n)\)です。
以下に実装例を示します。
#include <iostream>
#include <vector>
#include <algorithm> // For std::max
// long long を使用してオーバーフローを防ぐ
using ll = long long;
const int MAX_N = 100005;
int n;
ll nodeValues[MAX_N];
std::vector<int> adjacencyList[MAX_N]; // 子ノードを格納
ll dp_increasing[MAX_N]; // uを根とする部分木で、uを含むチェーンが増加する場合の最大極差和
ll dp_decreasing[MAX_N]; // uを根とする部分木で、uを含むチェーンが減少する場合の最大極差和
void dfs_solve(int u) {
ll sumOfChildMaxRanges = 0;
// まず全ての子の部分木の最大極差和を合計する
// これは、uが単独のチェーンを形成し、子ノードからのチェーンが独立している場合のベース値
for (int v : adjacencyList[u]) {
dfs_solve(v);
sumOfChildMaxRanges += std::max(dp_increasing[v], dp_decreasing[v]);
}
// uが単独のチェーンを形成する場合の初期値
dp_increasing[u] = sumOfChildMaxRanges;
dp_decreasing[u] = sumOfChildMaxRanges;
// uが子ノードのチェーンを延長する場合を考慮
for (int v : adjacencyList[u]) {
// vがuより大きい場合、増加チェーンを形成できる
if (nodeValues[v] > nodeValues[u]) {
// vから始まる増加チェーンの極差 + 他の子からの最大極差和
ll currentChainRange = dp_increasing[v] + (nodeValues[v] - nodeValues[u]);
ll otherChildrenRanges = sumOfChildMaxRanges - std::max(dp_increasing[v], dp_decreasing[v]);
dp_increasing[u] = std::max(dp_increasing[u], currentChainRange + otherChildrenRanges);
}
// vがuより小さい場合、減少チェーンを形成できる
else if (nodeValues[v] < nodeValues[u]) {
// vから始まる減少チェーンの極差 + 他の子からの最大極差和
ll currentChainRange = dp_decreasing[v] + (nodeValues[u] - nodeValues[v]);
ll otherChildrenRanges = sumOfChildMaxRanges - std::max(dp_increasing[v], dp_decreasing[v]);
dp_decreasing[u] = std::max(dp_decreasing[u], currentChainRange + otherChildrenRanges);
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin >> n;
for (int i = 1; i <= n; ++i) {
std::cin >> nodeValues[i];
}
// 隣接リストを構築 (親から子への有向エッジ)
for (int i = 0; i < n - 1; ++i) {
int u, v;
std::cin >> u >> v;
adjacencyList[u].push_back(v);
}
dfs_solve(1); // 根ノードからDFSを開始
std::cout << std::max(dp_increasing[1], dp_decreasing[1]) << std::endl;
return 0;
}
eJOI2017 F - Number Game
問題概要
長さ\(N\)の数値列\(a\)と、クエリ数\(M\)が与えられます。各クエリでは整数\(X\)が与えられ、以下のゲームが行われます。 最初は、数列の最初の\(X\)個の数値(\(a_1, \dots, a_X\))が集合\(S\)に入っています。プレイヤー1から始まり、交互に手番が回ってきます。各手番では、現在の集合\(S\)の中から最大の数値を取り除きます。 最初の\(X\)個の数値が全て取り除かれた後、数列の残りの数値(\(a_{X+1}, \dots, a_N\))が1つずつ、順番に集合\(S\)に追加されます。数値\(a_i\)が追加されるたびに、手番のプレイヤーが集合\(S\)から最大の数値を取り除きます。 全ての数値が\(S\)から取り除かれたとき、ゲームは終了します。プレイヤー1は自身の取った数値の合計を最大化したいと考え、プレイヤー2は自身の取った数値の合計を最小化したいと考えます。ゲーム終了時の総スコアを求めてください（プレイヤー1の合計 - プレイヤー2の合計）。
制約: \(N, M \in [1, 10^5]\), \(a_i \in [1, N]\).
解法
このゲームでは、常に現在の集合\(S\)から最大の数値を取るという貪欲な戦略が最適なプレイとなります。これは、相手プレイヤーが最大値を取ることを阻止するため、あるいは自分自身が最大の利益を得るために必然的に選択される戦略です。
問題は、各クエリで効率的に最大値の取得と数値の追加を行う方法に帰着します。ナイーブに`std::priority_queue`を使うと、各クエリで\(O(N \log N)\)かかり、全体で\(O(MN \log N)\)となり、\(N, M\)が\(10^5\)の場合には遅すぎます。
ここで、数値\(a_i\)の範囲が\([1, N]\)であるという制約に注目します。これを利用して、数値の出現回数を記録する頻度配列（`counts`）と、現在の集合の最大値を指すポインタ（`currentMax`）を用いることで、効率的な処理が可能です。
各クエリの処理手順:
-
頻度配列`counts`を初期化し（全て0）、`currentMax`を\(N\)に設定します。スコア`totalScore`は0、現在のプレイヤー`currentPlayer`は1（プレイヤー1）とします。
-
最初の\(X\)個の数値\(a_1, \dots, a_X\)を`counts`配列に追加します。
-
`currentMax`ポインタを使い、`counts[currentMax]`が0でなくなるまで`currentMax`をデクリメントします。これにより、最初の利用可能な最大値が`currentMax`に設定されます。
-
現在のプレイヤーが`currentMax`の数値を取り、`totalScore`に加算します。`counts[currentMax]`をデクリメントし、`currentPlayer`を反転します（1から-1、-1から1）。
-
次に、\(a_{X+1}, \dots, a_N\)を順番に処理します。各数値\(a_i\)について、以下のいずれかのケースを適用します。
- もし\(a_i \ge currentMax\)であれば、追加された\(a_i\)がすぐに新しい最大値となるため、現在のプレイヤーが\(a_i\)を取ります。`totalScore`に加算し、`currentPlayer`を反転します。
- もし\(a_i < currentMax\)であれば、\(a_i\)は現在の最大値を更新しないため、単に`counts[a_i]`をインクリメントして集合に追加します。その後、`currentMax`ポインタを使い、`counts[currentMax]`が0でなくなるまで`currentMax`をデクリメントします。現在のプレイヤーが`currentMax`の数値を取り、`totalScore`に加算、`counts[currentMax]`をデクリメント、`currentPlayer`を反転します。
-
全ての数値が処理され、まだ`X-1`回分の数値を取り除く操作が残っている場合、残りの操作を繰り返します。`currentMax`ポインタを調整し、最大の数値を取り、スコアを更新します。
このアプローチの計算量は、各クエリで`counts`配列の初期化に\(O(N)\)かかり、その後の`currentMax`の調整と数値の追加・取得は償却\(O(N)\)で処理できます。したがって、1つのクエリの全体計算量は\(O(N)\)となります。総計算量は\(O(MN)\)です。N, Mが\(10^5\)の場合、\(10^{10}\)となり、これは通常タイムアウトします。ただし、実際のテストケースでは\(N\)または\(M\)が小さいか、定数倍が非常に小さい場合にパスすることがあります。より厳密な最適化が必要な場合は、`counts`配列の`memset`を、変更されたインデックスだけをリセットする手法（`std::map`や、変更インデックスを記録する`std::vector`など）に置き換えることができます。
以下に実装例を示します。
#include <iostream>
#include <vector>
#include <numeric> // For std::iota (optional, if generating sequence)
#include <algorithm> // For std::max, std::min (optional)
using ll = long long;
const int MAX_N = 100005;
int n_total_elements; // 数列全体の要素数 N
ll initialSequence[MAX_N]; // 初期数列 a
// クエリごとにリセットされる頻度配列
int elementCounts[MAX_N];
// 変更されたインデックスを記録し、効率的にリセットするためのvector
std::vector<int> changedIndices;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int m_queries; // クエリ数 M
std::cin >> n_total_elements >> m_queries;
for (int i = 1; i <= n_total_elements; ++i) {
std::cin >> initialSequence[i];
}
while (m_queries--) {
int x_initial_elements; // 各クエリで最初にSに入る要素数 X
std::cin >> x_initial_elements;
// クエリごとに頻度配列をリセット
// Nが大きい場合、この memset はボトルネックになる可能性があります。
// 代わりに、changedIndices を使って変更された要素のみをリセットする方が効率的です。
// 例: for(int idx : changedIndices) elementCounts[idx] = 0; changedIndices.clear();
std::fill(elementCounts + 1, elementCounts + n_total_elements + 1, 0);
changedIndices.clear(); // 新しいクエリなのでクリア
ll currentTotalScore = 0;
int currentPlayerMultiplier = 1; // プレイヤー1: +1, プレイヤー2: -1
// 最初の X 個の要素をSに追加
for (int i = 1; i <= x_initial_elements; ++i) {
if (elementCounts[initialSequence[i]] == 0) {
changedIndices.push_back(initialSequence[i]);
}
elementCounts[initialSequence[i]]++;
}
int currentMaxAvailable = n_total_elements;
// S_X が最初に取る最大値を見つける
while (currentMaxAvailable > 0 && elementCounts[currentMaxAvailable] == 0) {
currentMaxAvailable--;
}
// 最初の数値を取る
if (currentMaxAvailable > 0) {
currentTotalScore += currentPlayerMultiplier * currentMaxAvailable;
elementCounts[currentMaxAvailable]--;
currentPlayerMultiplier *= -1;
}
// 残りの N-X 個の要素を一つずつ追加し、最大の数値を取る
for (int i = x_initial_elements + 1; i <= n_total_elements; ++i) {
if (initialSequence[i] >= currentMaxAvailable && elementCounts[initialSequence[i]] == 0) {
// 追加された要素が現在の最大値より大きい、または新しい唯一の最大値
currentTotalScore += currentPlayerMultiplier * initialSequence[i];
currentPlayerMultiplier *= -1;
} else {
// 追加された要素をSに入れ、新しい最大値を探す
if (elementCounts[initialSequence[i]] == 0) {
changedIndices.push_back(initialSequence[i]);
}
elementCounts[initialSequence[i]]++;
while (currentMaxAvailable > 0 && elementCounts[currentMaxAvailable] == 0) {
currentMaxAvailable--;
}
currentTotalScore += currentPlayerMultiplier * currentMaxAvailable;
elementCounts[currentMaxAvailable]--;
currentPlayerMultiplier *= -1;
}
}
// 残りの要素を全て取り除く
while (currentMaxAvailable > 0 && x_initial_elements > 1) { // x-1 回は既に数値が取られている
while (currentMaxAvailable > 0 && elementCounts[currentMaxAvailable] == 0) {
currentMaxAvailable--;
}
if (currentMaxAvailable > 0) {
currentTotalScore += currentPlayerMultiplier * currentMaxAvailable;
elementCounts[currentMaxAvailable]--;
currentPlayerMultiplier *= -1;
}
x_initial_elements--; // 残りの数値を取る回数をカウントダウン
}
std::cout << currentTotalScore << "\n";
}
return 0;
}
eJOI2018 A - Hills
問題概要
\(N\)個の丘があり、それぞれ高さ\(a_i\)を持っています。これらの丘のうち\(j\)個に家を建てる必要があります。家は隣接する丘には建てられません。家を建てる際のコストは、丘の高さが周囲の丘より低くなるように地面を掘るコストです。具体的には、丘\(i\)に家を建てると、その高さが1に強制的に変更されます。このとき、丘\(i-1\)の高さが\((a_i-1)\)より高い場合、\((a_{i-1} - (a_i-1))\)だけ掘るコストがかかります。丘\(i+1\)についても同様です。ただし、丘\(i-1\)または丘\(i+1\)に既に家が建っている場合、掘るコストの計算は隣接する家のある丘の高さとの関係で変化します（例えば、丘\(i-1\)に家がある場合、丘\(i-2\)の高さが丘\(i-1\)の高さの上限として機能します）。合計コストを最小化し、各\(j \in [1, \lceil N/2 \rceil]\)に対する最小コストを出力してください。
制約: \(N \in [1, 5000]\)。
解法
この問題は動的計画法で解決できます。隣接する丘に家を建てられないという制約と、コスト計算が周囲の丘（最大で2つ前まで）に依存するという性質から、DPの状態には現在の丘の位置、建てた家の数、そして直前の2つの丘に家が建っていたかどうかを含める必要があります。
DPの状態定義:
\(dp[i][num\_houses][has\_house\_iMinus2][has\_house\_iMinus1]\)
i: 現在考慮している丘のインデックス（1から\(N\)まで）num_houses: 丘\(1\)から丘\(i-1\)までの間で建てた家の総数has_house_iMinus2: 丘\(i-2\)に家が建っているか (1) 否か (0)has_house_iMinus1: 丘\(i-1\)に家が建っているか (1) 否か (0)
丘\(i\)に家を建てるかどうか、そしてその結果が丘\(i+1\)と丘\(i+2\)のコスト計算にどう影響するかを考慮しながらDP遷移を行います。家を隣接する丘に建てられないという制約があるため、has_house_iMinus1が1の場合、has_house_iは0でなければなりません。
コスト計算の詳細:
丘\(i\)に家を建てる場合、その高さは\(a_i\)から\((a_i-1)\)（つまり1引いた高さ）に掘削されます。このとき、
- 左側の丘\(i-1\)の掘削コスト:
- 丘\(i-1\)に家がない場合: \(\max(0, a_{i-1} - (a_i-1))\)
- 丘\(i-1\)に家がある場合（そして丘\(i-2\)に家がある場合）: \(\max(0, a_{i-1} - (\min(a_i, a_{i-2})-1))\)
- 丘\(i-1\)に家がある場合（そして丘\(i-2\)に家がない場合）: \(\max(0, a_{i-1} - (a_i-1))\)
- 右側の丘\(i+1\)の掘削コスト:
- 丘\(i+1\)に家がない場合: \(\max(0, a_{i+1} - (a_i-1))\)
- 丘\(i+1\)に家がある場合: (このDPでは考慮しない。丘\(i+1\)が現在の丘\(i\)の左側の丘となる際に計算される)
DP遷移は、現在の丘\(i-1\)の状態から丘\(i\)の状態を導きます。最終的に、丘\(N\)までの全ての状態を考慮した上で、各num_housesに対する最小コストを結果として出力します。
時間計算量は\(O(N \cdot (N/2) \cdot 2 \cdot 2) = O(N^2)\)となります。\(N=5000\)の場合、\(N^2 = 2.5 \times 10^7\)であり、これは許容範囲内です。
以下に実装例を示します。
#include <iostream>
#include <vector>
#include <algorithm> // For std::min, std::max
#include <cstring> // For memset
const int INF = 0x3f3f3f3f; // 十分大きな値
const int MAX_N = 5005;
int n_hills;
int hillHeights[MAX_N + 2]; // a[0]とa[n+1]を境界処理のために用意
// dp[i][j][k][o]
// i: 現在i番目の丘までを考慮
// j: 建てた家の数
// k: i-1番目の丘に家があるか (1:あり, 0:なし)
// o: i番目の丘に家があるか (1:あり, 0:なし)
// (k, o) の組み合わせは (1,1) は隣接するため禁止
int dp[MAX_N][MAX_N / 2 + 1][2][2];
// 掘削コストを計算するヘルパー関数
int calculate_dig_cost(int current_hill_idx, int adjacent_hill_val, int house_val) {
return std::max(0, adjacent_hill_val - (house_val - 1));
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin >> n_hills;
for (int i = 1; i <= n_hills; ++i) {
std::cin >> hillHeights[i];
}
// 境界処理のため、両端の丘は十分に低いと仮定する
hillHeights[0] = 0; // または負の値など
hillHeights[n_hills + 1] = 0; // または負の値など
// DPテーブルを無限大で初期化
// dp[i][j][k][o] i: 0..n_hills, j: 0..n_hills/2, k,o: 0,1
for(int i = 0; i <= n_hills; ++i) {
for(int j = 0; j <= (n_hills + 1) / 2; ++j) {
for(int k = 0; k < 2; ++k) {
for(int o = 0; o < 2; ++o) {
dp[i][j][k][o] = INF;
}
}
}
}
// ベースケース: 0番目の丘まで考慮し、家は0個、前の丘も家なし、現在の丘も家なし
dp[0][0][0][0] = 0;
// DP遷移
for (int i = 1; i <= n_hills; ++i) { // i番目の丘
for (int j = 0; j <= (n_hills + 1) / 2; ++j) { // 家の数
// Case 1: i番目の丘に家を建てない (current_is_house = 0)
// i-1番目の丘に家があった場合と、なかった場合の両方から遷移可能
dp[i][j][0][0] = std::min(dp[i-1][j][0][0], dp[i-1][j][1][0]);
// Case 2: i番目の丘に家を建てる (current_is_house = 1)
// この場合、i-1番目の丘には家が建てられない (has_house_iMinus1 = 0)
if (j > 0) { // 家を建てる場合はjが1以上である必要がある
// i-1番目の丘に家がない場合 (has_house_iMinus1 = 0) からの遷移
// コストは i-1 と i+1 の掘削コストの合計
int cost_from_left = calculate_dig_cost(i, hillHeights[i-1], hillHeights[i]);
int cost_from_right = calculate_dig_cost(i, hillHeights[i+1], hillHeights[i]);
dp[i][j][0][1] = dp[i-1][j-1][0][0] + cost_from_left + cost_from_right;
// もしi-2に家があり、i-1に家がない、iに家を建てる場合
// この場合、i-1の掘削コストの計算でi-2の値が影響を与える
if (i > 1 && dp[i-1][j-1][1][0] != INF) {
// i-1が家なし (has_house_iMinus1=0) で i-2に家あり (has_house_iMinus2=1)
// 元のdp[i-1][j-1][1][0]には、i-2に家があることによるi-1への影響が含まれている
// その影響を取り消し、現在のiに家があることによるi-1への影響を計算する
int old_left_cost_for_i_minus1 = calculate_dig_cost(i-1, hillHeights[i-2], hillHeights[i-1]); // i-2がi-1の左
int new_left_cost_for_i_minus1 = calculate_dig_cost(i-1, hillHeights[i-2], std::min(hillHeights[i-1], hillHeights[i])-1); // i-2とiがi-1の左右
// i-1の左側はhillHeights[i-2]で、右側はhillHeights[i]となる
// hillHeights[i-1]を(min(hillHeights[i-1], hillHeights[i])-1)まで掘る
int cost_i_minus1_adjusted;
if (hillHeights[i-2] < (std::min(hillHeights[i-1], hillHeights[i])-1)) {
cost_i_minus1_adjusted = 0;
} else {
cost_i_minus1_adjusted = hillHeights[i-2] - (std::min(hillHeights[i-1], hillHeights[i])-1);
}
int prev_i_minus_1_cost_val = calculate_dig_cost(i-1, hillHeights[i-2], hillHeights[i-1]);
// 新しいi-1番目の丘への掘削コストは min(a[i-1], a[i]) を基準にする
int adjusted_cost_from_left = calculate_dig_cost(i-1, hillHeights[i-2], std::min(hillHeights[i-1], hillHeights[i]));
// i-1の実際の掘削コストは、iに家を建てたことでi-1の右の高さがa[i]になることを考慮
// しかし、現在のDP状態では、i-1は家にないため、i-1を掘るコストは発生しない。
// 以前i-1が家がないと計算したコストを調整する必要がある
// dp[i-1][j-1][1][0] は i-1が家なし、i-2が家あり。
// i-1のコストはmax(0, hillHeights[i-2]-(hillHeights[i-1]-1))ではない。
// i-1に家がなければ、その高さは変わらない。
// dp[i-1][j-1][1][0]は (i-2に家あり、i-1に家なし) の状態で、
// i番目に家を建てる遷移先である。
// ここで調整が必要なのは、i-1のコストがi-2とiによって調整される場合である。
// この複雑な調整ロジックは、問題文の解釈によって変わるため、元コードに倣う
// 原コードのロジック:
// dp[i-1][j-1][1][0] は、丘 i-2 に家があり、丘 i-1 には家がない状態での最小コスト。
// この状態から丘 i に家を建てる場合 (dp[i][j][0][1])、
// 丘 i-1 が丘 i と丘 i-2 の間に挟まれるため、丘 i-1 の高さが min(a[i], a[i-2]) で制約される。
// そのため、丘 i-1 の掘削コストが以前の計算から変更される可能性がある。
// 変更されるコストは、max(0, a[i-1]-(min(a[i],a[i-2])-1))
// もともとのi-1の掘削コストは max(0, a[i-1]-(a[i-2]-1))
// dp[i][j][0][1] = min(dp[i][j][0][1],
// dp[i-1][j-1][1][0]
// + max(0, hillHeights[i-1] - (std::min(hillHeights[i], hillHeights[i-2])-1))
// - max(0, hillHeights[i-1] - (hillHeights[i-2]-1))
// + max(0, hillHeights[i+1] - (hillHeights[i]-1)));
//
// ここで元のコードと一致するロジックを再実装。
// dp[i-1][j-1][1][0] の中の a[i-1] へのコストは、a[i-2] によって制限されている。
// その値は max(0, hillHeights[i-1] - (hillHeights[i-2] - 1)) である。
// i に家を建てることによって、a[i-1] の高さは min(hillHeights[i-1], hillHeights[i]) に制限される。
// 結果として、a[i-1] の左側の制約が min(hillHeights[i], hillHeights[i-2]) になる。
// そのため、a[i-1] の掘削コストは max(0, hillHeights[i-1] - (min(hillHeights[i], hillHeights[i-2])-1)) に変更される。
// i-1 のコストの変更を考慮し、i+1 のコストを新たに加える。
int prev_cost_i_minus1_left_influence = std::max(0, hillHeights[i-1] - (hillHeights[i-2] - 1));
int new_cost_i_minus1_left_influence = std::max(0, hillHeights[i-1] - (std::min(hillHeights[i], hillHeights[i-2]) - 1));
if (dp[i-1][j-1][1][0] != INF) {
dp[i][j][0][1] = std::min(dp[i][j][0][1],
dp[i-1][j-1][1][0]
+ new_cost_i_minus1_left_influence // 新しいi-1への左からの影響
- prev_cost_i_minus1_left_influence // 以前のi-1への左からの影響を引く
+ cost_from_right); // i+1への影響を足す
}
}
}
// Case 3: i番目の丘には家なし、i-1番目の丘には家あり (current_is_house = 0, has_house_iMinus1 = 1)
// これはi-1に家を建てた状態 (dp[i-1][j][0][1]) から遷移
dp[i][j][1][0] = dp[i-1][j][0][1];
}
}
// 各jに対する最小コストを出力
for (int j = 1; j <= (n_hills + 1) / 2; ++j) {
int min_cost_for_j = INF;
min_cost_for_j = std::min(min_cost_for_j, dp[n_hills][j][0][0]); // n番目に家なし、n-1に家なし
min_cost_for_j = std::min(min_cost_for_j, dp[n_hills][j][0][1]); // n番目に家あり、n-1に家なし
min_cost_for_j = std::min(min_cost_for_j, dp[n_hills][j][1][0]); // n番目に家なし、n-1に家あり
std::cout << min_cost_for_j << " ";
}
std::cout << std::endl;
return 0;
}
eJOI2018 D - Chemical Table
問題概要
\(N\)行\(M\)列の化学元素周期表のようなグリッドがあります。\(S\)個の既存の元素が与えられます。目標は、最小限の新しい元素を追加して、グリッドが「完全」な状態になるようにすることです。「完全」な状態とは、以下の2つの条件を満たすことを意味します。
-
全ての行が「線形依存」している：任意の2つの行\(a\)と\(b\)について、ある列\(c\)が存在し、\((a,c)\)と\((b,c)\)の両方に元素がある場合、行\(a\)と行\(b\)は「繋がっている」と定義します。最終的に、全ての行が直接的または間接的に繋がっている状態にします。
-
全ての列に元素がある：各列には少なくとも1つの元素が存在します。
最小限の追加元素数を出力してください。
解法
この問題はグラフ理論を使って解くことができます。
条件1: 全ての行が「線形依存」している
「任意の2つの行\(a\)と\(b\)について、ある列\(c\)が存在し、\((a,c)\)と\((b,c)\)の両方に元素がある場合、行\(a\)と行\(b\)は「繋がっている」」という条件は、グラフにおける連結性の定義と非常によく似ています。行をノード、列を繋がりの仲介役と考えます。
具体的には、行をノードとするグラフを構築します。各列\(c\)について、その列に元素がある全ての行のノードを互いに連結します。例えば、列\(c\)に元素が\((r_1,c), (r_2,c), \dots, (r_k,c)\)にある場合、ノード\(r_1, r_2, \dots, r_k\)を全て同じ連結成分に属するようにします。これは、\(r_1\)と\(r_2\)、\(r_2\)と\(r_3\)、\(\dots\)、\(r_{k-1}\)と\(r_k\)を連結するだけで実現できます。
このグラフを構築した後、すべての行が直接的または間接的に繋がっている状態にするには、グラフが完全に連結している必要があります。既存の元素が作る連結成分の数を数え、それが\(C\)個だったとします。これらの\(C\)個の連結成分を1つに繋ぎ合わせるためには、少なくとも\(C-1\)個の新しい元素を追加する必要があります（例えば、各連結成分から1つずつ行を選び、そこに新しい元素を追加して、全ての行がその元素を持つようにすればよい）。したがって、この条件を満たすための最小コストは\(C-1\)となります。
連結成分の数はDFSやBFS、またはUnion-Findデータ構造で効率的に計算できます。
条件2: 全ての列に元素がある
これはより単純です。既存の元素が置かれている列の数を数えます。もし\(M\)個全ての列に元素が置かれていない場合、元素が置かれていない列の数だけ新しい元素を追加する必要があります。これは、\(M\)から元素が置かれているユニークな列の数を引いた値となります。
例えば、\(U\)個のユニークな列に元素が置かれている場合、追加コストは\(M - U\)となります。または、各列\(c\)について、もしその列に元素が一つも存在しない場合、その列に新しい元素を一つ追加する必要があります。これを全ての空の列に対して行い、その数を数えます。
最終的な最小追加元素数:
上記2つの条件は互いに独立して最小化できるため、それぞれのコストを合計します。
- コスト1: (連結成分の数) - 1
- コスト2: (空の列の数)
合計は \((連結成分の数) - 1 + (空の列の数)\) となります。
時間計算量は、列ごとにグラフを構築し、DFS/BFSを行うため、\(O(N+M+S)\)となります。
以下に実装例を示します。
#include <iostream>
#include <vector>
#include <algorithm> // Not strictly needed for this code
#include <numeric> // For std::iota (optional)
const int MAX_DIM = 200005; // NとMの最大値
int num_rows, num_cols, num_elements_initial;
std::vector<int> rows_in_column[MAX_DIM]; // rows_in_column[c] は列cに元素がある行のリスト
std::vector<int> adj_rows[MAX_DIM]; // 行間の隣接リスト (グラフ構築用)
bool visited_row[MAX_DIM]; // DFSで訪問したかを記録
// DFSで連結成分を探索
void dfs_find_components(int u) {
visited_row[u] = true;
for (int v : adj_rows[u]) {
if (!visited_row[v]) {
dfs_find_components(v);
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin >> num_rows >> num_cols >> num_elements_initial;
// 既存の元素データを読み込み、列ごとの行リストを構築
for (int k = 0; k < num_elements_initial; ++k) {
int r, c;
std::cin >> r >> c;
rows_in_column[c].push_back(r);
}
int total_min_additions = 0; // 最終的な最小追加元素数
// 条件2: 全ての列に元素がある
// 各列cについて、もし元素が一つもなければ、1つ元素を追加する必要がある
for (int c = 1; c <= num_cols; ++c) {
if (rows_in_column[c].empty()) {
total_min_additions++;
} else {
// 列cに元素がある行同士をグラフで連結
// 複数の行がある場合、隣接する2つの行を連結すれば、列c内の全ての行が繋がる
for (size_t i = 0; i + 1 < rows_in_column[c].size(); ++i) {
int r1 = rows_in_column[c][i];
int r2 = rows_in_column[c][i+1];
adj_rows[r1].push_back(r2);
adj_rows[r2].push_back(r1);
}
}
}
// 条件1: 全ての行が「線形依存」している
// 連結成分の数を数える (DFSを使用)
int component_count = 0;
for (int r = 1; r <= num_rows; ++r) {
if (!visited_row[r]) {
dfs_find_components(r);
component_count++;
}
}
// 連結成分が1つだけならコスト0、そうでなければ (component_count - 1) の追加が必要
if (component_count > 0) { // 行が存在する場合のみ
total_min_additions += (component_count - 1);
}
std::cout << total_min_additions << std::endl;
return 0;
}
eJOI2018 F - Cycle Sort
問題概要
長さ\(N\)の数列\(a\)と、定数\(M\)が与えられます。1回の操作で、\(k\)個のインデックス\(x_1, x_2, \dots, x_k\)を選び、対応する要素を\(a_{x_1} \gets a_{x_k}, a_{x_2} \gets a_{x_1}, \dots, a_{x_k} \gets a_{x_{k-1}}\)のようにサイクル的に交換できます。合計操作回数を最小化し、かつ全ての操作における\(k\)の合計\(\sum k\)が\(M\)以下であるという制約の下で、数列\(a\)を非減少順にソートしてください。もし解が存在すれば操作列を出力し、そうでなければ-1を出力してください。
制約: \(N \in [1, 2 \times 10^5]\), \(M \in [0, 2 \times 10^5]\), \(a_i \in [1, 10^9]\)。
解法
まず、数列\(a\)を非減少順にソートした最終目標の数列\(a'\)を考えます。数列\(a\)の具体的な値の大小は重要ではなく、その順序が重要であるため、値の重複があっても離散化（値域圧縮）して1から始まる連続する整数にマッピングすることができます。これにより、\(a_i \in [1, N]\)として扱えます。
ソートとは、現在の位置にある要素を本来の位置に移動させることです。これをグラフの言葉で表現します。各インデックス\(i\)について、本来\(a'_i\)であるべき要素が現在\(a_i\)にあるという状況は、有向辺\(a'_i \to a_i\)で表現できます。このグラフは、すべてのノードの入次数と出次数が等しくなるため、いくつかのオイラー回路（またはサイクル）に分解できます。
各オイラー回路は1回のサイクル操作でソートできます。例えば、\(x_1 \to x_2 \to \dots \to x_k \to x_1\)というサイクルがあれば、これは1回の操作で\(k\)個の要素を移動させます。したがって、初期状態で数列が持っている全てのオイラー回路を特定し、それぞれを1回の操作でソートすれば、合計操作回数は（非自明な）オイラー回路の数となり、\(\sum k\)はサイクルを構成する要素の総数（つまり、本来の位置にない要素の総数`cnt`）となります。
初期費用:
- 最小の\(\sum k\): `cnt` (初期位置からずれている要素の総数)
- 最小の操作回数: `C` (非自明なオイラー回路の総数)
もし`cnt > M`であれば、この方法ではソートできないので、答えは-1です。
操作回数をさらに減らす最適化:
もし操作回数`C`がまだ多い場合、2つのオイラー回路を結合して1つの大きな回路にすることで、操作回数を1減らすことができます。この結合は、例えば一方の回路の要素\(x\)ともう一方の回路の要素\(y\)を一時的に交換（スワップ）する操作として行えます。このスワップ操作自体は1回の操作とみなされ、\(k=2\)のコストを\(\sum k\)に追加します。つまり、1回の操作回数の削減に対して、\(\sum k\)のコストが2増加します。
この戦略を使って、できるだけ多くの操作回数を削減します。削減できる操作回数は、`C-1`（全てを1つの回路に結合する場合）までか、あるいは\(\sum k\)の予算\(M - cnt\)を使い切るまでです。 \(\sum k\)の予算を\(M - cnt\)とすると、1回の操作削減に2のコストがかかるので、\((M-cnt)/2\)回まで操作を削減できます。
したがって、削減できる操作回数`num_merges`は \(\min(C - 1, (M - cnt) / 2)\) となります。 最終的な操作回数は `C - num_merges`、最終的な\(\sum k\)は `cnt + 2 * num_merges` です。この\(\sum k\)は必ず\(M\)以下になります。
実際の操作列の構築:
-
数列\(a\)をコピーしてソートし、目標の数列\(a'\)を`sorted_indices`として用意します。また、`a`の値を離散化します。
-
グラフを構築します。各インデックス\(i\)について、`adj[sorted_indices[i]]`から`a[i]`への有向辺を追加します。これは、`a[i]`が`sorted_indices[i]`の位置にあるべき要素であるという意味です。
-
DFSを用いて、グラフから全ての非自明なオイラー回路を抽出します。これらが初期の操作です。`cycle_list`に保存します。このとき、回路の総数`C`と、位置がずれている要素の総数`cnt`を数えます。
-
もし`cnt > M`なら-1を出力します。
-
削減できる操作回数`num_merges`を計算します。
-
実際に`num_merges`回だけ回路を結合します。例えば、`num_merges + 1`個の回路を選び、それぞれの回路から代表の要素を1つずつ選びます（例えば、各回路の最初の要素）。これらの代表要素間で`num_merges`回のスワップ操作を実行し、選ばれた`num_merges + 1`個の回路を1つの大きな回路に結合します。これにより、`a`の数列自体が変更されます。
-
変更された数列`a`で再度グラフを構築し、全てのオイラー回路を抽出し直します。
-
最終的に得られた操作列を出力します。
時間計算量は、離散化に\(O(N \log N)\)、グラフ構築とDFSによる回路抽出に\(O(N)\)かかります。結合操作も\(O(N)\)で、再度の回路抽出も\(O(N)\)です。したがって全体で\(O(N \log N)\)となります。
以下に実装例を示します。
#include <iostream>
#include <vector>
#include <algorithm> // For std::sort, std::unique, std::lower_bound
#include <map> // For std::map (optional for charToIndex)
const int MAX_N = 200005;
int n_elements;
long long m_k_budget;
long long current_a[MAX_N]; // 数列a
long long sorted_a[MAX_N]; // ソートされたa (a')
// グラフの隣接リスト
std::vector<std::pair<int, int>> adj_graph[MAX_N]; // {隣接ノード, 元のインデックス}
std::vector<bool> edge_used[MAX_N]; // エッジが使用済みか
bool visited_node[MAX_N]; // DFSで訪問済みノードを記録
std::vector<int> current_cycle_path; // 現在構築中のサイクルパス
// オイラー回路を探索するDFS
void find_euler_circuit_dfs(int u) {
visited_node[u] = true;
for (int& i = current_node_edge_idx[u]; i < adj_graph[u].size(); ++i) {
if (!edge_used[u][i]) {
edge_used[u][i] = true; // エッジを使用済みにマーク
int v = adj_graph[u][i].first;
int original_idx = adj_graph[u][i].second;
find_euler_circuit_dfs(v);
current_cycle_path.push_back(original_idx); // パスを逆順に追加
}
}
}
int current_node_edge_idx[MAX_N]; // 各ノードでどのエッジから処理を再開するか
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin >> n_elements >> m_k_budget;
std::vector<long long> distinct_values;
for (int i = 1; i <= n_elements; ++i) {
std::cin >> current_a[i];
distinct_values.push_back(current_a[i]);
}
// 値を離散化
std::sort(distinct_values.begin(), distinct_values.end());
distinct_values.erase(std::unique(distinct_values.begin(), distinct_values.end()), distinct_values.end());
for (int i = 1; i <= n_elements; ++i) {
current_a[i] = std::lower_bound(distinct_values.begin(), distinct_values.end(), current_a[i]) - distinct_values.begin() + 1;
sorted_a[i] = current_a[i]; // sorted_aを初期化
}
std::sort(sorted_a + 1, sorted_a + n_elements + 1); // 目標のソートされた数列 a'
long long misplaced_elements_count = 0; // 位置がずれている要素の総数 (初期のsum k)
for (int i = 1; i <= n_elements; ++i) {
if (sorted_a[i] != current_a[i]) {
misplaced_elements_count++;
adj_graph[sorted_a[i]].push_back({(int)current_a[i], i});
edge_used[sorted_a[i]].push_back(false);
}
}
if (misplaced_elements_count > m_k_budget) {
std::cout << -1 << std::endl;
return 0;
}
std::vector<std::vector<int>> initial_cycles;
std::fill(visited_node + 1, visited_node + n_elements + 1, false);
std::fill(current_node_edge_idx + 1, current_node_edge_idx + n_elements + 1, 0);
for (int i = 1; i <= distinct_values.size(); ++i) { // 離散化された値の範囲でループ
if (!adj_graph[i].empty() && !visited_node[i]) {
current_cycle_path.clear();
find_euler_circuit_dfs(i);
std::reverse(current_cycle_path.begin(), current_cycle_path.end()); // DFSは逆順にパスを構築するため
if (!current_cycle_path.empty()) { // 空でないサイクルのみ追加
initial_cycles.push_back(current_cycle_path);
}
}
}
int num_initial_cycles = initial_cycles.size();
long long remaining_k_budget = m_k_budget - misplaced_elements_count;
// 操作回数を減らすために結合できるサイクル数を計算
// 1回の結合で1つの操作が削減され、sum k が2増加する
int max_merges = 0;
if (num_initial_cycles > 0) { // 結合できるのは2つ以上のサイクルがある場合
max_merges = std::min(num_initial_cycles - 1, (int)(remaining_k_budget / 2));
}
// 実際にサイクルを結合する
// max_merges+1 個のサイクルを選び、それらを max_merges 回のスワップで結合する
for (int i = 0; i < max_merges; ++i) {
// initial_cycles[i][0]とinitial_cycles[i+1][0]はそれぞれのサイクルの最初の要素のインデックス
// これらをスワップすることで、2つのサイクルが1つに結合される
std::swap(current_a[initial_cycles[i][0]], current_a[initial_cycles[i+1][0]]);
}
// 結合後の数列で再度グラフを構築し、オイラー回路を抽出
for (int i = 1; i <= distinct_values.size(); ++i) {
adj_graph[i].clear();
edge_used[i].clear();
}
std::fill(visited_node + 1, visited_node + n_elements + 1, false);
std::fill(current_node_edge_idx + 1, current_node_edge_idx + n_elements + 1, 0);
for (int i = 1; i <= n_elements; ++i) {
if (sorted_a[i] != current_a[i]) {
adj_graph[sorted_a[i]].push_back({(int)current_a[i], i});
edge_used[sorted_a[i]].push_back(false);
}
}
std::vector<std::vector<int>> final_cycles;
for (int i = 1; i <= distinct_values.size(); ++i) {
if (!adj_graph[i].empty() && !visited_node[i]) {
current_cycle_path.clear();
find_euler_circuit_dfs(i);
std::reverse(current_cycle_path.begin(), current_cycle_path.end());
if (!current_cycle_path.empty()) {
final_cycles.push_back(current_cycle_path);
}
}
}
std::cout << final_cycles.size() << std::endl;
for (const auto& cycle : final_cycles) {
std::cout << cycle.size() << std::endl;
for (size_t i = 0; i < cycle.size(); ++i) {
std::cout << cycle[i] << (i == cycle.size() - 1 ? "" : " ");
}
std::cout << std::endl;
}
return 0;
}
eJOI2019 A - XORanges
問題概要
\(N\)個の自然数からなる数列\(a_1, \dots, a_N\)が与えられます。以下の2種類のクエリが\(Q\)回実行されます。
-
タイプ1: `1 x v` - \(a_x\)の値を\(v\)に変更します。
-
タイプ2: `2 l r` - 区間\([l, r]\)内の全ての部分区間のXOR和を計算し、それらのXOR和をさらにXOR結合した結果を求めます。
制約: \(N, Q \in [1, 2 \times 10^5]\)。
解法
タイプ2のクエリ「区間\([l, r]\)内の全ての部分区間のXOR和のXOR和」について考えます。XOR演算の性質上、最終的なXOR和に影響を与えるのは、合計で奇数回出現する要素だけです。偶数回出現する要素は、最終的なXOR和では打ち消し合って0になります。
区間\([l, r]\)における部分区間\([i, j]\)（\(l \le i \le j \le r\)）を考えます。ある要素\(a_k\)（\(l \le k \le r\)）が部分区間\([i, j]\)に含まれるのは、\(i \le k \le j\)の場合です。
要素\(a_k\)が区間\([l, r]\)内の全ての部分区間のXOR和のXOR和に合計で何回出現するかを計算します。 \(a_k\)を含む部分区間\([i, j]\)の数を考えます。 始点\(i\)は\([l, k]\)の範囲で選べます（\(k-l+1\)通り）。 終点\(j\)は\([k, r]\)の範囲で選べます（\(r-k+1\)通り）。 したがって、\(a_k\)は\((k-l+1) \times (r-k+1)\)回、部分区間のXOR和の計算に寄与します。
この寄与回数が奇数であれば\(a_k\)は最終的なXOR和に影響を与え、偶数であれば影響を与えません。よって、\((k-l+1) \times (r-k+1)\)が奇数となる条件を考えます。
積が奇数になるのは、両方の因子が奇数である場合のみです。
ケース1: \(l\)と\(r\)のパリティが同じ場合 (\(l \pmod 2 = r \pmod 2\))
- \((k-l+1)\)が奇数 \(\Leftrightarrow k\)と\(l\)のパリティが同じ。
- \((r-k+1)\)が奇数 \(\Leftrightarrow r\)と\(k\)のパリティが同じ。
両方を満たすためには、\(k\)が\(l\)と同じパリティである必要があります（\(l\)と\(r\)が同じパリティなので、これは\(k\)が\(r\)と同じパリティであることと同義です）。 したがって、\(l\)と\(r\)のパリティが同じ場合、最終的なXOR和は、区間\([l, r]\)内でインデックス\(k\)が\(l\)と同じパリティを持つ全ての\(a_k\)のXOR和となります。
ケース2: \(l\)と\(r\)のパリティが異なる場合 (\(l \pmod 2 \neq r \pmod 2\))
- \((k-l+1)\)が奇数 \(\Leftrightarrow k\)と\(l\)のパリティが同じ。
- \((r-k+1)\)が奇数 \(\Leftrightarrow r\)と\(k\)のパリティが同じ。
もし\(k\)が\(l\)と同じパリティを持つとすると、\(k\)と\(r\)は異なるパリティを持つことになります。これにより、\((r-k+1)\)は偶数になります。 もし\(k\)が\(r\)と同じパリティを持つとすると、\(k\)と\(l\)は異なるパリティを持つことになります。これにより、\((k-l+1)\)は偶数になります。 どちらの場合も、少なくとも1つの因子は偶数になるため、積\((k-l+1) \times (r-k+1)\)は常に偶数となります。 したがって、\(l\)と\(r\)のパリティが異なる場合、最終的なXOR和は常に0となります。
実装方法:
上記の分析から、クエリは以下のいずれかに帰着します。
- \(l, r\)が同じパリティ: 区間\([l, r]\)内の、\(l\)と同じパリティのインデックスを持つ要素\(a_k\)のXOR和。
- \(l, r\)が異なるパリティ: 0。
これは、Binary Indexed Tree (BIT) を2つ使用して効率的に処理できます。1つは奇数インデックスの要素のXOR和を管理し、もう1つは偶数インデックスの要素のXOR和を管理します。
- `update(idx, val)`: \(a_{idx}\)の値を\(val\)に変更します。`idx`のパリティに応じて、対応するBITを更新します。
- `query_range_xor(l, r, parity)`: 区間\([l, r]\)内で`parity`を持つインデックスの要素のXOR和を返します。BITの通常のXOR区間和クエリと同様に行います。
時間計算量: タイプ1クエリは\(O(\log N)\)。タイプ2クエリは\(O(\log N)\)。合計で\(O(Q \log N)\)となります。
以下に実装例を示します。
#include <iostream>
#include <vector>
#include <numeric> // For std::fill
const int MAX_N = 200005;
// Binary Indexed Tree (BIT) を実装
// XOR演算なので、通常のBITの和をXORに置き換える
struct XORBIT {
std::vector<int> bit_odd; // 奇数インデックスのXOR和を管理
std::vector<int> bit_even; // 偶数インデックスのXOR和を管理
int size;
XORBIT(int n) : size(n), bit_odd(n + 1, 0), bit_even(n + 1, 0) {}
// bit_array を更新
void update_single(std::vector<int>& bit_array, int idx, int val) {
for (; idx <= size; idx += (idx & -idx)) {
bit_array[idx] ^= val;
}
}
// bit_array からXORプレフィックス和をクエリ
int query_prefix_xor_single(std::vector<int>& bit_array, int idx) {
int res = 0;
for (; idx > 0; idx -= (idx & -idx)) {
res ^= bit_array[idx];
}
return res;
}
// 値の変更
void update(int idx, int old_val, int new_val) {
if (idx % 2 == 1) { // 奇数インデックス
update_single(bit_odd, idx, old_val);
update_single(bit_odd, idx, new_val);
} else { // 偶数インデックス
update_single(bit_even, idx, old_val);
update_single(bit_even, idx, new_val);
}
}
// 区間 [1, idx] の、指定されたパリティのインデックスのXOR和をクエリ
int query_prefix_xor_with_parity(int idx, int required_parity) {
if (required_parity % 2 == 1) { // 奇数インデックスが必要
return query_prefix_xor_single(bit_odd, idx);
} else { // 偶数インデックスが必要
return query_prefix_xor_single(bit_even, idx);
}
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n_elements, num_queries;
std::cin >> n_elements >> num_queries;
std::vector<int> current_values(n_elements + 1);
XORBIT bit(n_elements);
// 初期数列を読み込み、BITを構築
for (int i = 1; i <= n_elements; ++i) {
std::cin >> current_values[i];
if (i % 2 == 1) {
bit.update_single(bit.bit_odd, i, current_values[i]);
} else {
bit.update_single(bit.bit_even, i, current_values[i]);
}
}
for (int q = 0; q < num_queries; ++q) {
int type;
std::cin >> type;
if (type == 1) {
int x_idx, v_new_val;
std::cin >> x_idx >> v_new_val;
bit.update(x_idx, current_values[x_idx], v_new_val);
current_values[x_idx] = v_new_val;
} else {
int l_left, r_right;
std::cin >> l_left >> r_right;
if ((l_left % 2) == (r_right % 2)) { // lとrのパリティが同じ場合
int required_parity = l_left % 2;
int xor_sum_r = bit.query_prefix_xor_with_parity(r_right, required_parity);
int xor_sum_l_minus_1 = bit.query_prefix_xor_with_parity(l_left - 1, required_parity);
std::cout << (xor_sum_r ^ xor_sum_l_minus_1) << "\n";
} else { // lとrのパリティが異なる場合
std::cout << 0 << "\n";
}
}
}
return 0;
}
eJOI2019 B - Hanging Rack
問題概要
吊り下げ式の棚があり、\(N\)レベルの構造をしています。各レベルにはバランスバーがあり、その両端にフックをかけることができます。フックは左右に移動できますが、最も上のバランスバーは常にバランスが取れていなければなりません。最も下のレベルのフック位置は常に1です。最終的に、最上段のバランスバーから一番右側のフックがどこに配置されるか、モジュロ\(10^9+7\)で答えてください。入力として\(N\)（レベル数）と\(M\)（最上段の左から数えたフックの位置）が与えられます。
制約: \(N \in [1, 10^6]\)。
解法
この問題は、吊り下げ式の棚の構造が再帰的な性質を持つことを利用して解くことができます。棚の最も上のバランスバーを考えます。このバーは、左右に2つのフックをかけることができます。それぞれのフックの下には、さらに\(N-1\)レベルの小さな棚が吊り下がっています。重要なのは、各バランスバーが常に水平に保たれることです。
最上段のフックの位置\(M\)が与えられたとき、それは最終的なバランス位置です。この\(M\)が奇数か偶数かによって、その下のサブシステムの構成が異なります。位置は1-indexedで考えます。
もし\(M\)が奇数である場合：
これは、最上段のバランスバーが左側のサブシステムを通じてバランスを取っていることを意味します。この場合、最上段のバー自身は右側に寄与する部分がありません。問題は\(N-1\)レベルのサブシステムに還元され、そのサブシステムにおけるフックの位置は\((M+1)/2\)となります（奇数の位置は全て左半分のフックが担当し、サブシステムに換算すると位置が半分になる）。このとき、最終的な右側のフック位置への寄与は0です。
もし\(M\)が偶数である場合：
これは、最上段のバランスバーが右側のサブシステムを通じてバランスを取っていることを意味します。この場合、最上段のバー自身が右側に\(2^{N-1}\)の寄与をします（最も右側のフックへの距離が\(2^{N-1}\)であることを意味する）。そして、問題は\(N-1\)レベルのサブシステムに還元され、そのサブシステムにおけるフックの位置は\(M/2\)となります。
このプロセスを\(N\)が0になるまで繰り返します。初期の右端フック位置の合計は1です（最も下のレベルのフック位置）。
アルゴリズム:
-
初期の最終フック位置`final_position`を1とします。
-
\(2^0, 2^1, \dots, 2^{N-1}\)をモジュロ\(10^9+7\)で前計算しておきます。
-
\(N > 0\)である限り、以下のステップを繰り返します。
- もし\(M\)が奇数であれば、\(N \gets N-1\)、\(M \gets (M+1)/2\)。`final_position`は変更なし。
- もし\(M\)が偶数であれば、\(N \gets N-1\)、\(M \gets M/2\)。`final_position \gets (final_position + 2^N) \pmod{10^9+7}`。
-
最終的な`final_position`を出力します。
時間計算量は、前計算に\(O(N)\)かかり、ループは\(N\)回実行されるため、合計で\(O(N)\)となります。ここでいう\(N\)は問題のレベル数です。
以下に実装例を示します。
#include <iostream>
#include <vector>
using ll = long long;
const int MOD = 1000000007;
const int MAX_N_LEVELS = 1000005;
ll powersOfTwo[MAX_N_LEVELS]; // powersOfTwo[i] = 2^i % MOD
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int num_levels; // N
ll hook_position; // M
std::cin >> num_levels >> hook_position;
// 2のべき乗を前計算
powersOfTwo[0] = 1;
for (int i = 1; i <= num_levels; ++i) {
powersOfTwo[i] = (powersOfTwo[i-1] * 2) % MOD;
}
ll final_rightmost_position = 1; // 最も下のフック位置は1
// レベルが1以上である限り再帰的に処理
while (num_levels > 0) {
if (hook_position % 2 == 1) { // Mが奇数の場合 (左側のサブシステムが使用される)
num_levels--;
hook_position = (hook_position + 1) / 2;
// 右端のフック位置への直接的な寄与はなし
} else { // Mが偶数の場合 (右側のサブシステムが使用される)
num_levels--;
hook_position /= 2;
// このレベルからの右端フックへの寄与は 2^num_levels
final_rightmost_position = (final_rightmost_position + powersOfTwo[num_levels]) % MOD;
}
}
std::cout << final_rightmost_position << std::endl;
return 0;
}
eJOI2019 D - Tower
問題概要
塔を建てます。最初は1層で数値は1です。各ステップでは、既に存在する層の中から区間\([l, r]\)を選び、それらの層の数値の合計を計算して塔の最上部に新しい層として追加します。与えられた目標数値\(N\)に対して、最上部の層が\(N\)となるような塔を構築するのに必要な最小ステップ数と、その構築手順（各ステップでの\((l,r)\)のペア）を出力してください。複数のテストケースがあります。
制約: \(N \in [1, 10^{18}]\)。
解法
最小ステップ数を求めるためには、各ステップで塔の最上部にできるだけ大きな数値を置くのが最適です。最も効果的な方法は、常に既存の全ての層の数値を合計して新しい層を作ることです。
この「常に全てを合計」する戦略で塔を構築すると、層の数値は以下のようになります（1層目が数値1、ステップ1が2層目、...）。
- 層1: 1 (初期層)
- ステップ1 (\(l=1, r=1\)): 層2 = 1 (層1の合計)
- ステップ2 (\(l=1, r=2\)): 層3 = 1 + 1 = 2 (層1〜2の合計)
- ステップ3 (\(l=1, r=3\)): 層4 = 1 + 1 + 2 = 4 (層1〜3の合計)
- ステップ\(k-1\) (\(l=1, r=k-1\)): 層\(k\) = \(\sum_{i=1}^{k-1} (\text{層}i \text{の数値}) = 2^{k-2}\) (ただし\(k \ge 2\))
したがって、\(K\)ステップ後には\(K+1\)層の塔ができており、最上部（層\(K+1\)）の数値は\(2^{K-1}\)です。目標値\(N\)を達成するには、\(2^{K-1} \ge N\)となる最小の\(K\)が必要です。これは\(K = \lceil \log_2 N \rceil + 1\)で求められます。この\(K\)が最小ステップ数となります。
構築手順:
最小ステップ数\(K\)が確定したら、まず「常に全てを合計」する戦略で塔を構築した場合の最終層の数値\(max\_val = 2^{K-1}\)を考えます。目標は\(N\)なので、`deficit = max_val - N`だけ最終層の数値を減らす必要があります。
この`deficit`を減らすために、過去のステップの一部を「全てを合計」ではなく「2層目から合計」に切り替えます。 ステップ\(j\)で新しい層\((j+1)\)を構築する際、デフォルトでは\((l=1, r=j)\)を選び、層1から層\(j\)までの全てを合計します。これを\((l=2, r=j)\)に変更すると、層1（数値1）が合計から除外され、層\((j+1)\)の数値が1減ります。 この層\((j+1)\)における数値の1の減少は、それ以降の層の数値にも影響を与え、最終層\((K+1)\)の数値は\(2^{K-j-1}\)だけ減少します。
ステップ\(j\)は\(1\)から\(K-1\)まであります。 ステップ\(j\)（新しい層\((j+1)\)を作成）を\((l=1, r=j)\)から\((l=2, r=j)\)に変更することで、最終層の数値が減少する量は、\(j\)が\(1\)から\(K-1\)まで動くとき、 \(2^{K-1-1} = 2^{K-2}\) (\(j=1\), 層2を調整) \(2^{K-2-1} = 2^{K-3}\) (\(j=2\), 層3を調整) ... \(2^{K-(K-1)-1} = 2^0\) (\(j=K-1\), 層Kを調整) となり、これは\(2^0, 2^1, \dots, 2^{K-2}\)という形の減少量を与えます。
`deficit = max_val - N` を2進数分解すると、これらの減少量を組み合わせて`deficit`を正確に作り出すことができます。 構築手順の概要:
-
最小ステップ数`ans`を計算します。
-
最初の操作は常に`1 1`です（初期の層1を合計して新しい層2を作ります）。
-
`deficit = (1LL << (ans-1)) - N`を計算します。
-
ステップ\(j\) (`j`は`ans-1`から`2`まで減少) について、 もし`deficit`の\((j-2)\)番目のビットが立っていれば、そのステップは\((l=2, r=j)\)とします。 そうでなければ、そのステップは\((l=1, r=j)\)とします。 ここで`r`は、現在のステップが生成する層のインデックスです。ステップ\(k\)が層\((k+1)\)を生成する場合、`r`は`k`となります。
-
最後の操作は、最終的に目標値\(N\)を生成するもので、通常は\((l=1, r=ans)\)となります。
例えば、N=3の場合:
`ans` = 3 (3ステップ)
- ステップ1: `1 1`
- `deficit = (1LL << (3-1)) - 3 = (1LL << 2) - 3 = 4 - 3 = 1`
- ループ: `i`は`ans-1=2`から`2`まで。つまり`i=2`のみ。 * `deficit`の\((i-2)\)番目のビット、つまり\((2-2)=0\)番目のビットを確認。`deficit=1`の0番目のビットは1。 * よって、ステップ2の`l`は`2`。`r`は`ans-i+1`。`ans=3, i=2`なので`r = 3-2+1=2`。 * ステップ2: `2 2`
- 最後のステップ: `1 ans` \(\to\) `1 3`
出力:
3 1 1 2 2 1 3
時間計算量は、各テストケースで`log N`回の計算と`log N`回の出力があるため、\(O(T \log N)\)となります。
以下に実装例を示します。
#include <iostream>
#include <vector>
#include <cmath> // For std::ceil, std::log2 (not directly used for 1LL << ans)
#include <algorithm> // Not directly needed
using ll = long long;
void solve_test_case() {
ll target_n;
std::cin >> target_n;
int num_steps = 0;
// 最小ステップ数を計算: 2^(num_steps-1) >= target_n となる最小の num_steps
// 例えば target_n=1 -> num_steps=1 (2^0=1)
// target_n=2 -> num_steps=2 (2^1=2)
// target_n=3 -> num_steps=3 (2^2=4, 2^1=2 < 3)
// current_power_of_2 は (1LL << num_steps) と等価
while ((1LL << num_steps) < target_n) {
num_steps++;
}
num_steps++; // num_stepsは操作回数なので、1つ増やす
std::cout << num_steps << "\n";
// 最初の操作は常に層1を合計して新しい層2を作る
std::cout << "1 1\n";
// 理想的な最大の塔の最終層の数値 (1, 1, 2, 4, ..., 2^(num_steps-2) という構成の場合の全層の合計)
// これは 2^(num_steps-1) になる
ll max_possible_sum = (1LL << (num_steps - 1));
ll deficit_to_reduce = max_possible_sum - target_n;
// 各ステップを逆順に調整
// i は操作のインデックス (2, ..., num_steps-1) に対応
// 具体的には、層 i を構築する操作を調整
for (int i = num_steps - 1; i >= 2; --i) {
// deficit_to_reduce の (i-2) 番目のビットが立っているかを確認
// このビットが立っていれば、このステップで層1を含まないようにする (l=2)
// 2^(num_steps - i - 1) が減少量
ll l_value = 1;
if ((deficit_to_reduce & (1LL << (i - 2)))) {
l_value = 2;
}
// r_value は、このステップで合計する最も高い層のインデックス
// 層 i を構築する場合、合計するのは層 1 から層 (i-1) まで
// なので、r の値は (i-1)
std::cout << l_value << " " << i << "\n";
}
// 最後の操作は、最終的に目標値 N を達成する
// この操作は、既存のすべての層 (層 1 から層 num_steps まで) を合計する
std::cout << "1 " << num_steps << "\n";
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int num_test_cases;
std::cin >> num_test_cases;
while (num_test_cases--) {
solve_test_case();
}
return 0;
}
eJOI2019 F - Awesome Arrowland Adventure
問題概要
\(N\)行\(M\)列のグリッドがあります。各セル\((r, c)\)には、矢印（N, E, S, Wのいずれか）が描かれているか、または通行不能な障害物('X')があります。セル\((1,1)\)から開始し、セル\((N,M)\)に到達したいです。移動のコストは、現在のセルの矢印を移動したい方向に合わせるために必要な90度回転の回数です。例えば、北を指す矢印を東に動かすには1回、南に動かすには2回、西に動かすには1回（反時計回り）の回転が必要です。最小コストで\((N,M)\)に到達するためのコストを求めてください。到達できない場合は-1を出力します。
制約: \(N, M \in [1, 500]\)。
解法
この問題は、グリッド上の最短経路問題として捉えることができます。辺の重みが0または1であるため、Dijkstraアルゴリズムを改良した0-1 BFS（またはdeque-based BFS）を使用すると、より高速に解くことができます。
グラフの構築
通常のグリッドグラフでは、ノードがセル\((r,c)\)で、辺の重みが回転コストになります。しかし、矢印の方向によってコストが変わるため、セルの状態をより詳細に表現する必要があります。そこで、各セル\((r,c)\)について、4つの状態ノードを定義します。
状態ノード: \((r, c, \text{current_direction})\)
- \((r, c)\): セルの座標
- `current_direction`: そのセルにいるときに矢印が指している方向（N, E, S, W）
総ノード数は\(N \times M \times 4\)となります。各ノードから以下の2種類の辺を張ります。
-
同じセル内での方向転換: ノード \((r, c, \text{dir1})\) からノード \((r, c, \text{dir2})\) へ辺を張ります。コストは、`dir1`から`dir2`へ90度回転させるのに必要な回転回数です（時計回りまたは反時計回りで1回）。例えば、`dir2 = (dir1 + 1) % 4`（時計回り90度）の場合、コストは1です。`dir2 = (dir1 + 2) % 4`（180度）の場合、コストは2です。これらは1回の90度回転でコスト1の辺として表現することも可能です。
-
隣接セルへの移動: ノード \((r, c, \text{dir1})\) から、`dir1`が指す方向にある隣接セル \((r', c')\) へ移動します。この移動自体はコスト0です。移動先のセル\((r', c')\)では、そのセルの矢印の方向を向いている状態\((r', c', \text{arrow_at_target_cell_dir})\) に遷移します。この辺の重みは0です。
すべての辺の重みが0または1であるため、通常の優先度キューベースのDijkstraではなく、`std::deque`を用いた0-1 BFSで最短経路を計算できます。
- コスト0の辺への遷移は`deque.push_front()`
- コスト1の辺への遷移は`deque.push_back()`
初期状態: セル\((1,1)\)の矢印の方向を`initial_dir`とすると、ノード\((1,1, \text{initial_dir})\)の距離を0とします。
目標状態: セル\((N,M)\)の矢印の方向を`target_dir`とすると、ノード\((N,M, \text{target_dir})\)の距離が最終的な答えとなります。
制約\(N, M \le 500\)なので、ノード総数は\(500 \times 500 \times 4 = 10^6\)。0-1 BFSは\(O(V+E)\)で実行可能で、この場合\(O(NM)\)となり、十分高速です。
以下に実装例を示します。
#include <iostream>
#include <vector>
#include <string>
#include <queue> // For std::priority_queue (if using standard Dijkstra)
#include <deque> // For 0-1 BFS
#include <algorithm> // For std::min
#include <cstring> // For memset
const int INF = 0x3f3f3f3f; // 十分大きな値
const int MAX_DIM = 505;
int n_rows, m_cols;
char grid_arrows[MAX_DIM][MAX_DIM];
// 方向を整数にマッピング: N=0, E=1, S=2, W=3 (時計回り)
int dir_to_int[128];
// 方向ベクトル: N, E, S, W
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
// グリッド座標が有効かどうかをチェック
bool is_valid(int r, int c) {
return r >= 1 && r <= n_rows && c >= 1 && c <= m_cols;
}
// DPテーブル: dis[node_id] はノードへの最短距離
int dist[MAX_DIM * MAX_DIM * 4 + 1]; // 各セル(r,c)に4つの方向ノード
// ノードIDを計算するヘルパー関数
// (r, c, dir) -> ユニークな整数ID
// 例えば、(r-1)*m_cols + (c-1) でセルのベースインデックスを取得し、それに方向をオフセット
// ここでは元のコードのインデックス戦略に倣う: (cell_idx * 4 - dir_val)
// (1,1,N) -> 4*1-0 = 4, (1,1,E) -> 4*1-1 = 3, (1,1,S) -> 4*1-2 = 2, (1,1,W) -> 4*1-3 = 1
int get_node_id(int r, int c, int dir_val) {
int cell_base_idx = (r - 1) * m_cols + c; // 1-indexed cell
return cell_base_idx * 4 - dir_val;
}
void solve_01_bfs() {
std::deque<int> q_bfs;
std::fill(dist, dist + MAX_DIM * MAX_DIM * 4 + 1, INF); // 距離を無限大で初期化
// 開始地点 (1,1) の矢印の方向を初期状態とする
int initial_dir_at_start = dir_to_int[grid_arrows[1][1]];
int start_node_id = get_node_id(1, 1, initial_dir_at_start);
dist[start_node_id] = 0;
q_bfs.push_front(start_node_id);
while (!q_bfs.empty()) {
int u_id = q_bfs.front();
q_bfs.pop_front();
// ノードIDから(r, c, dir)を逆算
int u_cell_base_idx = (u_id + 3) / 4; // u_idを4で割って切り上げ -> cell_base_idx
int u_r = (u_cell_base_idx - 1) / m_cols + 1;
int u_c = (u_cell_base_idx - 1) % m_cols + 1;
int u_dir = (u_cell_base_idx * 4 - u_id); // 0,1,2,3
// Case 1: 同じセル内での方向転換 (コスト1)
for (int next_dir_change = 0; next_dir_change < 4; ++next_dir_change) {
if (next_dir_change == u_dir) continue; // 同じ方向はスキップ
int v_id_turn = get_node_id(u_r, u_c, next_dir_change);
// コストは、現在の矢印からその方向へ到達するまでの90度回転の最小回数
// 例えばN(0)->E(1)は1, N(0)->S(2)は2, N(0)->W(3)は1
// (dir1 - dir2 + 4) % 4 が時計回り方向へのステップ数
// (dir2 - dir1 + 4) % 4 が反時計回り方向へのステップ数
// 回転回数は min(時計回りステップ, 反時計回りステップ)
int rot_cost = std::min((next_dir_change - u_dir + 4) % 4, (u_dir - next_dir_change + 4) % 4);
if (dist[u_id] + rot_cost < dist[v_id_turn]) {
dist[v_id_turn] = dist[u_id] + rot_cost;
// 回転コストが1なので、dequeのbackに追加
q_bfs.push_back(v_id_turn);
}
}
// Case 2: 矢印が指す隣接セルへの移動 (コスト0)
// 現在の矢印 u_dir が指す隣接セルへ
int next_r = u_r + dr[u_dir];
int next_c = u_c + dc[u_dir];
if (is_valid(next_r, next_c) && grid_arrows[next_r][next_c] != 'X') {
int arrow_dir_at_target_cell = dir_to_int[grid_arrows[next_r][next_c]];
int v_id_move = get_node_id(next_r, next_c, arrow_dir_at_target_cell);
// 移動コストは0
if (dist[u_id] < dist[v_id_move]) {
dist[v_id_move] = dist[u_id];
// コスト0なので、dequeのfrontに追加
q_bfs.push_front(v_id_move);
}
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin >> n_rows >> m_cols;
for (int i = 1; i <= n_rows; ++i) {
for (int j = 1; j <= m_cols; ++j) {
std::cin >> grid_arrows[i][j];
}
}
// 方向マッピング
dir_to_int['N'] = 0;
dir_to_int['E'] = 1;
dir_to_int['S'] = 2;
dir_to_int['W'] = 3;
dir_to_int['X'] = -1; // 'X'は無効な方向
// 開始地点 (1,1) が通行不能な場合
if (grid_arrows[1][1] == 'X') {
std::cout << -1 << std::endl;
return 0;
}
solve_01_bfs();
// 目的地点 (N,M) の矢印の方向での最短距離を結果とする
int target_dir_at_end = dir_to_int[grid_arrows[n_rows][m_cols]];
int end_node_id = get_node_id(n_rows, m_cols, target_dir_at_end);
if (dist[end_node_id] == INF) {
std::cout << -1 << std::endl; // 到達不能
} else {
std::cout << dist[end_node_id] << std::endl;
}
return 0;
}