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

2019年6月9日 23:52

Intro

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

・ABC129A

お久しぶりです！！！！！
今回も出れましたABC！！！
しっかりといていきます！！！！！

問題文
空港 A, B, C があり、それぞれの空港の間では、双方向に飛行機が運航しています。
空港 A, B 間の飛行時間は片道P時間、空港 B, C 間の飛行時間は片道Q時間、空港 C, A 間の飛行時間は片道R時間です。
いずれかの空港からスタートして他の空港に飛行機で移動し、さらにそのどちらでもない空港に飛行機で移動するような経路を考えます。
飛行時間の和は最短で何時間になるでしょうか。

制約
1≤P,Q,R≤100
入力は全て整数である

入力
入力は以下の形式で標準入力から与えられる。
P　Q　R

出力
飛行時間の和の最小値を出力せよ。
A - Airplane

P+Q、Q+R、P+Rのうち一番短いやつになればいいとおもったよ！

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
   int P,Q,R;
   cin >> P >> Q >> R;
   
   int A=0,B=0,C=0;
   A = P+Q;
   B = Q+R;
   C = P+R;
   
   int ans = 0;
   ans = min({A,B,C});
   
   cout << ans << endl;
   return 0;
}

もっといい方法あったかなと思いつつ
｛｝でくくると3つ以上でも比較できることを思い出して優勝っ！

{←これのこと「ぴょろ」って呼んでる
— マリー (@CBOX360) May 27, 2019

・ABC129B

問題文
1からNの番号がついたN個の重りがあり、番号iの重りの重さはWiです。
ある整数1≤T<Nに対してこれらの重りを、番号がT以下の重りと番号がTより大きい重りの2グループに分けることを考え、それぞれのグループの重さの和をS1,S2とします。
このような分け方全てを考えた時、S1とS2の差の絶対値の最小値を求めてください。

制約
2≤N≤100
1≤Wi≤100
入力は全て整数である

入力
入力は以下の形式で標準入力から与えられる。
N
W1 W2...WN−1 WN
出力
S1とS2の差の絶対値の最小値を出力せよ。
B - Balance

問題を整理します。

S1とS2の境目を動かしつつ、S1とS2の差の絶対値が少なくなるパターンをさがします。

入力からもってくるついでに、全部足したやつallをもっておきます。


   int N;
   cin >> N;
   
   int S1[100],S2[100],ans[100],all=0;
   
   int W[100] = {};
   for(int i=1;i<=N;i++){
       cin >> W[i];
       all += W[i];
   }

1番目からN番目ということでワケわからなくなりそうなので、
S1[0]は無視して1番目から考えることにします！！！！！！！！
（いつもここでつまづく）

   S1[0] = 0;

まず1番目からi番目(境目）まで全部足します。
それから、allからS1を引いたらS2なので、答えになる差の絶対値をans[i]に入れます！！！

   for(int i=1;i<=N;i++){
       S1[i]= S1[i-1] + W[i];
       S2[i]= all - S1[i];
       ans[i] = abs(S1[i]-S2[i]);
   }

あとはansのなかで一番小さいのを探す！
そして出力すると自動で優勝します。

   int MIN = 2147483647;
   for(int i=1;i<=N;i++){
       MIN = min(MIN,ans[i]);
   }
   cout << MIN << endl;

はい！！！！！！！！！！！！！！！！！！！！！！
天才！！！！！！！！！！！！！！


#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
   int N;
   cin >> N;
   
   int S1[100],S2[100],ans[100],all=0;
   
   int W[100] = {};
   for(int i=1;i<=N;i++){
       cin >> W[i];
       all += W[i];
   }
   
   S1[0] = 0;
   
   for(int i=1;i<=N;i++){
       S1[i]= S1[i-1] + W[i];
       S2[i]= all - S1[i];
       ans[i] = abs(S1[i]-S2[i]);
   }
   
   int MIN = 2147483647;
   for(int i=1;i<=N;i++){
       MIN = min(MIN,ans[i]);
   }
   cout << MIN << endl;
   
   return 0;
}

C問題解けなくて悲しみだったんですが、、、
終了後天の声を召喚して教えてもらったので、近いうちまた整理して書こうと思います！（忘れちゃうから）

とりあえずB問題までは解けそうなんだけどなあ。
最近忙しくて勉強時間が取れていなかったのもあるので、復習します。。。

Outro

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

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