AtCoder M-SOLUTIONS プロコンオープン 2020 反省会 [A,B,C,D完][C++]

久しぶりの参戦。

A

#include <bits/stdc++.h>
using namespace std;

int main(){
  int x;cin>>x;
  if(x<600)cout<<8<<endl;
  else if(x<800)cout<<7<<endl;
  else if(x<1000)cout<<6<<endl;
  else if(x<1200)cout<<5<<endl;
  else if(x<1400)cout<<4<<endl;
  else if(x<1600)cout<<3<<endl;
  else if(x<1800)cout<<2<<endl;
  else cout<<1<<endl;
}

そのまま。

B

#include <bits/stdc++.h>
using namespace std;

int main(){
  int A,B,C,K;cin>>A>>B>>C>>K;

  while(K--){
    if(A>=B)B *= 2;
    else if(B>=C)C *= 2;
  }

  cout<<( (A<B && B<C) ? "Yes" : "No")<<endl;
}

目標は $A < B < C$ なので、そうなるように $K$ 回の間倍々にしていく。

最後の最後で、$A < B < C$ が完成していたらOK！！

C

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

int main(){
  int N,K;cin>>N>>K;
  vi A(N);
  rep(i,N)cin>>A[i];

  for(int i=K; i<N; i++){
    cout<<(A[i-K]<A[i] ? "Yes" : "No")<<endl;
  }
}

評点比較は例1を使うと

$$ \{96, 98, 95, 100, 20\} $$

については

$96\times98\times95$ と $98\times95\times100$ の比較 → $96$ と $100$ の比較

$98\times95\times100$ と $95\times100\times20$ の比較 → $98$ と $20$ の比較

という風に単純化できる。あとはfor文のiとか添字に気をつけて順次判定していく。

D

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define rep(i, n) for(int i=0; i<(int)n; i++)

int main(){
  int N;cin>>N;
  vi A(N);
  rep(i,N)cin>>A[i];
  A.push_back(0);

  ll money = 1000;

  vi list;
  for(int i=0; i<N; i++){
    list.push_back(A[i]); //今日の株価を区域に追加

    if(A[i] <= A[i+1]){
      //明日上がる
      ; //なにもしない
    }else{
      //明日下がる
      ll buy = money / list.front();
      money -= buy * list.front();
      money += buy * list.back();
      list.clear();
    }
  }

  cout<<money<<endl;
}

中心の考え方は、株価が上昇（等価含む）していく区域を見つけて、その初日で最大限買って最終日で最大限売る。これでマックスの利益が出る。

区域をlistで作ってゆき、翌日も株価が上がるならなにもしない。翌日に株価が下がるならその日が「区域」の終わりなので売買を（過去に遡って）やる。そして区域のリセットをする。

入力例1

$$ A = \{ 100, 130, 130, 130, 115, 115, 150 \} $$

区域 $\{100, 130, 130, 130 \}$ まで見て、100円で買い130円で売る処理をする

区域 $\{ 115, 115, 150 \}$ を見て、115円で買い150円で売る処理をする

なお、入力例1のように上昇したまま最終日を迎えると、「売買しなきゃいけないのに『翌日』がない」となり売買し損ねるため、「最終日」の後ろに株価が0円の日を付け加えておく。こうすると、

$$ \cdots 200, 100, 150, 0 $$

のときは最終日にlist = {100, 150}、「明日下がる」条件なので100円で買って150円で売る。

$$ \cdots 200, 150, 100, 0 $$

のときは最終日にlist = {100}、「明日下がる」条件なので100円で買って100円で売る（実質何もしない）。

ちなみに、株価が下がり続けているときは、上記のようにlistに1つだけ（その日の）株価が入るので「実質何もしない」状態になる。

最初、int型でやってたらWAが出たんでlong longにしたらACなった。80日間あって $100 \le 株価 \le 200$ なので、株価が $100, 200, 100, 200, \cdots$ となる所持金が2倍になる$\times$40回で $2^{40} \times 1000 = 1099511627776 \times 1000 \approx 10^{15}$ まで膨れ上がるんですね。