AtCoder

やらかし反省録が増えました！！！！！！！！！！！！！！！！！！！

問題リンク

https://atcoder.jp/contests/abc185/tasks/abc185_e

問題概要

$N,\ M$ 要素からなる整数列 $A,\ B$ があります。$A,\ B$ からいくつかの要素をコスト $1$ で取り除くことができます。取り除いたあと、$A,\ B$ の要素数が同じでなくてはなりません。
取り除いたあとの $A,\ B$ について $A_i\neq B_i$ である要素があれば、その個数だけコストが $1$ ずつ上乗せされます。
コストの最小値を求めてください。

制約

$1\le N,\ M\le 1000$
$1\le A_i,\ B_i\le 10^{9}$

この記事は、色変記事 Advent Calendar 2020 の12月9日公開の記事です。

色変記事アドベントカレンダー、なるものの募集を見ました。

色変記事AdventCalendarを作成しました。
みなさまの勇気ある宣言をお待ちしております！https://t.co/1NqMxq7Wu3

— dokin (@ayoiyouyoeyo) November 4, 2020

この恐ろしいアドベントカレンダーを見てしまった私。そういえば、AtCoder 青も Codeforces 紫も、近かったような……あれ、Topcoder も黄になれるんじゃ？

ということで、参加してみました。完全にノリですが、Topcoder はともかく AtCoder と Codeforces はずっと色変しないまま膠着していたので、これを期に色変してやろうと考えました。

(達成できたら)恐らく前代未聞の、3 コンテストサイト同時の色変記事になります。

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

問題リンク

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$

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}$

この問題だけどうして問題名の最初が英小文字なのか気になってしまい夜も眠れません。

問題リンク

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

問題概要

袋の中に金貨が $A$ 枚、銀貨が $B$ 枚、銅貨が $C$ 枚入っています。
袋の中から硬貨をランダムに選び、それと同じ種類の硬貨をもう $1$ 枚入れるのをいずれかの種類の硬貨が $100$ 枚になるまで繰り返します。
操作回数の期待値を求めてください。

制約

$0\le A,\ B,\ C\le 99$
$A+B+C\ge 1$

この問題がこのセットで最難……。

問題リンク

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

問題概要

斜めにどこまででも進め、また マンハッタン距離 が $3$ 以下である場所に進める駒「超竜馬」があります。
$(r_{1},\ c_{1})$ から $(r_{2},\ c_{2})$ へ動くのに必要な最小手数を求めてください。

制約

$1\le r_{1},\ c_{1},\ r_{2},\ c_{2}\le 10^{9}$

AtCoder Problems に本日(11月17日)アップデートが入り、各問題の difficulty (以下、diff)の推定アルゴリズムが変わりました。これに伴いいくつかの問題で diff の色が変更になったため、色が変更になった問題をまとめます。

先日の エイシング プログラミング コンテスト 2020 で、AtCoder水色になりました！！！！！！！！！！！！！！！！！！！！！！

fancy_lettuceさんのエイシング プログラミング コンテスト 2020での成績：837位
パフォーマンス：1599相当
レーティング：1166→1218 (+52) :)
Highestを更新し、4 級になりました！#AtCoder #エイシングプログラミングコンテスト2020 https://t.co/72e591XRhS
青パフォ逃しましたが入水です！！！ pic.twitter.com/q1qJf43FQj

— れたす (@lettuce_cs) July 11, 2020

自分にとって水色は通過点だと思っていたのでぱぱっと水色になって上に行こうと思っていたら思いの外レートが伸び悩んでしまい、一時期非常に苦しかったのですが、無事水色になれました。マイルストーンとして今までに競プロでやったことをまとめようと思います。

ところで、先日って7月11日？もう1か月経ったらしいですよ？ぼーっとしてたらこの記事を下書きに保存したまま1か月経ったらしいです。怠惰ですね。この記事をお蔵入りさせるわけにもいかないので、1か月遅刻してしまいましたが公開します。