この記事ははてなブログhttp://blue-jam.hatenablog.com/entry/2016/05/04/130116に移動しました．

Easy概要

卵が先に出てきたのか，鶏が先にでてきたのか気になったので，過去を見通す力がある人に聞こうとした．

しかし，その人はすでにn人の人に同じことを聞かれていたので，もう答えたくないといった．

そこで，そのn人を紹介してもらいそれぞれに卵が先か鶏が先かたずねた．eggCount人は卵が先だと答えたが，それ以外の人は鶏が先だと答えた．

正解がわからず再び超能力者に会うと，どうやらlieCount人には嘘の情報を教えたらしい．また，liarCount人は超能力者に教えてもらった答えと反対のことを言っているという．（嘘をついている人が本当のことを教えてもらったとは限らない）

果たして卵が先か，鶏が先なのだろうか．はたまた超能力者は嘘をついているのだろうか．

Easy解法

卵と答えた人のうち，嘘をついている人をiとし，ループ処理を行う．

鶏と答えた人のうち，嘘をついている人をjとすると，j = liarCount - i

これを元に，実際に卵と教えられた人，鶏と教えられた人の人数を計算する．

lieCountとその人数が等しければ，そちらが嘘だと判断することができる．

しかし，この方法に基づき卵，鶏の両方が嘘だと判断されたなら，正解はわからない．

この方法に基づき，卵，鶏の両方とも嘘ではないと判断されたなら，超能力者はうそつき．

1回といたことがあるにもかかわらず，129ptぐらいだった．遅すぎ．

class ChickenOracle {
    public:
    string theTruth(int n, int eggCount, int lieCount, int liarCount) {
        int res = 0;
        int chickenCount = n - eggCount;
        for(int i=0; i<=liarCount; ++i){
            int j = liarCount - i;
            int e = eggCount - i + j;
            int c = chickenCount - j + i;
            if(i > eggCount || j > chickenCount) continue;
            if(e == lieCount){
                if(res == 2 || res == 3){
                    res = 3;
                }
                else{
                    res = 1;
                }
            }
            if(c == lieCount){
                if(res == 1 || res == 3){
                    res = 3;
                }
                else{
                    res = 2;
                }
            }
        }
        if(res == 0){
            return "The oracle is a lie";
        }
        else if(res == 1){
            return "The chicken";
        }
        else if(res == 2){
            return "The egg";
        }
        else{
            return "Ambiguous";
        }
    }
};

Medium概要

1台のコンピュータと，n個の処理がある．

コンピュータは1度に1つの処理しか行うことができない．

処理にはuserが対応付けられていて，複数の処理を行うuserもいる．

userの待ち時間(userの処理がすべて終了するまでの時間)の総和が最小になるように順番を決める．

上記の条件を満たすように順番はランダムで定められる．

各処理が終了する時間の期待値を求める．

Medium解法

こういう期待値を計算するのは苦手．

userの待ち時間の合計を最小にするには，すべての処理にかかる時間がもっとも小さいuserからさきに処理を行わせればいい．これはわりとよく問題で出てくるからほぼ条件反射．

同じ処理時間であれば，userの順番が前後することがある．

同じuserであれば，処理の順番が前後することがある．

同一userの処理の間に別のuserの処理が入ることはありえない．

現在調べている処理のuserをA，現在調べている処理にかかる時間をt1，Aの処理の合計時間よりも短い処理時間で処理が終了するuser達にかかる時間をt2，Aの処理の合計時間と等しい時間で処理が終了するuserの人数をcnt，Aの処理の合計時間をt3とする．

このとき，この処理が終了する時間の期待値は，

t2 + (cnt - 1) * t3 / 2 + (t3 - t1) / 2 + t1

となる．

t2はほっといて，別の2項についての説明をしておく．

(cnt - 1) * t3 / 2

処理の1個目に入る確立はcnt分の1，先に行われる処理の数は0個．

処理の2個目に入る確立はcnt分の1，先に行われる処理の数は1個．

処理の3個目に入る確立はcnt分の1，先に行われる処理の数は2個．

...

よって，Aよりも先に行われる処理の数の期待値は，(0 ~ cnt-1の整数の合計値) / cntになる．

(0 ~ cnt-1の整数の合計値) = cnt * (cnt - 1) / 2なので，上記の式は，

(cnt - 1) / 2となる．

(t3 - t1) / 2

上と同じ考え方が使えそうだが，1回の処理時間がまちまちなので少々難しそう．

1つの処理が生成する待ち時間の期待値を考えるほうが楽．(ここへの発想がなかった）

同一userの処理の数をmとすると，

処理の1個目に入る確立はm分の1，現在調べている処理がその後にはいる確立は(m-1) / (m-1)．

処理の2個目に入る確立はm分の1，現在調べている処理がその後にはいる確立は(m-2) / (m-1).

処理の3個目に入る確立はm分の1，現在調べている処理がその後にはいる確立は(m-3) / (m-1).

...

これらの合計値は，

1/m * m * (m-1) / 2 / (m-1)

約分すると1/2になる．

最後のところ意外はちゃんと思いついたが，コーディングに時間がかかった．

いろいろな処理を行うのに簡潔に書ける方法を思いつくって大事だよな．

解説のコードを読んで目から鱗だった．

class BatchSystemRoulette {
    public:
    vector <double> expectedFinishTimes(vector <int> duration, vector <string> user) {
        vector <double> res;
        int n = duration.size();
        map<string, long long> user_duration;
        for(int i=0;i<n;++i){
            user_duration[user[i]] += duration[i];
        }

        for(int i=0;i<n;++i){
            double beforeTime = 0;
            int cnt = 0;
            for(map<string, long long>::iterator j=user_duration.begin(); j!=user_duration.end(); ++j){
                if(j->second < user_duration[user[i]]){
                    beforeTime += j->second;
                }
                else if(j->second == user_duration[user[i]]){
                    ++cnt;
                }
            }
            double et = beforeTime
                            + (cnt - 1) * user_duration[user[i]] / 2.0
                            + (user_duration[user[i]] - duration[i]) / 2.0
                            + duration[i];
            res.push_back(et);
        }
        return res;
    }
};

括弧内は本番で気がつくことのなかった反省点．反省点しかないとかいわない．

問題概要

0..N-1の整数で表される数列pがある．

すべての整数k(0<=k<N-1)について，p[k]とp[k+1]を入れ替える操作を1回ずつ行い，pを昇順にソートしたい．</ppp>

このとき，並べ替える方法は何通りあるか．

解法

dp[i][j]をi番目からj番目までの要素を昇順に並べ替える方法の数としてDP．(DPの方針を間違えたので，重複が削除できなかった）

dp[i][i] = 1

t(i, j, k)をi番目からj番目までの要素を並べ替える方法のうち，k番目の要素とk+1番目の要素を最後に交換する方法の数とすると，dp[i][j]は，t(i, j, k) (i <= k < j)の和になる．

t(i, j, k)は，数列をi~k, k+1~jまでの数列に分割して並べ替えた後，k番目の要素とk+1番目の要素を最後に入れ替えるというように考える．

2つの数列を並べ替える方法はそれぞれdp[i][k]，dp[k+1][j]で，その手順の数はk-i，j-(k+1)回．(ここに気がつかなかった）

この2種類の手順を組み合わせて実行する．それぞれの手順は独立に考えることができるので，

t(i, j, k) = C(j-i-1, k-i)*dp[i][k]*dp[k+1][j]（コンビネーションを使う発想がなかった．）

当然すべて適用していいというわけではなく，i~jまでの要素を確実に昇順にソートしないといけない．

上記の方法を適用して，i~jまでの数列をソートするには，

p[i], p[i+1], .. , p[k-1], p[k+1], p[k], p[k+2], p[k+3], .. , p[j]が昇順である必要がある．

つまり，p[i], p[i+1], .. , p[k-1], p[k+1]を昇順に並べ替えたときの結果と，p[i], p[i+1], .. , p[j]を昇順に並べ替えた結果のp[i] .. p[k]が等しいものだけを加算する．

この計算量は，dpを埋めるのにO(N^2)，各dp[i][j]を計算するのにO(N)かかるので，O(N^3)．

C(n, r)は，dpで事前に求めておく．

制約に合致するかどうかも事前に計算して配列に保存しておける．こちらはO(N^3logN)かかる．

Nは最大でも50なので，log 50 / log 2 = 5.6...

掲載するソースは，合致するかどうかいちいちソートして調べているので，O(N^4logN)．

あと，再帰をメモ化するタイプのDPです．漸化式をもとにループで計算している例は，TopCoderの解説にあります．

const int DIV = 1000000007;

class AdjacentSwaps {
    public:
    int c[51][51];
    int dp[60][60];
    int init(){
        memset(c, 0, sizeof(c));
        for(int i=0;i<=50;++i){
            for(int j=0;j<=i;++j){
                if(j == 0 || j == i){
                    c[i][j] = 1;
                }
                else{
                    c[i][j] = (c[i-1][j-1] + c[i-1][j]) % DIV;
                }
            }
        }
        memset(dp, -1, sizeof(dp));
    }
    int calc(int s, int e, vector<int> &p){
        if(s == e){
            return 1;
        }
        if(dp[s][e] >= 0){
            return dp[s][e];
        }
        dp[s][e] = 0;
        for(int k=s;k<e;++k){
            bool flag = true;
            vector<int> v(p), w(p);
            sort(v.begin() + s, v.begin() + (e + 1));
            sort(w.begin() + s, w.begin() + (k + 1));
            for(int i=s;i<k;++i){
                flag = flag && v[i] == w[i];
            }
            flag = flag && v[k+1] == w[k];
            if(!flag){
                continue;
            }
            int l = calc(s, k, p);
            int r = calc(k+1, e, p);
            int t = ((long long)l * r) % DIV;
            t = ((long long)t * c[e-s-1][k-s]) % DIV;
            dp[s][e] = (t + dp[s][e]) % DIV;
        }
        return dp[s][e];
    }
    int theCount(vector <int> p) {
        int res;	
        int n = p.size();
        init();
        res = calc(0, n-1, p);
        return res;
    }
};

新しいPC使って始めてのPractice．

337のPracticeには2人ほど付き合ってくださった．感謝．

Easy概要

1から1000000のカードまたはジョーカー（ワイルドカード）が最大50枚配られる．

それらを使って階段を作りたい．

最長でどれだけの長さの階段が作れるか．

Easy方針

高々50枚なので，最長で50の階段．カードの数も1000000までなので，始点を定めてそこからどれだけの長さの階段ができるか調べる．

int tab[10000010];
class CardStraights {
    public:
    int longestStraight(vector <int> cards) {
        int res = 0;
        int joker = 0;
        int n = cards.size();
        memset(tab, 0, sizeof(tab));
        sort(cards.begin(), cards.end());
        for(int i=0;i<n;++i){
            if(cards[i] == 0){
                joker++;
            }
            else{
                tab[cards[i]]++;
            }
        }
        for(int i=1;i<=1000000;++i){
            int tmp = joker;
            int count = 0;
            for(int j=i;j<=1000000;++j){
                if(tab[j] == 0){
                    if(tmp > 0){
                        --tmp;
                    }
                    else{
                        break;
                    }
                }
                ++count;
            }
            res = max(count, res);
        }
        return res;
    }
};

Medium概要

高さがまちまちのビルがある．その壁面に長方形の広告を載せたい．

最大でどれだけの面積の広告を貼り付けられるか．

Medium方針

各地点でのx座標と高さをスタックに積みながら進む．

途中で，スタックに積んでいる高さよりも低いものが現れたら，面積を計算しながらスタックからおろして面積を計算．（その地点の高さより小さくなるまで続ける．）その後にスタックに積む．（最後におろしたスタックのx座標を使う）

これを続けていって，最大値が答え．

class BuildingAdvertise {
    public:
    void getR(vector<int> h, int n, vector<long long> &R){
        int j = 0;
        int m = h.size();
        for(int i=0; i<n; ++i){
            R.push_back(h[j]);
            int s = (j + 1) % m;
            h[j] = ((h[j] ^ h[s]) + 13) % 835454957;
            j = s;
        }
    }
    long long getMaxArea(vector <int> h, int n) {
        long long res = 0ll;
        vector<long long> R;
        stack<pair<int, int> > st;
        getR(h, n, R);
        st.push(make_pair(0, 0));
        for(int i=0;i<n;++i){
            if(R[i] < st.top().second){
                int last = 0;
                while(R[i] < st.top().second){
                    res = max(res, (long long)(i - st.top().first) * st.top().second);
                    last = st.top().first;
                    st.pop();
                }
                st.push(make_pair(last, R[i]));
            }
            else if(R[i] > st.top().second){
                st.push(make_pair(i, R[i]));
            }
        }
        while(!st.empty()){
            res = max(res, (long long)(n - st.top().first) * st.top().second);
            st.pop();
        }
        return res;
    }
};

hという配列から高さを表すRを作るという制約を忘れていて，一緒に練習していた人に指摘された．すごく恥ずかしかった．

概要

N個の石が1列にあって，M番目の石が白，他はすべて黒になっている．

2人のプレイヤーが交互にK個の連続した石を選んで，その順番を入れ替える．

先にL番目の位置に白い石を配置したほうが勝ち．

どちらのプレイヤーが勝つか求める．（いつまでたっても終わらない場合は引き分け）

解法

初手でLに移動させられたら，先手の勝ち．

2手目で確実にLに移動させられたら，後手の勝ち．

3手以上かかる場合は，相手と同じ動きをして，無限ループに落としこむことができるので，引き分け．

class StonesGame {
public:
    bool can(int N,int M, int K, int L){
        int num = max(L, M) - min(L, M) + 1;
        if(num % 2 != K % 2) return false;
        int t = (K - num) / 2;
        if(t < 0) return false;
        return min(M, L) - t  >= 0 && max(M, L) + t < N;
    }
    string winner(int N, int M, int K, int L) {
        bool win;
        M = M - 1; L = L - 1;
        if(can(N, M, K, L)) return "Romeo";
        win = true;
        for(int i=0;i+K<=N;++i){
            int next;
            if(i + K <= M)
                continue;
            if(M < i)
                continue;
            next = i + K - (M - i) - 1;
            win = win && can(N, next, K, L);
        }
        return win ? "Strangelet": "Draw";
    }
};

概要

木の高さが一直線上に並ぶようにそろえる．

主人公は時間を巻き戻せるので，木は短くすることができる．

最小でいくつの木を短くすればいいだろうか．

解法

全探索．

2本の木を順番に選んで，いくつ木を短くすればいいか調べる．

#define EPS (1e-10)
class TimeTravellingGardener {
public:
    int determineUsage(vector <int> distance, vector <int> height) {
        int n = height.size();
        int res = n - 1;
        vector<int> v;
        v.push_back(0);
        for(int i=0;i<n;++i){
            v.push_back(v[i] + distance[i]);
        }
        for(int a=0;a<n;++a){
            for(int b=0;b<n;++b){
                double t = double(height[b] - height[a]) / (v[b] - v[a]);
                double s = height[a] - t * v[a];
                int cnt = 0;
                bool flag = true;
                for(int i=0;i<n;++i){
                    if(s + t * v[i] < - EPS){
                        flag = false;
                    }
                    else if(height[i] - EPS < s + t * v[i] && s + t * v[i] < height[i] + EPS){
                    }
                    else if(height[i] + EPS > s + t * v[i]){
                        ++cnt;
                    }
                    else{
                        flag = false;
                    }
                }
                if(flag) res = min(cnt, res);
            }
        }
        return res;
    }
};

概要

ピクセルの情報が与えられるので，それを塗りつぶすことができる最大のブラシの大きさを求める．

解法

O(min(W,H) * (WH)^2)で全部ぬって確かめる．

O(WH)でいけない気がしなくもない．

なんかすごい時間かかった．

class Painting {
public:
    int largestBrush(vector <string> picture) {
        int w, h;
        bool checked[60][60];
        w = picture[0].size(); h = picture.size();
        for(int k=1;k<=min(w,h);++k){
            bool filled;
            memset(checked, 0, sizeof(checked));
            for(int i=0;i+k<=h;++i){
                for(int j=0;j+k<=w;++j){
                    bool flag = true;
                    for(int ti=0;ti<k;++ti){
                        for(int tj=0;tj<k;++tj){
                            if(picture[i+ti][j+tj] == 'W'){
                                flag = false;
                            }
                        }
                    }
                    if(flag){
                        for(int ti=0;ti<k;++ti){
                            for(int tj=0;tj<k;++tj){
                                checked[i+ti][j+tj] = true;
                            }
                        }
                    }
                }
            }
            filled = true;
            for(int i=0;i<h;++i){
                for(int j=0;j<w;++j){
                    if(picture[i][j] == 'B' && !checked[i][j]){
                        filled = false;
                    }
                }
            }
            if(!filled) return k - 1;
        }
        return min(h, w);
    }
};