はじめに
競プロに興味を持ち,少しづつ参加しているのですが,モチベ維持のためにQiitaに少しづつ載せていけたらなと思います.過去に参加したものに遡って少しづつ書いていく予定です.
今回のコンテストのurlはこちら
A問題
問題概要
2つのボタン$A, B$が与えられる.
ボタン$X$を押すとコインを$X$枚取得してボタンが$X-1$になる.
ボタンを2回押すときの獲得コイン最大値を求める.
自分の解答
二つの入力の大小関係を確認してそれによって出力を条件分岐させた.
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b;
cin >> a >> b;
int dif = a - b;
if(dif==0){
cout << a + b << endl;
}else if(dif>=1){
cout << a + a - 1 << endl;
}else{
cout << b + b - 1 << endl;
}
return 0;
}
解説を見た後
自分で作成したソースコードでは条件分岐をしていたのだが,この程度の分岐ではmax()
で場合分けをした方が簡潔に書けた.
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b;
cin >> a >> b;
cout << max({a+a-1, b+b-1, a+b}) << endl;
return 0;
}
B問題
問題概要
山の個数$N$とその高さ$H_1,H_2,...,H_N$が与えられる.
ある自然数$1\leq n\leq N$に対して,$H_1\leq H_n, H_2\leq H_n, ..., H_{n-1}\leq H_n$が成り立つ$n$の個数を求める.
自分の解答
問題自体が単純であったため,ソースコードも難なく完成した.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
int i,j;
cin >> n;
vector<int> h(n);
for(i=0; i<n; i++){
cin >> h[i];
}
int counter = 1;
for(i=1; i<n; i++){
for(j=0; j<i; j++){
if(h[i]<h[j]){
break;
}
if(j==i-1){
counter++;
}
}
}
cout << counter << endl;
return 0;
}
解説を見た後
大きく変更した点は無いが,break
を無くしたことで少しだけ計算速度が削減された.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
int i,j;
cin >> n;
vector<int> h(n);
for(i=0; i<n; i++){
cin >> h[i];
}
int counter = 1;
for(i=1; i<n; i++){
for(j=0; j<i && h[i]>=h[j]; j++){
if(j==i-1) counter++;
}
}
cout << counter << endl;
return 0;
}
アドバイスを受けた後
提出した回答では計算速度の違いはなかったが,山の数が多くなれば計算速度が削減される書き方となった.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
int i,j;
cin >> n;
vector<int> h(n);
for(auto& e : h) cin >> e;
int counter = 0;
int hMax = h[0];
for(i=0; i<n; ++i){
if(hMax <= h[i]){
counter++;
hMax = h[i];
}
}
cout << counter << endl;
return 0;
}
C問題
問題概要
'0','1'で構成される文字列$S$が与えられる.$
S$を'0'と'1'交互にするために必要な文字書き換え回数を計算する.
自分の解答
普通に解けたのだが,内容に対して長いソースコードになってしまった.
#include <bits/stdc++.h>
using namespace std;
int main(){
// start process
string s;
int i,j;
cin >> s;
int even = 0, odd = 0;
for(i=0; i<s.length(); i++){
if(s[i]=='0'){
if(i%2==0){
even++;
}else{
odd++;
}
}
}
int change = 0;
if(even>odd){
for(i=0; i<s.length(); i++){
if(i%2==0){
if(s[i]!='0'){
change++;
}
}else{
if(s[i]=='0'){
change++;
}
}
}
}else{
for(i=0; i<s.length(); i++){
if(i%2==0){
if(s[i]=='0'){
change++;
}
}else{
if(s[i]!='0'){
change++;
}
}
}
}
cout << change << endl;
// end process
return 0;
}
解説を見た後
少しだけ簡潔に書けるようになった.特に,1行のみのif
,else
について{}
を省略して書くと便利だと感じた.しかし,処理を追加する可能性があれば省略しない方が良いとも考えている.
#include <bits/stdc++.h>
using namespace std;
int main() {
string S;
cin >> S;
char s=S[0];
int bw = 0;
int wb = 0;
char w='0';
char b='1';
for(int i=0;i<S.size();i++){
if(i%2==0){
if(S[i]==b)bw++;
else wb++;
}else
if(S[i]==w)bw++;
else wb++;
}
cout << min(bw, wb) << endl;
return 0;
}
D問題
問題概要
'0','1'で構成される長さ$N$の文字列$S$および自然数$K$が与えられる.
連続した任意の文字を反転できるとして,$K$回の反転で'1'が最大何個連続する状態を作れるか計算する.
自分の解答
解けなかった.
切り替わりのみを確認したら良いという発想にはなったがそれを実装できなかった.
解説を見た後
#include <bits/stdc++.h>
using namespace std;
void view(const vector<int>& v){for(const auto& e : v)cout << e << " ";cout << endl;}
int main(){
int i;
int n, k;
string s;
cin >> n >> k >> s;
s += 'x';
vector<int> organ;
char past = s[0];
int count = 0;
for(i=0; i<s.length(); ++i){
if(past != s[i]){
organ.push_back(count);
count = 0;
}
count ++;
past = s[i];
}
for (int i=1; i<organ.size(); ++i)
organ[i] += organ[i - 1];
int humanState = (s[0] == '1');
int maxHuman = 0;
for(i=0; i<organ.size(); ++i){
int humans;
if(organ.size()<i+2*k+(humanState+i)%2){
humans = organ[organ.size()-1] - (i? organ[i-1] : 0);
}else{
humans = organ[i+2*k-1+(humanState+i)%2] - (i? organ[i-1] : 0);
}
maxHuman = max(maxHuman, humans);
}
cout << maxHuman << endl;
return 0;
}
おわりに
- 3つ以上の
max()
関数の使い方を学んだmax({x1, x2, x3});
-
if
文の見やすい書き方を学んだ- `if(conditions) process;
-
if
文の便利な表記方法を学んだ- `(conditions ? trueProcess : falseProcess)