Growth Record of Lettuce Farm

競プロの記録・解説をします

鹿島建設プログラミングコンテスト2020 (ARC110) D - Binomial Coefficient is Fun 解説

競プロ解説 AtCoder

数学問エスパーが成功したときほど気持ちいい瞬間はありません。

問題リンク

https://atcoder.jp/contests/arc110/tasks/arc110_d

問題概要

長さ $N$ の非負整数列 $A$ があります。長さ $N$ 、総和 $M$ 以下の非負整数列 $B$ 全てについて、 $\displaystyle \prod_{i=1}^{N} \binom{B_i}{A_i}$ の総和を $10^9+7$ で割った余りを出力してください。

制約

$1\le N\le 2000$
$1\le M\le 10^9$
$1\le A_i \le 2000$

続きを読む

yukicoder No. 1306 - Exactly 2 Digits 解説

競プロ解説 yukicoder

yukicoder Advent Calendar Contest 2020 の 12/03 出題問題です。

教育的問題除く ★4 初 AC！(★3.5 の AC が無いのは内緒) ちなみに 16 番目の AC でした。時間はかかったけれど、高難易度の問題をじっくり攻略するのは楽しいです。

おことわりですが、問題を解いた後ぼーっとしながら思考をそのまま書き連ねているので、解説の体を成していないかもしれません(ごめんなさい)。「考察」の内容は解説というよりは私の思考手順をなるべく細かく文章にしたものです。解説記事については、「私と同じ知識を有する人が同じ問題が全く分からなかった際に見て思考を追える文章」をモットーにしているので、いささか回りくどいかもしれません。その代わり、「解法」パートは簡潔に解き方をまとめようと思うので、どうかご容赦ください。
解説をどれくらいの細かさで書くかは本当に人々の思想だと思うんですけれど(ABC の解説を見ているとよく分かります……)、どうしたらいいんでしょうか……。

問題リンク

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

問題概要

インタラクティブ数当てゲーム。

$\{N,\ N+1,\ \dots ,\ N^2 -1\}$ をちょうど $1$ つずつ含む順列 $A$ があります。この順列を以下のクエリを高々 $1.5\times(N^2-N)$ 回行うことで特定してください。

? i j
1. $p=\lfloor A_i/N\rfloor-\lfloor A_j/N\rfloor$ とする。つまり、 $A_i,\ A_j$ の $N$ の位の差。
2. $q=\lfloor A_i\%N\rfloor-\lfloor A_j\%N\rfloor$ とする。つまり、 $A_i,\ A_j$ の $1$ の位の差。
3. もし $p\lt q$ なら $p,\ q$ を swap する。
4. $p,\ q$ が返される。

数列を特定したら、! に続けて数列を出力してください。

ただし、出力したクエリによって完全に数列を特定できることができない状態で数列を答えても AC とはなりません(adaptive なジャッジ)。

制約

$2\le N\le 50$

続きを読む

yukicoder No. 1305 - Speak of the Devil 解説

競プロ解説 yukicoder

yukicoder Advent Calendar Contest 2020 の 12/02 出題問題です。
今気付いたんですが、これ yukicoder の記念すべき第 300 回目のコンテストらしいですね。

問題リンク

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

問題概要

太郎君を呼ぶためにあなたは以下のうちのどちらかの行動をします。

噂をする。 $1$ 分後に太郎君は $1/p$ の確率で来る。そうでない確率 $(p-1)/p$ のときは再度どちらかの行動をする。
電話をして呼び出す。太郎君は $q$ 分後に必ず来る。

太郎君が来るまでの時間の期待値の最小値を求めてください。

制約

$1\le p,\ q\le 10^{9}$
入力は整数

続きを読む

Educational Codeforces Round 99 D - Sequence and Swaps 解説

競プロ解説 Codeforces

大爆死。反省を込めて解説ブログを書きます。

問題リンク

https://codeforces.com/contest/1455/problem/D

問題概要

非負整数からなる数列 ${a_i}$ および非負整数 $x$ が与えられます。
$a_{i}>x$ である $a_{i},\ x$ を swap することを任意の回数できます。 $a$ を広義単調増加にするためには最小で何回の操作を行えばいいでしょうか。

制約

$1\le t\le 500$ (テストケース数)
$1\le n\le 500$
$0\le x,\ a_i\le 500$

続きを読む

Codeforces Round #686 Div.3-F - Array Partition 解説

競プロ解説 Codeforces

これ E よりも簡単じゃないですか？

問題リンク

https://codeforces.com/contest/1454/problem/F

問題概要

$n$ 要素からなる数列 $a$ があります。 $a$ を $1$ 以上の要素からなる $3$ つの部分列に分けます。
最初の部分列の最大値、真ん中の部分列の最小値、最後の部分列の最大値が全て等しくなるような分け方は存在しますか。存在するときはその分け方も出力してください。

制約

$1\le t\le 2\times 10^{4}$ (テストケース数)
$3\le n\le 2\times 10^{5}$
$1\le a_{i} \le 10^{9}$
$\sum{n}\le 2\times 10^{5}$

続きを読む

Codeforces Round #686 Div.3-E - Number of Simple Paths 解説

競プロ解説 Codeforces

Div. 3 全完しようと思ったらこの問題に阻まれてしまいました。どう考えても不可能だと思ってたけど、よくよく見たらなもりグラフという制約を見逃していました。恥ずかしい。

問題リンク

https://codeforces.com/contest/1454/problem/E

問題概要

自己ループや多重辺のない $n$ 頂点 $n$ 辺の連結グラフ(つまり、なもりグラフ[^1])が与えられます。このグラフに含まれる長さが $1$ 以上の単純パスの数を求めてください。ただし、逆順にたどっただけのパスは同じものとみなします。

制約

$1\le t\le 2\times 10^{4}$ (テストケース数)
$3\le n\le 2\times 10^{5}$
$\sum{n}\le 2\times 10^{5}$

続きを読む

AtCoder Beginner Contest 184 F - Programming Contest 解説 (おまけ: 半分全列挙高速化について)

競プロ解説 AtCoder

ABC184-F Programming Contest を題材に、典型アルゴリズムである半分全列挙について詳しく解説します。実装の細かい部分まで解説します。

また、半分全列挙の高速化 (今回は主に $\log$ を取る部分について) についても掘り下げていきます。

問題リンク

https://atcoder.jp/contests/abc184/tasks/abc184_f

問題概要

$N$ 問の問題があります。 $i$ 番目の問題は解くのに $A_i$ 分かかります。

この中からいくつかの問題を選んで解くのにかかる時間の総和のうち、 $T$ 分以下での最大値を求めてください。

制約

$1\le N\le 40$
$1\le T\le 10^{9}$
$1\le A_i\le 10^{9}$

続きを読む