No.202 1円玉投げ

No.202 1円玉投げ - yukicoder

• バケット法を使う。分割領域に含まれる一円玉の最大個数はたかだか 25 個程度なので十分間に合う。

class ThrowOneYenCoin {
public:
    static const int r = 10;
    typedef pair<int,int> Pt;
    bool hit(const Pt &a, const Pt &b) {
            int ax,ay,bx,by;
            tie(ax,ay) = a;
            tie(bx,by) = b;
            return (ax-bx)*(ax-bx)+(ay-by)*(ay-by) < 4*r*r;
    }
    void solve(void) {
            int N;
            cin>>N;

            const int B = 100;
            const int maxX = 20000;
            const int maxY = 20000;
            const int maxBX = maxX/B;
            const int maxBY = maxY/B;
            list<Pt> field[maxBY+1][maxBX+1];

            // 100*100 に含まれるコインの数は最大25程度
            // O(N*9*25)
            REP(i,N)
            {
                int x,y;
                cin>>x>>y;

                Pt p(x,y);
                int bx = x/B;
                int by = y/B;

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

                bool ok = true;
                REP(j,3)
                REP(k,3)
                {
                    int nx = bx+dx[j];
                    int ny = by+dy[k];

                    if (nx < 0 || ny < 0 || maxBX < nx || maxBY < ny)
                        continue;

                    auto &f = field[ny][nx];
                    for (auto c : f)
                    {
                        if ( hit(c,p) )
                            ok = false;
                    }
                }
                if (ok)
                    field[by][bx].push_back(p);
            }
            ll cnt = 0;
            REP(i,maxBX+1)
            REP(j,maxBY+1)
            {
                auto &f = field[j][i];
                cnt += f.size();
            }
            cout<<cnt<<endl;
    }
};

No.199 星を描こう

No.199 星を描こう - yukicoder

• 星を一筆書きするとみなして、辺を順列で表現して、一つの辺にたいして接続しない残りの２辺が条件を満たすかチェックすれば良い。

class WriteStars {
public:
    void solve(void) {
            vector<Ptd> verts(5);
            REP(i,5)
            {
                int x,y;
                cin>>x>>y;
                verts[i] = Ptd(x,y);
            }

            sort(RANGE(verts));
            // O(5!*5*5)
            do {
                vector<pair<Ptd,Ptd>> edges;
                REP(i,5)
                    edges.push_back(make_pair(verts[i], verts[(i+1)%5]));

                bool ok = true;
                REP(i,5)
                {
                    auto e = edges[i];
                    Ptd p1,p2;
                    tie(p1,p2) = e;

                    REP(j,5)
                    {
                        if (i == j)
                            continue;

                        Ptd q1,q2;
                        tie(q1,q2) = edges[j];

                        if (p1 == q1 || p1 == q2 || p2 == q1 || p2 == q2)
                            continue;

                        // 線分 e と交差するもののうち端点を left/right に振り分ける
                        //       2
                        //   0 --------- 1
                        //      3    4
                        // のように 線分01 の端点とつながらない二本の線分が 01 とまじわっていればよい
                        if ( !Ptd::intersect(p1,p2,q1,q2) )
                        {
                            ok = false;
                            break;
                        }
                    }
                }
                if (ok)
                {
                    cout<<"YES"<<endl;
                    return;
                }
            } while(next_permutation(RANGE(verts)));
            cout<<"NO"<<endl;
    }
};

• convex hull を使う想定解法がステキ。

    void solve(void) {
            vector<Ptd> verts(5);
            REP(i,5)
            {
                int x,y;
                cin>>x>>y;
                verts[i] = Ptd(x,y);
            }

            auto pts = Ptd::convex_hull(verts);
            if (pts.size() == 5)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
    }

No.190 Dry Wet Moist

No.190 Dry Wet Moist - yukicoder

• 貪欲法でとける問題。Moist なケースを最初に考えてとっかかりにして他のケースの解き方も思いついた。
• multiset じゃなくて set にしてしまって間違えてしまった...。しょうもない。
• もうちょい綺麗にコードがかけるといいな。Dry のケースは Wet のケースと比較すると配列の中身の符号を反転させるだけでよさそうなんでそうすればよかったかも。

class DryWetMoist {
public:
    void solve(void) {
            int N;
            cin>>N;
            vector<int> A(2*N);
            REP(i,2*N) cin>>A[i];

            // まともに計算すると O(N!) になってしまう。
            //
            // まず Moist を最大化する組み合わせに注目する
            // Moist になるには (a,-a) なる組み合わせしかありえないので、
            // 貪欲法で計算すればよい。ソートしておけば O(N*log(N)) で計算できる。
            //
            // 同様に Dry なものを作るには貪欲法で a<0 のとき (a,b) (b<-a なる最大の b)
            //        Wet なものを作るには        a>0 のとき (a,b) (b>-a なる 最小の b)
            // なる b を選べば良い。
            // これらも二分探索で O(N*log(N)) でみつかる
            //
            // multiset をつかえば配列の要素の削除・更新ができる。
            //

            int nDry = 0;
            {
                multiset<int> S(RANGE(A));
                while (!S.empty())
                {
                    auto beg = S.begin();
                    int  a = *beg;

                    if (a >= 0)
                        break;

                    S.erase(beg); // 重複検索しないように先に削除
                    auto found = S.lower_bound(-a);
                    if (found != S.begin())
                    {
                        --found;
                        assert(a+*found <0);
                        ++nDry;
                        S.erase(found);
                    }
                }
            }

            int nWet = 0;
            {
                multiset<int> S(RANGE(A));
                while (!S.empty())
                {
                    // 大きいものから取り出す
                    auto it = S.end();
                    --it;
                    int  a = *it;

                    if (a < 0)
                        break;

                    S.erase(it);
                    auto found = S.upper_bound(-a);
                    if (found != S.end() && a + *found > 0)
                    {
                        ++nWet;
                        S.erase(found);
                    }
                }
            }

            int nMoist = 0;
            {
                multiset<int> S(RANGE(A));
                while (!S.empty())
                {
                    auto beg = S.begin();
                    int  a = *beg;

                    S.erase(beg);

                    auto found = S.lower_bound(-a);
                    if (found != S.end() && *found == -a)
                    {
                        ++nMoist;
                        S.erase(found);
                    }
                }
            }

            cout<<nDry<<" "<<nWet<<" "<<nMoist<<endl;
    }
};

No.189 SUPER HAPPY DAY

No.189 SUPER HAPPY DAY - yukicoder

• TDPC E-数 でやった桁 DP を使う。桁を大きいほうから DP するのがポイント
• 最後は 00...0 と全て 0 のケースを除くことことが必要。

const ll Mod = 1000000009;
class SuperHappyDay
{
public:
    void solve(void)
    {
        string MD[2];
        cin>>MD[0]>>MD[1];

        // 数字和の最大値は 200*9 = 1800 程度
        // M,D それぞれで数字和をカウントしておいて、和が一致するものの数をかければ良い

        // 大きい方の桁から下ってやることで DP 場合分けを減らす
        vector<vector<ll>> dpMD[2];
        REP(l,2)
        {
            auto &dp = dpMD[l];
            dp = vector<vector<ll>>(2,vector<ll>(2001,0));

            const auto &S = MD[l];
            dp[1][S[0]-'0'] = 1;
            REP(x,S[0]-'0') dp[0][x] = 1;

            FOR(i,1,S.size())
            {
                vector<vector<ll>> tmp(2,vector<ll>(2001,0));
                REP(x,10)
                for (int j = 0; x+j <= 2000; ++j)
                {
                    if (x < S[i]-'0')
                    {
                        REP(k,2)
                            (tmp[0][x+j] += dp[k][j]) %= Mod;
                    }
                    else if (S[i]-'0' == x)
                    {
                        REP(k,2)
                            (tmp[k][x+j] += dp[k][j]) %= Mod;
                    }
                    else
                    {
                        (tmp[0][x+j] += dp[0][j]) %= Mod;
                    }
                }
                dp = tmp;
            }
        }
        ll cnt = 0;
        REP(k,2)
        REP(j,2)
        REP(i,2001)
        {
            // i が一致するもの同士の組み合わせを数える
            (cnt += dpMD[0][j][i]*dpMD[1][k][i]%Mod) %= Mod;
        }
        // 0000...0 のケースを取り除く
        cout<<(cnt-1+Mod)%Mod<<endl;
    }
};

No.176 2種類の切手

No.176 2種類の切手 - yukicoder

• アルゴリズム的には全探索なのだけど、計算量見積もりがうまくできなかった。
• 最適化対象式の対称性に気がつけば O(√T) 計算量が導きだせたかも。
• T-m*B >= 0 の判定が抜けてしまった...。

class TwoKindsOfStamp
{
public:
    ll roundUp(ll a, ll b) {
        ll x = ceil((double)a/b);
        return (x>=0)? x : 0;
    }
    void solve(void)
    {
        ll A,B,T;
        cin>>A>>B>>T;

        // f(n,m) = n*A + m*B >= T
        // を満たす f(n,m) の最小値をもとめればよい
        //
        // A,B < 10^9 なので単純な全探索では間に合わない。
        //
        // m を固定してみる。このとき条件をみたすには n は
        // n >= (T - m*B)/A
        // n >= ceil((T-m*B)/A)
        // を満たす必要がある。
        //
        // よって m を固定したときのとりうる f(n,m) の最小値は
        // f(n,m) = ceil((T-m*B)/A)*A + m*B
        //
        // m > T/B を超えると T-m*B < 0 になってしまうので m <= T/B まで探索すればよい。
        // このままだと B が小さいときは T < 10^9 のままなので間に合わない
        //
        // そこで m > A のときを考える
        // f(n,m) = n*A + (m'-A*k)*B  (m = m'-A*k, k >= 1)
        //        = (n-B*k)*A + m'*B (m' < A)
        // とかけるので m <= A と見なしてよい
        //
        // よって探索上限は min(T/B,A) となり
        // T/B == A つまり O(√T) < 10^4 にて計算できる。

        // A,B > T のケースもあるので +1 して計算する
        ll ret = max((T/A+1)*A, (T/B+1)*B);
        for (ll m = 0; m <= min(T/B+1,A); ++m)
        {
            ll x = roundUp(T-m*B,A)*A + m*B;
            ret = min(ret,x);
        }
        cout<<ret<<endl;
    }
};

No.171 スワップ文字列(Med)

No.171 スワップ文字列(Med) - yukicoder

• 組み合わせ計算問題
• 解くべき式は単純なんだけど、1/a! mod 573 をどう計算するか悩んだ。573 が素数のようなケースは過去にやったことがあったんだけど。
• 式変形して nCr の積に帰着させればよい。
• 最後の -1 部分でうっかり count=0 のケースで WA してしまった。こういうつまらないミスは本当になくしたいな....。

class SwapStringMed
{
public:
    void solve(void)
    {
        string S;
        cin>>S;

        const int Mod = 573;

        int N = S.size();
        map<int,ll> cnt;
        for (auto c : S)
        {
            cnt.emplace(c,0);
            ++cnt[c];
        }

        // 隣同士の swap だけ並び替えを表現できる
        // a,b,...,c をそれぞれのアルファベットの出現数として
        // N!/(a!b!...c!) を計算すればよいだけ

        // mod 込みの 1/a! 計算をする必要がある。
        //
        // nCr = n!/(r!(n-r)!) より
        // N!/(a!b!) = N!/(a!(N-a)!) * (N-a!)/b!
        //           = NCa * (N-a)Cb * (N-a-b)!
        //
        // と nCr で表現できるのでこれを計算すればよい
        nComb nCr(N, Mod);

        ll count = 1;
        for (auto c : cnt)
        {
            int a = c.second;
            (count *= nCr(N,a)) %= Mod;
            N -= a;
        }
        // (a+b+...+c = N より最後の (N-a-b)! = 0! = 1 となる)

        // 最初の文字列はのぞく(count=0 のときもあるので +Mod してから %Mod しておく)
        cout<<(count+Mod-1)%Mod<<endl;
    }
};

No.168 ものさし

No.168 ものさし - yukicoder

• 二分探索を使う問題
• 10^9 まである座標を hypot につっこんで計算して精度落ちしてしまった...。
• あと何気に最後の cout で long long にキャストせずに WA してしまった...。出力時にキャストしわすれないようにしよう。

class Ruler {
public:
    void solve(void) {
        int N;
        cin>>N;

        vector<ll> xs(N);
        vector<ll> ys(N);
        REP(i,N)
        {
            cin>>xs[i]>>ys[i];
        }

        vector<vector<ll>> dist(N,vector<ll>(N,0));
        REP(i,N)
        REP(j,i+1)
        {
            ll dx = xs[i]-xs[j];
            ll dy = ys[i]-ys[j];
            // (10^9)^2 を double で扱うと精度落ちするので二乗距離として long long で扱う
            dist[i][j] = dist[j][i] = dx*dx+dy*dy;
        }
        ll low = 0;
        ll high = 2*1E+9+1;

        vector<bool> vis(N,false);
        while (low+1 < high)
        {
            ll mid = (low+high)/2;

            fill(RANGE(vis),false);
            function<void(int)> dfs = [&](int v) {
                vis[v] = true;
                REP(u,N)
                {
                    if (vis[u])
                        continue;
                    if (dist[v][u] > mid*mid)
                        continue;
                    dfs(u);
                }
            };
            dfs(0);
            if (vis[N-1])
                high = mid;
            else
                low = mid;
        }
        cout<<(ll)ceil(high/10.0)*10<<endl;
    }
};