C++ の動作確認をしてみた（１９）

C++の練習を兼ねて, AtCoder Beginner Contest 069 の問題C（4-adjacent）を解いてみた.

■感想.
1. 解答方針が決まるまで, 試行錯誤したものの, 何とかACになったので良かったと思う.
2. コーディング後, 解説を見たら, 多分同じ方針だったので, とりあえず良かったと思う.

本家のサイトABC #069 / ARC #080 Editorialをご覧下さい.

■C++版プログラム.

#include <iostream>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)

typedef long long LL;

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    
    // 2. a(i) と a(i+1) の積が, 4の倍数になるには？.
    LL a;
    int odd = 0;    // 奇数の個数.
    int m2  = 0;    // 2の倍数の個数.
    int m4  = 0;    // 4の倍数の個数.
    
    FOR(i, 0, N) {
        LL ai;
        cin >> ai;
        if(ai % 2 != 0) {
            odd++;
        } else {
            if(ai % 4 == 0) {
                m4++;
            } else {
                m2++;
            }
        }
    }
    
    // 3. 判定.
    bool ok = false;
    // N = 2 の 場合, 
    // 1 1 は, NG. (合計 2)
    // 2 2 は, OK. (合計 4)
    // 1 4 は, OK. (合計 5)
    // 
    // N = 3 の 場合, 
    // 1 4 1 は, OK. (合計 6)
    // 2 2 2 は, OK. (合計 6)
    // 1 4 2 は, OK. (合計 7)
    // 1 2 2 は, NG. (合計 5)
    // 
    // N = 4 の 場合, 
    // 2 2 2 2 は, OK. (合計 8)
    // 1 2 4 1 は, NG. (合計 8)
    // 1 4 4 1 は, OK. (合計 10)
    
    // N = 5 の 場合, 
    // 2 2 2 1 2 は, NG. (合計  9)
    // 2 2 2 2 2 は, OK. (合計 10)
    // 2 2 2 4 1 は, OK. (合計 11)
    // 2 2 4 1 4 は, OK. (合計 13)
    // 1 4 2 4 1 は, OK. (合計 12)
    // 1 4 1 4 1 は, OK. (合計 11)
    // 
    // -> 上記のように, 合計を考えるアプローチは, 厳しそう.
    // 
    // 1 と 4 の 組み合わせを, どんどん削除していくことを考える.
    // 1 4 1 4 2 2 2 のような並びなら,
    // 1 4 1 4 2 2 2 -> 1 4 2 2 2 -> 2 2 2 のイメージ(目標達成).
    // 
    // 1 4 1 4 1 4 1 4 1 2 のような並びなら,
    // 1 4 1 4 1 4 1 4 1 2 -> 1 4 1 4 1 4 1 2 -> 1 4 1 4 1 2 -> 1 4 1 2 -> 1 2 のイメージ(目標達成不可能).
    // 
    // 1 4 1 4 1 のような並びなら,
    // 1 4 1 4 1 -> 1 4 1 -> 1 のイメージ(目標達成).
    // 
    // 1 4 1 4 のような並びなら,
    // 1 4 1 4 -> 1 4 -> "" のイメージ(目標達成).
    
    // 3-1. 1 が存在しない場合は, すでに目標達成.
    if(odd == 0) ok = true;
    
    // 3-2. 1 と 4 のペアを消していって, 最終的に, 
    // ① 何も残らない.
    // ② 1 が, 1個だけ残る.
    // ③ 2, 4 の 片方, もしくは, 両方 が残る.
    // の場合は, 目標達成と判定できる.
    if(odd <= m4) ok = true;
    if(odd - m4 == 1 && m2 == 0) ok = true;
    
    // 4. 出力 ～ 後処理.
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
    
}

#include <iostream>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)

typedef long long LL;

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

// 2. a(i) と a(i+1) の積が, 4の倍数になるには？.

LL a;

int odd = 0; // 奇数の個数.

int m2 = 0; // 2の倍数の個数.

int m4 = 0; // 4の倍数の個数.

FOR(i, 0, N) {

LL ai;

cin >> ai;

if(ai % 2 != 0) {

odd++;

} else {

if(ai % 4 == 0) {

m4++;

} else {

m2++;

}

// 3. 判定.

bool ok = false;

// N = 2 の場合,

// 1 1 は, NG. (合計 2)

// 2 2 は, OK. (合計 4)

// 1 4 は, OK. (合計 5)

// N = 3 の場合,

// 1 4 1 は, OK. (合計 6)

// 2 2 2 は, OK. (合計 6)

// 1 4 2 は, OK. (合計 7)

// 1 2 2 は, NG. (合計 5)

// N = 4 の場合,

// 2 2 2 2 は, OK. (合計 8)

// 1 2 4 1 は, NG. (合計 8)

// 1 4 4 1 は, OK. (合計 10)

// N = 5 の場合,

// 2 2 2 1 2 は, NG. (合計 9)

// 2 2 2 2 2 は, OK. (合計 10)

// 2 2 2 4 1 は, OK. (合計 11)

// 2 2 4 1 4 は, OK. (合計 13)

// 1 4 2 4 1 は, OK. (合計 12)

// 1 4 1 4 1 は, OK. (合計 11)

// -> 上記のように, 合計を考えるアプローチは, 厳しそう.

// 1 と 4 の組み合わせを, どんどん削除していくことを考える.

// 1 4 1 4 2 2 2 のような並びなら,

// 1 4 1 4 2 2 2 -> 1 4 2 2 2 -> 2 2 2 のイメージ(目標達成).

// 1 4 1 4 1 4 1 4 1 2 のような並びなら,

// 1 4 1 4 1 4 1 4 1 2 -> 1 4 1 4 1 4 1 2 -> 1 4 1 4 1 2 -> 1 4 1 2 -> 1 2 のイメージ(目標達成不可能).

// 1 4 1 4 1 のような並びなら,

// 1 4 1 4 1 -> 1 4 1 -> 1 のイメージ(目標達成).

// 1 4 1 4 のような並びなら,

// 1 4 1 4 -> 1 4 -> "" のイメージ(目標達成).

// 3-1. 1 が存在しない場合は, すでに目標達成.

if(odd == 0) ok = true;

// 3-2. 1 と 4 のペアを消していって, 最終的に,

// ① 何も残らない.

// ② 1 が, 1個だけ残る.

// ③ 2, 4 の片方, もしくは, 両方が残る.

// の場合は, 目標達成と判定できる.

if(odd <= m4) ok = true;

if(odd - m4 == 1 && m2 == 0) ok = true;

// 4. 出力～後処理.

cout << (ok ? "Yes" : "No") << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 069

C++の練習を兼ねて, AtCoder Beginner Contest 069 の 問題C（4-adjacent）を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 069 の問題C（4-adjacent）を解いてみた.

コメントを残すコメントをキャンセル