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

2019年5月16日 21:35

Intro

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

・ABC095B

けんちょんさんの記事に戻りつつ埋めていたりします。
最近色々と忙しくてなかなか優勝する時間が取れない、、、
忘れる前にガンガン解いていきたいと思います！！！！

問題文
パティシエの赤木さんは、「お菓子の素」という粉のみを材料としてN種類のドーナツを作ることができます。
これらのドーナツはドーナツ1、ドーナツ2、...、ドーナツNと呼ばれます。
ドーナツi(1≤i≤N)を1個作るには、お菓子の素miグラムを消費する必要があります。
なお、0.5個など整数でない個数のドーナツを作ることはできません。
いま、赤木さんはお菓子の素をXグラム持っています。
これを使って、今夜のパーティーに向けて可能な限りたくさんのドーナツを作ることにしました。
ただし、来客の味の好みは様々なので、次の条件を守ることにしました。
N種類のドーナツそれぞれを少なくとも1個は作る。
このとき、最大で何個のドーナツを作ることができるでしょうか？
お菓子の素を使い切る必要はありません。
また、この問題の制約のもとでは、条件を守ることは必ず可能です。

制約
2≤N≤100
1≤mi≤1000
m1+m2+...+mN≤X≤10^5
入力中のすべての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X
m1
m2
:
mN

出力
条件を守って作ることのできるドーナツの最大の個数を出力せよ。

B - Bitter Alchemy

ドーナツ食べたい…
しかもめっちゃ種類作ってくれるとかミスドかよ。優勝でしょ。

問題を整理します。
N種類のドーナツをそれぞれ少なくとも1個は作れることが保証されてる中で、個数を最大にしたいということは、
N種類のドーナツを作った上で、まだ余ったお菓子の素を使って素を使う量が一番少ないドーナツを量産するのが最善です。

必要な素の量を、motoとおきます。

   int N,X;
   cin >> N >> X;
   int m[100] = {};
   int moto = 0;
   
   for(int i=0;i<N;i++){
       cin >> m[i];
       moto = moto+m[i];
   }

レシピm[i]をしまうついでに、N種類のドーナツをつくったときの素の量も取ってみます。

ドーナツのレシピを並び替えて…

   sort(m,m+N);

N個つくる＋持ってる素からmotoを引いたものから、一番少ないm[0]のレシピで量産するので割ります。

   cout << N+((X-moto)/m[0]) << endl;

あっさり優勝〜〜〜〜！

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
   int N,X;
   cin >> N >> X;
   int m[100] = {};
   int moto = 0;
   
   for(int i=0;i<N;i++){
       cin >> m[i];
       moto = moto+m[i];
   }
   
   sort(m,m+N);
   
   cout << N+((X-moto)/m[0]) << endl;
   
       return 0;
}

B問題はさっくり思いつく場合が多くなってきました。
これが天才の成長力であり優勝力です。（天才）

ドーナツネタでもう一本。

・ABC105B

問題文
ABC洋菓子店では,1個4ドルのケーキと1個7ドルのドーナツが売られている.
このとき, 合計金額がNドルとなる買い方はあるか, 判定せよ.
ただし, 同じ商品を二個以上買っても良く, 買わない商品があっても良いものとする.

制約
Nは1以上100以下の整数

入力
入力は以下の形式で標準入力から与えられる.
N

出力
合計がNドルとなる買い方がある場合 Yes,
そうでない場合 No と出力せよ.

B - Cakes and Donuts

今度は買います。
ケーキが4ドルは割とお買い得だけど、7ドルのドーナツ何個入りなんだろ…（どうでもいい疑問）

ケーキの個数をx,ドーナツの個数をyとおいて、条件満たしたら1にするyesを作ります。


   int N;
   cin >> N;
   int x = 0;
   int y = 0;
   int yes = 0;

あとはたかだか2重なのでイケると踏んで、
for文でぶん回します！

   for(x=0;x<N;x++){
       for(y=0;y<N;y++){
       if((x*4)+(y*7)==N){
           yes = 1;
           break;
           }
       }

yesが１だったらYes,そうでなかったらNoを出力して優勝です。


   if(yes == 1){
       cout << "Yes" << endl;
   }else{
       cout << "No" << endl;
   }
       return 0;
}

はい〜〜〜〜完全☆勝利〜〜優勝！！！


#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
   int N;
   cin >> N;
   int x = 0;
   int y = 0;
   int yes = 0;
   for(x=0;x<N;x++){
       for(y=0;y<N;y++){
       if((x*4)+(y*7)==N){
           yes = 1;
           break;
           }
       }
   }
   if(yes == 1){
       cout << "Yes" << endl;
   }else{
       cout << "No" << endl;
   }
       return 0;
}

さっくり解けました！！！
更新頻度が最初の頃より下がるとは思いますが、
合間合間に優勝していきますのでよろしくおねがいします！！！

Twitterは元気に更新中ですので、便利なテクニックからクソリプまでバンバンお待ちしております！
（競プロリストも結構眺めてるよ！）

計算量落とすの下手っぽいな、移項ってきいたことあるよ
— マリー (@CBOX360) May 12, 2019

↑TLEへの恐怖に怯えるわたしです

Outro

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

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

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