公式
D - 分身 解説 by QCFium
\(x, y\) が同じであれば、二つの種類の操作をどのような順番で行っても最終的に少なくとも一人の忍者がいるマスは変わりません。これは、最初に忍者がいるマス \(i\) を一つとって考えたとき、最終的にそのマス由来の忍者が少なくとも一人いるマスは、\(i - x \le j \le i + y\) を満たす マス \(j\) であることから分かります。
また、どちらかの操作を \(N\) 回以上行う意味はありません。
よって \(x, y\) を \(0 \le x, y \lt N\) の範囲で全探索し、それぞれの \(x, y\) について実際に最終的にすべてのマスに少なくとも一人の忍者がいる状態になるかを判定し、条件を満たすもののうち \(x + y\) が最小になる \(x, y\) を出力すればよいです。
\(x + y\) が最小になるような \(x, y\) を求めるのは以下のようにしてできます。
- 今までの \(x + y\) の最小値を持つ変数 \(\mathrm{sum\_min}\) を十分大きい値で初期化する
- \(x + y\) が最小になるような \(x, y\) を保存する変数 \(\mathrm{x\_res}, \mathrm{y\_res}\) を用意する
- \(x, y\) を全探索して、今調べている \((x, y)\) が最終的にすべてのマスに少なくとも一人の忍者がいるようなものだったら :
- もし \(\mathrm{sum\_min} > x + y\) なら \(\mathrm{sum\_min}\) を \(x + y\) で置き換え、\(\mathrm{x\_res}, \mathrm{y\_res}\) を \(x, y\) で置き換える。
解答例 (C++)
#include <algorithm>
#include <string>
#include <iostream>
int main() {
int n;
std::string s;
std::cin >> n >> s;
int sum_min = 1000000000;
int x = -1, y = -1;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
std::string t = s;
for (int k = 0; k < i; k++) for (int l = 1; l < n; l++) if (t[l] == '#') t[l - 1] = '#';
for (int k = 0; k < j; k++) for (int l = n - 1; l; l--) if (t[l - 1] == '#') t[l] = '#';
bool ok = true;
for (auto c : t) if (c != '#') ok = false;
if (ok && sum_min > i + j) sum_min = i + j, x = i, y = j;
}
printf("%d %d\n", x, y);
return 0;
}
投稿日時:
最終更新: