kojingharangの日記

SRM 606 Div1 250 EllysNumberGuessing

12:56 |

• 隠された数字 X があって、推測値 G[i] と差の絶対値 A[i]=|X-G[i]| が与えられる。
• X が一意に定まるならその数字、定まらないなら -1, どれかの A[i] が矛盾してるなら -2 を返せ。
• 1≦X,G[i]≦1,000,000,000, 1≦A[i]≦999,999,999, 1≦G.size≦50

• X の候補は G[0]+A[0], G[0]-A[0] の 2 つだから、それぞれについて残りの G, A をみてけばいいっすね
• と思いつつスラスラ書き始められないのがつらぽよ
• 制約を満たす答えが 0 個なら矛盾, 1個なら一意, 2個なら定まらないとすればよいのか。

• accepted

class EllysNumberGuessing {
  public:
  int getNumber(vector <int> G, vector <int> A) {
    ll limit=1000000000;
        VI w(2);
        w[0]=G[0]-A[0];
        w[1]=G[0]+A[0];
        VI ans;
        REP(j, 2) {
            bool has=true;
            REP(i, G.size()) {
                ll a=G[i]-A[i];
                ll b=G[i]+A[i];
                if(!(w[j]==a || w[j]==b)) has=false;
            }
            if(has) {
                if(1<=w[j] && w[j]<=limit) {
                    ans.PB(w[j]);
                }
            }
        }
        if(ans.size()==0) return -2;
        if(ans.size()==1) return ans[0];
        if(ans.size()==2) return -1;
        return -1;
  }
};

ツイートする