問題

問題概要

$n$ 人が1列に並んだ椅子に座っている。人々はそれぞれ出身国があり、同じ出身国の人たちは固まって座る。インタビュアーが座っている人のうちの何人かに次のような質問をしました：「ここにあなたと同じ出身国の人は何人いますか？」

インタビューの回答状況が配列 $a$ として与えられる。インタビューをしていない人は $0$ 、した人はその回答状況が正の整数で与えられる。今得られている回答状況からまだインタビューしていない人の出身国を全て決定することができるかどうか判定せよ。

$1 \le n \le 100$
正答な割り当て方は存在する

アイデア

出身国の割り当てが一意に定まるかどうかを判定したい。情報が少なすぎると候補が何通りも出てきてしまうので、そういうのは無理である。つまり、問題を言い換えると配列 $a$ の0に部分を全て埋めて完成させていくと考えたときにその数字を埋める方法が何通りあるかを数えそれが1通りなら可能、2通り以上なら不可能という判定問題になる。

配列の例として{3, 0, 3, 0, 0, 3, 0, 0, 2, 0}というものを考える。

先頭の3に関しては、以降の3人が同じ出身国であると一意に定めることが出来る。つまり最初の3つはそれぞれ0か3でなければいけない。つまり2番目の位置には3が入ることが決まる。最初3人は決まって独立で、以降はその後の{0, 0, 3, 0, 0, 2, 0}について考えていく。

先頭の値に何が入るのかを考えてみる。この先頭の値が $x$ と決まると、そこを先頭として $x$ 人が同じ出身であるということが確定するので、それを元にまた進めていくことができる。

まず、1が入ると仮定すると、正統性が保たれて次に進むことが出来る(次に考えるべきものは{0, 3, 0, 0, 2, 0}になる)。次に2が入ると仮定すると、正統性が保たれて次に進むことが出来る(次に考えるべきものは{3, 0, 0, 2, 0}になる)。次に3が入ると仮定すると、正統性が保たれて次に進むことが出来る(次に考えるべきものは{0, 0, 2, 0}になる)。次に4が入ると仮定すると辻褄が合わなくなるのでこれ以上の数は入れられない。

このような考えに基づき、配列のsuffixを引数とした再帰関数を考えることができる。そして、suffix全体を保存し続ける必要はなく、その先頭の添字を保存しながら再帰を回していく。現在のindexが $i$ の時は $a[i ]$ が0かそれ以外かで処理が分かれる：

$a[i ] = 0$ のとき：

このときは、この位置に候補となる数字を $1$ ~ $n$ まで選ぶことが出来る。候補となる数字を $j$ とすると、次は $i+j$ へ遷移していくことになる。

$a[i ] > 0$ のとき：

このときは既に決まっているので次は $i+ a[i ]$ に遷移していく。

あとはこのDPをする際に、2通り以上はもう何通りでもいいので、オーバーフローしないように圧縮しながら進めていく。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

class CountryGroupHard {
    public:
    string solve(vector<int> a) {
        string OK="Sufficient", NG="Insufficient";
        int n=a.size();

        int dp[101]={0};
        dp[0]=1;
        rep(i,n)
        {
            if(a[i]==0)
            {
                for(int j=1; i+j<=n; ++j)
                {
                    bool ok=true;
                    for(int k=i; k<i+j; ++k)
                    {
                        if(a[k]!=0 && a[k]!=j)
                        {
                            ok=false;
                            break;
                        }
                    }

                    if(ok) dp[i+j] = min(dp[i+j]+dp[i],2);
                }
            }
            else
            {
                if(i+a[i]>n) continue;

                bool ok=true;
                for(int j=i; j<i+a[i]; ++j)
                {
                    if(a[j]!=0 && a[j]!=a[i]) ok=false;
                }

                if(ok) dp[i+a[i]] = min(dp[i+a[i]]+dp[i],2);
            }
        }

        // rep(i,n+1) printf("dp[%d] = %d\n", i,dp[i]);

        if(dp[n]==1) return OK;
        return NG;
    }
};

裏紙

ほぼ競プロ、たまに日記

SRM 653 Div1 Easy - CountryGroupHard

問題

問題概要

アイデア

実装(C++)