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

2019年4月20日 00:20

Intro

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

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

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

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

問題文
N枚のカードがあります.
i枚目のカードには, aiという数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います.
ゲームでは, 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

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

ん？
これは？（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に続く！(不定期連載です。)
これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。