SRM 696 div2 Medium Arrfix

問題

問題概要

aとbの数字が与えられる。aをfの数字で変えることができる。この操作を行って、aiとbiが異なる組数の最小値を求めよ。ただし、異なる数が増えてしまうような場合であっても、fはすべて使わないといけない。

解法

貪欲法で解いた。まず、一番最初にaの中で変えたい数字は、aiとbiが異なっていて、biとfが一致している場合である。これは、異なっている状態から、同じ状態になるので、最高のパターン。次にするのは、aとbが一致していて、bとfが一致いる場合。これは同じ状態から同じ状態になるだけなので、損することはない。あとは、これ以上数字を変えても、aとbが異なる状態から同じ状態にすることはできないので、aとbがはじめから一致していない状態のものを優先して変えていき、aとbがはじめから一致しているものを無駄に、変えないように貪欲に変えていく。

ミス

誤読によりいろいろめんどくさいことをした。はじめ、異なる組数を求めるのではなく、aiとbiの差の合計を最小値にするものだと思い。あと解法はdpでやるのかなと思って書いたけど、うまくいかない。下の様に書いたけど、これだと、fを使う順番が与えらた通りの順番で、aiのiの小さいほうから使っていくものしか調べられていないので、できない。aの制約が50だから、fの順列全部ためしたりできないし、dpじゃむりか? WA

class Arrfix{
public:
    int dp[55][55];
    int mindiff(vector <int> A, vector <int> B, vector <int> F){
        if(F.size() == 0){
            int ans = 0;
            rep(i, A.size()){
                ans = max(ans, abs(A[i] - B[i]));
            }
            return ans;
        }

        rep(i, 55)rep(j, 55) dp[i][j] = INF;
        dp[0][0] = 0;
        for (int i = 0; i < A.size(); ++i){
            for (int j = 0; j <= F.size(); ++j){
                if(j < F.size()){//ステッカーが余ってる
                    //j番目のステッカーをi番目に使う
                    if(B[i] == F[j]){
                        dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
                    }else{
                        dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + 1);
                    }
                    //j番目のステッカーを使わない
                    if(B[i] == A[i]){
                        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
                    }else{
                        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
                    }
                }else{//ステッカーが余ってない
                    if(B[i] == A[i]){
                        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
                    }else{
                        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
                    }
                }
            }
        }
        return dp[A.size()][F.size()];
    }
};

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

class Arrfix{
public:
    bool usedA[55];
    bool usedF[55];
    int mindiff(vector <int> A, vector <int> B, vector <int> F){
        rep(i, 55) usedA[i] = usedF[i] = false;

        //aがbと異なっていて、bとfが一致するときが一番良い(good)
        rep(i, F.size()){
            rep(j, A.size()){
                if(usedA[j] == false && A[j] != B[j] && B[j] == F[i] && A[j] != F[i]){
                    usedA[j] = usedF[i] = true;
                    A[j] = F[i];
                    break;
                }
            }
        }
        //aとbが一致していて、bとfが一致するとき(normal)
        rep(i, F.size()){
            if(usedF[i]) continue;
            rep(j, A.size()){
                if(usedA[j] == false && A[j] == B[j] && B[j] == F[i]){
                    usedA[j] = usedF[i] = true;
                    A[j] = F[i];
                    break;
                }
            }
        }
        //aとbが一致していない場所を優先して、aを変える
        rep(i, F.size()){
            if(usedF[i]) continue;
            rep(j, A.size()){
                if(usedA[j] == false && A[j] != B[j]){
                    usedA[j] = usedF[i] = true;
                    A[j] = F[i];
                    break;
                }
            }
        }
        

        //残っている分を変える
        rep(i, F.size()){
            if(usedF[i]) continue;
            rep(j, A.size()){
                if(usedA[j] == false){
                    usedA[j] = usedF[i] = true;
                    A[j] = F[i];
                    break;
                }
            }
        }

        int ans = 0;
        rep(i, A.size()){
            if(A[i] != B[i]) ans++;
        }
        return ans;
    }
};