yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

G - Chimpanzini Bananini / Codeforces Round 1017 (Div. 4)

CF2094 Codeforces C++ Div.4 Codeforces Round 1017 Diff 1700 区間和 累積和 競技プログラミング

問題

m 個の整数からなる数列 b の rizziness を

\begin{align} \displaystyle \sum^{m}_{i = 1} {b}_{i} \cdot {i} = {b}_{1} \cdot 1 + {b}_{2} \cdot {2} + \cdots + {b}_{m} \cdot m \end{align}

で定義する。

はじめ、空の数列が与えられており、この数列に対して次の3種類の操作を行える。

  1. 最初の要素を最後に移動する。 すなわち、数列が \left[ {a}_{1}, \, \cdots , \, {a}_{n - 1} , \, {a}_{n} \right] のとき、 \left[ {a}_{n}, \, {a}_{1} , \, \cdots , \, {a}_{n - 1} \right] にする。

  2. 数列を逆順にする。 すなわち、数列が \left[ {a}_{1}, \, {a}_{2}, \, \cdots , \, {a}_{n - 1} , \, {a}_{n} \right] のとき、 \left[ {a}_{n}, \, {a}_{n-1}, \, \cdots , \, {a}_{2}, \, {a}_{1} \right] にする。

  3. 数列の最後尾に整数 k を追加する。 すなわち、数列が \left[ {a}_{1}, \, \cdots , \, {a}_{n} \right] のとき、 \left[ {a}_{1}, \, \cdots , \, {a}_{n}, \, k \right] にする。

各操作の完了後での数列の rizziness を求めよ。

入力

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

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

  • 最初の1行目には操作の個数 q が与えられる。
  • その後 q 行に渡り、 i 行目には i 個目の操作が次のように与えられる。
    • 各行には必ず操作の種類を表す整数 s が与えられる。
    • s = 1 のときは操作 1 を表す。
    • s = 2 のときは操作 2 を表す。
    • s = 3 のときは操作 3 を表し、同じ行に追加で整数 k が空白区切りで与えられる。 この整数 k は数列の最後尾に追加する整数を表す。

条件

  • 実行時間制限: 2s
  • メモリ制限: 256MB
  • 1 \leq t \leq {10}^{4}
  • 1 \leq q \leq 2 \cdot {10}^{5}
  • 1 \leq s \leq 3
  • 1 \leq k \leq {10}^{6}
  • t 個のテストケースでの q の総和は 2 \cdot {10}^{5} を超えない。
  • 各テストケースでの最初の操作は s = 3 であることが保証される。

出力

t 個のテストケースそれぞれについて、 q 行に渡り i 個目の操作が終了した時点での rizziness の値を改行区切りで出力すること。

解法

現在の数列が a = \left[ {a}_{1}, \, \cdots , \, {a}_{n} \right] であると考えます。 このときの rizziness の値は定義通りに

\begin{align} {a}_{1} \cdot 1 + {a}_{2} \cdot 2 + \cdots + {a}_{n - 1} \cdot \left( n - 1 \right) + {a}_{n} \cdot n \end{align}

で与えられます。

ここで操作 1 が発生したとすると、 a = \left[ {a}_{n}, \, {a}_{1} , \, \cdots , \, {a}_{n-1} \right] となります。 このときの rizziness の値は

\begin{align} {a}_{n} \cdot 1 + {a}_{1} \cdot 2 + {a}_{2} \cdot 3 + \cdots + {a}_{n - 1} \cdot n \end{align}

となります。 操作前の rizziness の値から操作後の rizziness を導出するために、操作後の rizziness の値を変形します。 操作前と操作後の rizziness の値をそれぞれ {r} , \, {r}' とすると、

\begin{align} & {r}' \\ = & {a}_{n} \cdot 1 + {a}_{1} \cdot 2 + {a}_{2} \cdot 3 + \cdots + {a}_{n - 1} \cdot n \\ = & {a}_{n} \cdot 1 + \left( {a}_{1} \cdot 1 + {a}_{1} \right) + \left( {a}_{2} \cdot 2 + {a}_{2} \right) + \cdots + \left( {a}_{n -1} \cdot (n-1) + {a}_{n-1} \right) \\ = & {a}_{n} + \left( {a}_{1} \cdot 1 + \cdots + {a}_{n-1} \cdot (n-1) \right) + \left( {a}_{1} + {a}_{2} + \cdots + {a}_{n-1} \right) \\ = & \left( {a}_{1} \cdot 1 + \cdots + {a}_{n-1} \cdot (n-1) \right) + \left( {a}_{1} + \cdots + {a}_{n} \right) \\ = & \left( {r} - n \cdot {a}_{n} \right) + \sum_{i=1}^{n} {a}_{i} \end{align}

として計算することができます。 ここで、 \mathrm{sum} = \displaystyle \sum_{i=1}^{n} {a}_{i} と定義すると、

\begin{align} r' = r - n \cdot {a}_{n} + \mathrm{sum} \end{align}

が言えます。 従って、 \mathrm{sum} の値を予め持つことにより、 O(1) 程度の計算量で操作 1 実行後の rizziness の値を求めることができます。

次に、操作 2 実行後の rizziness の値について考えます。 操作 2 では数列が a = \left[ {a}_{1}, \, \cdots , \, {a}_{n} \right] から a = \left[ {a}_{n}, \, \cdots , \, {a}_{1} \right] に変化します。

このときの操作前と操作後の rizziness の値を先程と同様にそれぞれ r, \, r' とすると、

\begin{align} r & = {a}_{1} \cdot 1 + {a}_{2} \cdot 2 + \cdots + {a}_{n - 1} \cdot \left( n - 1 \right) + {a}_{n} \cdot n \\ r' & = {a}_{n} \cdot 1 + {a}_{n - 1} \cdot 2 + \cdots + {a}_{2} \cdot (n-1) + {a}_{1} \cdot n \\ & = {a}_{1} \cdot n + {a}_{2} \cdot (n-1) + \cdots + {a}_{n-1} \cdot 2 + {a}_{n} \cdot 1 \end{align}

がそれぞれ言えます。 従って、

\begin{align} r + r' & = {a}_{1} \cdot (n+1) + {a}_{2} \cdot (n+1) + \cdots + {a}_{n} \cdot (n+1) \\ & = (n+1) \cdot \sum_{i=1}^{n} {a}_{i} \end{align}

が言えるので、先程の \mathrm{sum} を用いて、

\begin{align} r' = (n+1) \cdot \mathrm{sum} - r \end{align}

であると言えます。 以上から、操作 2 実行後の rizziness の値についても、 \mathrm{sum} の値を予め持つことにより O(1) 程度の計算量で求めることができると言えます。

最後に操作 3 について考えます。 操作 3 では、数列 a = \left[ {a}_{1}, \, \cdots , \, {a}_{n} \right] の最後尾に整数 k が追加されるので、数列 a は a = \left[ {a}_{1}, \, \cdots , \, {a}_{n}, \, k \right] となります。

すなわち、 {a}_{n + 1} = k となることから、操作前、操作後の rizziness の値をそれぞれ r, \, r' とすると、

\begin{align} r' = r + (n+1) \cdot k \end{align}

として与えられます。 また、先程の \mathrm{sum} の値については

\begin{align} \mathrm{sum} \leftarrow \mathrm{sum} + k \end{align}

として更新されます。

以上を整理すると、 rizziness の値を r とし、数列のすべての要素の和を \mathrm{sum} とし、操作前の数列の要素数を n とすると

  • 操作 1 の実行
    • r \leftarrow r - n \cdot {a}_{n} + \mathrm{sum}
  • 操作 2 の実行
    • r \leftarrow (n + 1) \cdot \mathrm{sum} - r
  • 操作 3 の実行
    • r \leftarrow r + (n + 1) \cdot k
    • \mathrm{sum} \leftarrow \mathrm{sum} + k
    • n \leftarrow n + 1

として値を更新していくことにより、それぞれの操作後の rizziness の値を O(1) 程度の計算量で導出することができると言えます。

なお、操作 1 の実行において数列の最後尾を管理する必要があるので、現在の数列が正順になっているか逆順になっているかを管理する必要があります。 C++ の deque のような両方向から値を入れられるデータ構造を用いて、

  • 正順になっていたら
    • 操作 1 では最後尾の値を参照し、先頭に入れる
    • 操作 2 では現在の順番を逆順とする
    • 操作 3 では最後尾に k を入れる
  • 逆順になっていたら
    • 操作 1 では先頭の値を参照し、最後尾に入れる
    • 操作 2 では現在の順番を正順とする
    • 操作 3 では先頭に k を入れる

という管理を行うことにより、数列の先頭と最後尾を正しく管理しながら rizziness の値を導出できます。

数列の操作回数が q 回あることから、1つのテストケースに対して O(q) 程度の計算量でこれらは導出できます。 また、問題の条件より q の総和は 2 \cdot {10}^{5} を超えないことが保証されているので、これで実行時間制限にも十分間に合うといえます。

ソースコード

各テストケースでの答えを出力する関数 solve() を以下のように実装しました。

void solve() {
  int q, s, k;
  deque<ll> que; // 数列を管理するための deque
  bool reversed = false; // 正順か逆順か管理する bool 値。 false のとき正順で、true のとき逆順。
  ll sum = 0, ans = 0, n = 0; // ans は rizziness の値を表す。

  cin >> q; // q の入力
  for (int i = 1; i <= q; i++) {
    // 全 q 回の操作を、 for ループで扱う
    cin >> s; // s の入力

    if (s == 1) {
      // 操作 1 の場合
      if (!reversed) {
        // 正順の場合
        ll a = que.back(); // 最後尾の値 a は back で扱う
        que.pop_back(); // 最後尾の値を deque から外す
        ans = ans - n * a + sum; // ans の値の更新
        que.push_front(a); // a を deque の先頭に入れる
      } else {
        // 逆順の場合
        ll a = que.front(); // 先頭の値 a は front で扱う
        que.pop_front(); // 先頭の値を deque から外す
        ans = ans - n * a + sum; // ans の値の更新
        que.push_back(a); // a を deque の最後尾に入れる
      }
    } else if (s == 2) {
      // 操作 2 の場合
      reversed = !reversed; // reversed の値を反転させる
      ans = sum * (n + 1) - ans; // ans の値の更新
    } else {
      cin >> k; // k の値の入力

      sum += k; // sum の更新
      n++; // n の値を 1 増やす
      ans = ans + n * k; // ans の値の更新

      if (!reversed) {
        que.push_back(k); // 正順の場合 deque の最後尾に k を入れる
      } else {
        que.push_front(k); // 逆順の場合 deque の先頭に k を入れる
      }
    }

    cout << ans << endl; // rizziness の値の出力
  }

  return;
}

この solve() 関数がある状態で、 main() 関数に下記のように実装することで、 t 個のテストケースに対応しました。

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }

  return 0;
}

D - Tung Tung Sahur / Codeforces Round 1017 (Div. 4)

CF2094 Codeforces C++ Div.4 Codeforces Round 1017 Diff 1100 文字列 競技プログラミング

問題

左右に1個ずつドラムがあり、左のドラムは L 、右のドラムは R として記録される。

ドラムはそれぞれ不思議な性質があり、1回叩くと1回分の音が鳴るときと2回分の音が鳴るときがそれぞれ存在する。 すなわち、左側のドラムを1回叩くと L または LL として記録され、右側のドラムを1回叩くと R または RR として記録される。

文字列 p がドラムを叩いた記録を表し、文字列 s がドラムの音が聞こえた記録を表すとき、文字列 s が文字列 p の通りにドラムを叩いたときの結果としてあり得るかどうかを判定せよ。

例えば、 p が LR のとき、 s としては LR, LRR, LLR, LLRR があり得るが、 LLLR や LRL などはあり得ない。

入力

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

その後、各テストケースについて、次のように与えられる。

  • 最初の1行目には、文字列 p が与えられる。
  • 次の1行には、文字列 s が与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 256MB
  • 1 \leq t \leq {10}^{4}
  • 1 \leq |p| \leq |s| \leq 2 \cdot {10}^{5}
  • 文字列 p, \, s はいずれも L または R から構成される文字列である。
  • t 個のテストケースでの |s| の総和は 2 \cdot {10}^{5} を超えない。

出力

t 行にわたり、 i 行目 ( 1 \leq i \leq t ) には i 個目のテストケースの答えを出力すること。 答えについては、あり得る場合は YES を、あり得ない場合は NO を出力すること。

解法

この問題を要約すると、文字列 p の L を L または LL に、 R を R または RR にそれぞれ変換できるとき、文字列 p を文字列 s にできるかを判定する、という問題になります。

従って、 p と s のそれぞれについて、「 L または R の文字が何個連続で続いているのか」を管理することを考えます。

このときに、 p と s ついてできる配列をそれぞれ {v}_{p}, \, {v}_{s} とします。 そして、それぞれの {v} について、「現在の文字」と「何個続いているか」を同時に管理します。 例えば、文字列 p が LRRL の場合は、

\begin{align} {v}_{p} = \left[ \left( \mathrm{L}, \, 1 \right) , \, \left( \mathrm{R}, \, 2 \right) , \, \left( \mathrm{L}, \, 1 \right) \right] \end{align}

となります。 ここで、 {v}_{p} の i 番目の要素の文字を {c}_{{p}_{i}} 、個数を \mathrm{cnt}_{{p}_{i}} とします。 {v}_{s} についても同様です。

文字列 p から文字列 s を生成できるかどうかについては、このようにできた {v}_{p}, \, {v}_{s} に対して、下記の条件をすべて満たせば可能であると言えます。

  1. {v}_{p} と {v}_{s} の要素数が一致する。
  2. 各 i ( 1 \leq i \leq \left| {v}_{p} \right| ) に対して、 {c}_{ {p}_{i} } = {c}_{ {s}_{i} } が成立する。
  3. 各 i ( 1 \leq i \leq \left| {v}_{p} \right| ) に対して、 \mathrm{cnt}_{{p}_{i}} \leq \mathrm{cnt}_{{s}_{i}} \leq 2 \cdot \mathrm{cnt}_{ {p}_{i} } が成立する。

条件1については、 {v} が「ある文字が何個連続で続いているか」を管理していることから、要素数が異なるときは p と s を構成している文字の種類がそもそも異なる、ということになります。

条件2については、文字列 p はある1文字を「そのままにする」か「2文字に増やす」かの操作を行い s にしています。 そのため条件2が成立しない場合、 p に無い要素を使用して s を生成していることになります。

ちなみに、この問題では、 p, \, s が L と R の2種類しか無いため、 {v} の文字の部分は L と R の交互になります。 そのため、 {c}_{ {p}_{1}} = {c}_{ {s}_{1}} が成立していれば、その他の i に対してもこの条件は成立すると言えます。

条件3については、文字列 p の各文字を1文字もしくは2文字にすることで s が生成されているため、 \mathrm{cnt}_{ {p}_{i} } の文字数は \mathrm{cnt}_{ {p}_{i} } 以上 2 \cdot \mathrm{cnt}_{ {p}_{i} } 以下になると言えます。 従って、これが文字列 s になることから、

\begin{align} \mathrm{cnt}_{ {p}_{i} } \leq \mathrm{cnt}_{ {s}_{i} } \leq 2 \cdot \mathrm{cnt}_{ {p}_{i} } \end{align}

が成立するときに、 p から s が生成できると言えます。

以上を、各テストケースについて調べることにより、この問題は解くことができます。 {v} を作るのに p, \, s の各文字を見ていくことから、これはそれぞれ O(|p|), \, O( |s| ) 程度の計算量が必要と言えます。

そうして出来上がった {v} の各要素に対して、条件 1 ~ 3 が成立するかを判定するにも、 O ( | v | ) 程度の計算量が必要ですが、 {v} の要素数は最大でも |s| となります。

従って、1テストケースに対しての必要な計算量は O ( |s| ) 程度であると言え、すべてのテストケースでの |s| の総和は 2 \times {10}^{5} を超えないことが保証されていることから、この解法で実行時間制限に十分間に合うと言えます。

ソースコード

各テストケースでの答えを出力する関数 solve() を以下のように実装しました。

void YES() { printf("YES\n"); } // "YES" を出力する関数 YES()
void NO() { printf("NO\n"); } // "NO" を出力する関数 NO()

string p, s;
vector<pair<char, int>> vp, vs;

void solve() {
  cin >> p; // p の入力
  vp.resize(0); // vp のリセット
  int cnt = 1; // 連続する文字数を表す整数 cnt
  for (int i = 1; i < p.length(); i++) { // i = 1, ... について考える (i = 0 はすでに考えられたものとする)
    if (p[i] == p[i - 1]) {
      cnt++; // p[i] が前の文字と同じときは cnt を 1 増やす
    } else {
      vp.push_back({p[i - 1], cnt}); // p[i] が前の文字と異なるときは vp に前の文字の状態を入れる
      cnt = 1; // cnt を 1 にリセットする
    }
  }
  vp.push_back({p[p.length() - 1], cnt}); // p[n] の分は入っていないので、入れる

  cin >> s; // s の入力
  vs.resize(0); // vp と同様に vs の更新を行う
  cnt = 1;
  for (int i = 1; i < s.length(); i++) {
    if (s[i] == s[i - 1]) {
      cnt++;
    } else {
      vs.push_back({s[i - 1], cnt});
      cnt = 1;
    }
  }
  vs.push_back({s[s.length() - 1], cnt});

  // 条件 1 の確認
  if (vp.size() != vs.size()) {
    NO();
    return;
  }

  // 条件 2, 3 を確認する
  for (int i = 0; i < vp.size(); i++) {
    // 条件 2 の確認
    if (vp[i].first != vs[i].first) {
      NO();
      return;
    }
    // 条件 3 の確認
    if (vp[i].second > vs[i].second || vp[i].second * 2 < vs[i].second) {
      NO();
      return;
    }
  }

  YES(); // すべてを満たしたときのみ、 YES を出力する
  return;
}

この solve() 関数がある状態で、 main() 関数に下記のように実装することで、 t 個のテストケースに対応しました。

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }

  return 0;
}

C - Brr Brrr Patapim / Codeforces Round 1017 (Div. 4)

CF2094 Codeforces C++ Div.4 Codeforces Round 1017 Diff 900 競技プログラミング

問題

2n 個の要素からなる順列 p があり、これをパスワードとして用いている。

この p について、 n \times n の行列 G があり、 G の i 行 j 列の要素 {G}_{i, \, j} は {p}_{i + j} を表す。

p がただ一つ存在することが保証されているとき、 G が与えられるので p を求めよ。

入力

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

その後、各テストケースについて、次のように与えられる。

  • 最初の1行目には整数 n が与えられる。
  • 次の n 行にわたり、 i 行目 ( 1 \leq i \leq n ) には n 個の整数 {G}_{i, \, 1}, \, \cdots , \, {G}_{i, \, n} が空白区切りで与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 256MB
  • 1 \leq t \leq 200
  • 1 \leq n \leq 800
  • 1 \leq {G}_{i, \, j} \leq 2n \; ( 1 \leq i, \, j \leq n)
  • t 個のテストケースでの n の総和は 800 を超えない。

出力

t 行にわたり、 1 \leq i \leq t 行目には i 個目のテストケースの答えとなる順列 p の要素を、順に空白区切りで出力すること。

解法

問題文より、 p が必ず存在する前提で行列 G が与えられ、 {p}_{i + j} = {G}_{i, \, j} であることから、行列 G の各要素から p を埋めていくことを考えます。

このときに、 1 \leq i, \, j \leq n より 2 \leq i + j \leq 2n となります。 すなわち、行列 G には {p}_{1} の値は出てこないと言えます。

従って、 G の要素として出てきた値を確認し、 1 から 2n までの中で出現しなかった値が {p}_{1} となります。 これにより、順列 p の各要素の値を特定することができます。

n \times n の行列 G の各要素を見ていくことから、この部分の計算量は O( {n}^{2} ) 程度になります。 また、 1 から 2n までの値を見ていくところについては O(2n) 程度の計算量になります。

t 個のテストケースでの n の総和が 800 を超えないことから、この方法で実行時間制限にも十分に間に合うと言えます。

ソースコード

各テストケースでの答えを出力する関数 solve() を以下のように実装しました。

int n, g[805][805];
int ans[1605]; // 答えとして出力する順列 ans
bool visited[1605]; // 1 ~ 2n までの値が出現したかを管理する visited

void solve() {
  cin >> n; // n の入力
  fill(visited + 1, visited + 2 * n + 1, false); // visited[1] ~ visited[2 * n] を false でリセットする

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> g[i][j]; // g[i][j] の入力
      visited[g[i][j]] = true; // g[i][j] の値が出現したことを記録する
      ans[i + j] = g[i][j]; // ans[i + j] の値を更新する
    }
  }

  // ans[1] の値を求めるために、 i = 1, ..., 2n の順で visited[i] を調べる
  for (int i = 1; i <= 2 * n; i++) {
    if (!visited[i]) {
      ans[1] = i; // 出現していない i が見つかったら、それが ans[1] の値となる
    }
  }

  // 答えの出力
  for (int i = 1; i <= 2 * n; i++) {
    cout << ans[i] << (i == 2 * n ? '\n' : ' ');
  }
  return;
}

この solve() 関数がある状態で、 main() 関数に下記のように実装することで、 t 個のテストケースに対応しました。

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }

  return 0;
}

B - Bobritto Bandito / Codeforces Round 1017 (Div. 4)

CF2094 Codeforces C++ Div.4 Codeforces Round 1017 Diff 800 競技プログラミング

問題

無限に続く数直線上に無限個の家があり、家は \cdots , \, −2, \, −1, \, 0, \, 1, \, 2, \, \cdots の位置に存在する。

0 日目に、家 0 に疫病が発生した。 その後は毎日、疫病が発生している範囲に隣接するちょうど 1 軒の家に新たに疫病が発生する。

n 日目には、家 \left[ l, \, r \right] の範囲に疫病が発生していたとわかっている。 このとき m \; (\leq n) 日目に疫病が発生していた可能性がある家の区間 \left[ l', \, r' \right] を1つ求めよ。

入力

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

その後 t 行について、 i 行目 ( 1 \leq i \leq t ) には i 個目のテストケースとして、空白区切りで整数 n, \, m, \, l, \, r が順に与えられる。

条件

  • 実行時間制限: 1s
  • メモリ制限: 256MB
  • 1 \leq t \leq 100
  • 1 \leq m \leq n \leq 2000
  • -n \leq l \leq 0 \leq r \leq n
  • r - l = n

出力

t 行にわたり i 行目 ( 1 \leq i \leq t ) には i 個目のテストケースの答えとなる整数 l', \, r' を空白区切りで出力すること。

解法

0 日目では感染範囲が \left[ 0, \, 0 \right] であり、1日ごとに 1 軒ずつ範囲が増えていくことから、 m 日目での範囲 \left[ l', \, r' \right] については r' - l' = m であると言えます。

また、 m \leq n で、 n 日目での範囲が \left[ l, \, r \right] であることから、 l \leq l' \leq 0 かつ 0 \leq r' \leq r であることも言えます。

従って、 r' - l' = m より r' = m + l' で、 l' \leq 0 であることから、 r' \leq m が言えます。 このことから r' は r' \leq r かつ r' \leq m を満たす整数と言えます。

この問題では m 日目の範囲として可能性があるものを1つ導出すればよいので、以上の考察から

\begin{align} r' = \min \left(m, \, r \right) \end{align}

とすることにより、必ず条件を満たす r' の値が得られます。 また、このとき r' - l' = m であるので、

\begin{align} l' = r' - m = \min \left( m, \, r \right) - m \end{align}

とすることにより、条件を満たす l', \, r' の値の組を求めることができます。

これは各テストケースに対して O(1) 程度の計算量で導出することができます。 従って全テストケースについては O(t) 程度の計算量となり、 t \leq 100 であることから、実行時間制限にも十分間に合うと言えます。

ソースコード

各テストケースでの答えを出力する関数 solve() を以下のように実装しました。

void solve() {
  int n, m, l, r;
  cin >> n >> m >> l >> r; // 値の入力
  cout << min(m, r) - m << " " << min(m, r) << endl; // l', r' の値の出力
  return;
}

この solve() 関数がある状態で、 main() 関数に下記のように実装することで、 t 個のテストケースに対応しました。

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }

  return 0;
}

A - Trippi Troppi / Codeforces Round 1017 (Div. 4)

CF2094 Codeforces C++ Div.4 Codeforces Round 1017 Diff 800 文字列 競技プログラミング

問題

3個の文字列が与えられるので、そのそれぞれの頭文字をつなげた3文字の文字列を出力せよ。

入力

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

その後 t 行について、 i 行目 ( 1 \leq i \leq t ) には i 個目のテストケースとして、空白区切りで3個の文字列が与えられる。

条件

  • 実行時間制限: 1s
  • メモリ制限: 256MB
  • 1 \leq t \leq 100
  • 与えられる文字列は英小文字のみで構成される
  • 与えられる文字列の長さは 10 以下

出力

t 行にわたり i 行目 ( 1 \leq i \leq t ) には i 個目のテストケースの答えを出力すること。

解法

3個の文字列を入力し、頭文字をつなげた3文字の文字列を出力する問題なので、1個文字列を入力するたびにその先頭の文字を出力すれば、この問題を解くことができます。

文字列は1テストケースにつき3個入力されるので、1 テストケースについては O(1) 程度の計算量で解くことができます。 従って、この問題全体で O(t) 程度の計算量で解くことができ、 t \leq 100 なので、これは実行時間制限に十分に間に合うと言えます。

ソースコード

各テストケースでの答えを出力する関数 solve() を以下のように実装しました。

string s; // 入力される文字列 s

void solve() {
  for (int i = 0; i < 3; i++) {
    // for ループで 3 回実施する
    cin >> s; // s の入力
    cout << s[0]; // s の先頭の出力
  }
  cout << endl; // 改行文字の出力

  return;
}

この solve() 関数がある状態で、 main() 関数に下記のように実装することで、 t 個のテストケースに対応しました。

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }

  return 0;
}

B - Find Permutation 2 / ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425）

ABC425 C++ AtCoder AtCoder Beginner Contest 200点 順列 競技プログラミング

問題

長さ n の整数列 a = ( {a}_{1}, \, {a}_{2}, \, \cdots , \, {a}_{n} ) が与えられる。

以下の条件を満たす長さ n の整数列 p = ( {p}_{1}, \, {p}_{2} , \, \cdots , \, {p}_{n}) が存在するか判定し、存在するならば1つ求めよ。

  • p は (1, \, 2, \, \cdots , \, n) を並び替えてできる数列である。
  • i = 1, \, 2, \, \cdots , \, n に対し、 {a}_{i} \ne -1 ならば {p}_{i} = {a}_{i} である。

入力

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

次の1行に、 n 個の整数 {a}_{1}, \, {a}_{2}, \, \cdots , \, {a}_{n} が空白区切りで与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 1024MB
  • 1 \leq n \leq 10
  • {a}_{i} = -1 または 1 \leq {a}_{i} \leq n

出力

条件を満たす p が存在しない場合は No を出力すること。

存在する場合は1行目に Yes を出力し、2行目に条件を満たす {p}_{1}, \, \cdots , \, {p}_{n} を空白区切りで出力すること。

解法

まず、条件を満たす数列 p が存在する条件について考えます。

数列 p は (1, \, 2, \, \cdots, \, n) を並び替えたものになるので、 1 から n までの整数が必ず1個ずつ出現するようなものになります。 p の条件として、「 {a}_{i} \ne -1 ならば {p}_{i} = {a}_{i} である」というものがあるので、 {a}_{i} \ne -1 である {a}_{i} のうち、値が2回以上出てくるものがあれば、条件を満たす数列 p は存在しない、ということになります。

すなわち、 \mathrm{cnt}_{i} を、 a の要素のうち値が i であるものの個数として定義すると、 \mathrm{cnt}_{i} \geq 2 であるものが存在した場合、 p は存在しないということになります。 これにより、まず数列 p が存在するかどうかの判定を行えます。

次に数列 p が存在する場合での p について考えます。 条件より、 {a}_{i} \ne -1 の場合は {p}_{i} = {a}_{i} とすれば良いので、そのままその値を入れます。

一方で、 {a}_{i} = -1 である i に対しては、先程の \mathrm{cnt} の値が 0となっているものを順に埋めていけばよいです。 このようにすることで、 1 から n までの整数が p にそれぞれ1回ずつ出現することになるので、問題文の条件を満たせるといえます。

以上の方法により、この問題は解くことができると言えます。 計算量については、 {a}_{i} を i = 1, \, \cdots , \, n まで見ていくことなどから O(n) 程度になると言え、 1 \leq n \leq 10 であることから、これは実行時間制限に十分間に合うと言えます。

ソースコード

main() 関数の中に、直接答えを出力する部分を実装しました。

void Yes() { printf("Yes\n"); } // Yes を出力する関数 Yes()
void No() { printf("No\n"); } // No を出力する関数 No()

int n, a[15];
int cnt[15], p[15];

int main() {
  // 値の入力
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (a[i] != -1) {
      cnt[a[i]]++; // a[i] != -1 のとき、 cnt[a[i]] の値を1追加する
      p[i] = a[i]; // このとき p[i] に a[i] を代入する
    }
  }

  // i = 1, ..., n について cnt[i] の値を見る
  for (int i = 1; i <= n; i++) {
    if (cnt[i] >= 2) {
      // もし cnt[i] が 2 以上であれば、 No を出力し終了する
      No();
      return 0;
    }
  }

  Yes(); // 条件を満たす場合は Yes を出力する
  int now = 1; // cnt[i] = 0 である整数を管理するための整数 now
  for (int i = 1; i <= n; i++) {
    // cnt[now] = 0 である整数 now を探す
    while (cnt[now] > 0) {
      now++;
    }

    // もし p[i] にまだ値が代入されていないのであれば、 now を代入する
    if (p[i] == 0) {
      p[i] = now;
      now++; // now を 1 増やしておく
    }
  }

  // 数列 p の出力
  for (int i = 1; i <= n; i++) {
    cout << p[i] << (i == n ? '\n' : ' ');
  }

  return 0;
}

A - Sigma Cubes / ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425）

ABC425 C++ AtCoder AtCoder Beginner Contest 100点 競技プログラミング

問題

整数 n が与えられる。 i = 1, \, 2, \, \cdots , \, n について、 {(-1)}^{i} \times {i}^{3} を計算したときの、それら n 個の値の総和を求めよ。 すなわち、

\begin{align} \sum_{i = 1}^{n} {(-1)}^{i} \times {i}^{3} \end{align}

の値を求めよ。

入力

整数 n が1行で与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 1024MB
  • 1 \leq n \leq 10
  • n は整数

出力

答えとなる値を1行で出力すること。

解法

問題の条件より、 1 \leq n \leq 10 なので、 1 \leq i \leq n である整数 i について、 {(-1)}^{i} \times {i}^{3} の値を順に求めていき、それらの総和を求めることによりこの問題の答えが得られます。

{(-1)}^{i} の値を丁寧に求めるのであれば、 O(i) 程度の計算量が必要で、 i = 1, \, 2, \, \cdots , \, n の順に求めていくことから、回答を得るまでの計算量としては O( {n}^{2} ) 程度になると言え、これは実行時間制限に十分間に合うと言えます。

ソースコード

main() 関数に直接、答えを出力するところまでを実装しました。

int main() {
  // 値の入力
  int n;
  cin >> n;

  int ans = 0; // ans は最終的な答えを表す

  // i = 1, …, n の順に計算する
  for (int i = 1; i <= n; i++) {
    int now = 1; // now は現在の i での値を表す
    for (int j = 1; j <= i; j++) {
      now *= -1; // now = (-1) ^ i とする
    }
    now *= i * i * i; // now に i ^3 を掛ける
    ans += now; // ans に現在の値を加える
  }

  // 値の出力
  cout << ans << endl;

  return 0;
}