引き続き、B問題を解いていきます。
ABC B051 – Sum of Three Integers
問題
2つの整数K,Sが与えられます。
3つの変数X,Y,Zがあり、0≦X,Y,Z≦Kを満たす整数の値を取ります。
X+Y+Z=Sを満たすX,Y,Zへの値の割り当ては何通りありますか。
自分の回答
#include <bits/stdc++.h>
using namespace std;
int main () {
int K, S;
cin >> K >> S;
int count = 0;
for (int i = 0; i <= K; i++){
for (int j = 0; j <= K; j++){
int k = S - i - j;
if(k >= 0 && k <= K){
count += 1;
}
}
}
cout << count << endl;
}// 間違い例
// 間違い例
#include <bits/stdc++.h>
using namespace std;
int main () {
int K, S;
cin >> K >> S;
int count = 0;
for (int i = 0; i <= K; i++){
for (int j = 0; j <= K; j++){
for (int k = 0; k <= K; k++){
if(i + j + k == S){
count += 1;
}
}
}
}
cout << count << endl;
}B問題にありがちなパターンの問題ですので、とても大事です。最初は間違い例のようなコードを書いてしまうと思います。違いはfor文を回す回数です。
間違い例では、変数i、j、kに対して、for文を使っているので、3回for文を回しています。正解では、i、jに対してだけなので、2回で済んでいます。何故かというと、変数kはi、jが決まると自動的に決まります。あとは、kが条件に収まる時(0<=k<=S)にのみ、カウントするようにすればいいだけです。
間違い例では、答え自体は正しいものが出ますが、SやKの値が大きくなると、実行時間超過となって、正解になってくれません。B問題になると、計算速度を早くする工夫もしなくてはいけなくなります。特に、このように、for文を回す回数を少なくする問題は度々出てくきますので、今回のテクニックは覚えておきましょう。
ABC 052B – Increment Decrement
問題
あなたは整数xを持っています。 最初、x=0です。
あなたは、長さNの文字列Sをもらったので、これを使ってN回の操作を行いました。i回目の操作では、Si=Iならばxの値を1増やし、Si=Dならばxの値を1減らしました。
操作の途中(1回目の操作の前、N回目の操作の後も含む)でxがとる値の最大値を答えてください。
自分の回答
#include <bits/stdc++.h>
using namespace std;
int main () {
int N;
string S;
cin >> N >> S;
int now = 0;
int MAX = 0;
for (int i = 0; i < N; i++){
if(S[i] == 'I'){
now += 1;
MAX = max(now,MAX);
}else if(S[i] == 'D'){
now -= 1;
}
}
cout << MAX << endl;
}文字列を一文字ずつ取り出して、’I’だった場合、変数nowに1を足していきます。そして、最大値を残すために、max関数でその都度比較して、最大値を変数MAXに格納します。
文字が’D’だったら、nowから1を引きます。
if文の条件のところをシングルクォーテーションにすることに気をつけましょう。
詳しくは以下の記事を参考に。
https://cloraordinary.com/c%e3%82%b7%e3%83%b3%e3%82%b0%e3%83%ab%e3%82%af%e3%82%a9%e3%83%bc%e3%83%86%e3%83%bc%e3%82%b7%e3%83%a7%e3%83%b3%e3%81%a8%e3%83%80%e3%83%96%e3%83%ab%e3%82%af%e3%82%a9%e3%83%bc%e3%83%86%e3%82%b7
