Quora Programming Challenge 2021

www.quora.com

Division 1に参加して、247/700点。 100位台。

今年初めて開催で来年もあるかもしれないので、色々と書いておく。端的に言うと、実装が重くてつらい。

Quora Programming Challenge

Quoraは最近良く目にするようになったQ&Aサイト。 Stack Overflowに比べて回答が少ないがその分回答に気合いが入っているように思う。

トップページにリンクを貼ろうと思ったが……トップページはログインフォームが出てくるだけなのか。こんな感じのサイト。

jp.quora.com

CEOが競プロガチ勢らしい。

CEOが競プロガチ勢なのに、なぜか競プロコンテストを開いてなかったQuoraが、ついにコンテストを開くとは…https://t.co/n7A6vAPnZJ
— nico_shindannin（診断人） (@nico_shindannin) January 14, 2021

Google Code Jamのように複数ラウンドに分かれていたりはしない一発勝負。ただし、タイムゾーンを考慮して、Division 1とDivision 2に分かれている。どちらかに一方に出ても良いし、両方に出ても良い。どちらも10以内なら賞金、50以内ならTシャツ。

タイムゾーンに配慮していると言っているけど、これ日本がとても不利じゃない？ Division 1は日本時間の23時から翌日3時、Division 2が同日の10時から14時。両方出ればその分有利。普通に1回だけの開催ならば睡眠時間を適当にズラすが、3時から10時の間にピタリと睡眠時間を持ってくるはつらい。ということでDivision 2はスルーした。

問題はDivisionごとに全7問で全て100点。簡単でも難しくても点数が同じなので、順位表の解いている人の人数から簡単な問題を見極める必要がある。でも、コンテストサイトに順位表が無い。 1時間ごとくらいにトップ50位までの順位表が貼り出される。

誤答ペナルティは無し。提出数と間隔にちょっと制限はあるが気にするほどではない。

制約の小さなテストケースを通すことによる部分点が多い。今となってはこの方式も珍しい。

私のコンテスト中の様子と回答

1問目: digest

Quoraの記事推薦システムが題材。企業コンテストでこういう問題良いね。

ユーザーがユーザーをフォローすることもできるし、ユーザーが記事をフォローすることもできる。記事には記事を作成したユーザーが存在する。これらの関係から、記事 $S_k$ のユーザー $U_i$ に対するスコアは、

$\sum_{j=1}^m a\left(U_i, U_j\right)\times b\left(U_j, S_k\right)$

と計算される。関数 $a$ と $b$ の値はユーザー同士やユーザーの記事とのフォローしているかどうかとかの関係から決まる。これで各ユーザーについてスコア上位3件の記事を推薦しろという問題。

ユーザー数と記事数がどちらも最大200。制限時間が0.5秒。 $O\left(n^{3}\right)$ 通るかな？　通るよね。 $a$ と $b$ の値を事前に計算しておく。

実装が面倒でバグって時間が溶ける。計算が複雑だからサンプルケースと見比べるの大変。何とか修正して通った。

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int main()
{
    int n, m;
    cin>>n>>m;
    vector<int> creator(n);
    for (int &c: creator)
        cin>>c, c--;
    int p, q;
    cin>>p>>q;
    vector<vector<bool>> FU(m, vector<bool>(m));
    for (int x=0; x<p; x++)
    {
        int i, j;
        cin>>i>>j;
        FU[i-1][j-1] = true;
    }
    vector<vector<bool>> FS(m, vector<bool>(n));
    for (int x=0; x<q; x++)
    {
        int i, k;
        cin>>i>>k;
        FS[i-1][k-1] = true;
    }

    vector<vector<int>> a(m, vector<int>(m, -1));
    for (int i=0; i<m; i++)
        a[i][i] = 0;
    for (int i=0; i<m; i++)
        for (int j=0; j<m; j++)
            if (FU[i][j] && a[i][j]==-1)
                a[i][j] = 3;
    for (int i=0; i<m; i++)
        for (int j=0; j<n; j++)
            if (FS[i][j] && a[i][creator[j]]==-1)
                a[i][creator[j]] = 2;
    for (int i=0; i<m; i++)
        for (int j=0; j<m; j++)
            for (int k=0; k<n; k++)
                if (FS[i][k] && FS[j][k] && a[i][j]==-1)
                    a[i][j] = 1;
    for (int i=0; i<m; i++)
        for (int j=0; j<m; j++)
            if (a[i][j]==-1)
                a[i][j] = 0;

    vector<vector<int>> b(m, vector<int>(n));
    for (int i=0; i<m; i++)
        for (int j=0; j<n; j++)
            if (creator[j]==i)
                b[i][j] = 2;
            else if (FS[i][j])
                b[i][j] = 1;

    for (int i=0; i<m; i++)
    {
        vector<pair<int, int>> S;
        for (int j=0; j<n; j++)
        {
            int s = 0;
            if (creator[j]==i || FS[i][j])
                s = -1;
            else
                for (int k=0; k<m; k++)
                    s += a[i][k]*b[k][j];
            S.push_back(make_pair(-s, j));
        }
        sort(S.begin(), S.end());
        for (int j=0; j<3; j++)
            cout<<(j==0 ? "" : " ")<<S[j].second+1;
        cout<<endl;
    }
}

2問目: escape

グリッド上の迷路に閉じ込められてしまったので、SからEまで移動して脱出したい。何体かのガードがいて、各ガード $i$ は（マンハッタン距離で） $d_{i}$ の範囲の好きな場所に移動できる。捕まらないように脱出する最小ステップは？

ガードの移動可能な範囲を壁にしてしまえば良い。各ガードについて求めていると間に合わないので、同時に求める。移動範囲の広いガードは先に、狭いガードは後に時間差で置いていき、1マスずつ広げていくイメージ。

これは素直に通った。

#include <iostream>
#include <vector>
#include <string>
#include <utility>
using namespace std;

int main()
{
    int n, m, k;
    cin>>n>>m>>k;
    vector<string> M(n);
    for (string &s: M)
        cin>>s;
    vector<vector<pair<int, int>>> G(n*m+1);
    for (int i=0; i<k; i++)
    {
        int r, c, d;
        cin>>r>>c>>d;
        G[d].push_back(make_pair(r-1, c-1));
    }

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    vector<pair<int, int>> T;
    for (int s=0; s<=n*m; s++)
    {
        vector<pair<int, int>> P;
        P.swap(T);

        for (auto p: P)
            for (int d=0; d<4; d++)
            {
                int tx = p.second + dx[d];
                int ty = p.first + dy[d];
                if (M[ty][tx]!='#')
                {
                    M[ty][tx] = '#';
                    T.push_back(make_pair(ty, tx));
                }
            }

        for (auto p: G[n*m-s])
            if (M[p.first][p.second]!='#')
            {
                M[p.first][p.second] = '#';
                T.push_back(p);
            }
    }

    int sx = -1;
    int sy = -1;
    int ex = -1;
    int ey = -1;
    for (int y=0; y<n; y++)
        for (int x=0; x<m; x++)
        {
            if (M[y][x]=='S')
                sx = x,
                sy = y;
            if (M[y][x]=='E')
                ex = x,
                ey = y;
        }
    if (sx==-1 || ex==-1)
    {
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }

    vector<vector<int>> D(n, vector<int>(m, -1));
    D[sy][sx] = 0;
    T.clear();
    T.push_back(make_pair(sy, sx));

    for (int s=1; s<=n*m; s++)
    {
        vector<pair<int, int>> P;
        P.swap(T);

        for (auto p: P)
            for (int d=0; d<4; d++)
            {
                int tx = p.second + dx[d];
                int ty = p.first + dy[d];
                if (M[ty][tx]!='#' && D[ty][tx]==-1)
                {
                    D[ty][tx] = s;
                    T.push_back(make_pair(ty, tx));
                }
            }
    }

    if (D[ey][ex]==-1)
    {
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }

    cout<<D[ey][ex]<<endl;
}

3問目: students

$n\times n$ （ $2\leq n \leq 3\times 10^{3}$ ）のグリッドに生徒が敷き詰められている。 4近傍隣接のうち $m$ （ $0\leq m \leq min\left(2n(n-1), 2\times 10^{5}\right)$ ）組はおしゃべりをしている。おしゃべりしている生徒同士を含まないように生徒は最大何人選べる？

二部グラフの最大独立集合。

どうやって求めるんだっけ？　直感的には最大マッチングを求めて何とかするのだろうが……。ググる。

二部グラフの最小点被覆と最大安定集合と最小辺被覆の求め方 from Kensuke Otsuki

www.slideshare.net

こんなん考えても分かるわけがないな。ググって良かった。けんちょんさんありがとう。

持っているライブラリーはマッチング数しか返さなかったので、ポチポチ修正。ライブラリゲー止めてくれ。まあ、修正が必要になると、ACLではなく自分でライブラリを書いていたのが生きてくる。自分で書いたコードのほうが修正がしやすい。

提出すると47/100。 Memory Limit Exceededで落ちていた。制限は256 MiBらしい。

たしかにけっこうギリギリか……。型をsigned charに変えてもダメ。 $m$ の上限がちょっと小さいので、おしゃべりしていない生徒を除外して、おしゃべりしている生徒だけでグラフを作ってみる。こういう非本質的なところで手間を掛けさせるのは止めてくれ～

今度はTime Limit Exceeded。最大流のアルゴリズムをDinicに貼り替えてみたら、バグった。諦め。

今気が付いたけど、これ、cinを止めれば通ったか……？

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

/*
void maxflow(vector<vector<int>> E_, vector<vector<int>> &F_, int s, int t)
{
    int n = (int)E_.size();

    vector<vector<int>> E(n), R(n), Forg(n);
    vector<vector<int>> F(n);
    for (int i=0; i<n; i++)
    for (int j=0; j<(int)E_[i].size(); j++)
    {
        int v = E_[i][j];
        R[i].push_back(int(E[v].size()));
        R[v].push_back(int(E[i].size()));
        E[i].push_back(v);
        E[v].push_back(i);
        F[i].push_back(F_[i][j]);
        Forg[i].push_back(j);
        F[v].push_back(0);
        Forg[v].push_back(-1);
    }
    vector<bool> U(n);
    function<int (int, int)> dfs = [&](int p, int f)
    {
        if (p==t)
            return f;
        U[p] = true;
        for (int i=0; i<(int)E[p].size(); i++)
        if (!U[E[p][i]] && F[p][i]>0)
        {
            int t = dfs(E[p][i], min(f, (int)F[p][i]));
            if (t>0)
            {
                F[p][i] -= t;
                F[E[p][i]][R[p][i]] += t;
                return t;
            }
        }
        return 0;
    };
    
    int flow = 0;
    while (true)
    {
        for (int i=0; i<n; i++)
            U[i] = false;
        int f = dfs(s, 0x7fffffff);
        if (f==0)
            break;
        flow += f;
    }

    //return flow;
    for (int i=0; i<n; i++)
        for (int j=0; j<(int)Forg[i].size(); j++)
            if (Forg[i][j]!=-1)
                F_[i][Forg[i][j]] = F[i][j];
}
*/

template<class T>
T maxflow(vector<vector<int>> E_, vector<vector<T>> C_, int s, int t)
{
    int n = (int)E_.size();
    vector<vector<int>> E(n), R(n), Corg(n);
    vector<vector<T>> C(n);
    T mx = {};
    for (int i=0; i<n; i++)
    for (int j=0; j<(int)E_[i].size(); j++)
    {
        int v = E_[i][j];
        R[i].push_back((int)E[v].size());
        R[v].push_back((int)E[i].size());
        E[i].push_back(v);
        E[v].push_back(i);
        C[i].push_back(C_[i][j]);
        Corg[i].push_back(j);
        C[v].push_back(T());
        Corg[v].push_back(-1);
        mx = max(mx, C_[i][j]);
    }

    vector<int> D;
    vector<int> I;

    auto bfs = [&]()
    {
        D = vector<int>(n, -1);
        vector<int> Q;
        D[s] = 0;
        Q.push_back(s);
        int q = 0;
        while (q<(int)Q.size())
        {
            int v = Q[q++];
            for (int i=0; i<(int)E[v].size(); i++)
            if (C[v][i]>0 && D[E[v][i]]==-1)
            {
                D[E[v][i]] = D[v]+1;
                Q.push_back(E[v][i]);
            }
        }
    };

    function<T(int,T)> dfs = [&](int v, T f)
    {
        if (v==t)
            return f;
        for (int &i=I[v]; i<(int)E[v].size(); i++)
        if (C[v][i]>0 && D[v]<D[E[v][i]])
        {
            T d = dfs(E[v][i], min(f, C[v][i]));
            if (d>0)
            {
                C[v][i] -= d;
                C[E[v][i]][R[v][i]] += d;
                return d;
            }
        }
        return T();
    };

    T flow = {};
    while (true)
    {
        bfs();
        if (D[t]==-1)
            break;
        I = vector<int>(n, 0);
        while (true)
        {
            T f = dfs(s, mx);
            if (f == T())
                break;
            flow += f;
        }
    }
    //return flow;
    for (int i=0; i<n; i++)
        for (int j=0; j<(int)Corg[i].size(); j++)
            if (Corg[i][j]!=-1)
                C_[i][Corg[i][j]] = C[i][j];
    return 0;
}

#include <iostream>
#include <queue>

int main()
{
    int n, m;
    cin>>n>>m;
    vector<int> x1(m), y1(m), x2(m), y2(m);
    for (int i=0; i<m; i++)
    {
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
        x1[i]--, y1[i]--, x2[i]--, y2[i]--;
    }

    //  https://www.slideshare.net/drken1215/ss-86894312
    vector<vector<int>> M(n, vector<int>(n, -1));
    for (int i=0; i<m; i++)
    {
        M[y1[i]][x1[i]] = 0;
        M[y2[i]][x2[i]] = 0;
    }
    int C = 0;
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if (M[y][x]>=0)
                M[y][x] = C++;
    vector<bool> O(C);
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if (M[y][x]>=0)
                O[M[y][x]] = (y+x)%2!=0;

    vector<int> e1(m), e2(m);   //  even, odd
    for (int i=0; i<m; i++)
    {
        e1[i] = M[y1[i]][x1[i]];
        e2[i] = M[y2[i]][x2[i]];
        if (O[e1[i]])
            swap(e1[i], e2[i]);
    }

    vector<vector<int>> E(C+2);
    vector<vector<int>> F(C+2);
    for (int i=0; i<m; i++)
    {
        E[e1[i]].push_back(e2[i]);
        F[e1[i]].push_back(1);
    }
    for (int i=0; i<C; i++)
        if (!O[i])
        {
            E[C].push_back(i);
            F[C].push_back(1);
        }
        else
        {
            E[i].push_back(C+1);
            F[i].push_back(1);
        }

    maxflow(E, F, C, C+1);
    for (int i=0; i<C+2; i++)
        E[i].clear();
    vector<int> EC(C);
    vector<bool> FF(C);
    for (int i=0; i<C; i++)
        if (!O[i])
            FF[i] = true;
    for (int i=0; i<m; i++)
    {
        if (F[e1[i]][EC[e1[i]]]!=0)
        {
            E[e2[i]].push_back(e1[i]);
            FF[e1[i]] = false;
        }
        else
            E[e1[i]].push_back(e2[i]);
        EC[e1[i]]++;
    }

    queue<int> Q;
    for (int i=0; i<C; i++)
        if (FF[i])
            Q.push(i);
    while (!Q.empty())
    {
        int q = Q.front();
        Q.pop();
        for (int e: E[q])
            if (!FF[e])
            {
                FF[e] = true;
                Q.push(e);
            }
    }

    int ans = 0;
    for (int i=0; i<C; i++)
        if (!O[i] && FF[i] ||
            O[i] && !FF[i])
            ans++;
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if (M[y][x]<0)
                ans++;
    cout<<ans<<endl;
}


/*
int main()
{
    int n, m;
    cin>>n>>m;
    vector<int> x1(m), y1(m), x2(m), y2(m);
    for (int i=0; i<m; i++)
    {
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
        x1[i]--, y1[i]--, x2[i]--, y2[i]--;
    }

    //  https://www.slideshare.net/drken1215/ss-86894312
    vector<vector<int>> E(n*n+2);
    vector<vector<signed char>> F(n*n+2);
    for (int i=0; i<m; i++)
    {
        int p1 = y1[i]*n+x1[i];
        int p2 = y2[i]*n+x2[i];
        if ((x1[i]+y1[i])%2!=0)
            swap(p1, p2);
        E[p1].push_back(p2);
        F[p1].push_back(1);
    }
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if ((x+y)%2==0)
            {
                E[n*n].push_back(y*n+x);
                F[n*n].push_back(1);
            }
            else
            {
                E[y*n+x].push_back(n*n+1);
                F[y*n+x].push_back(1);
            }

    maxflow(E, F, n*n, n*n+1);
    for (int i=0; i<n*n; i++)
        E[i].clear();
    vector<int> EC(n*n);
    vector<bool> FF(n*n);
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if ((x+y)%2==0)
                FF[y*n+x] = true;
    for (int i=0; i<m; i++)
    {
        int p1 = y1[i]*n+x1[i];
        int p2 = y2[i]*n+x2[i];
        if ((x1[i]+y1[i])%2!=0)
            swap(p1, p2);
        if (F[p1][EC[p1]]==0)
        {
            E[p2].push_back(p1);
            FF[p1] = false;
        }
        else
            E[p1].push_back(p2);
        EC[p1]++;
    }

    queue<int> Q;
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if (FF[y*n+x])
                Q.push(y*n+x);
    while (!Q.empty())
    {
        int q = Q.front();
        Q.pop();
        for (int e: E[q])
            if (!FF[e])
            {
                FF[e] = true;
                Q.push(e);
            }
    }

    int ans = 0;
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if ((x+y)%2==0 && FF[y*n+x] ||
                (x+y)%2!=0 && !FF[y*n+x])
                ans++;
    cout<<ans<<endl;
}
*/

3問目: walls

公開された順位表で解いている人数が少なかったのでスルー。

4問目: tourism

木が与えられる。頂点では金がもらえる。辺では金が取られる。移動元と移動先のクエリが複数与えられ、それぞれについて、金が尽きないように移動できる初期所持金の最小値を求める。

各頂点xについて、xから根に移動するときに必要な初期所持金と、根からxに移動するときに必要な初期所持金と、xから根に移動したときに所持金がいくらになっているかを求めておけば、各クエリが $O(n)$ で処理できる。

書いてみたけどサンプルケースが合わない → あ、経由するのは根ではなく最小共通祖先か。

だいたい差分計算ができそうだが、必要な金の最小値を取っているところがあり、これはSegment Tree的なことをしないといけない。この時点で残り10分。解けるわけがない。終わり。

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main()
{
    int n, m;
    cin>>n>>m;
    vector<long long> x(n);
    for (long long &t: x)
        cin>>t;
    vector<vector<int>> E(n);
    vector<vector<long long>> T(n);
    for (int i=0; i<n-1; i++)
    {
        int v, w;
        long long t;
        cin>>v>>w>>t;
        v--, w--;
        E[v].push_back(w);
        T[v].push_back(t);
        E[w].push_back(v);
        T[w].push_back(t);
    }

    vector<long long> MF(n);    //  MF[x]: needed money from x to 0
    function<void(int, int, long long)> f1 = [&](int c, int p, long long t)
    {
        if (p>=0)
            MF[c] = max(0LL, t-x[c]+MF[p]);
        for (int i=0; i<(int)E[c].size(); i++)
            if (E[c][i]!=p)
                f1(E[c][i], c, T[c][i]);
    };
    f1(0, -1, 0);

    vector<long long> MT(n);    //  MT[x]: needed money from 0 to x
    function<void(int, int, long long)> f2 = [&](int c, int p, long long m)
    {
        if (p>=0)
            MT[c] = max(0LL, max(MT[p], -m));
        for (int i=0; i<(int)E[c].size(); i++)
            if (E[c][i]!=p)
                f2(E[c][i], c, m+x[c]-T[c][i]);
    };
    f2(0, -1, 0);

    vector<long long> MS(n);
    function<void(int, int, long long)> f3 = [&](int c, int p, long long m)
    {
        if (p>=0)
        {
            m += x[c];
            MS[c] = m;
        }
        for (int i=0; i<(int)E[c].size(); i++)
            if (E[c][i]!=p)
                f3(E[c][i], c, m-T[c][i]);
    };
    f3(0, -1, 0);

    for (int i=0; i<n; i++)
        cout<<i<<" "<<MF[i]<<" "<<MT[i]<<" "<<MS[i]<<endl;

    for (int i=0; i<m; i++)
    {
        int a, b;
        cin>>a>>b;
        a--, b--;
        //cout<<MF[a]+max(0LL, MT[b]-MS[a])<<endl;
        cout<<MF[a]+max(0LL, MT[b]-MS[a])<<" "<<MF[a]<<" "<<MT[b]<<" "<<MS[a]<<endl;
    }
}