問題

C 4-adjacent

問題文

長さ N の数列 a=(a1,a2,...,aN) があります。各 ai は正の整数です。

すぬけ君の目標は、a の要素を自由に並べ替え、次の条件が成り立つようにすることです。各 1 ≤ i ≤ N − 1 について、ai と ai+1 の積は 4 の倍数である。すぬけ君が目標を達成できるか判定してください。

制約

* 2 ≤ N ≤ 10^5
* ai は整数である。
* 1 ≤ ai ≤ 10^9

とこんな感じ結果から考えると

4 1 1  ・ ・ ・(1)
1 1 4 1 ・ ・ ・(2)
2 2 2 ・ ・ ・ (3)

(1)みたいなのはOK、(2)みたいなのはNG、(3)みたいなのはOK

となります。

これから数列の要素が奇数の場合と偶数の場合での処理を分ける必要がありそうですね。

考えたこと

愚直に2重ループで4の倍数とそれ以外のペアを見つけるのはO(N²)かかりそうなのでTLEで問題が解けません。

4の倍数の個数と奇数の数と数列の要素数の関係みていけばペアが4の倍数になるかどうかについて考えることができそうなので、この方法を採用します。

上記の例(1)場合

* 4の倍数は1個 奇数は2個 数列の要素数は3個

上記の例(2)場合

* 4の倍数は1個 奇数は3個 数列の要素数は4個

上記の例(3)場合

* 2の倍数が3個

では、(2)の場合においてOKになる場合を考えてみると 4 1 4 1 は大丈夫でしょう。このとき 4の倍数は2個奇数は2個数列の要素数は4個になります。

以上のことから

1. 数列の要素数が奇数の場合 4の倍数の個数 - 奇数の個数 は -1以上であれば問題ない
2. 数列の要素数が偶数の場合 4の倍数の個数 - 奇数の個数 は 0以上であれば問題ない

の二つのルールが出来上がります。じゃあ2の倍数の(3)はどうなるのとなりますが、この場合上の二つのルールに該当するので問題ありません。(4の倍数の個数 : 0 奇数の個数 : 0 0 - 0 = 0)

フロー

4の倍数の個数、2の倍数の個数、その他の倍数の個数を定義
入力を受け取り
数列の受け取りのループ
- その入力が4の倍数の場合 4の倍数の個数 +1
- その入力が2の倍数かつ4の倍数でない場合 2の倍数の個数+1
- それ以外の場合その他の倍数の個数+1
もし、要素数が2の倍数のとき
- 2 のルールに該当するならば
  - Yesと出力し終了
それ以外の場合
- 1 のルールに該当するならば
  - Yesと出力し終了
Noと出力し終了

プログラム

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
using namespace std;

int main(void){
    long long N;
    cin >> N;
    vector<long long>a(N);
    long long bai4 = 0;
    long long bai2 = 0;
    long long other = 0;
    for (long long i = 0;i < N;i++){
        cin >> a[i];
        if(a[i] % 2 == 0 && a[i] % 4 == 0){
            bai4++;
        }else if(a[i] % 2 == 0 && a[i] % 4 != 0){
            bai2++;
        }else{
            other++;
        }
    }
    if (N % 2 == 0){
        if (bai4 - other >= 0){
            cout << "Yes" << endl;
            return 0;
        }
    }else{
        if (bai4 - other >= -1){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

こんな感じでACとれました。

xlkeiの日記

ARC080-C 4-adjacent を解いてみた

問題

C 4-adjacent

問題文

制約

考えたこと

フロー

プログラム