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

2019年4月27日 22:59

Intro

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

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

・ABC125

出ましたABC125！
なんとかBまで通したので書いていきます。

・A問題

問題文
ビスケット生産装置を起動すると、起動してからA秒後、2A秒後、3A秒後、...(Aの倍数秒後)にB枚ずつビスケットを生産します。
ビスケット生産装置を起動してからT+0.5秒後までに生産されるビスケットの合計枚数を求めてください。

制約
入力は全て整数である。
1≤A,B,T≤20入力入力は以下の形式で標準入力から与えられる。
A　B　T

出力
ビスケット生産装置を起動してからT+0.5秒後までに生産されるビスケットの合計枚数を出力せよ。

見覚えのあるビスケット生産装置。
もう平成も終わりますね…（遠い目）
クッキーおばあちゃん元気かな…

ビスケットの枚数をbiscuitとおきます。
秒数iがAで割り切れるとき(Aの倍数のとき)
biscuitがB枚製造されます。

   for(int i=1;i<=T;i++){
       if(i%A==0){
           biscuit = biscuit+B;
       }

0.5秒後というのはA=3なら、3,6,9秒ジャストで製造してから終わる、という条件なだけな気がしました。

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
   int A,B,T;
   cin >> A >> B >> T;
   
   int biscuit = 0;
   
   for(int i=1;i<=T;i++){
       if(i%A==0){
           biscuit = biscuit+B;
       }
   }
   cout << biscuit << endl;
   
return 0;
}

とりあえず優勝です！ビスケット食べたい〜！

・B問題

問題文
N個の宝石があり、i番目の宝石の価値はViです。
あなたはこれらの宝石の中からいくつかを選んで手に入れます。
このとき、1つも選ばなくとも、全て選んでも構いません。
ただし、i番目の宝石を手に入れる場合コストCiを支払わなければいけません。
手に入れた宝石の価値の合計をX、支払ったコストの合計をYとします。
X−Yの最大値を求めてください。

制約
入力は全て整数である。
1≤N≤20
1≤Ci,Vi≤50

入力
入力は以下の形式で標準入力から与えられる。
N
V1V2...VN
C1C2...CN

出力
X−Yの最大値を出力せよ。

転売できる宝石を選べばいいっぽいですね、良い商売・・・。

ゴールを整理します。
まず、i番目の宝石について、V[i]-C[i]=転売したときの利益＝コスパを
cp[i]とします。

cp[i]が0以上の宝石だけを全部とれば、それが最大利益＝求められている最大値になりそうです。

for(int i=0;i<=N;i++){
       cp[i] = V[i] - C[i];
       
   }

何も考えずに配列にcpをぶっこみましたが、今考えるとそのまま足してもよかった…。

 int ans = 0;
   for(int i=0;i<=N;i++){
       if(cp[i]>=0){
           ans = ans+cp[i];
       }
   }
       cout << ans << endl;

0以上なら出力用に用意したansに足していきます。
出力して優勝です。天才！！！！！！！！！！！！！！！

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
   int N;
   cin >> N;
   int V[100] = {};
   
   for(int i=0;i<N;i++){
       cin >> V[i];
   }
   
    int C[100] = {};
   int i = 0;
   for(i=0;i<=N;i++){
       cin >> C[i];
   }
   
   int cp[50];
   
   for(int i=0;i<=N;i++){
       cp[i] = V[i] - C[i];
       
   }
   
   int ans = 0;
   for(int i=0;i<=N;i++){
       if(cp[i]>=0){
           ans = ans+cp[i];
       }
   }
       cout << ans << endl;
          return 0;
}

C問題も頑張って考えたんですが全く歯が立たなかったのでまた後日。
数学力の欠如を感じる…。

・嘘解法で通した

前回解いた問題が嘘解法によるものだとご指摘いただき修正しました。

嘘解法で通した、競プロerっぽくなってきたワード第1位
— マリー (@CBOX360) April 25, 2019

敗北を知りたいとか言ってたら普通に敗北してた…。
でも通っちゃってるので嘘じゃない解法によるものだということの証明はできず
何が正しい答えなんだ…と1日悩みました（哲学ギャル）

わかりやすい反例を使って検証しました。
まだ嘘だったら教えてください。
嘘じゃない解法って何かの答えもぜひ教えてください。

前回の記事です。→#16

   int ans1 = 0;
   int ans2 = 0;
       for(int i=0;i<size;i++){
           if(S[i]!=trueans[i]){
               ans1++;
           }
           if(S[i]!=trueans[i+1]){
               ans2++;
           }
       }
   cout << min(ans1,ans2) << endl;
   return 0;
}

この部分を修正しました。
0から始まるか、1から始まるかだけを判定して並べ直していたものを、
最小値を取るように修正してみました。

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
   string S;
   cin >> S;
   
   size_t size = S.size();
   
   //01をいっぱい作る
   string trueans = "01";
   for(int i=0;i<size;i++){
       trueans = trueans+"01";
   }
   int ans1 = 0;
   int ans2 = 0;
       for(int i=0;i<size;i++){
           if(S[i]!=trueans[i]){
               ans1++;
           }
           if(S[i]!=trueans[i+1]){
               ans2++;
           }
       }
   cout << min(ans1,ans2) << endl;
   return 0;
}

1101010など…頭だけ変えれば良いものに適応してなかったのが、
これで大丈夫なはずです。
間違いに気づいて直す、これぞ天才！優勝！！

Outro

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

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

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