文系ギャルが0から始める競技プログラミング#27

マリー

2019年5月26日 01:00

Intro

この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0

↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#26

・コンテスト出ました

ひっさしぶりーーーにちゃんと机に向かってコンテストです！
今日はタピオカも用意して準備万端。
本番ではBまでしか通せませんでしたが、、、
順番にといていくよ！

・ABC127A

問題文
A歳の高橋君が観覧車に乗ろうとしています。
この観覧車は、13歳以上が乗るにはB円 (Bは偶数) かかりますが、6歳以上12歳以下の人はその半額で乗ることができ、さらに5歳以下の人は無料で乗ることができます。
高橋君が観覧車に乗るには何円かかるかを求めてください。

制約
0≤A≤100
2≤B≤1000
Bは偶数

入力
入力は以下の形式で標準入力から与えられる。
A
B

出力
高橋君が観覧車に乗るには何円かかるかを出力せよ。
A - Ferris Wheel

100歳になっても観覧車に乗る高橋君すてきやんけ！！
これはまあ高橋くんの年齢で切り分けたらいいだけですね、優勝！

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
   int A,B;
   cin >> A >> B;
   if(A<13){
       if(6<=A){
           cout << B/2 << endl;
       }else{
           cout << 0 << endl;
       }
   }else{
       cout << B << endl;
   }
   
   return 0;
}

13歳未満だったら、6歳以上だったら、その他でB円、B/2円、0円を出力して優勝です。
3：37で提出〜〜！

・ABC127B

さくさくいくぞ〜〜〜！

問題文
ある池に生えている藻類は、以下のように成長します。
西暦i年になる瞬間に生えている重さの合計をxiグラムとすると、i≥2000に対して、以下の式が成り立ちます:xi+1=rxi−D
r,D,x2000が与えられます。
x2001, ...,x2010を計算し、順に出力してください。

制約
2≤r≤5
1≤D≤100
D<x2000≤200
入力はすべて整数

入力
入力は以下の形式で標準入力から与えられる。
r　D　x2000

出力
10行出力せよ。
i行目 (1≤i≤10) にはx2000+iを整数で出力せよ。
B - Algae

与えられたのが2000に対して、2001から出力すればいいのでシンプルな気がします。
xを都度更新しつつ出力します！

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
   int r,D,x;
   cin >> r >> D >> x;
for(int i=0;i<10;i++){
       cout << r*x-D << endl;
       x = r*x-D;
   }
   return 0;
}

これは問題文が分かりづらいような気がしたのだけど、ちゃんと読んだらもう思いつきました。（天才）
6:50で優勝！

C問題は何言ってるかさっぱりわからず飛ばしてしまい…
Dがあと少しのところで詰まったので、書き直していきたいと思います！

・ABC127D

問題文
N枚のカードがあり、i番目のカードには整数Aiが書かれています。
あなたは、j=1,2,...,Mについて順に以下の操作を1回ずつ行います。
操作:カードをBj枚まで選ぶ(0枚でもよい)。選んだカードに書かれている整数をそれぞれCjに書き換える。
M回の操作終了後にN枚のカードに書かれた整数の合計の最大値を求めてください。

制約
入力は全て整数である。
1≤N≤10^5
1≤M≤10^5
1≤Ai,Ci≤10^9
1≤Bi≤N

入力
入力は以下の形式で標準入力から与えられる。
N M
A1 A2...AN
B1 C1
B2 C2
⋮
BM CM

出力
M回の操作終了後にN枚のカードに書かれた整数の合計の最大値を出力せよ。
D - Integer Cards

本番中は結局解けずでしたが、多分あと一歩なので頑張ってときます！

   int N,M;
   cin >> N >> M;
   
   int A[100000] = {};
   for(int i=0;i<N;i++){
       cin >> A[i];
   }
   sort(A,A+N);

Aまでをじゃらじゃらっと持ってきつつ、並び替えます。
BとCはセットで扱いたいのでpairで！！！

vector<pair<int,int>> BC(M);
   for(int i=0;i<M;i++){
       cin >> BC[i].second >> BC[i].first;
}

Cをキーにソートしたいので、逆に入れます。

   sort(BC.begin(),BC.end(),greater<pair<int,int>>());

これでBとCは、Cが大きい順に並んでくれたのであとは書き換えていきます。
書き換える数Cに対して、Bは書き換え可能な残り回数と捉えて処理を進めていこうと思います（天才ムーブ）
（そう…ここまでは…ここまではよかったんだ………………）

   int j = 0;
   for(int i = 0;i<M;i++){
       int nokori = BC[i].second;
       while(nokori > 0){
           if(A[j]<BC[i].first){
               A[j] = BC[i].first;
               j++;
               nokori--;
           }else{
               break;
           }
       }
   }

書き換え可能な残り回数＝Bのi番目＝nokoriとします。
nokoriが0になるまでぐるぐると書き換えたほうがいいかを判定します。

書き換えたほうがよさそうなら（AよりCのほうが大きかったら）書き換えて、そうじゃなければ昇順に並べ替えてるので次のカードに行っちゃっていいって算段です。
天才じゃん！！！！

ん？？

ん？？？？

提出 #5620000 - AtCoder Beginner Contest 127 https://t.co/eGxTsWCHxQ

うっ…
— マリー (@CBOX360) May 25, 2019

もうダメだ……助けてツイッターランド…と激凹みのところ救世主カツサンドくんが登場します。

jがN以上になるとA[j]が範囲外参照になるのでそこかと思います(僕もやりました)
— カツサンドくん (@IKyopro) May 25, 2019

nokoriの回数分jを足してるので、nokoriがN以上になると配列ぶっぱしちゃうんですね。。。

   int j = 0;
   for(int i = 0;i<M;i++){
       int nokori = BC[i].second;
       while(nokori > 0){
           if(A[j]<BC[i].first){
               A[j] = BC[i].first;
               j++;
               nokori--;
               if(j>=N){
                   goto out;
               }
           }else{
               break;
           }
       }
   }
out:

もしjがN以上になっちゃったら、そもそもループから飛び出しちゃうことにしました。

   long long ans = 0;
   for(int i=0;i<N;i++){
       ans += A[i];
   }
   cout << ans << endl;
   
   return 0;
}

あとは1つずつ足していくだけ。優勝です！！！！！

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
   int N,M;
   cin >> N >> M;
   
   int A[100000] = {};
   for(int i=0;i<N;i++){
       cin >> A[i];
   }
   sort(A,A+N);
   
   vector<pair<int,int>> BC(M);
   for(int i=0;i<M;i++){
       cin >> BC[i].second >> BC[i].first;
   }
   sort(BC.begin(),BC.end(),greater<pair<int,int>>());
   
   int j = 0;
   for(int i = 0;i<M;i++){
       int nokori = BC[i].second;
       while(nokori > 0){
           if(A[j]<BC[i].first){
               A[j] = BC[i].first;
               j++;
               nokori--;
               if(j>=N){
                   goto out;
               }
           }else{
               break;
           }
       }
   }
out:
   long long ans = 0;
   for(int i=0;i<N;i++){
       ans += A[i];
   }
   cout << ans << endl;
   
   return 0;
}

優勝〜〜〜〜〜〜〜〜〜〜〜本番中に通したかったぞ〜〜〜〜〜〜
着眼点がよかったので優勝は優勝です。天才なので。

明日もあるので頑張っていきたいと思います！
今日でratedコンテスト3回目なので、もうちょっとでリセマラ規制抜けられる〜〜

Outro

#28に続く！(不定期連載です。)

これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。

この記事が気に入ったらサポートをしてみませんか？