ABC127 初心者備忘録

問題A
問題B
問題C
問題D(未回答)
まとめ

A - Ferris Wheel



using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  if (a >= 13)
    cout << b << endl;
  else if (a <= 12 && a >= 6)
    cout << b / 2 << endl;
  else
    cout << 0 << endl;
}

普通の条件分岐です。これ以上語ることがないですね……正直A問題って毎回何を語るのか困るので次からカットしたいと思います。楽をしていく。

B - Algae



using namespace std;

int main() {
　 int r, d, x;
　 cin >> r >> d >> x;
　 for (int i = 1; i <= 10; i++) { 
     x=r * x - d; cout << x << endl;
   } 
 return 0;
}

xにrx-Dを代入、それを表示する感じです。次に代入する時は一つ前のxが残ってるので結果的に問題文の式
x[i+1]=r*x[i]-D
になります。ちなみにiに入る数値は2001~2010となってますがぶっちゃけ1~10でも変わりません。
N^3したら計算量に関わってきそうな大きい数字が出ても焦らないように注意……私は焦りました。

C - Prison


  using namespace std;

  int main() {
  int N, M;
  cin >> N >> M;
  int L[M], R[M];
  for (int i = 0; i < M; i++) { cin>> L[i] >> R[i];
    }

  int Lmax = 0, Rmin = N;
  for (int i = 0; i < M; i++) { 
      if (L[i]> Lmax) Lmax = L[i];
      if (R[i] < Rmin) Rmin=R[i]; 
      if(Lmax> Rmin){
        cout << 0 << endl; return 0; 
      } 
   } 


  if (N < Rmin - Lmax + 1) { 
      cout << N << endl; 
    } else if (N>= Rmin - Lmax + 1) {
          cout << (Rmin - Lmax + 1) << endl;
    } 

  return 0; 
 }

要はIDカードの数字が、L（左側)の一番大きい数字からR(右側)の一番小さい数字の間なら通り抜けられます。
それらを求め、引き算でその間に幾つの数字があるかを調べます。ただし右側が左側より小さい数字になったら通り抜けられないので0を表示。
後はNより範囲が多かったらN枚フルに使える、N枚フルに使えないなら範囲の分だけが枚数に、という条件分岐です。

D - Integer Cards


  bool compare_by_b(pair<int, long> b, pair<int, long> c) {
      if(b.second != c.second){
            return c.second < b.second;
      }else{
        return c.first < b.first;
      }
  }

  int main(){
     int N,M; cin>> N >> M;
     vector A(N);
     vector <pair<int,long> > card(M);
     int count =0;
     long answer=0;

     for(int i=0;i<N;i++) {
       cin>> A[i];
      }

     for(int i=0;i<M;i++) {
       int b,c;
       cin>> b >> c;
       card[i] = make_pair(b,c);
    }

     sort(A.begin(),A.end());
     sort(card.begin(),card.end(),compare_by_b);

     for(int i=0;i<N;i++) {
       if(A[i]>= card[count].second || count > M) break;


     if(card[count].first != 0){
        A[i] = card[count].second;
        card[count].first--;
     }else{
        count++;
        A[i] = card[count].second;
        }
     }

     for(int i=0;i<N;i++) 
       answer +=A[i];
     }

     cout << answer << endl;
   }

通ったのは12ケース、つまりACではありません
Aのもっとも小さい数を、Cの最大の整数と置き換える貪欲法です。
簡単に言うとN枚のAと入れ替え用のカードがあり、Aのカードを小さい順、入れ替えカードを大きい順にソートします。
そして、前から順番に見比べAのカードより入れ替え用カードが大きかったら。Aのカードが入れ替えカードの数になります。
ある場所でAの数字が入れ替えカードの数字以上になったら、予めソートしている為以降もそうなります。なので、ループ脱出です。
……とまあこんな感じの考え方だったのですが、8ケース落としました。正直初めてD問題クリアできると思ったのでかなり悔しいです。
しかし12ケース通るということは多分筋道は合っているはずなので、後は見落としてたり考え不足の部分ですね。頑張ります！

まとめ

今回で確信したのですが、もうC問題まではほぼ解けるといってもいいでしょう。しかし、D問題以降はもう別世界です。
大体のD問題は優先探索系、コンテナ、グラフ等本格的にアルゴリズム特有の知識が必要になっていきます。とりあえずアルゴリズムの項目があるので応用情報の本を読んでみたのですが~~未だに人月という全く役に立たない単位を採用してるだけあってやはりレベルが低~~競技プログラミングの敷居は少々高いのか全く載ってませんでしたね、というわけで図書館で借りてきました、有名な蟻本をもう一回読んでみます。
はい、難しいです。いや正直今なら全てが理解できるはずという謎の自信をもって挑んだのですがすごいです……密度が濃くて……。
ですが、競技プログラミング本が少ないことや一般的なアルゴリズム本で書かれている内容が初級であること、それに問題の豊富さを考えると初心者向けではありませんが間違いなく名著です。このブログにアフィリエイト機能がついてたら多分貼り付けてました。買いたい方は「蟻本」でググってください。
というわけで、しばらくは螺旋本かチーター本を買って再び勉強です。……おかしいな、今月分の学費の支払いを終えると残金-40k……？
……………………………………なんとかします！！！！

usam44’s blog

■

ABC127 初心者備忘録

A - Ferris Wheel

B - Algae

C - Prison

D - Integer Cards

まとめ