IT・ビッグデータ徒然ブログ

関西でインフラ、データ基盤系のエンジニアになりたい

AtCoderに登録したら解くべき精選過去問10問の類題をC++で解いてみた(その6)

競技プログラミング

第7問(ABC 085 B - Kagami Mochi)の類題を解いていきます。

ABC 071 B - Not Found

  • C++で初めてsetを使ってみた(といってもAtcoderきっかけで勉強し始めたので大した歴ではない)
  • 与えられた文字を突っ込んで行ったあと、アルファベットで全件走査させる。
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
 
using namespace std;
int main() {
 
    string str;
    int length,i;
    set<char> alphabets;
    
    cin >> str;
 
    length = str.length();
 
    for(i = 0; i<length; i++){
        alphabets.insert(str[i]);
    }
    
    set<char>::iterator it;
 
     for(i = 'a';i <= 'z'; i++) {
        it = alphabets.find(i);
        if(it == alphabets.end()){
            cout << (char)i << endl;
            return 0;
        }
    }
    cout << "None" << endl;
    return 0;
}

ABC 061 B - Counting Roads

  • 各都市(数値で表される)を配列のキーとして用意しておき、2行目以降、その数値が出るたびにキーの値をインクリメントさせる
  • 今思えばmap使わなくても普通の配列でできたかなと思うけど、、、まあいいか。
#include <iostream>
#include <algorithm>
#include <string>
#include <map>

using namespace std;
int main() {

    int number_of_cities,number_of_roads,i,j,k;
    map<int,int> road_to_city;

    cin >> number_of_cities >> number_of_roads;

    for(i = 0 ; i< number_of_cities; i++) {
        road_to_city[i] = 0;
    }

    for(i = 0; i < number_of_roads;i++) {
        cin >> j >> k;
        road_to_city[j-1]++;
        road_to_city[k-1]++;
    }

    for(i = 0; i<number_of_cities;i++){
        cout << road_to_city[i] << endl;
    }

    return 0;
}

ABC 047 B - Snuke's Coloring 2 (ABC Edit)

  • 一旦xとy座標を変数にした後、4象限(x軸の上側、下側、y軸の上側、下側)で隠される面積を割り出して、引き算する。
  • 多分もっといい解法があるんだろうとは思うけど、今の実力ではこれがいっぱいいっぱいでした。
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
 
using namespace std;
int main() {
 
    int x,y,i,j,k,l,number_of_coloring;
    int left_coloring_x = 0;
    int right_coloring_x = 0;
    int upper_coloring_y = 0;
    int lower_coloring_y = 0;
 
    cin >> x >> y >> number_of_coloring;
  
    for(i = 0; i < number_of_coloring;i++){
        cin >> j >> k >> l;
 
        switch(l){
            case 1:
                if(left_coloring_x < j){
                    left_coloring_x = j;
                }
                break;
            case 2:
                if(right_coloring_x < abs(x - j)){
                    right_coloring_x = abs(x - j);
                }
                break;
            case 3:
                if(lower_coloring_y < k){
                    lower_coloring_y = k;
                }
                break;
            case 4:
                if(upper_coloring_y < abs(y - k)){
                    upper_coloring_y = abs(y - k);
                }
                
                break;
        }
    }
 
    x = x - left_coloring_x - right_coloring_x;
    y = y - lower_coloring_y - upper_coloring_y;
 
    if(x <= 0 || y <= 0) {
        cout << 0 << endl;
    } else {
        cout << x * y << endl;
    }
    return 0;
}

ABC 091 B Two Colors Card Game

  • mapを用意
  • 青いカードのときは文字列を見るたびににその文字をキーとして数値をインクリメント
  • 赤いカードのときはその逆でその文字キーで数値をデクリメント
  • あとはmapを上からキーを走査して、もっとも大きい数値を出力する
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>

using namespace std;
int main() {

    int i,number_of_bluecard,number_of_redcard;
    map<string,int> strs;
    string str;
    int max_yen = 0;

    cin >> number_of_bluecard;

    for(i = 0; i< number_of_bluecard; i++){
        cin >> str;
        if(strs.find(str) == strs.end()){
            strs[str] = 1;
        } else {
            strs[str]++;
        }
    }

    cin >> number_of_redcard;

    for(i = 0;i<number_of_redcard; i++){
        cin >> str;
        if(strs.find(str) != strs.end() && strs[str] != 0 ){
            strs[str]--;
        }
    }

    for(auto itr = strs.begin(); itr != strs.end(); itr++){
        if(max_yen < itr->second) {
            max_yen = itr->second;
        }
    }

    cout << max_yen << endl;
    return 0;
}

ABC 081 C - Not so Diverse　

  • 入力される数値をキーとして、各数値の出現回数をカウント
  • 出現回数が多い順にキーをソート
  • 規定されている数値の種類までカウントし、超えた場合は各キーに紐づく値を足し算していく
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
 
using namespace std;
 
int main() {
 
   int i,ball,balls,num_ball_type;
   int ball_type[210000] = {0};
   int counter = 0;
   int number_of_changed_type = 0;
 
   cin >> balls >> num_ball_type;
 
   for(i = 0; i < balls; i++){
       cin >> ball; 
       ball_type[ball]++;
   }
 
   sort(ball_type,ball_type+210000,greater<int>());
 
   for(i = 0; i < 210000; i++){
 
       if(ball_type[i] == 0){
           break;
       }
       if(counter >= num_ball_type) {
           number_of_changed_type += ball_type[i];
       } else {
           counter++;
       }
   }
 
    cout << number_of_changed_type << endl;
 
    return 0;
}