ABC C問題埋め2

投稿者: | 2020年5月27日
0件のコメント

Atcoder ProblemsのTrainingのEasyにあるC問題埋めの続きです。

Easyでも最後の3問ぐらいはどうやっても解法が思い浮かばなかったりしたので、実力の無さを噛み締めていました。

1.ABC139

問題:C-Lower

N個のマスが並んでいて、隣のマスの高さが今のマスの高さ以下なら移動できるので、可能な移動回数を出力せよという問題。

右だけに進むので、高さを配列に入れて右にずっと見ていけば答えが出ます。

書いたコードは以下の通り。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
int n;
cin >> n;
int a[n];
rep(i, n) cin >> a[i];
int count = 0;
int m = 0;
rep(i,n-1) {
if(a[i]>=a[i+1]){
count++;
}else{
m = max(m, count);
count = 0;
}
if(i==n-2)
m = max(m, count);
}
cout << m << endl;
return 0;
}
view raw ABC139c.cpp hosted with ❤ by GitHub

2.ABC140

問題:C-Maximal Value

少し苦労した問題です。一個一個整理しながら考える必要があります。

謎の整数列Aがあり、そこに既知の整数列Bが与えられます。整数列Bのそれぞれの要素は、同じ番目の整数列Aの要素と次の要素の最大値より大きくなるという条件があります。このとき、整数列Aの総和を求めよという問題。

整数列Aの総和を最大にするので、それぞれの要素はわからなくても大丈夫ですが、入れながらやったほうがデバッグするときとかわかりやすい気がします。

書いたコードは以下の通り。無理やり実装した。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
int n;
cin >> n;
int a[n];
rep(i, n) a[i] = -1;
vector<P> p(n - 1);
rep(i, n - 1) {
int tmp;
cin >> tmp;
p[i] = make_pair(tmp, i);
}
sort(p.begin(), p.end());
rep(i,n-1){
int num = p[i].second;
if(a[num] == -1) {
a[num] = p[i].first;
}
if(a[num + 1] == -1) {
a[num + 1] = p[i].first;
}
}
ll sum = 0;
rep(i, n) sum += a[i];
cout << sum << endl;
return 0;
}
view raw ABC140c.cpp hosted with ❤ by GitHub

3.ABC158

問題:C-Tax Increase

制約条件が高々100までなので、ループ内で値を一つずつ増やしていって、一致するかしないかだけ見ていれば大丈夫です。小数点以下切り捨てだけ注意。

書いたコードは以下の通り。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
int a, b;
cin >> a >> b;
int x = 1;
while(1) {
int aa = x * 0.08;
int bb = x * 0.1;
if(aa == a && bb == b)
break;
if(aa > a && bb > b){
x = -1;
break;
}
x++;
}
cout << x << endl;
return 0;
}
view raw ABC158c.cpp hosted with ❤ by GitHub

4.ABC148D

問題:D-Brick Break

レンガを壊して、残ったレンガに書かれている数字を1,2,3,…とするとき、壊すレンガの最小個数を答えよという問題。

左から1,2,3,…と書かれたレンガが残ればいいので、左から1のレンガが出るまで壊す、1のレンガが出たら2のレンガが出るまで壊す、というのを繰り返せば答えが出ます。

書いたコードは以下の通り。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
int n;
cin >> n;
int a[n];
rep(i, n) cin >> a[i];
int num = 1, count = 0;
rep(i,n){
if(a[i]==num){
num++;
} else {
count++;
}
}
if(count==n)
count = -1;
cout << count << endl;
return 0;
}
view raw ABC148d.cpp hosted with ❤ by GitHub

5.ABC155

問題:C-Poll

出てくる文字列をそれぞれカウントするという問題。私は無理やりpairを作ってやってましたが、解説ではmapを使って実装していたので、なるほどなあとなりました。

今回の問題では出力されるのは、書かれた回数が最も多い文字列を全て、"辞書順"で小さい順に出力するというものです。

なので、mapに入れれば勝手にsortされるので、出力するときに便利です。また、文字列をkeyとすることで、めんどくさいことをしなくても、そのkeyのvalueにアクセスできます。

mapを使わずに実装すると次のようになります。mapを使った場合は解説を見て下さい。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
int n;
cin >> n;
vector<string> v;
rep(i, n) {
string s;
cin >> s;
v.push_back(s);
}
sort(v.begin(), v.end());
int count = 0;
int max = 0;
vector<pair<string, int>> d;
rep(i, n-1) {
if(v[i] == v[i + 1]) {
count++;
} else {
count++;
d.push_back(make_pair(v[i], count));
if(count>max)
max = count;
count = 0;
}
if(i == n - 2){
if(v[i]==v[i+1]){
count++;
d.push_back(make_pair(v[i], count));
if(count > max)
max = count;
} else {
d.push_back(make_pair(v[i], count));
if(count > max)
max = count;
d.push_back(make_pair(v[i+1], 1));
}
}
}
rep(i, d.size()) {
if(d[i].second == max)
cout << d[i].first << endl;
}
return 0;
}
view raw ABC155c.cpp hosted with ❤ by GitHub

6.三井住友信託銀行プログラミングコンテスト2019

問題:C-100 to 105

1個100円、101円、102円、103円、104円、105円の品物がぞれぞれ(実装する上では気にしなくていいぐらい)大量に売られています。それらを組み合わせて合計金額がX円になるような買い方ができるかどうか判定せよという問題です。

どれか1個だけ買う場合、2個買う場合、3個買う場合・・・と考えてあげると、次の表のようになります。

買う個数 範囲
1 100~105
2 200~210
3 300~315

ここからわかることは、合計金額を100で割った商をNとすれば、可能な合計金額の範囲は100N~105Nになります。

書いたコードは以下の通り。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
int x;
cin >> x;
int k = x / 100;
if(x >= 100 * k && x <= 105 * k)cout<< 1 << endl;
else cout<< 0 << endl;
return 0;
}
view raw SMBT2019c.cpp hosted with ❤ by GitHub

7.ABC095

問題:Half and Half

Aピザ、Bピザ、ABピザ(Aピザ半分、Bピザ半分)の3種類のピザがあり、AピザをX枚、BピザをY枚用意する必要がある。ABピザ2枚でAピザ1枚、Bピザ1枚に組み替えることはできる。このとき、最小でいくら必要かという問題。

私は、ABピザを買う枚数を2枚ずつ増やしていって、その中で一番値段の安かった場合を出力するようにしました。

書いたコードは以下の通り。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
#define INF 1001001001
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
ll a, b, c, x, y;
cin >> a >> b >> c >> x >> y;
ll max_pizza = max(x, y);
ll cost = INF;
for(ll i = 0; i <= max_pizza * 2; i += 2) {
int tmp_x, tmp_y;
if(x - i / 2 < 0)
tmp_x = 0;
else
tmp_x = x - i / 2;
if(y - i / 2 < 0)
tmp_y = 0;
else
tmp_y = y - i / 2;
cost = min(cost, tmp_x * a + tmp_y * b + c * i);
}
cout << cost << endl;
return 0;
}
view raw ABC095c.cpp hosted with ❤ by GitHub

8.ABC151

問題:C-Welcom to AtCoder

コンテストの問題ごとにACした数と、ペナルティ数(ACするまでに提出した数)を出力せよという問題。

提出する問題は順番通りではないので、前から順番に取っていくのはダメ。ただ、問題番号が数字なので、vectorや配列で取っていれば大した問題ではない。

各問題にACしたか？という情報と、ACするまでに何回提出したかという情報を持つpairを作成して、ACしたら提出回数をカウントストップさせれば良さそうです。

書いたコードは以下の通り。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
int n, m;
cin >> n >> m;
vector<pair<bool, int>> v;
rep(i, n) v.push_back(make_pair(false, 0));
rep(i,m){
int p;
string s;
cin >> p >> s;
if(s=="AC"){
if(v[p-1].first==false)
v[p - 1].first = true;
}
if(s=="WA"){
if(v[p-1].first==false)
v[p - 1].second++;
}
}
int ac = 0, pena = 0;
rep(i, n) {
if(v[i].first==true){
ac++;
pena += v[i].second;
}
}
cout << ac << " " << pena << endl;
return 0;
}
view raw ABC151c.cpp hosted with ❤ by GitHub

9.おわりに

pairの扱いは慣れてきました。しかし連想配列を使うのは全然経験値が足りてない。もっと練習します。

10.参考文献

ABC155解説.pdf

コメントを残す

This site uses Akismet to reduce spam. Learn how your comment data is processed.