はまやんはまやんはまやん

hamayanhamayan's blog

エレベーター [yukicoder No.801]

https://yukicoder.me/problems/no/801

解法

https://yukicoder.me/submissions/325930

dp[k][floor] := k回移動後にfloor回にいる組合せ
でDPしよう。
dp[k][???]からdp[k+1][???]を高速に更新することを考えよう。
 
まずは、愚直解から作る。
あるエレベータmを使うとしたときに、
dp[k+1][x] += sum{y=L[m]...R[m]}dp[k][y]
L[m]≦x≦R[m]
という遷移となることが分かる。
これを高速化したいのだが、sum{y=L[m]...R[m]}dp[k][y]の部分は慣れていると、累積和でいけるなと気づく。
しかも重要なことに、この値は、あるエレベータmによって固定の値になっている。
つまり、sumの値をdp[k + 1][L[m]], dp[k + 1][L[m]+1], ..., dp[k + 1][R[m]]に一律足していることになる。
この一律に足す操作はimos法を使えば、O(M+N)で実現できる。
 
移動はK回行われるので、O(K(M+N) )となり、これは間に合う。

int N, M, K, L[3010], R[3010];
mint dp[3010][3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(m, 0, M) {
        cin >> L[m] >> R[m];
    }

    dp[0][1] = 1;
    rep(k, 0, K) {
        rep(i, 1, N + 1) dp[k][i] += dp[k][i - 1];
        
        rep(m, 0, M) {
            int l = L[m], r = R[m];
            
            mint sm = dp[k][r] - dp[k][l - 1];

            dp[k + 1][l] += sm;
            dp[k + 1][r + 1] -= sm;
        }

        rep(i, 1, N + 1) dp[k + 1][i] += dp[k + 1][i - 1];
    }

    cout << dp[K][N] << endl;
}

四平方定理 [yukicoder No.800]

https://yukicoder.me/problems/no/800

解説

https://yukicoder.me/submissions/325337

まずはz,wを全列挙しよう。
z,wがわかっていれば、d = w^2 + D - z^2とおくと、
x^2 + y^2 = d
を満たすx,yの組が分かれば、それを答えに足せばいいと分かる。
 
よって、z,wの前にx,yを全列挙して、
cnt[d] := x^2+y^2=dを満たす(x,y)の組
を求めておこう。
cnt[10101010]はギリギリメモリに乗る。

int N, D;
ll cnt[10101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D;

    rep(x, 1, N + 1) rep(y, 1, N + 1) cnt[x*x + y * y]++;

    ll ans = 0;
    rep(z, 1, N + 1) rep(w, 1, N + 1) {
        int d = D + w * w - z * z;
        if (0 < d) ans += cnt[d];
    }
    cout << ans << endl;
}

赤黒かーどげぇむ [yukicoder No.799]

https://yukicoder.me/problems/no/799

解説

https://yukicoder.me/submissions/325296

「全通り-被ってしまった場合」で答えを出す。
全通りは、(B-A+1)*(D-C+1)である。
被ってしまった場合は、同じ数がでてきた場合になるので、[A,B]と[C,D]が重なっている区間を見る。
これは、[max(A,C),min(B,D)]となる。
この区間の長さが同じ数となる組み合わせ数となる。

int A, B, C, D;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C >> D;

    int ans = (B - A + 1) * (D - C + 1);

    int L = max(A, C), R = min(B, D);
    ans -= max(0, R - L + 1);

    cout << ans << endl;
}

【.NET向けライブラリ+アプリ 開発日記 day01】 環境設定

急にどうした?

なんとなく試してみたい開発環境というか開発体制が頭の中で固まってきたので、ちょっと実践したくなった。

題材

競技プログラミングサイトの.NET APIとそれを使ったWPFアプリ

入れたい要素

まずはレポジトリを作る

https://github.com/hamayanhamayan/online-judge-apis-dotnet

とりあえず、MITライセンスでgitignoreはVisual Studioで作った。

f:id:hamayanhamayan:20190317012556p:plain

CI環境 AppVeyorに登録

AppVeyorにとりあえず、登録して、レポジトリを指定しておく。

次は、ソリューションを作る

.Net Standartとか.Net Coreとかどれ向けに作っていいか正直良くわからんので、これで作成。

f:id:hamayanhamayan:20190317012847p:plain

後々残すか分からないけど、適当にクラスを作っておく。
テスト駆動開発するので、テストプロジェクトも作成。
テストプロジェクトの方も、さっき作ったクラスに対して適当にテストしておく。
テストフレームワークはMSTestを使うが、ChainingAssertionだけ入れておく。

f:id:hamayanhamayan:20190317012856p:plain

ちゃんとオールグリーンですね。

Initial Commit!!

正確にはInitialではないが、masterへ初コミット。
どうせ一人だし、形になってくるまではmasterに突っ込んでくことにする。
ここでgithubで何やら❌が出る。

f:id:hamayanhamayan:20190317012913p:plain

Appveyorででているので、見に行ってみる。

Build started
git clone -q --branch=master https://github.com/hamayanhamayan/online-judge-apis-dotnet.git C:\projects\online-judge-apis-dotnet
git checkout -qf 9d55145626512d8371989e979751d6433944e1cb
msbuild "C:\projects\online-judge-apis-dotnet\online-judge-apis-dotnet.sln" /verbosity:minimal /logger:"C:\Program Files\AppVeyor\BuildAgent\Appveyor.MSBuildLogger.dll"
Microsoft (R) Build Engine version 14.0.25420.1
Copyright (C) Microsoft Corporation. All rights reserved.
  online-judge-apis-dotnet -> C:\projects\online-judge-apis-dotnet\online-judge-apis-dotnet\bin\Debug\online-judge-apis-dotnet.dll
C:\projects\online-judge-apis-dotnet\online-judge-apis-dotnet-test\online-judge-apis-dotnet-test.csproj(72,5): error : ??????????????????????? NuGet ???????????????????????????????????[NuGet ????????] ???????????????http://go.microsoft.com/fwlink/?LinkID=322105 ????????????????????? ..\packages\MSTest.TestAdapter.1.3.2\build\net45\MSTest.TestAdapter.props ???
Command exited with code 1

?ばっかりだけど、他の画面で確認すると、NuGetの取得に失敗しているらしい。
ぐぐる解決法がある。

f:id:hamayanhamayan:20190317012939p:plain

これをやると

f:id:hamayanhamayan:20190317012946p:plain

成功してる!

f:id:hamayanhamayan:20190317012957p:plain

テストも成功してるので、満足。
Nugetデプロイがまだ残っているが、CIはできる状態になったので、満足。
doxygenの自動化を先にやりたい気持ちもあるけど・・・
本当はasciidocとかでドキュメント管理(RedPenとかで校正とか)してってシステムも作りたいが・・・
開発始めたくなるよね・・・

Reversi [AtCoder Grand Contest 031 B]

https://atcoder.jp/contests/agc031/tasks/agc031_b

解説

https://atcoder.jp/contests/agc031/submissions/4597345

まず、もともとの数列で同じ色の石が連続していても数え上げには影響が無いので、圧縮しておく。
(自分の実装では一旦ランレングス表現にしているが、どうやってもいい)
 
この状態でDPをする。
dp[i] := i番目の石まで塗り替えが終わっている場合の組合せ
i+1番目の石の色がcだったとする。
すると、i+1番目の石までの塗り替えを考えると、

  • i+1番目の石には何もしない
  • i+1番目以前の石で色がcのものと組合せて塗り替える

という選択が考えられる。
前者の操作は普通にdp[i + 1] += dp[i]である。
 
後者の説明のために、i+1番目以前で色がcの石の添字をj[0], j[1], j[2], ...とする。
i+1番目とj[0]番目で操作を行うと、dp[i + 1] += dp[ j[0] - 1]となる。
なので、dp[i + 1] += dp[ j[0] - 1] + dp[ j[1] - 1] + ... となる。
これはいかにもメモ化できそうな感じがある。
dp[i + 1] += (これまでの色がcの石の1つ前のDPの値の総和)
といえるので、
sm[c] := これまでの色がcの石の1つ前のDPの値の総和
として、メモっておこう。

int NN; vector<int> CC;
mint sm[201010];
mint dp[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> NN;
    rep(i, 0, NN) {
        int c; cin >> c;
        CC.push_back(c);
    }
 
    auto C = runLengthEncoding(CC);
    int N = C.size();
 
    dp[0] = 1;
    rep(i, 0, N) {
        int c = C[i].first;
        dp[i + 1] += sm[c] + dp[i];
        sm[c] += dp[i];
    }
    cout << dp[N] << endl;
}

Differ by 1 Bit [AtCoder Grand Contest 031 C]

https://atcoder.jp/contests/agc031/tasks/agc031_c

解法

https://atcoder.jp/contests/agc031/submissions/4606271

!!注意!!もっとスマートな解法があります!!

まず、"NO"となるのは、AとBで立っているビット数のパリティが一致しているとき。
まずパリティが一致していると駄目なのは、二部グラフっぽく見ると分かる。
これが必要条件な理由は分からない。AC証明した。
 
さて、問題が構築だが、以下の関数を用いて、根性で構築する。
go1(L,R,from,len) := [L,R)の区間でfromを始点として一筆書きした時の終点を返す
go2(L,R,from,to,len) := [L,R)の区間でfromとtoを始点として、それぞれ一筆書きした時の終点を2つ返す
connect2(L,R,from,to,len) := [L,R)の区間でfromとtoをつなぐ、一筆書きをする
これが正しく作れれば、connect2(0,1<<N,A,B,1<<N)で答えが求まる。
上記の関数内では、辺を作りながら、処理を進めている。
以下、中心C=(L+R)/2を説明に使う。
 
connect2関数

  • [L,C)にfromもtoもある場合
    • [L,C)の区間でgo2関数を使って、2本の一筆書きをする
    • それぞれの一筆書きの終点を[C,R)に伸ばして、[C,R)でconnect2関数をやる
  • [C,R)にfromもtoもある場合
    • 同様
  • [L,C)にfrom, [C,R)にtoがある場合
    • 2つの区間をつなぐiとi+len/2間の辺を決めて、connect2関数で、fromとi, i+len/2とtoをつなぐ

 
go1関数

  • [L,C)にfromがある場合
    • [L,C)でgo1関数をやって、でてきた終点から、[C,R)に辺を張って、改めて、go1関数をする
  • [C,R)にfromがある場合
    • 同様

 
go2関数

  • [L,C)にfromもtoもある場合
    • [L,C)の区間でgo2関数を使って、2本の一筆書きをする
    • それぞれの一筆書きの終点を[C,R)に伸ばして、[C,R)でgo2関数をやる
  • [C,R)にfromもtoもある場合
    • 同様
  • [L,C)にfrom, [C,R)にtoがある場合
    • それぞれの区間でgo1関数をやる

 
こうするとグラフが出来上がるので、ここから数列作ると答え。

int N, A, B;
vector<int> E[1 << 17];
//---------------------------------------------------------------------------------------------------
void add(int a, int b) {
    E[a].push_back(b);
    E[b].push_back(a);
}
//---------------------------------------------------------------------------------------------------
void connect2(int L, int R, int from, int to, int len);
int go1(int L, int R, int from, int len) {
    if (len == 1) return from;
    else if (len == 2) {
        if (L == from) {
            add(L + 1, from);
            return L + 1;
        }
        else {
            add(L, from);
            return L;
        }
    }
 
    int C = (L + R) / 2;
 
    // 上にある
    if (from < C) {
        rep(i, L, C) if (i != from) {
            if (__builtin_popcount(i) % 2 != __builtin_popcount(from) % 2) {
                connect2(L, C, min(from,i), max(from,i), len / 2);
 
                add(i, i + len / 2);
 
                return go1(C, R, i + len / 2, len / 2);
            }
        }
    }
 
    // 下にある
    if (C <= from) {
        rep(i, C, R) if (i != from) {
            if (__builtin_popcount(i) % 2 != __builtin_popcount(from) % 2) {
                connect2(C, R, min(from, i), max(from, i), len / 2);
 
                add(i, i - len / 2);
 
                return go1(L, C, i - len / 2, len / 2);
            }
        }
    }
}
pair<int, int> go2(int L, int R, int from, int to, int len) {
    if (len == 2) return { from, to };
 
    int C = (L + R) / 2;
 
    // 上に2つともある
    if (to < C) {
        auto p = go2(L, C, from, to, len / 2);
 
        add(p.first, p.first + len / 2);
        add(p.second, p.second + len / 2);
 
        return go2(C, R, p.first + len / 2, p.second + len / 2, len / 2);
    }
 
    // 下に2つともある
    if (C <= from) {
        auto p = go2(C, R, from, to, len / 2);
 
        add(p.first, p.first - len / 2);
        add(p.second, p.second - len / 2);
 
        return go2(L, C, p.first - len / 2, p.second - len / 2, len / 2);
    }
 
    return { go1(L, C, from, len / 2), go1(C, R, to, len / 2) };
}
void connect2(int L, int R, int from, int to, int len) {
    if (len == 2) {
        add(from, to);
        return;
    }
 
    int C = (L + R) / 2;
 
    // 上に2つともある
    if (to < C) {
        auto p = go2(L, C, from, to, len / 2);
 
        add(p.first, p.first + len / 2);
        add(p.second, p.second + len / 2);
 
        connect2(C, R, p.first + len / 2, p.second + len / 2, len / 2);
        return;
    }
 
    // 下に2つともある
    if (C <= from) {
        auto p = go2(C, R, from, to, len / 2);
 
        add(p.first, p.first - len / 2);
        add(p.second, p.second - len / 2);
 
        connect2(L, C, p.first - len / 2, p.second - len / 2, len / 2);
        return;
    }
 
    rep(i, L, C) if(i != from and i + len / 2 != to) {
        if (__builtin_popcount(i) % 2 != __builtin_popcount(from) % 2) {
 
            add(i, i + len / 2);
 
            connect2(L, C, min(i, from), max(i, from), len / 2);
            connect2(C, R, min(i + len/2, to), max(i + len/2, to), len / 2);
            return;
        }
    }
}
//---------------------------------------------------------------------------------------------------
int vis[1 << 17];
vector<int> ans;
void dfs(int cu) {
    ans.push_back(cu);
    vis[cu] = 1;
    fore(to, E[cu]) if (!vis[to]) dfs(to);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> A >> B;
 
    if (__builtin_popcount(A) % 2 == __builtin_popcount(B) % 2) {
        printf("NO\n");
        return;
    }
 
    int isSwap = 0;
    if (A > B) {
        swap(A, B);
        isSwap = 1;
    }
 
    connect2(0, 1 << N, A, B, 1 << N);
    dfs(A);
 
    printf("YES\n");
 
    if (isSwap) reverse(all(ans));
 
    rep(i, 0, 1 << N) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}

コレクション [yukicoder No.798]

https://yukicoder.me/problems/no/798

解説

https://yukicoder.me/submissions/323864

買うか買わないかという問題なので、ナップサック系DP感があるので、そこから考える。
順番が決まっていない所を考えると、ちょうどパラメタ2つなので、うまくソートして系かなと思いつく。
DPテクの「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」を使う。
 
どのようにソートするかであるが、買うものが既に決まっているときを考えると、傾きがより大きいものから買っていけば最適に買える。
そのため、順番はBで昇順ソートすれば良いと分かる。
後は、買うか買わないかなので、
dp[i][get] := i番目まででget個買うときの最小金額
を普通のナップサックDPで作っていけばいい。
奇数の日に0円で購入できるシステムは商品がN個あった場合は、floor(N/3)個分はそのシステムが使えるので、
買うべき個数はN-floor(N/3)となる。
よって、dp[N][N-floor(N/3)]が答え。

int N, A[2010], B[2010];
ll dp[2010][2010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];

    vector<int> ord;
    rep(i, 0, N) ord.push_back(i);
    sort(all(ord), [&](int a, int b) {return B[a] > B[b]; });

    rep(i, 0, N + 1) rep(get, 0, N + 1) dp[i][get] = infl;
    dp[0][0] = 0;
    rep(i, 0, N) rep(get, 0, N) {
        ll a = A[ord[i]];
        ll b = B[ord[i]];

        chmin(dp[i + 1][get], dp[i][get]);
        chmin(dp[i + 1][get + 1], dp[i][get] + a + b * get);
    }

    cout << dp[N][N - N / 3] << endl;
}