AtCoderチャレンジまとめ（２） - AtCoder Beginner Contest 116

やりたいこと

C++に慣れつつアルゴリズムの知識を上げたい。

そんなわけでAtCoderにチャレンジ ！

チェレンジコンテスト

AtCoder Beginner Contest 116 - AtCoder

変数名適当でごめんなさい。。。初めてのAtCoder。

問題A : Right Triangle

直角三角形 ABC があります。∠ABC=90°

です。

三角形 ABC の三辺の長さである |AB|,|BC|,|CA| が与えられるので、直角三角形 ABC

の面積を求めて下さい。

ただし、三角形 ABC の面積は整数となることが保証されています。

自分の回答

    #include<iostream>
    using namespace std;
     
    int main(){
      int a,b,c;
      cin>>a>>b>>c;
      int ans;
      ans = a*b/2;
      cout << ans << endl;
      
      return 0;
    }

問題B : Collatz Problem

数列 a={a1,a2,a3,......}

は、以下のようにして定まります。

初項 s

は入力で与えられる。

関数 f(n) を以下のように定める: n が偶数なら f(n)=n/2、n が奇数なら f(n)=3n+1。

i=1のとき ai=s、i>1 のとき ai=f(ai−1)である。

このとき、次の条件を満たす最小の整数 m

を求めてください。

am=an(m>n)

を満たす整数 n が存在する。

自分の回答

        #include<iostream>
        #include <set>
         
        using namespace std;
         
        int main(){
          int a;
          cin>>a;
          
          set<int> values;
          int ans = a;
          
          for(int i=0; i < 100000000; ++i){
            values.insert(ans);
            if(ans%2==0){
              ans = ans / 2;
            }else{
              ans = 3 * ans + 1;
            }
            if (values.size()!=i+1){
              break;
            }
          }
          cout << values.size() + 1 << endl;
          return 0;
        }

先生の回答

            #include<iostream>
            #include <set>
             
            using namespace std;
             
            int main(){
              int a;
              cin>>a;
              
              set<int> values;
              int ans = a;
              
              while(values.count(ans) == 0){
                values.insert(ans);
                if(ans%2==0){
                  ans = ans / 2;
                }else{
                  ans = 3 * ans + 1;
                }
              }
              cout << values.size() + 1 << endl;
              return 0;
            }

• setのcountを使って重複があるかどうかを調べている（values.count(ans) == 0）。こっちのほうがイイね！

問題C : Grand Garden

花壇に N 本の花が咲いており、それぞれ 1,2,......,N と番号が振られています。最初、全ての花の高さは 0 です。 数列 h={h1,h2,h3,......} が入力として与えられます。以下の「水やり」操作を繰り返すことで、すべての k(1≦k≦N) に対して花 k の高さを hk

にしたいです。

整数 l,r

を指定する。l≦x≦r を満たすすべての x に対して、花 x の高さを 1 高くする。

条件を満たすための最小の「水やり」操作の回数を求めてください。

先生の回答

            #include<iostream>
            using namespace std;
             
            int main(){
              int n;
              cin>>n;
              
              int a[n];
              for(int i=0; i < n; i++){
                cin>>a[i];
              }
              
              int ans = 0;
              int active = 0;
              for(int i;i<n;i++){
                if(active>=a[i]){
                  active = a[i];
                }else{
                  ans += a[i]-active;
                  active = a[i];
                }
              }
              cout << ans << endl;
              return 0;
            }

とてもシンプル！素晴らしい。

問題D : Various Sushi

N 個の寿司があり、それぞれの寿司には「ネタ」ti と「おいしさ」di のパラメータが設定されています。 あなたはこの N 個の寿司の中から K

個を選んで食べようとしています。 この時のあなたの「満足ポイント」は、以下のようにして計算されます。

    「満足ポイント」は、「おいしさ基礎ポイント」と、「種類ボーナスポイント」の和である。
    「おいしさ基礎ポイント」は、食べた寿司の「おいしさ」の総和である。
    「種類ボーナスポイント」は、食べた寿司の「ネタ」の種類数を x

としたとき、x∗x

    である。

あなたは、「満足ポイント」をできるだけ大きくしたいです。 この時の「満足ポイント」の値を求めてください。

回答

TBD
時間あるとき追記します〜

所感

D問題解けるようになりたい。