2024-01-26

C - Sending Messages / Codeforces Round 920 (Div. 3)

問題

携帯電話で $n$ 件のメッセージを時刻 ${m}_{1}, \, {m}_{2}, \, \cdots , \, {m}_{n}$ （ただし、 ${m}_{i} \lt {m}_{i + 1}$ ）に送らなければならない。ただし、時刻 $0$ にて携帯には $f$ 単位の電力しか残っていない。また、時刻 $0$ では携帯の電源はついている。

携帯電話は、 $1$ 単位時間で $a$ 単位の電力を消費する。

また、どの時刻でも携帯の電源を落とし、その後携帯の電源を付けることができる。この操作には $b$ 単位の電力を消費する。

携帯電話の残り電力が $0$ 以下になってしまうと、それ以降ではメッセージを送ることができない。

このとき、携帯電話を充電することなく、すべてのメッセージを送信できるかを判定せよ。

入力

まず最初の1行目に、テストケースの個数を表す整数 $t$ が与えられる。

その後、 $t$ 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

まず最初の1行目に、整数 $n, \, f, \, a, \, b$ が与えられる。
次の1行に、整数 ${m}_{1}, \, {m}_{2}, \, \cdots , \, {m}_{n}$ が順に与えられる。

条件

実行時間制限: 2s
メモリ制限: 512MB
$1 \leq t \leq {10}^{4}$
- すべてのテストケースにおける $n$ の値の合計は $2 \cdot {10}^{5}$ を超えない。
$1 \leq f, \, a, \, b \leq {10}^{9}$
- ${m}_{i} \lt {m}_{i + 1}$

出力

各テストケースに対し、すべてのメッセージを送信できる場合は YES を、できない場合は NO を出力すること。

解法

$(i - 1)$ 個目のメッセージを送ってから、 $i$ 個目のメッセージを送る際には、以下の2通りの操作のいずれかを行うことが考えられます。

電源をそのままつけておく: 電力を $a({m}_{i} - {m}_{i - 1})$ だけ消費する
メッセージを送った瞬間に電源を切り、次のメッセージを送る直前に電源を付ける: 電力を $b$ だけ消費する

従って、メッセージを送り切るためには、消費電力をなるべく最小限に抑えることが必要なので、このうちの消費電力が小さい方を選んでいくことになります。

このようにして得られる消費電力の総量が $f$ よりも小さいときに $n$ 個のメッセージをすべて送りきれ、そうでないときにはメッセージを送りきることができないと判定できます。

すなわち、数式に直すと \begin{align} \sum_{i = 1}^{n} \min (a ({m}_{i} - {m}_{i - 1}), \, b) < f \end{align} が成立すればメッセージを送りきれるということになります。

この左辺の値は $O(n)$ の計算量で求めることができるので、これは実行時間制限に十分間に合うと言えます。

ソースコード

各テストケースに対して、 $n$ 個のメッセージすべてを送りきれるかどうかを判定する関数 solve() を以下のように実装しました。

int n;
ll f, a, b, m[int(2e5 + 5)];

bool solve() {
  // 値の入力
  cin >> n >> f >> a >> b;
  for (int i = 1; i <= n; i++) {
    cin >> m[i];
  }

  ll c = 0; // c はすべての消費電力量を表す
  for (int i = 1; i <= n; i++) {
    c += min(a * (m[i] - m[i - 1]), b); // i 個目のメッセージを送るための消費電力を足していく
  }

  return c < f; // c < f であれば、メッセージを送りきれるので、これを返す
}

提出したコード: https://codeforces.com/contest/1921/submission/243260846
GitHub

2024-01-26

B - Arranging Cats / Codeforces Round 920 (Div. 3)

CF1921 Codeforces C++ Div.3 Codeforces Round 920 Diff 800 競技プログラミング

問題

$n$ 個の箱があり、そのそれぞれには猫が入っている可能性がある。猫が入っているかどうかは数列 ${b}_{1}, \, \cdots , \, {b}_{n}$ で与えられ、 ${b}_{i} = 1$ であれば箱 $i$ に猫が入っており、 ${b}_{i} = 0$ であれば箱 $i$ に猫はいない。

この状況下で、以下の操作のいずれかを何回でも行える。

猫の入っていない箱に、新たに猫を入れる。
- このとき ${b}_{i} = 0$ である箱 $i$ に対して、 ${b}_{i} = 1$ とする。
猫の入っている箱から、猫を取り出す。
- このとき ${b}_{i} = 1$ である箱 $i$ に対して、 ${b}_{i} = 0$ とする。
猫の入っている箱から猫を取り出し、他の猫の入っていない箱にその猫を入れる。
- このとき ${b}_{i} = 1, \, {b}_{j} = 0$ である箱 $i, \, j$ に対して、 ${b}_{i} = 0, \, {b}_{j} = 1$ とする。

$n$ 個の箱の初期状態を数列 ${s}_{1}, \, \cdots , \, {s}_{n}$ とし、最終的に $n$ 個の箱の状態を数列 ${f}_{1}, \, \cdots , \, {f}_{n}$ としたいとき、以上の操作を行う回数の最小値を求めよ。

入力

まず最初の1行目に、テストケースの個数を表す整数 $t$ が与えられる。

その後、 $t$ 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

まず最初の1行目に、整数 $n$ が与えられる。
次の1行に、文字列 ${s}_{1} {s}_{2} \cdots {s}_{n}$ が与えられる。
次の1行に、文字列 ${f}_{1} {f}_{2} \cdots {f}_{n}$ が与えられる。

条件

実行時間制限: 2s
メモリ制限: 512MB
$1 \leq t \leq {10}^{4}$
- すべてのテストケースにおける $n$ の値の合計は ${10}^{5}$ を超えない。
${s}_{i}, \, {f}_{i} =$ 0 または 1 である。

出力

各テストケースに対して、答えを1行で出力すること。

解法

操作のうち、操作1と操作2のみが行える場合について考えます。

操作1では猫を新たに箱に投入することになるので、 ${s}_{i} =$ 0 かつ ${f}_{i} =$ 1 である $i$ の個数分だけ操作1を行うことになります。（この回数を、以下 $x$ とします。）

同様に、操作2では猫を箱から取り出すことになるので、 ${s}_{i} =$ 1 かつ ${f}_{i} =$ 0 である $i$ の個数分だけ操作2を行うことになります。（この回数を、以下 $y$ とします。）

ここで、操作3では「箱から猫を取り出し、その猫を空の箱に入れる」という操作なので、操作2を行った直後に操作1を行うのと同じ作業ということが言えます。従って、 $x, \, y$ のうち小さい値の方の回数分だけ作業3を行うことができます。

作業3を行うことにより、作業1, 2を1回ずつ行うという作業回数を、作業3を1回行うという作業回数へ減らすことができることから、全体での作業回数の最小値は、 \begin{align} x + y - \min (x, \, y) \end{align} によって与えられます。ここで、 $x, \, y$ は2つの値であることから、 $x + y = \min (x, \, y) + \max (x, \, y)$ が必ず成り立ちます。従って、 \begin{align} x + y - \min (x, \, y) = \max (x, \, y) \end{align} が成立します。

よって、求める回数は $\max (x, \, y)$ であるので、 $x, \, y$ の値を求めることにより、この問題の解答が得られます。

また、 $x, \, y$ の値は $O(n)$ の計算量で求められ、これは実行時間制限に十分間に合うと考えられます。

ソースコード

操作回数の最小値を返す関数 solve() を以下のように実装しました。

int n;
string s, f;

int solve() {
  // 値の入力
  cin >> n;
  cin >> s;
  cin >> f;

  int x = 0, y = 0;
  for (int i = 0; i < n; i++) {
    // s[i] と f[i] が異なるとき、 x または y の値が 1 増える
    if (s[i] != f[i]) {
      if (s[i] == '0') {
        x++; // s[i] = '0', f[i] = '1' のときには x が 1 増える
      } else {
        y++; // s[i] = '1', f[i] = '0' のときには y が 1 増える
      }
    }
  }

  return max(x, y); // x, y のうち大きい方を返す
}

提出したコード: https://codeforces.com/contest/1921/submission/243249457
GitHub

2024-01-26

A - Square / Codeforces Round 920 (Div. 3)

CF1921 Codeforces C++ Div.3 Codeforces Round 920 Diff 800 競技プログラミング

問題

座標軸に平行な辺を持つ座標平面上に正方形が存在する。この頂点がランダムな順序で与えられるとき、その正方形の面積を求めよ。

入力

まず最初の1行目に、テストケースの個数を表す整数 $t$ が与えられる。

その後、 $t$ 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

4行に渡り、正方形の頂点にあたる座標 ${x}_{i}, \, {y}_{i}$ がそれぞれ1行ずつ与えられる。

条件

実行時間制限: 1s
メモリ制限: 256MB
$1 \leq t \leq 100$
$-1000 \leq {x}_{i}, \, {y}_{i} \leq 1000$

出力

各テストケースに対して、正方形の面積を1行で出力すること。

解法

与えられる4つの座標はランダムではありますが、いずれも正方形の頂点を表します。従って、 $x, \, y$ の値はそれぞれ2種類ずつ与えられるということが言えます。

このことから、 $x$ 座標のうち小さい方を ${x}_{a}$ とし、大きい方を ${x}_{b}$ とします。また同様に、 $y$ 座標のうち小さい方を ${y}_{a}$ とし、大きい方を ${y}_{b}$ とします。

このとき、正方形の面積は $({x}_{b} - {x}_{a})({y}_{b} - {y}_{a})$ で与えられるので、これを出力することで、この問題を解くことができます。

ソースコード

正方形の面積を返す関数 solve() を以下のように実装しました。

int x[4], y[4]; // それぞれ4ヶ所の座標を表す

int solve() {
  // 4つ分の値の入力
  for (int i = 0; i < 4; i++) {
    cin >> x[i] >> y[i];
  }
  sort(x, x + 4); // x 座標の値をソートする
  sort(y, y + 4); // y 座標の値をソートする

  // (x座標の最大値 - 最小値) * (y座標の最大値 - 最小値) が面積になるので、それを返す
  return (x[3] - x[0]) * (y[3] - y[0]);
}

提出したコード: https://codeforces.com/contest/1921/submission/243244912
GitHub

2024-01-26

J - Sushi / Educational DP Contest

EDPC AtCoder C++ Educational DP Contest DP 期待値確率再帰競技プログラミング

問題

$n$ 枚の皿があり、皿には $1, \, 2, \, \cdots , \, n$ と番号が振られている。

最初、各 $i$ について、皿 $i$ には ${a}_{i}$ 個の寿司が置かれている。

すべての寿司がなくなるまで、以下の操作を繰り返し行うとき、すべての寿司がなくなるまでの操作回数の期待値を求めよ。

の目が等確率で出るサイコロを振り、出目の番号の皿に置かれている寿司を1つ食べる。
- ただし、その皿に寿司がない場合は何も行わない。

入力

まず最初の1行目に、整数 $n$ が与えられる。

その次の1行に、整数 ${a}_{1}, \, {a}_{2}, \, \cdots , \, {a}_{n}$ が順に与えられる。

条件

実行時間制限: 2s
メモリ制限: 1024MB
$1 \leq n \leq 300$
$1 \leq {a}_{i} \leq 3$

出力

答えとなる値を1行で出力すること。ただし、答えとの絶対誤差が ${10}^{-9}$ 以下ならば正解となる。

解法

皿はサイコロで等確率で選ばれるため、どの皿に何個の寿司が置かれているのか、ということは状態変化に関係がありません。

寿司が1個、2個、3個と置かれている皿の枚数をそれぞれ $i, \, j, \, k$ とすると、1個、2個、3個の寿司が置かれている皿が選ばれる確率はそれぞれ $\displaystyle \frac{i}{n}, \, \frac{j}{n}, \, \frac{k}{n}$ ということになります。従って、寿司が置かれていない皿が選ばれる確率は $\displaystyle \left( 1 - \frac{i + j + k}{n} \right)$ となります。

このことから、寿司が1個、2個、3個と置かれている皿の枚数がそれぞれ $i, \, j, \, k$ のときに操作を1回行うとき、状態変化としては、

確率 $\displaystyle \frac{i}{n}$ で、寿司が1個、2個、3個と置かれている皿の枚数はそれぞれ $i - 1, \, j, \, k$ となる
確率 $\displaystyle \frac{j}{n}$ で、寿司が1個、2個、3個と置かれている皿の枚数はそれぞれ $i + 1, \, j - 1, \, k$ となる
確率 $\displaystyle \frac{k}{n}$ で、寿司が1個、2個、3個と置かれている皿の枚数はそれぞれ $i, \, j + 1, \, k - 1$ となる
確率 $\displaystyle 1 - \frac{i + j + k}{n}$ で、寿司が1個、2個、3個と置かれている皿の枚数はそれぞれ $i, \, j, \, k$ となる

というものになると言えます。

ここで、 $\mathrm{dp}_{i, \, j, \, k}$ を「寿司が1個、2個、3個と置かれている皿の枚数がそれぞれ $i, \, j, \, k$ のときの、最終的に寿司をすべてなくすまでの操作回数の期待値」として定めます。このとき、以上の考察での変化後の状態では、最終的な操作回数が $1$ 回減ると考えられるので、 \begin{align} \mathrm{dp}_{i, \, j, \, k} = 1 + \left\{ \frac{i}{n} \cdot \mathrm{dp}_{i - 1, \, j, \, k} \right. + \frac{j}{n} \cdot \mathrm{dp}_{i + 1, \, j - 1, \, k} & + \frac{k}{n} \cdot \mathrm{dp}_{i, \, j + 1, \, k - 1} \\ & \left. + \left( 1 - \frac{i + j + k}{n} \right) \cdot \mathrm{dp}_{i, \, j, \, k} \right\} \end{align} という等式が成立すると言えます。この等式を整理すると、 \begin{align} \frac{i + j + k}{n} \cdot \mathrm{dp}_{i, \, j, \, k} = 1 + \frac{i}{n} \cdot \mathrm{dp}_{i - 1, \, j, \, k} + \frac{j}{n} \cdot \mathrm{dp}_{i + 1, \, j - 1, \, k} + \frac{k}{n} \cdot \mathrm{dp}_{i, \, j + 1, \, k - 1} \end{align} より、 \begin{align} \mathrm{dp}_{i, \, j, \, k} = \frac{1}{i + j + k} \left( n + i \cdot \mathrm{dp}_{i - 1, \, j, \, k} + j \cdot \mathrm{dp}_{i + 1, \, j - 1, \, k} + k \cdot \mathrm{dp}_{i, \, j + 1, \, k - 1} \right) \end{align} が成立します。

また、どの皿にも寿司が置かれていない場合は操作を行う必要がないので、 $\mathrm{dp}_{0, \, 0, \, 0} = 0$ が成立します。

従って、初期状態での寿司が1個、2個、3個と置かれている皿の枚数をそれぞれ $i, \, j, \, k$ とするときに、以上の漸化式を用いて求められる $\mathrm{dp}_{i, \, j, \, k}$ の値が、この問題の答えとなります。

この問題での皿の枚数は $n$ で与えられるため、値の導出に必要な計算量は $O({n}^{3})$ です。 $n \leq 300$ であるので、これは実行時間制限に十分間に合うと考えられます。

ソースコード

寿司が1個、2個、3個と置かれている皿の枚数をそれぞれ $i, \, j, \, k$ とするときの、 $\mathrm{dp}_{i, \, j, \, k}$ の値を再帰的に求める関数 solve() を以下のように実装しました。

double dp[305][305][305];
bool visited[305][305][305]; // visited[i][j][k] は solve(i, j, k) を既に計算したかどうかを表す

double solve(int i, int j, int k) {
  // i, j, k が 0 未満のとき自体が発生しないので、このときは 0 を返す
  if (i < 0 || j < 0 || k < 0) {
    return 0;
  }

  // i = j = k = 0 のときは、操作回数の期待値は 0 なので、 0 を返す
  if (i == 0 && j == 0 && k == 0) {
    return 0;
  }
  // solve(i, j, k) を計算済であれば、そのまま dp[i][j][k] を返す
  if (visited[i][j][k]) {
    return dp[i][j][k];
  }

  // solve(i, j, k) を計算済ということにする
  visited[i][j][k] = true;

  // ans は最終的な期待値の値を表す
  double ans = (double)(n) / (double)(i + j + k);

  // 寿司が1個置かれている皿を選ぶ場合
  ans += (double)(i) / (double)(i + j + k) * solve(i - 1, j, k);

  // 寿司が2個置かれている皿を選ぶ場合
  ans += (double)(j) / (double)(i + j + k) * solve(i + 1, j - 1, k);

  // 寿司が3個置かれている皿を選ぶ場合
  ans += (double)(k) / (double)(i + j + k) * solve(i, j + 1, k - 1);

  // 最終的に dp[i][j][k] を ans で更新して、 ans を返す
  return dp[i][j][k] = ans;
}

提出したコード: https://atcoder.jp/contests/dp/submissions/49621309
GitHub

感想

期待値のDPについては、状態変化を正確に把握しきれるかがポイントになると思います。（これが結構難しいんですよね…。）

前回: I問題
次回: （未定）

2024-01-24

E - Increasing Subsequences / Educational Codeforces Round 161 (Rated for Div. 2)

CF1922 Codeforces C++ Div.2 Educational Codeforces Round 161 Diff 1800 2進数数え上げ競技プログラミング

問題

数列 $a$ の部分増加列を、「 $a$ の要素の順番を変えることなく $0$ 個以上の要素を削除したときに、残った要素が狭義単調増加となるような数列」として定義する。ただし、空の場合も部分増加列とする。

整数 $x$ が与えられるので、部分増加列がちょうど $x$ 個存在するような数列を出力せよ。ただし、出力する数列の要素数は最大で $200$ とする。

入力

まず最初の1行目に、テストケースの個数を表す整数 $t$ が与えられる。

その後、 $t$ 行に渡り、 $i$ 行目には $i$ 個目のテストケースとして整数 $x$ が与えられる。

条件

実行時間制限: 2s
メモリ制限: 256MB
$1 \leq t \leq 1000$
$2 \leq x \leq {10}^{18}$

出力

各テストケースに対して、以下のように出力すること。

まず最初の1行目には、出力する数列の要素数を出力すること。
次の1行には、数列の要素を空白区切りで出力すること。

解法

まず初めに、数列 $[ 1, \, 2, \, \cdots , \, n ]$ の中に部分増加列がいくつあるかについて考えます。

この部分列はすべて必ず増加列となることから、各 $n$ 個の要素が部分列に入るか入らないかを考えればよいので、部分増加列の個数は、 \begin{align} 2 \times 2 \times \cdots \times 2 = {2}^{n} \end{align} となります。（ここで、すべての要素が入らないとしたときは、数列が空となりますが、問題の定義ではこれも部分増加列です。）

この数列に対して、例えば $[ 1, \, 2, \, \cdots, \, i, \, n + 1, \, i + 1, \, \cdots, \, n ]$ というように、 $i$ と $i + 1$ の間に要素 $n + 1$ が入った場合について考えます。この新しくできた数列の部分増加列として、要素 $n + 1$ が含まれるものの個数について考えます。

このとき、 $i + 1$ 以降の要素が部分増加列に含まれることはありません。というのも、この数列では $n + 1$ よりも大きい要素は存在しないためです。

一方で、 $n + 1$ 以前の要素（ $1, \, 2 , \, \cdots , \, i$ ）は含まれても含まれなくても必ず部分増加列となります。従って、 $n + 1$ が含まれる部分増加列の個数は、先程の考え方から ${2}^{i}$ 個ということになります。

以上から、数列 $[ 1, \, 2, \, \cdots , \, i, \, n + 1, \, i + 1, \, \cdots , \, n ]$ の部分増加列の総数は ${2}^{n} + {2}^{i}$ となります。

この考え方から、与えられた整数 $x$ に対して、部分増加列の総数が $x$ 個となるような数列を作るには、

というようにして、をの累乗の和で表す
- このとき、 $n \gt m$ とします。
$n$ 個の整数による数列 $[ 1, \, 2, \, \cdots , \, n ]$ を作成する
その他の $2$ の累乗の成分に対して、 $[ 1, \, 2, \, \cdots , \, m, \, n + 1 , \, m + 1 , \, \cdots , \, n ]$ というようにして、 $m$ と $m + 1$ の間にその時点での数列の要素の最大値に $1$ を加えた数を追加する

という手順を繰り返すことによって、条件を満たす数列を作成することができます。

また、 $x = {2}^{n} + {2}^{n - 1} + \cdots + {2}^{1} + {2}^{0}$ と表せるとき、手順1にて $n$ 個の整数が並び、その後 $n$ 回の手順2で $1$ 個ずつの整数が並ぶことから、この場合の作成される数列の要素数は $2n$ 個となります。

この問題では $x \leq {10}^{18}$ であり、 ${10}^{18} \lt {2}^{60}$ であることから、以上の $n$ について $n \lt 60$ であると言えます。

従って、 $2n \lt 120$ より、この方法で作成される数列の要素数は $120$ を超えないと言えるので、要素数についての条件も必ず満たされると言えます。

以上から、 $x$ を $2$ の累乗の和で表すことによって、実行時間制限に十分間に合いながら、条件を満たす数列を作成することができます。

ソースコード

各テストケースに対して、条件を満たす数列を出力する関数 solve() を以下のように実装しました。

ll x;
bool bit[105]; // bit[i] は x を2の累乗の和で表したときに、 2^i が含まれるか否かを表す

// 数列 p は初めの 1, 2, ..., n を保存するための数列で、数列 q は途中に挿入される値を保存するための数列
// q[i] > 0 ならば、その値を p[i] と p[i + 1] の間に入れる
int p[105], q[105];

void solve() {
  cin >> x; // 値の入力

  int m = 0; // m は x を2の累乗の和で表したときの 2^m の最大となる値を表す
  for (int i = 0; i <= 100; i++) {
    bit[i] = x % 2; // x % 2 = 1 ならば、その桁では和に含まれる
    x /= 2; // 次の桁について考えるために、 x を2で割る

    if (bit[i]) {
      m = i; // i の小さい順に考えているため、bit[i] = true ならばそのときの i の値が暫定的に m となる
    }
  }

  // 数列 p に i = 1, ..., m を入れておく
  for (int i = 1; i <= m; i++) {
    p[i] = i;
  }

  // 挿入する値について見る
  int now = m + 1; // now は次に挿入する値を表す
  // i = m - 1 から 0 の順に、 bit[i] = true の箇所に値 now を入れていく
  for (int i = m - 1; i >= 0; i--) {
    if (bit[i]) {
      q[i] = now; // 2^i が和に含まれるので、このときは p[i] と p[i + 1] の間に now の値を入れるようにする
      now++; // now が使われたら値を 1 増やして更新する
    }
  }

  vector<int> ans; // 最終的に答えとなる数列を入れるための vector

  // p[i], q[i] の順に、i = 0, ..., m について 0 より大きい値のものをすべて ans に入れる
  for (int i = 0; i <= m; i++) {
    if (p[i] > 0) {
      ans.push_back(p[i]);
    }
    if (q[i] > 0) {
      ans.push_back(q[i]);
    }
  }

  // 答えの出力
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i];
    if (i == ans.size() - 1) {
      cout << endl;
    } else {
      cout << " ";
    }
  }

  return;
}

提出したコード: https://codeforces.com/contest/1922/submission/243096872
GitHub

感想

部分増加列に空の数列も含まれる、というところがこの問題のミソのように思います。（最初この問題を見たときに、その部分を読み飛ばしていたのが反省点です。）

2024-01-24

D - Berserk Monsters / Educational Codeforces Round 161 (Rated for Div. 2)

CF1922 Codeforces C++ Div.2 Educational Codeforces Round 161 Diff 1900 set 競技プログラミング

問題

$n$ 体のモンスターが1列に並んでおり、左から $1$ から $n$ までの番号が順につけられている。 $i$ 番目のモンスターの攻撃のパラメータは ${a}_{i}$ であり、防御のパラメータは ${d}_{i}$ である。

この状態で、以下のモンスター同士の対戦を $n$ 回行う。

まず、すべての生存しているモンスターが、左右の最も近い生存しているモンスターに対して、同時に攻撃を行う。
- $i$ 番目のモンスターは、攻撃するモンスターに対して ${a}_{i}$ の大きさのダメージを負わせる。
次に、すべての生存しているモンスターが、ダメージを受ける。
- $j$ 番目のモンスターは、 ${d}_{j}$ よりも大きいダメージを受けると、倒されてしまう。

それぞれの対戦にて、倒されるモンスターの数を求めよ。

入力

まず最初の1行目に、テストケースの個数を表す整数 $t$ が与えられる。

その後、 $t$ 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

最初の1行目には、整数 $n$ が与えられる。
次の1行には、整数 ${a}_{1}, \, {a}_{2}, \, \cdots , \, {a}_{n}$ が順に与えられる。
次の1行には、整数 ${d}_{1}, \, {d}_{2}, \, \cdots , \, {d}_{n}$ が順に与えられる。

条件

実行時間制限: 2s
メモリ制限: 256MB
$1 \leq t \leq {10}^{4}$
- すべてのテストケースにおける $n$ の値の合計は $3 \cdot {10}^{5}$ を超えない。
$1 \leq {a}_{i} \leq {10}^{9}$
$1 \leq {d}_{i} \leq {10}^{9}$

出力

各テストケースに対して、各対戦にて倒されるモンスターの数を、1行で順番に空白区切りで $n$ 個出力すること。

解法

まず、各対戦ごとに $n$ 体のモンスターの状態を把握していき、 $n$ 回の対戦すべてでどのようなダメージを受けるかを考える方法が考えつきます。しかし、この方法では $O( {n}^{2} )$ の計算量が必要であり、 $n \leq 3 \cdot {10}^{5}$ であるので、実行時間制限に間に合いません。

そこで、どのモンスターについて着目すべきなのかについて考えます。

ここで、1回の対戦でモンスター $i$ が倒されたとします。（モンスター $i$ の左隣にいるモンスターを ${l}_{i}$ とし、右隣にいるモンスターを ${r}_{i}$ とします。）

この対戦にて、モンスター $i$ の両隣のモンスター ${l}_{i}, \, {r}_{i}$ がどちらも倒されなかったとすると、次の対戦にてモンスター ${l}_{i}, \, {r}_{i}$ の受けるダメージの値は変化します。これは、モンスター ${l}_{i}$ については元の対戦でモンスター $i$ からの攻撃を受けていたのに対し、モンスター $i$ が倒れた直後の対戦ではモンスター ${r}_{i}$ からの攻撃を受けるためです。（もちろん、モンスター ${r}_{i}$ についても同様です。）

従って、ある1体のモンスターが倒されることにより、次の対戦に影響の出るモンスターの数は最大でも2体ということが言えます。

このことから、次の対戦ではモンスター $i$ の影響を受けたモンスター ${l}_{i}, \, {r}_{i}$ が倒されるかどうかに着目すれば、全体の計算量を落としつつモンスターの倒された数を把握できると言えます。

この方法の場合、モンスターは全部で $n$ 体いることから、この問題で考えるべきモンスターののべ総数は最大で $3n$ 体ということになります。

以上の考察から、この方法では $O(n)$ 程度の計算量で、毎回の対戦で何体のモンスターが倒されたのかを導出することができると言えます。

手順としては、

1回目の対戦として、モンスター $1, \, 2, \, \cdots , \, n$ の受けるダメージを調べ、どのモンスターが倒れるかを調べる
倒れたモンスターを列から除外する
その対戦で倒れたモンスターに対して、その両隣にいるモンスターを次の調査対象とする
次の対戦として、調査対象となったモンスターの受けるダメージを調べ、どのモンスターが倒れるかを調べる
手順2から手順4までを $n$ 回の対戦が終わるまで繰り返す

という方法になります。

このときに「生存しているモンスターの番号」「調査中のモンスターの番号」「倒されたモンスターの番号」を C++ での std::set などを用いて管理すれば、重複を気にすることなく番号の管理を行えます。（ただし、値の検索や挿入、削除に必要な計算量は $O(1)$ ではないことに注意が必要です。）

以上の方法を実装することによって、この問題を解くことができます。

ソースコード

各テストケースに対して、 $n$ 回の対戦で倒されたモンスター数を出力する関数 solve() を以下のように実装しました。

int n;
int a[int(3e5 + 5)], d[int(3e5 + 5)];

int ans[int(3e5 + 5)]; // ans[i] は i 回目の対戦で倒されたモンスターの数を表す

void solve() {
  // 値の入力（実行時間に不安があるため、 scanf を使用する）
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &d[i]);
  }

  // 生存しているモンスター、調査中のモンスター、倒されたモンスターの番号を管理する set を用意する
  set<int> alive, searching, dead;

  // 隣になっているモンスターを簡単に出すために、存在しないモンスター0, n + 1 を生存しているものとして追加する
  alive.insert(0);
  alive.insert(n + 1);

  // モンスター 1, ..., n を生存しているモンスターと、次に調査するモンスターとしてそれぞれ追加する
  for (int i = 1; i <= n; i++) {
    alive.insert(i);
    searching.insert(i);
  }

  // 1 回目の対戦から n 回目の対戦までをすべて考える
  for (int i = 1; i <= n; i++) {
    // searching に入っているすべてのモンスターに対して、倒されるかどうかを調査する
    for (int m : searching) {
      // before_iter は m の直前にあたる生存しているモンスターの番号へのイテレータを表す
      auto before_iter = alive.find(m);
      before_iter--; // m へのイテレータの直前

      // after_iter は m の直後にあたる生存しているモンスターの番号へのイテレータを表す
      auto after_iter = alive.find(m);
      after_iter++;

      // 隣同士の攻撃力の合計が、防御力を上回ったら、モンスター m は倒される
      // *before_iter, *after_iter の値が 0 または n + 1 のときは a の値は 0 である
      if (a[*before_iter] + a[*after_iter] > d[m]) {
        ans[i]++; // i 回目の対戦での倒された値を 1 増やす
        dead.insert(m); // 倒されたモンスターとして m を追加する
      }
    }

    // 倒されたモンスターを、生存しているモンスターの set から削除する
    for (int m : dead) {
      alive.erase(m);
    }

    // 調査中のモンスターの入る set の内容を一旦リセットする
    searching.clear();

    // 倒されたモンスターから、次に調べるモンスターを調べる
    for (int m : dead) {
      // before_iter は alive の中にある m 未満の値での最大値へのイテレータを表す
      auto before_iter = alive.upper_bound(m);
      before_iter--;
      // after_iter は alive の中にある m より大きい値での最小値へのイテレータを表す
      auto after_iter = alive.upper_bound(m);

      // *before_iter の値が 0 より大きければ、存在するモンスターなので、これを searching に入れる
      if (0 < *before_iter) {
        searching.insert(*before_iter);
      }
      // *after_iter の値が n 以下ならば、存在するモンスターなので、これを searching に入れる
      if (*after_iter <= n) {
        searching.insert(*after_iter);
      }
    }

    // 次の対戦の記録のために、 dead をリセットする
    dead.clear();
  }

  // 値の出力
  for (int i = 1; i <= n; i++) {
    printf("%d", ans[i]);
    if (i == n) {
      printf("\n");
    } else {
      printf(" ");
    }
  }

  return;
}

提出したコード: https://codeforces.com/contest/1922/submission/243073262
GitHub

感想

今回の問題では、元々 std::cin や std::cout を使用した回答を提出して正解しましたが、実行時間が 1432ms とかなり長めになりました *1 。

提出したコードとして出した回答 *2 では、 608ms となったので、これだけでも実行時間の短縮になりますね。

*1:https://codeforces.com/contest/1922/submission/243072675

*2:https://codeforces.com/contest/1922/submission/243073262

2024-01-23

C - Closest Cities / Educational Codeforces Round 161 (Rated for Div. 2)

CF1922 Codeforces C++ Div.2 Educational Codeforces Round 161 Diff 1300 最短経路競技プログラミング

問題

$n$ 個の町が数直線上に並んでおり、 $i$ 番目の町は座標 ${a}_{i}$ に位置している。 $n$ 個の町は数直線上に昇順に並んでいるため、 ${a}_{1} \lt {a}_{2} \lt \cdots \lt {a}_{n}$ である。

このとき、2つの町 $x, \, y$ の距離は $| {a}_{x} - {a}_{y} |$ である。町 $i$ に対して、最も近い町を $j$ とするとき、 $k \ne i$ である $k$ に対して $| {a}_{i} - {a}_{j} | \leq | {a}_{i} - {a}_{k} |$ が成立する。

ここで、あなたは町 $x$ から町 $y$ に移動しようとしている。このとき移動に際して、以下の行動を行うことができる。

他の町 $y$ に対して、 $| {a}_{x} - {a}_{y} |$ 枚のコインを支払って移動する。
町 $x$ に最も近い町に、 $1$ 枚のコインを支払って移動する。

この状況下で、 $m$ 個のクエリが与えられる。各クエリに対して2つの町 $x, \, y$ が与えられるので、町 $x$ から町 $y$ に移動するのに必要な最小のコインの枚数を求めよ。

入力

まず最初の1行目に、テストケースの個数を表す整数 $t$ が与えられる。

その後、 $t$ 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

最初の1行目には整数 $n$ が与えられる。
次の1行には $n$ 個の整数 ${a}_{1}, \, {a}_{2}, \, \cdots , \, {a}_{n}$ が順に与えられる。
次の1行には整数 $m$ が与えられる。
次の $m$ 行のうち $i$ 行目には、 $i$ 個目のクエリを表す整数 ${x}_{i}, \, {y}_{i}$ が与えられる。

条件

実行時間制限: 2s
メモリ制限: 256MB
$1 \leq t \leq {10}^{4}$
- すべてのテストケースにおける $n$ の値の合計は ${10}^{5}$ を超えない。
$0 \leq {a}_{1} \lt {a}_{2} \lt \cdots \lt {a}_{n} \leq {10}^{9}$
- すべてのテストケースにおける $m$ の値の合計は ${10}^{5}$ を超えない。
- ただし、 ${x}_{i} \ne {y}_{i}$ である。

出力

各テストケースに対して、 $m$ 行に渡り、 $i$ 行には $i$ 番目のクエリでの払うコインの最小枚数を出力すること。

解法

まず、町 $x$ から町 $y$ へと進む際に、 $x \lt y$ であれば「町 $x$ → 町 $x + 1$ → … → 町 $y$ 」と進むことが最小コストとなりますし、 $x \gt y$ であれば「町 $x$ → 町 $x - 1$ → … → 町 $y$ 」と進むことが最小コストとなります。

これは例えば $x \lt y$ の場合、仮に町 $x - 1$ を経由した場合では、「町 $x$ → 町 $x - 1$ → 町 $x$ → 町 $x + 1$ → … → 町 $y$ 」というルートになり、最初の「町 $x$ → 町 $x - 1$ → 町 $x$ 」の部分が余分なものとなってしまうからです。（ $x \gt y$ の場合についても同様です。）

ここで、 $\mathrm{cost 0}_{i}$ を町 $i + 1$ から町 $i$ まで進むときの最小コスト、 $\mathrm{cost 1}_{i}$ を町 $i - 1$ から町 $i$ まで進むときの最小コストとして定めます。ただし、 $\mathrm{cost 0}_{n} = 0, \, \mathrm{cost 1}_{1} = 0$ とします。

まず、 $\mathrm{cost 0}_{i}$ の値について考えます。

町 $n$ は必ず町 $n - 1$ が最も近い町となることから、 $\mathrm{cost 0}_{n - 1} = 1$ が成立します。

その上で、 $1 \leq i \leq n - 2$ とするとき、 $\mathrm{cost 0}_{i}$ の値は、町 $i + 1$ の最も近い町が町 $i$ になる場合には $1$ となり、そうでない場合は $| {a}_{i} - {a}_{i + 1} |$ となります。すなわち、 \begin{align} \mathrm{cost 0}_{i} = \left\{ \begin{aligned} & 1 & & (|{a}_{i + 1} - {a}_{i}| \leq |{a}_{i + 1} - {a}_{i + 2}| \, \text{のとき}) \\ & | {a}_{i} - {a}_{i + 1} | & & (\text{otherwise}) \end{aligned} \right. \end{align} が成立します。

以上から、 $\mathrm{cost 0}_{i}$ の値が $i = 1, \, 2, \, \cdots , \, n$ に対して導けます。

次に、 $\mathrm{cost 1}_{i}$ の値について考えます。

町 $1$ は必ず町 $2$ が最も近い町となることから、 $\mathrm{cost 1}_{2} = 1$ が成立します。

その上で、 $3 \leq i \leq n$ とするとき、 $\mathrm{cost 1}_{i}$ の値は、町 $i - 1$ の最も近い町が町 $i$ になる場合には $1$ となり、そうでない場合は $|{a}_{i - 1} - {a}_{i}|$ となります。すなわち、 \begin{align} \mathrm{cost 1}_{i} = \left\{ \begin{aligned} & 1 & & (|{a}_{i - 1} - {a}_{i}| \leq |{a}_{i - 1} - {a}_{i - 2}| \, \text{のとき}) \\ & | {a}_{i} - {a}_{i - 1} | & & (\text{otherwise}) \end{aligned} \right. \end{align} が成立します。

以上から、 $\mathrm{cost 1}_{i}$ の値が $i = 1, \, 2, \, \cdots, \, n$ に対して導けます。

このようにして求まった $\mathrm{cost0}, \, \mathrm{cost1}$ を用いて、町 $x$ から町 $y$ までの最小コストを求めます。

$x \gt y$ の場合は、町 $i + 1$ から町 $i$ への移動を繰り返し行うことから、 \begin{align} \mathrm{cost 0}_{x - 1} + \mathrm{cost 0}_{x - 2} + \cdots + \mathrm{cost 0}_{y} \end{align} によって最小コストが求まります。

また、 $x \lt y$ の場合は、町 $i - 1$ から町 $i$ への移動を繰り返し行うことから、 \begin{align} \mathrm{cost 1}_{x + 1} + \mathrm{cost 1}_{x + 2} + \cdots + \mathrm{cost 1}_{y} \end{align} によって最小コストが求まります。

これらを毎回足していくことで導出すると、 $O(n)$ 程度の計算量が1回につき必要になり、全体で [O(nm)] の計算量が必要になるため、これでは実行時間制限に間に合いません。

従って、値 $\mathrm{sum0}_{i}, \, \mathrm{sum1}_{i}$ を、 \begin{align} \mathrm{sum 0}_{i} & = \mathrm{cost 0}_{n} + \mathrm{cost 0}_{n - 1} + \cdots + \mathrm{cost 0}_{i} \\ \mathrm{sum 1}_{i} & = \mathrm{cost 1}_{1} + \mathrm{cost 1}_{2} + \cdots + \mathrm{cost 1}_{i} \end{align} としてそれぞれ定めます。

この値を用いることによって、 $x \gt y$ の場合の最小コストは、 \begin{align} \mathrm{cost 0}_{x - 1} + \cdots + \mathrm{cost 0}_{y} = \mathrm{sum 0}_{y} - \mathrm{sum 0}_{x} \end{align} で導出することができ、 $x \lt y$ の場合の最小コストは、 \begin{align} \mathrm{cost 1}_{x + 1} + \cdots + \mathrm{cost 1}_{y} = \mathrm{sum 1}_{y} - \mathrm{sum 1}_{x} \end{align} で導出することができます。

$\mathrm{sum 0}_{i}, \, \mathrm{sum 1}_{i}$ の値はそれぞれ $O(n)$ で求めることができ、その上で1つのクエリに対しては $O(1)$ で求めることができるので、この方法では全体で $O(n + m)$ の計算量で求めることができます。従って、この方法によって実行時間制限に十分間に合うと言えます。

ソースコード

各テストケースに対して、 $m$ 個のクエリの答えを出力する関数 solve() を以下のように実装しました。

int n, m, a[int(1e5 + 5)];

int cost[int(1e5 + 5)][2], sum[int(1e5 + 5)][2]; // cost[i][0] が cost0 の値を表す。 sum についても同様

void solve() {
  // 値の入力
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  // cost0 の値を求める
  for (int i = 1; i <= n - 2; i++) {
    if (abs(a[i + 1] - a[i]) <= abs(a[i + 1] - a[i + 2])) {
      cost[i][0] = 1;
    } else {
      cost[i][0] = abs(a[i] - a[i + 1]);
    }
  }
  cost[n - 1][0] = 1;

  // cost1 の値を求める
  cost[2][1] = 1;
  for (int i = 3; i <= n; i++) {
    if (abs(a[i - 1] - a[i]) <= abs(a[i - 1] - a[i - 2])) {
      cost[i][1] = 1;
    } else {
      cost[i][1] = abs(a[i] - a[i - 1]);
    }
  }

  // 求めた cost0, cost1 の値から、 sum0, sum1 の値を求める
  for (int i = 1; i <= n; i++) {
    sum[i][1] = sum[i - 1][1] + cost[i][1];
  }
  for (int i = n; i >= 1; i--) {
    sum[i][0] = sum[i + 1][0] + cost[i][0];
  }

  // クエリへの回答
  cin >> m;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;

    if (x <= y) {
      // x <= y のときは、 sum1 の値を用いる
      cout << sum[y][1] - sum[x][1] << endl;
    } else {
      // x > y のときは、 sum0 の値を用いる
      cout << sum[y][0] - sum[x][0] << endl;
    }
  }

  return;
}

提出したコード: https://codeforces.com/contest/1922/submission/242975722
GitHub

感想

それぞれの道順に対して、 $i$ の値がどのときにどうなるのか、ということを考えるのが少し複雑になりました。

記事を書くときのように整理できていると実装もしやすくなるのですが、いざコンテスト本番でこの方針で行うとなると、正解なのかどうかやや不安になりそうです。