C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

ABC062 A - Grouping|AtCoder

A: Grouping - AtCoder Beginner Contest 062 | AtCoder を解きました。
A 問題ですが、学びがあったのでメモ。

題意

・1 から 12 までの整数が下記のようにグループ分けされています。

  • 1, 3, 5, 7, 8, 10, 12
  • 4, 6, 9, 11
  • 2

・整数  x, y \, ( 1 ≤ x < y ≤ 12 ) が与えられるので、 \it x, \it y が同一のグループに属している場合 Yes を、そうでない場合は No を出力する。

コード:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x, y;
    cin >> x >> y;
 
    int cnt1{}, cnt2{};
    for( auto &i : vector<int>{ 1, 3, 5, 7, 8, 10, 12 } )
    {
        if( i == x || i == y ) cnt1++;        
    }
    for( auto &i : vector<int>{ 4, 6, 9, 11 } )
    {
        if( i == x || i == y ) cnt2++;        
    }
    cout << ( cnt1 == 2 || cnt2 == 2 ? "Yes" : "No" ) << endl;
}

実装を少し考えてみたけれど、自分ではこれ以上簡潔に書けなくて、
AC した後、他の方の提出を見たらグループ番号を持たせるという工夫があり、学びでした。

  • 1, 3, 5, 7, 8, 10, 12 ➡︎ グループ 0
  • 4, 6, 9, 11 ➡︎ グループ 1
  • 2 ➡︎ グループ 2

↑上記のようにグループ番号( 0, 1, 2 )を付加します。(番号は何でも良い)
↓そして、 1 から 12 までの整数を昇順に並び替えグループ番号で配列に持ちます

vector<int> vc{ -1, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 }

この時、制約より x0 が与えられる事はないので、適当に -1 とかで vc[ 0 ] を埋めておく。
これにより、vc[ x ] vc[ y ] がどのグループか  O( 1 ) で知る事ができ、一致判定が可能となる訳です。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> vc{ -1, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };
    
    int x, y;
    cin >> x >> y;
    
    cout << ( vc[ x ] == vc[ y ] ? "Yes" : "No" ) << endl;
}

↑コードが凄く簡潔になりました!