for 文で隣接する要素を見ながら処理していく系の問題
長さ の文字列
が与えられる。
を左から見ていき、文字列 "joi" が含まれるならば、これを "JOI" に変換していく処理を繰り返す。操作後の文字列を出力せよ。
次のように考えるとよいでしょう。 の
文字目を順に見ていき、もし
であるならば、これらをそれぞれ 'J', 'O', 'I' にしていきます。
#include <bits/stdc++.h> using namespace std; int main() { int N; string S; cin >> N >> S; for (int i = 0; i + 2 < N; ++i) { if (S[i] == 'j' && S[i+1] == 'o' && S[i+2] == 'i') { S[i] = 'J'; S[i+1] = 'O'; S[i+2] = 'I'; } } cout << S << endl; }
いろんな解法がある！
以上
以下の整数のうち、
との差の絶対値が最も小さいものを求めよ。
for 文一番確実な方法は、for 文を用いて、 をすべて調べることだと思われます。
が最小となるような
を求めればよいでしょう。
#include <bits/stdc++.h> using namespace std; int main() { int X, L, R; cin >> X >> L >> R; int min_value = 200000; // 十分大きな値で初期化 int min_x = -1; for (int x = L; x <= R; ++x) { int diff = abs(x - X); // x と X との差 if (diff < min_value) { min_value = diff; min_x = x; } } cout << min_x << endl; }
数学的に処理してみましょう。
まず、 のときは、
のとき、
と
の差は 0 となります。これが明らかに最小です。
次に、 のときは、
のとき、
と
の差は
となり、これが最小です。
最後に、 のときは、
のとき、
と
の差は
となり、これが最小です。
#include <bits/stdc++.h> using namespace std; int main() { int X, L, R; cin >> X >> L >> R; if (X < L) cout << L << endl; else if (R < X) cout << R << endl; else cout << X << endl; }
集計処理を練習しよう！
以上
以下の整数からなる、長さ
の数列
が与えられる。
長さ の新たな数列
を次のように定義する。
の最大値を求めよ。
問題の意味を解釈するのが難しいかもしれないですね。たとえば
について考えてみましょう。1 は 1 個、2 は 3 個、4 は 2 個、5 は 1 個、7 は 1 個あり、このうち最も多いのは 2 の 3 個ですので、答えは「3」です。
これを実装するためには、問題文中に書いてある通り、数列 を求めるとよいでしょう。次のように実装できます。
vector<int> B(M+1, 0); // M まで確保する for (int i = 0; i < N; ++i) ++B[A[i]]; // A[i] の分を 1 個増やす
これが求められたあとは、 の最大値を求めればよいでしょう。
#include <bits/stdc++.h> using namespace std; int main() { int N, M; cin >> N >> M; vector<int> A(N), B(M + 1, 0); for (int i = 0; i < N; ++i) { cin >> A[i]; ++B[A[i]]; } // B の最大値を求める int res = 0; for (int i = 1; i <= M; ++i) res = max(res, B[i]); cout << res << endl; }
reverse する系の問題
長さ の文字列
について、
文字目から
文字目までを反転して得られる文字列を出力せよ。
C++ でプログラムを書くときは、通常文字列は 0 始まりですので、 からあらかじめ 1 引いておきます。
その後は、次のように実装すればよいでしょう。
for 文を用いて実装できます。降順に出力するときは、添字 i をデクリメント (--i というように) していきます。
#include <bits/stdc++.h> using namespace std; int main() { int N, A, B; string S; cin >> N >> A >> B >> S; --A, --B; for (int i = 0; i < A; ++i) cout << S[i]; for (int i = B; i >= A; --i) cout << S[i]; for (int i = B+1; i < N; ++i) cout << S[i]; cout << endl; }
マージソートのマージの部分を実装する問題ですね。
添字を順に進めていくような処理を実装します！ この実装は、のちにしゃくとり法を学ぶ際の参考にもなります。
問題文が複雑で、何をすればいいのかを理解するのが大変かもしれないですね。
一般に、数列 の先頭の要素を削除していく処理は実装が大変です (なお、数列を
deque で実装するとか、数列を reverse して末尾から削除していくような実装をするなどの別解はあります)。
そこで、代わりに、数列 上の添字
と、数列
上の添字
を管理することにします。これらは「今この添字のある位置が疑似的に数列の先頭になっています」を表しています。
たとえば、上図のような状況を考えます。数列 の左 2 個 (2, 4) と、数列
の左 1 個 (3) がすでに削除されて、数列
に格納されている状態とします。
次のステップでは、数列 の真の先頭の要素 (疑似的に値
A[2] = 7) と、数列 の先頭の要素 (疑似的に値
B[1] = 8) とを比較します。A[2] の方が小さいので、A[2] を数列 に push して、
の添字
を 1 進めます。
このような処理を、添字 がそれぞれ数列
の終端に到達するまで繰り返せばよいでしょう。
#include <bits/stdc++.h> using namespace std; int main() { int N, M; cin >> N >> M; vector<int> A(N), B(M); for (int i = 0; i < N; ++i) cin >> A[i]; for (int i = 0; i < M; ++i) cin >> B[i]; vector<int> C; int i = 0, j = 0; // A 側の先頭の添字と B 側の先頭の添字 while (i < N || j < M) { if (i == N) { // A 側が終端に達していたら B 側を入れて、B 側の添字 j を進める C.push_back(B[j]); ++j; } else if (j == M) { // B 側が終端に達していたら A 側を入れて、A 側の添字 i を進める C.push_back(A[i]); ++i; } else if (A[i] < B[j]) { // A の方が小さいとき、A 側を入れて、A 側の添字 i を進める C.push_back(A[i]); ++i; } else { // B の方が小さいとき、B 側を入れて、B 側の添字 j を進める C.push_back(B[j]); ++j; } } // 出力 for (int i = 0; i < N + M; ++i) cout << C[i] << endl; }
