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

Intro

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

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

・コンテストに出れない

なんとなく解けるようになってきた？のでABCとか出たいな〜と思うんですが、土曜の夜ってなんだかんだ予定ありがちでなかなか参加できていません。

もうちょっと修行してから参戦になりそうです。

・最近買った本

最近Kindleで本を買って戻ったり進んだりしながら繰り返し読んでいます。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

まだできることが少ないのですが、この本を読んでなんとなくできること、解法を吸収していこうと思っています。
でもiPhoneXRで読むと字が細かいっていう…iPadかKindleか買うべきかな…
難しい問題は難しいから飛ばせ！ってはっきり書いてくれてて親切。
スピードとか、メモリとか、あんまり考えてなかった概念が出てきて勉強になるけれど、まだまださっくり理解できるまでは届いてないっぽいです…。
引き続き空き時間に読み進めていこうと思っています！

・ABC124-A

出そびれたので。
解いていきます。

問題文
2個のボタンがあり、大きさはそれぞれ A,Bです。
大きさXのボタンを押すと、X枚のコインを獲得し、そのボタンの大きさが1小さくなります。
あなたは、いずれかのボタンを押すことを2回行います。 同じボタンを2回押しても構いません。
最大で何枚のコインを獲得できるでしょうか。

制約
入力は全て整数である。
3≤A,B≤20

入力
入力は以下の形式で標準入力から与えられる。
A B

出力
獲得できるコインの枚数の最大値を出力せよ。
― A - Buttons

まずは大きい方のボタンを押して、それをcoinとします。

   int coin = max(A,B);

そのあと、取得コインの数coinがAだったらAをへらす、
そうじゃなかったらBを減らす処理をします。

if(coin == A){
A--;
}else{
B--;
}

そしてまた大きい方を押す！

coin += max(A,B);

2回しか押さない親切設計なので、coinを出力して終了ですね…！

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
   int A,B;
   cin >> A >> B;
   
   int coin = max(A,B);
   if(coin == A){
       A--;
   }else{
       B--;
   }
   coin += max(A,B);
   
   cout << coin << endl;
   
   return 0;
}

5分ぐらいで優勝しました！
天才なのでACです。
もっといい方法があったら、ぜひTwitterやコメントで教えてください！

・ABC124-B

そのままBに行ってみます！

問題文
東西にN個の山が連なっており、西の果てには広大な海が広がっています。
各山頂には旅館があり、あなたは海を眺められる旅館を選ぶことにしました。
西からi番目の山の高さはHiです。
西から1番目の山頂にある旅館からは必ず海を眺めることができます。
西からi(i=2,3,...,N)番目の山頂にある旅館については、
H1≤Hi,H2≤Hi,...,かつ Hi−1≤Hiのとき、その旅館から海を眺めることができます。
これらN個の旅館のうち、海を眺められる旅館はいくつあるでしょうか。

制約
入力は全て整数である。
1≤N≤20　1≤Hi≤100

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

出力
海を眺められる旅館の数を出力せよ。
― B - Great Ocean View

整理します。

見える条件はi番目の山より高い山が前にないことっぽいです。
その条件を満たす旅館の数を出力することがゴールです。

まずは100個以下のN個の山があるっぽいので、
配列に山の高さをぶっこんでいきます。

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

次に、ゴールで出力することになる旅館の数はviewとします。
i番目の時点でその山が最大だったら、viewに1を足す作りで計算していきます。

int view = 0;
int max_H = 0;
int a = 0;
for(i=0;i<=N;i++){
       while(a<=i){
   max_H = max(max_H,H[a]);
          a++;
       if(max_H==H[i]){
           view++;
       }
       }
   }

入れ子で計算できてる、、、！
配列の中で最大のものを選ぶのは前回マスターしたので、応用してfor文で山の数を東に進めていくイメージです。

あとはviewを出力して優勝！

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
   int N;
   cin >> N;
   
   int H[100] = {};
   
   int n = N;
   int i = 0;
   
   while (n--){
       cin >> H[i];
       i++;
   }
   
   int view = 0;
   int max_H = 0;
   int a = 0;
   
   for(i=0;i<=N;i++){
       while(a<=i){
   max_H = max(max_H,H[a]);
          a++;
       if(max_H==H[i]){
           view++;
       }
       }
   }
   
   cout << view << endl;
   return 0;
}

いやー、天才ムーブでした。ACです。
覚えたことが蓄積してる感が見えてイイ感じです。

Cも手を出しやすいと聞いたので、このあとちょっと見てみます！！

Outro

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

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