AtCoderチャレンジまとめ（3） - NIKKEI Programming Contest 2019

やりたいこと

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

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

チェレンジコンテスト

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 - AtCoder

問題A : Subscribers

私たちは、新聞の購読に関する調査を行いました。 具体的には、調査の対象者 N 人に対し、それぞれ次の 2つの質問を行いました。

質問 1 : あなたは新聞 X を購読しているか？

質問 2 : あなたは新聞 Y を購読しているか？

その結果、質問 1 に対して「はい」と回答した人の数は A 人、質問 2 に対して「はい」と回答した人の数は B人でした。

このとき、調査の対象者のうち新聞 X, Y の両方を購読している人の数は最大で何人であり、また最小で何人であると考えられるでしょうか？

この問いに答えるプログラムを書いてください。

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

N

A

B

自分の回答

    #include<iostream>
    using namespace std;
     
    int main(){
      int a,b,c;
      cin >> a >> b >> c;
      int amax;
      int amin;
      
      if(a >= b+c){
        amin = 0;
      }else{
        amin = b+c - a;
      }
      amax = min(b,c);
      cout << amax << " " << amin << endl;

      return 0;
    }

問題B : Touitsu

三つの文字列 A,B,C が与えられます。これらはそれぞれ、英小文字からなる長さ Nの文字列です。

私たちの目標は、これら三つの文字列をすべて等しくすることです。そのために、あなたは次の操作を繰り返し行うことができます。

操作: 文字列 A,B,Cのうち一つを選び、さらに 1 以上 N 以下の整数 i を指定する。そして、選んだ文字列の先頭から i文字目を別の何らかの英小文字に変更する。

目標を達成するためには最小で何回の操作が必要でしょうか？

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

N

A

B

C

自分の回答

    #include<iostream>
    #include <set>
     
    using namespace std;
     
    int main(){
      int n;
      cin >> n;
      
      string s1,s2,s3;
      cin >> s1 >> s2 >> s3;
      
      int ans=0;
      for(int i=0;i<n;i++){
        set<int> values;
        values.insert(s1[i]);
        values.insert(s2[i]);
        values.insert(s3[i]);
        ans += values.size() - 1;
      }
      cout << ans << endl;

      return 0;
    }

問題C : Different Strokes

高橋くんと青木さんの前に N 皿の料理が置かれています。 便宜上、これらの料理を料理 1、料理 2、…、料理 Nと呼びます。

高橋くんが料理 iを食べると彼は Ai ポイントの 幸福度 を得ます。 また、青木さんが料理 i を食べると彼女は Biポイントの幸福度を得ます。

彼らは、高橋くんから始めて交互に、料理を 1皿ずつ選んで食べることを料理が尽きるまで続けます。 ただし、彼らはともに、「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値を最大化するように料理を選びます。

このとき、「最終的に高橋くんが得る幸福度の総和」から「最終的に青木さんが得る幸福度の総和」を引いた値はいくつになるでしょうか？

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

N

A1

B1

:

AN

BN

自分の回答

    #include <iostream>
    #include <vector>
    #include <algorithm> 
     
    using namespace std;
     
    int main(){
      int n;
      cin >> n;
      
      int a[n],b[n];
      for(int i=0;i<n;i++){
        cin >> a[i] >> b[i];
      }
      
      std::vector<int> vec(n);
      long sumao=0;
      for (int i = 0; i < n; ++i) {
        vec[i] = a[i] + b[i];
        sumao += b[i];
      }
      
      std::sort(vec.begin(),vec.end(),std::greater<int>()); //降順ソート
      
      long sumta=0;
      for(int i=0;i<n;i++){
        if(i % 2 == 0){
          sumta += vec[i];
        }
      }
      cout << sumta - sumao << endl;

      return 0; 
    }

longで足りないこともあるから、競プロの人はlong longを使っている人が多い。

問題D : Restore the Tree

N 頂点の根付き木 (注記を参照) があり、その頂点には 1 から N までの番号が振られています。 根以外の各頂点には、その親から一本の有向辺が伸びています。 なお、根は頂点 1とは限りません。

高橋くんは、このグラフに M本の新たな有向辺を書き加えました。 書き足された各辺 u→v は、ある頂点 u からその子孫であるような頂点 vに向かって伸びています。

高橋くんが辺を書き加えたあとの N頂点 N−1+M 辺の有向グラフが与えられます。 より具体的には、N−1+M 組の整数のペア (A1,B1),...,(AN−1+M,BN−1+M) が与えられ、これらは i 番目の辺が頂点 Ai から頂点 Biに向かって伸びていることを表します。

元の根付き木を復元してください。

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

N

M

A1

B1

:

AN−1+M

BN−1+M

自分の回答

TDB
時間ができたら追記します。

参考: 有向非巡回グラフ（DAG）の意味とトポロジカルソート - 具体例で学ぶ数学

所感

やっぱりD問題が難しい。今回はトポロジカルソートを知らないと結構キツい。。。

D問題を解けるように頑張る!