NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ，自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので，過去にブックマークされた記事は URL が変わってしまっている可能性があります……．

yukicoder No.1001 注文の多い順列

競技プログラミング (問題解説)

問題: No.1001 注文の多い順列 - yukicoder

writer 解説: yukicoder

問題概要

$1$ 以上 $N$ 以下の整数の順列 $p_1, p_2, ... p_N$ であって，以下の条件を満たすものの数を $10^9+7$ で割った余りを求めよ。

  • すべての $i (1 \leq i \leq N)$ について以下を満たす。
    • $t_i = 1$ ならば $p_i \geq X_i$
    • $t_i = 0$ ならば $p_i \leq X_i$

解法概要

仮に条件が $t_i = 0$ のもののみであった場合，以下のようにして解ける。

  1. 条件を $X_i$ の昇順にソートする。ソート後のインデックスを $i' (1 \leq i' \leq N)$ とする。
  2. すべての $i'$ について，$\max(0, (X_i' - (i'-1)))$ の積をとる。 ($i'-1$ はこれまでに置いた要素の数にあたる)

例えば， $X_1 = 2, X_2 = 3, X_3 = 3$ ですべての $i$ について $t_i = 0$ であれば，$X_1 = 2$ については 1 か 2 を置くことができるので選択肢は2個，$X_2 = 3$ については 3 以下の整数が置けるが 1 か 2 はすでに使ってしまったので選択肢は $3-1=2$ 個，$X_3 = 3$ については 3 以下の整数が置けるが 2以下の整数 1 個と3以下の整数1個の計2個は使ってしまったので選択肢は $3-2=1$個，よって条件を満たす順列の数は $2 \times 2 \times 1 = 4$ 個，と求められる。

しかし今回は，$t_i = 0$ の条件と $t_i = 1$ の条件の両方が存在する。ただし，$t_i = 1$ の条件は反転させると $p_i \leq X_i-1$ と，$t_i = 0$ の条件と同じ形にすることができる。$t_i = 1$ の条件を反転させたものを利用すると，

($t_i = 0$ の条件をすべて満たし，かつ$t_i = 1$ の条件を反転させたものを1つも満たさない順列の数)

= ($t_i = 0$ の条件をすべて満たす順列の数) - ($t_i = 0$ の条件をすべて満たし，かつ$t_i = 1$ の条件を反転させたものを1つでも満たす順列の数)

のようにして数えることができる。条件がすべて $\leq$ の形をしていれば最初に述べたような方法で数えることができるので，$t_i = 0$ の条件そのものおよび $t_i = 1$ の条件を反転させたものを昇順にソートした後，DP で数える。

$ \mathit{dp}_{i, j} = i$ 個目の条件まで考慮済みで，そのうち $j$ 個の条件を満たす場合の配置の仕方の数

と定義し配る DP を考えると，条件を満たす場合の遷移は，

$\mathit{dp}_{i+1, j+1} = \mathit{dp}_{i+1, j+1} + \mathit{dp}_{i, j} \times \max(0, X_i -j)$ ($j$ 個配置済みなので)

となり，条件を満たさない場合の遷移は

$\mathit{dp}_{i+1, j} = \mathit{dp}_{i+1, j} + \mathit{dp}_{i, j}$

となる。ただし，$ t_i = 0$ の条件については条件を満たすものしか考えないので条件を満たさない場合の遷移は行わない。

すべての遷移の後に，$\mathit{dp}_{n, j}$ に対して $(n-j)!$ をかけた数が数えたい順列の数になる。

包除原理を使って

($t_i = 0$ の条件をすべて満たす順列の数)

$-$ ($t_i = 0$ の条件をすべて満たし，かつ$t_i = 1$ の条件を反転させたものを1つ満たす順列の数)

$+$ ($t_i = 0$ の条件をすべて満たし，かつ$t_i = 1$ の条件を反転させたものを2つ満たす順列の数)

$-$ ($t_i = 0$ の条件をすべて満たし，かつ$t_i = 1$ の条件を反転させたものを3つ満たす順列の数)

$\dots$

のように足し合わせたものが答え。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

using ll =  long long;
using Pii = pair<int, int>;

constexpr ll MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<Pii> p(n);
    int min_cnt = 0;
    for(int i=0;i<n;++i) {
        cin >> p[i].second >> p[i].first;
        if(p[i].second == 1) {
            --p[i].first;
        } else {
            ++min_cnt;
        }
    }
    sort(p.begin(), p.end());

    vector<vector<ll>> dp(n+1, vector<ll>(n+1, 0));
    dp[0][0] = 1;
    for(int i=0;i<n;++i) {
        for(int j=0;j<=i;++j) {
            if(p[i].second == 1) {
                dp[i+1][j] += dp[i][j];
                dp[i+1][j] %= MOD;
            }
            dp[i+1][j+1] += dp[i][j] * max(0, p[i].first-j) % MOD;
            dp[i+1][j+1] %= MOD;
        }
    }

    ll fact[n+1];
    fact[0] = 1;
    for(int i=1;i<=n;++i) fact[i] = (fact[i-1] * i) % MOD;

    ll ans = 0LL;
    for(int i=min_cnt;i<=n;++i) {
        if((i-min_cnt) % 2) {
            ans += MOD - dp[n][i] * fact[n-i] % MOD;
        } else {
            ans += dp[n][i] * fact[n-i] % MOD;
        }
        ans %= MOD;
    }
    
    cout << ans << endl;
}

所感

包除原理を使うための材料を DP で揃える問題を通したのは初めてかもしれない？

汎用性たかそう。

ゆるふわ競技プログラミングオンサイト at FORCIA #3 writer料は初任給に含まれます 参加 (作問) 記

参加記 (イベント・勉強会等) 競技プログラミング (雑記)

ゆるふわ競技プログラミングオンサイト at FORCIA #3 writer料は初任給に含まれます - connpass に writer として参加しました。writer をやるのは初めてでした。記憶が薄れないうちに感想など書き殴りたいと思います。

コンテストページと解説はこちらです。

目次

1月

もうバラしてしまったので書きますが私は今年の4月から，M1 のときのインターン先であり，今回含む今まで3回のゆるふわオンサイトの会場でもある フォルシア株式会社 に就職します。御社といえばゆるふわオンサイト (かなり語弊がある) 。ということで，「今年の春 (冬) はゆるふわオンサイトやるのかな」「やるんだったら今度こそ参加したいな」*1「あと準備のお手伝いでもさせてもらって入社してからちゃんと動けるようにしようかな」などと漠然と考えていました。

しかし 1/28，あるリプライで状況が一変します。

修論と両立できるのか，そもそも私に問題が作れるのかの2点で多少悩みましたが，割とすぐに writer をやることに決めました。2020 年の目標の記事 で

競プロの作問をする

(略)

オンサイトコンテスト or イベントに運営側で関わる (これは趣味の方に入れてもいいかもしれないけど)

などと書いていたことを思い出したのが後押しになりました。

writer をやることが決まってからは，作問の大まかな流れなどを他の人の記事を読んで勉強しながら，原案を作りました。特に参考にしたのは以下の記事です。

1月末の地点で Median Permutation, Coupons, Bananas Multiplier の原案が生えていました。もう1つか2つ生やしていた気もしますが，ボツにしました。 てんぷらくんのほうでも Banana Game，Sweets Distribution, Yet Another Cake Division, Digit Sum Multiple の原案が生えていて，Div. 2 only の問題を除く全問題の原案が出揃いました。

それと，サブタイトルの「writer料は初任給に含まれます 」が決まったりイベントの conpass ページが公開されたのもこの辺り。今回のサブタイトルを考えたのはもう一人の writer であるてんぷらくんです。ユーモアのレートも赤くらいありそう。

見るたびに申込者が増えていて，私の曖昧な記憶だと 80 人近くの方に申し込んでいただけていたんじゃないかと思います (本当にありがとうございます)

2月

2/6 までは修論発表に追われていて，その後に本格的な作業を開始しました。私が修論発表に追われている間に席が 36 人から 55 人に増席されていたりもしました。すごい。

この地点で writer である私のレートが中央値未満であるコンテストになる可能性が高いことがわかってゆるふわとは……？　となっていました。

修論発表後は，問題セットと Div 分けを仮確定させ，rime やtestlib を使ってテストケース，generator，validator，writer 解や tester 解を書いたりしていました。多分いろんなところで言われてることではありますが rime の使い方は beet さんの記事 を参考にしつつ実践して，てんぷらくんにアドバイスをもらって，を繰り返しました。

この辺の作業で，てんぷらくんは人に仕事を教えるのがうまいなあと思いました。例えば，最初にやるべきことの全体像を Slack にまとめて教えてくれたり，テストケースや writer 解を書きやすそうな問題 (今回は New Comers や Median Permutation) を使って OJT 的に仕事の流れを掴ませてくれたりとか。

セットのバランス的に 300-400 くらいの全探索問題を生やそうとしていたのですがなかなか生えず，抽選で参加者が決まったさらに後になんとか Books Rotation を生やしました。

問題が一通りできてから，tester のこるとんさんに問題を解いてもらいました。この地点で 2/21 とかだったと思います。こるとんさんからもらった指摘のおかげで問題文やサンプル，テストケースのクオリティが向上しました。ちなみにですが，こるとんさんに言われなければ Books Rotation のサンプル 3, 4 は存在しませんでした。その場合，各列の要素をカウントしただけでサンプルは通るが AC はしないという茶色あたりの方にとって意地の悪い問題になっていたかもしれません……。

当日

Prize が決まったのが前日だったので，朝からコンビニにプーさんを買い求めに行っていました。人気商品っぽいですし数日前に発売されたばかりなのでセブンイレブン5店舗ツアーを覚悟していましたが，1軒目6プーさん揃ってよかったです。

少し早めに会場に行ってOrganizer の matsu さん，社員枠の prd さん，tester のこるとんさん，参加者でお手伝いをしてくれていた nanae さんと一緒に会場準備をしました。重いテーブルを移動して並べたり，使わないものを別の場所に動かしたりなどの肉体労働でしたが，それなりにスムーズに終わりました。初回はこの準備を matsu さん一人でやっていたそうですが，あまりに偉大すぎる。

人が来始めると，流石に不安感がごまかせなくなってきました。私の問題で炎上したらどうしようとか，問題の不備で楽しくないコンテストになったらどうしようとか。

しかし実際のコンテスト中にはそんなこともなく，ほぼ平和に順位表観戦をして終わりました。Books Rotation のサンプル 0 の説明が間違っていたのでそこは申し訳ありませんでしたが，Clar をくれた方に感謝です。

解説はについては，ああいう，あんまりかっちりしてないカジュアルな場でプレゼンするのは得意ではないのですが，和やかな雰囲気で比較的フランクに話すことができてよかったです。Median Permutation で詰まった Div. 1 の方々を無自覚に煽ってしまったのはすみません……。

懇親会は約50人もの競プロer が1つの会議室に集合してワイワイ話していてすごかったです (小並感) 。懇親会では人との会話に入っていくのがなかなか大変だと思っているのですが，楽しそうな顔をしている人が多くてホッとしました。「Median Permutation が面白かった」と言ってくださる方が多くて嬉しかったです。しかし私個人の振る舞いとしては，「孤立する人を作らせない」「話したい人に話しかけにいく」のいずれも反省点が残るところなので，今後はコミュニケーションも要精進です。

Noimin がwriter の問題について

解かれ具合とか解法は解説スライドに書いたので，問題の生い立ちでも書こうかと。

Coupons

懇親会といえばピザ！　なので，懇親会の準備をする matsu さんに思いを馳せて作った問題です。 灰色の人が頑張れば解けて，茶色の人が気持ちよく解けるくらいの難易度感を目指しました。

Books Rotation

セット内に全探索問題がない気がして，ちょうどいい全探索の問題を生やそうと頑張りました。

読解も実装も面倒なので，最も心配していたのがこの問題でした。が，みなさん意外と解けている。参加者の実装力を見くびっていましたかもしれません。

Median Permutation

最初にできた問題です。 DEGwer 式作問法 (最初に操作や性質を定義してそれをいじる) で作りました。

作問当初は構築 (条件を満たす数列を1つ作る) でしたが，数え上げになりました。難しくなるので出題はしませんでしたが，辞書順最小を出すという案もありました。

懇親会で面と向かって言及してもらった回数はこの問題が一番多かったです。

Bananas Multiplier

実装寄りの問題が好きなので作ろうと思っていて，原案自体はすぐに生えたのですが，問題上での設定に苦労した問題です。

結果，matsu さんと prd さんがバナナを増やすという謎の問題になりました。 増やしたバナナは Banana Game で使ってもらえてよかったです (?)

ダブリングで LCA を求めるアルゴリズムは個人的には好きなアルゴリズムの1つです。

Noimin が test した問題について

私が test した問題も最終的にはこるとんさんに改めて test していただいたので「Noimin が tester の〜」とは書きませんでした。

Yurufuwa Division

ゆるふわオンサイトのレート分けにちなんだ問題。非常にシンプルな問題なので，この問題を通してtester 業務を教わりました。

New Comers

初心者向けかつ3回目のゆるふわオンサイトにふさわしい良問。標準で備わっているデータ構造を使うのは大事です。

Banana Game

頭でゲームをこねくり回しているうちは何日も悩んだのに，それなりの規模の実験をしたらすぐに見えてきた問題。Grundy 数の式の中に山の中のバナナと激辛バナナの数の差の偶奇が現れていてちょっと不思議でした。その意味を考えるのも楽しいので，好きな問題です。

最初はバナナを使っていないゲームだったのにいつの間にかバナナと激辛バナナを食べるゲームになっていて笑いました。

その他

本当に多くの方々のおかげで，楽しい writer デビューになりました (楽しいは「writer」ではなく「デビュー」にかかっています) 。

オンサイトコンテスト作りにご協力いただいた株式会社フォルシアの方々や参加者の皆さん，本当にありがとうございました。

特に，Organize をほぼ1人でやっていた matsu さん，writer / tester のやることを手取り足取り教えてくれたもう1人の writer のてんぷらくん，テスターとして数々の本質的指摘をくれた上に何故か会場準備/片付けも手伝ってくれたこるとんさんには頭が上がりません。

次回 (夏の終わり〜秋頃？) は Noimin 回になりそうなので，今からネタ出し頑張ります。

ところで， prd さん回はバナナ，てんぷらくん回はプーさんが Prize でしたが，Noimin 回はどうなるんでしょう……？

*1:前回は申し込んでいたものの，インフルエンザに罹ってしまいキャンセルしました。

Codeforces Round #620 (Div. 2) E - 1-Trees and Queries

競技プログラミング (問題解説)

問題: Problem - E - Codeforces

公式解説: Codeforces Round #620 (Div. 2) Editorial - Codeforces

問題概要

$n (3 \leq n \leq 10^5)$ 頂点の無向木が与えられる。次のクエリに $q (1 \leq n \leq 10^5)$ 回答えよ。

  • 頂点 $x$ と頂点 $y$ の間に辺を追加する。このとき，頂点 $a$ と頂点 $b$ の間に $k (k \leq 10^9)$ 本の辺を通るパスは存在するか？

ただし，同じ辺を何度通ってもよく，辺の追加はクエリごとにリセットされる。

解法概要

追加した辺を使わないパスについてのみ考えてみる。

与えられるグラフは木なので，頂点 $a$，$b$ 間について最短路はただ1つ存在する。また，最短路以外の頂点 $a$，$b$ 間のパスについても，最短路から外れる→最短路に戻ってくるという手順によるパス長の伸ばし方しかできない。最短路から外れて戻ってくるときのパスは行きと帰りで同じになる。したがって，追加した辺を使わない場合は頂点 $a$，$b$ 間のパス長の偶奇を変えることはできない。よって，頂点 $a$，$b$ 間の最短路が $k$ 以下であり，かつ頂点 $a$，$b$ 間の最短路と $k$ の偶奇が一致する場合， YES が確定する。

YES が確定しない場合，追加した辺を使うパスについて考える必要がある。

追加した辺を使うパスの使い方は2種類に分けられる。

  1. $a$ から $x$ に行き，追加した辺を通って $y$ に行き，　$y$ から $b$ に行く
  2. $a$ から $y$ に行き，追加した辺を通って $x$ に行き，　$x$ から $b$ に行く

この2種類のパス長 $d$ について， $d \leq k$ でかつ $d$ と $k$ の偶奇が一致するという条件を満たすものがあれば YES が確定する。

ここまでで YES が確定しなければ NO である。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

constexpr int N_MAX = 100000;

vector<int> graph[N_MAX];

class LowestCommonAncestor {
    public:
    int root, n, LOG_V_MAX = 30;
    vector<int> depth;
    vector<vector<int>> parent;

    LowestCommonAncestor(int root=0, int n=N_MAX): root(root), n(n) {
        depth.assign(n, -1);
        parent.assign(n, vector<int>(LOG_V_MAX, -1));
        dfs(root, -1, 0);
        for(int j=1;j<LOG_V_MAX;++j) {
            for(int i=0;i<n;++i) {
                if(parent[i][j-1] == -1) continue;
                parent[i][j] = parent[parent[i][j-1]][j-1];
            }
        }
    }

    void dfs(int node, int par, int d) {
        depth[node] = d;
        parent[node][0] = par;
        for(auto child: graph[node]) {
            int c = child;
            if(c == par) continue;
            dfs(c, node, d+1);
        }
    }

    int get_lca(int u, int v) {
        if(depth[u] > depth[v]) swap(u, v);
        int depth_diff = depth[v] - depth[u];
        for(int j=0;j<LOG_V_MAX;++j) {
            if(depth_diff & (1 << j)) {
                v = parent[v][j];
            }
        }
        if(u == v) return u;
        for(int j=LOG_V_MAX-1;j>=0;--j) {
            if(parent[u][j] != parent[v][j]) {
                u = parent[u][j];
                v = parent[v][j];
            }
        }
        return parent[u][0];
    }
    
    int get_dist(int u, int v) {
        return depth[u] + depth[v] - 2*depth[get_lca(u, v)];
    }
};

void solve(LowestCommonAncestor &lca) {
    int x,y,a,b,k;
    cin >> x >> y >> a >> b >> k;
    --x; --y; --a; --b;
    int xy = lca.get_dist(x, y), ab = lca.get_dist(a, b);

    if(ab <= k && k % 2 == ab % 2) {
        cout << "YES\n";
        return;
    }
    int d = lca.get_dist(a, x) + 1 + lca.get_dist(y, b);
    if(d <= k && d % 2 == k % 2) {
        cout << "YES\n";
        return;
    }
    d = lca.get_dist(a, y) + 1 + lca.get_dist(x, b);
    if(d <= k && d % 2 == k % 2) {
        cout << "YES\n";
        return;
    }
    cout << "NO\n";
    return;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i=0;i<n-1;++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    LowestCommonAncestor lca = LowestCommonAncestor();

    int t;
    cin >> t;
    while(t--) {
        solve(lca);
    }
}

所感

サイクル長の偶奇が〜サイクルの中で $a$ と$b$ に最も近い頂点は〜とか言って泥沼にはまっていたけど，追加した辺を使うかどうかで分けて考察するとすっきりするね。