スクリーンショット_2019-04-04_23

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

Intro


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

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

・ABC088B - 3秒で習得するソート講座


引き続きAtCoder Beginners Selectionの問題を解いていきます。

問題文
N枚のカードがあります.
i枚目のカードには, aiという数が書かれています.
AliceBob は, これらのカードを使ってゲームを行います.
ゲームでは, Alice と Bob が交互に1枚ずつカードを取っていきます.
Alice が先にカードを取ります.
2人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります.
2人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

制約
Nは1以上100以下の整数
ai(1≤i≤N)は1以上100以下の整数

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

出力
両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.
― ABC088B - Card Game for Two

アリス勝確ゲーすぎて、ボブはいったいアリスの何なんでしょうか。
下僕?

というわけで問題を整理していきます。
"戦略的に"カードを選ぶということは、
AliceとBobは大きい順から1枚ずつカードがなくなるまで引くということと考えられます。
Aliceの得点Bobの得点を求めれば、最後に引いて出力してゴールです。

具体的な手順は、
与えられた数を配列にぶっこみ
大きい順に並べたときに
偶数番目にあるカードをAliceが、
奇数番目にあるカードをBobが取ります。
Aliceの得点からBobの得点を引いて出力します。

①はいつもどおりでいけそうです。

   int N;
   cin >> N;
   
   int a[100] = {};
   int n = N;
   
   int i = 0;
   while(n--){
       cin >> a[i];
       i++;
   }

そして
ん?
これは?
ソートする必要があるぞ?

初めて概念が出てきました。
配列にぶっこみ、中身をソートをする必要があります。
はいここで天の声を仰いでみたいと思います。

師「sortってやつを使おう」

便利なものがあるらしいので、使ってみたいと思います。

sort(a,a+100,greater<int>());

とかくと、大きい順に並ぶようです、

sort(a,a+100);

とすれば、小さい順に並ぶようです!
便利!!!!!!!!
簡易的全選択して並べ替えてそうな気がします。

一旦出力してみても並び替わってそうなので、次の段階に行きます。
③④はif文でよさそうです。

int Alice = 0;
   int Bob = 0;
   
   n = N;
   i = 0;
   while(n--){
       if(i % 2 == 0){
           Alice = a[i]+Alice;
       }else{
           Bob = a[i]+Bob;
       }
       i++;
   }


0から始まっているから、0,2,4,6と2で割り切れる数Alice
1,3,5,7,と2で割り切れない数Bobが取っていきます。

あとは⑤、差を出力して優勝です。

cout << Alice-Bob << endl;

おっけ〜〜〜〜〜〜〜〜☆

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
   int N;
   cin >> N;
   
   int a[100] = {};
   int n = N;
   
   int i = 0;
   while(n--){
       cin >> a[i];
       i++;
   }
   
   sort(a,a+100,greater<int>());
   
   int Alice = 0;
   int Bob = 0;
   
   n = N;
   i = 0;
   while(n--){
       if(i % 2 == 0){
           Alice = a[i]+Alice;
       }else{
           Bob = a[i]+Bob;
       }
       i++;
   }
               cout << Alice-Bob << endl;
   return 0;
}

天才なのでまたもや優勝してしまいました。
天の声、感謝〜〜!

次に行きましょう。

・ABC085B - なんとなくわかるイテレータ講座

問題文
X段重ねの鏡餅(X≥1)とはX枚の円形の積み重ねたものであって、
どの餅もその真下の餅より直径が小さい(一番下の餅を除く)もののことです。
例えば、直径10、8、6センチメートルの餅をこの順に下から積み重ねると
3段重ねの鏡餅になり、餅を一枚だけ置くと1段重ねの鏡餅になります。
ダックスフンドのルンルンはN枚の円形の餅を持っていて、
そのうちi枚目の餅の直径はdiセンチメートルです。
これらの餅のうち一部または全部を使って鏡餅を作るとき、
最大で何段重ねの鏡餅を作ることができるでしょうか
制約
1≤N≤100
1≤di≤100
入力値はすべて整数である。

入力
入力は以下の形式で標準入力から与えられる。
N
d1
:
dN

出力
作ることのできる鏡餅の最大の段数を出力せよ。
― ABC085B - Kagami Mochi

ルンルン餅もっててワロタw
整理していきます。
ルンルンが持っているお餅のうち、重複しないものを重ねて何段重ねになるかを出力するのがゴールのようです。

ん?
これは?(2回め)
重複の削除がいるぞ???

天の声〜〜〜〜〜!(2回め)

天の声によるよく分かるイテレータ講座はそのうち夫が書いてくれるとして、
こういう作業をイメージしました。

vectorで配列にぶっこみ、
sortで並べ替えたあと、uniqueで重複を削除して前に詰め、
その後eraseでゴミを削除して、
vector内の要素の数がお餅の数と考えます。

始めて使います、vector

   int N;
   cin >> N;
   
   vector<int> d(N);
   int i = 0;
   int n = N;
   while(n--){
       cin >> d[i];
       i++;
   }

ぶっこむところまではいつもどおり。

   sort(d.begin(),d.end());


今回は始め終わりを指定してソートします。

   d.erase( unique(d.begin(),d.end()), d.end());


uniqueというのは隣り合った同じ値を消して詰めてくれるみたいです。
そして、eraseで詰めてもらった新しい終わりから、もとの終わりまでを(ゴミを)消します。

残ったのは一意の値のはずなので、
その要素の数が鏡餅の数のはず〜〜!

     cout<<d.size()<<endl;


出力して優勝です。
これが天才です。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
   int N;
   cin >> N;
   
   vector<int> d(N);
   int i = 0;
   int n = N;
   while(n--){
       cin >> d[i];
       i++;
   }
   
   sort(d.begin(),d.end());
   d.erase( unique(d.begin(),d.end()), d.end());
       cout<<d.size()<<endl;
   return 0;
}

今回は天の声スペシャルということで乱用しましたが、
よく使いそうなことシンプルにこなす方法を教えてもらいました!
これを生かしてまた次回からは自力優勝を狙いたいと思います。

Outro


#12に続く!(不定期連載です。)
これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。

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