Shuz*'s Blog

事象の性質を考察する

TPC_20200804 (Codeforces Round #245 (Div. 2))

1:09 4完
ちょっと参加が10分くらい遅くなってしまった。

Aを見る。ただでさえ問題文がわかりにくい上、変数が衝突していて読み解くのに時間がかかったが、適当に交互にすると問題の性質を満たすと分かったので提出。 (0:16 WA)
ソートを忘れていたのでなおす。 (0:22 AC)
Bを見て、適当にシミュレーションできるので書く。色々バグらせたが、とりあえずできたので提出。 (0:39 AC)
Cを見て、偶奇に気をつけて根からDFSするだけなので書いて提出。 (0:49 AC)
Dを見て、よくある両方からの累積DPなので書く。 (0:59 RE)
添字ミスはないし、メモリも大丈夫そうなので、とりあえず原因になってそうなpragmaを消して提出。 (1:03 WA)
なんか問題の解釈が間違ってそうなので、よく読んで簡単な考察をしなおして書きなおす。 (1:09 AC)
Eを見て、初歩的な考察だけはできるけど全く解法が浮かばないのであきらめ。

EのDifficultyは3000らしい。わからん。

TPC_20200721 (Codeforces Round #304 (Div.2))

2:01全完←間に合ってない

Aを眺めると数学 O(1) なので提出する (0:01 AC)
Bの制約を眺めると優先度付きキューでシミュレーションしたら通りそうなので提出する (0:07 AC)
Cを見て、なんか面倒そうなので先にDを見る
Dを見ると、ただのエラトステネス+累積和なので提出する (0:18 RE)
配列の大きさを1桁ミスっていたので、再提出する (0:19 AC)
Cを適当にループ回して判定する解法(未証明)を提出するもWA (0:42 WA)
未証明なので悩んだ末、わからないのでEも見たりしながらCの考察をする
よく見ると出力を誤読していたので、直してとりあえず未証明だけど提出する (1:15 AC)
Eを見て、よくよく見ると適当にフロー流せば良いことがわかったので提出する (2:01 AC)

yukicoder No.944 煎っぞ! 解説

No.944 煎っぞ! - yukicoder

問題概要

A_1,\ \cdots,\ A_N をいくつかに区切ってすべての区間和を等しくするとき、区切った区間数の最大値を求めよ。

解法

Writer解とは違うアプローチをしたので軽く解説する。
まず、最も左の区間を決め打ちすると、その区間は全部で N 個存在する。
最初の区間に選んだ区間の長さを i とすると、区間和を等しくできるかどうかを左から順に試すのにかかる回数は O\left(\frac{N}{i}\right) であり、累積和と二分探索を用いれば一回あたり O\left(\log N\right) でできるから、調和級数になって全体で O\left(N {\log}^2 N\right) で求められる。

提出コード

 

感想

一瞬でこれを思いついたので簡単だった。

ソートする系の貪欲証明 part.1

Minimum(Maximum) Scalar Product

与えられた 2 つの実ベクトル A=(A_1,\ A_2,\ \dots,\ A_n),\ B=(B_1,\ B_2,\ \dots,\ B_n) に対して適当な \sigma_a,\ \sigma_b を選び、 (A\sigma_a)\cdot (B\sigma_b)=A_{\sigma_a(1)}B_{\sigma_b(1)}+A_{\sigma_a(2)}B_{\sigma_b(2)}+\cdots+A_{\sigma_a(n)}B_{\sigma_b(n)} を最小・最大化する問題。解法は、最小の場合は A,\ B をそれぞれ昇順、降順に、最大の場合は A,\ B をそれぞれ昇順にソートするだけである。 蟻本に証明が載っているが、ちょっとだけ飛躍を感じたので補足になればと思う。

最初に最大化問題を考える。
簡単のため A,\ B をそれぞれ昇順にソートしておく(すなわち、 A_1\le A_2\le\dots\le A_n,\ B_1\le B_2\le\dots\le B_n となるよう並び替える)。
また、 \sigma_a は恒等置換とする。

まず、以下の補題はすぐにわかるだろう。
補題 I
x\le X,\ y\le Y のとき、 Xy+xY\le XY+xy
【証明】
(XY+xy)-(Xy+xY)=(X-x)(Y-y)\ge 0

さて、 i\lt j かつ (B\sigma_b\sigma_1\sigma_2\cdots\sigma_{k-1})_i\gt (B\sigma_b\sigma_1\sigma_2\cdots\sigma_{k-1})_j となる i,\ j が存在する間、k 回目には B\sigma_b\sigma_1\sigma_2\cdots\sigma_{k-1} に i と j の交換 \sigma_k を掛けて、 m 回の交換の後 i\lt j かつ B_{\sigma_b(i)}>B_{\sigma_b(j)} となる i,\ j が存在しなくなったとする。
このとき、 B\sigma_b\sigma_1\sigma_2\cdots\sigma_m=B が満たされている (すなわち、B\sigma_b\sigma_1\sigma_2\cdots\sigma_m は昇順にソートされている)。
ここで、補題 Iより、(A\sigma_a)\cdot(B\sigma_b)\le(A\sigma_a)\cdot(B\sigma_b\sigma_1)\le (A\sigma_a)\cdot(B\sigma_b\sigma_1\sigma_2)\le\cdots\le(A\sigma_a)\cdot(B\sigma_b\sigma_1\sigma_2\cdots\sigma_m)=A\cdot B であるから、任意の \sigma_b に対して (A\sigma_a)\cdot(B\sigma_b)\le A\cdot B が言え、すなわち A\sigma_a,\ B\sigma_b が昇順のとき (A\sigma_a)\cdot (B\sigma_b) が最大になることが言える。

最小の場合も同様にして、 A\sigma_a を昇順、 B\sigma_b を降順にすれば良いことがわかる。

木の最大マッチングと貪欲法の最適性証明

はじめに

木の最大マッチングとは、直接辺で結ばれたいくつかの 2 頂点の組 ( 「ペア」と呼ぶ ) からなる集合であって、どの頂点も高々 1 つのペアに属するようなもののうち、もっともペアの多いものを言う。ここでは、木の最大マッチングが、再帰的に葉を選ぶことによって構成できることを示す。

木を辺集合としてみる

木の最大マッチングは、木の最大安定「辺」集合と言い換えられる。さて、ある木に対して、各辺に e_1,\ e_2, ... とラベル付けをしてみよう。そして木を、辺を要素とする集合とみなしてみる。このとき、頂点は「辺の部分集合」と言い換えられる。

このとき木の最大安定「辺」集合は、以下のように言い換えられる。

  • 「各頂点、つまり辺の部分集合に対して、高々 1 つの辺だけを選べる」という制約の中で、もっとも多くの辺を選ぶ方法。

f:id:Shuzaei:20190903193020j:plain
木の最大マッチング

貪欲法の言い換え

木の最大マッチングの貪欲法は次のように構成できる。

  1. 葉であり、かつ隣にも頂点があるような頂点を一つ選び、隣の頂点とペアを構成する。このような頂点が存在しない場合は終了。
  2. その後、ペアになった頂点とそれらに隣接する辺を木から削除し、1. に戻る。

先ほどの言い換えにおいて、葉の頂点の辺集合を無視して考えると、「辺の片方の頂点が葉である」 \Longleftrightarrow 「辺はただ 1 つの頂点、つまり辺の部分集合に属する」となる。

さて、明らかに、辺がただ 1 つの部分集合に属する場合、その部分集合でその辺を選ぶことが最適である ( 各集合に対して高々 1 つの辺しか採用できないため ) 。したがってこの辺を選ぶ貪欲法は最大マッチングを構成できる。

例題

これでやっと、AtCoder Grand Contest 029 B - Powers of Two を安心して解ける ( 葉から貪欲にやればよい ) 。

yukicoder No.10 ＋か×か

No.10 ＋か×か - yukicoder

問題概要

1 列に並んだ数列 \langle A_i\rangle を順番を変えずに加法・乗法で結び、 Total に等しくなるように式を作る。ただし演算は左から順に行うものとし、辞書順最小の演算子列を求める。

解法

文字列を持ってDP。計算量がちょっとだけ大きいがまあ間に合う。 文字コードが '*' \lt '+' \lt '.' であることを利用した。

int main() {
    ll N, M;
    cin >> N >> M;
    ll A[N];
    rep(i, N) cin >> A[i];
    string DP[N][M + 1];
    DP[0][A[0]] = ".";
    rep(i, N - 1) {
        rep(j, M) {
            if (j + A[i + 1] <= M) {
                chmax(DP[i + 1][j + A[i + 1]], DP[i][j] + '+');
            }
            if (j * A[i + 1] <= M) {
                chmax(DP[i + 1][j * A[i + 1]], DP[i][j] + '*');
            }
        }
    }
    cout << DP[N - 1][M].substr(1, DP[N - 1][M].size() - 1) << endl;
}

yukicoder No.9 モンスターのレベル上げ

No.9 モンスターのレベル上げ - yukicoder

問題概要

味方モンスター(レベルはそれぞれ A_i )を以下の方法でレベル上げするとき、各味方モンスターのレベル上げ最大回数の最小を求める。

  1. 最初に、円形に並んだ敵モンスターの始点を定める。
  2. 始点から順(添字の昇順)に、以下を満たすように選ばれた味方モンスターのレベルを、敵モンスターのレベルの半分 \lfloor \frac{B_i}{2}\rfloor だけ上げる。
  3. 味方モンスターは、現時点でレベルが最小のものから任意に 1 匹選べる。
  4. 敵モンスターを 1 周したら終了。
解法

愚直にシミュレーションする。優先度付きキューを利用して、レベルとレベル上げ回数が常に昇順になるようにしておく。

inline constexpr ll modulo(const ll n, const ll m) noexcept {
    if (n < 0) {
        return n % m + m;
    } else if (n >= m) {
        return n % m;
    } else {
        return n;
    }
}

int main() {
    ll N, res = INF;
    cin >> N;
    ll A[N], B[N];
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i], B[i] /= 2;
    rpriority_queue<pair<ll, ll>> P;
    rep(i, N) {
        rep(i, N) P.push({A[i], 0});
        rep(j, N) {
            ll id = modulo(i + j, N), lv, n;
            tie(lv, n) = P.top(), P.pop();
            P.push({lv + B[id], n + 1});
        }
        ll max = 0;
        while (P.size()) {
            ll lv, n;
            tie(lv, n) = P.top(), P.pop();
            chmax(max, n);
        }
        chmin(res, max);
    }
    cout << res << endl;
}