2022-06-17 ARC134 の C を解いた
ARC134 : AtCoder Regular Contest 134 の C を解いた。
- C - The Majority
https://atcoder.jp/contests/arc134/tasks/arc134_c
- 提出: https://atcoder.jp/contests/arc134/submissions/32517245
- 解説 AC
- 各箱に 1 個はないと過半数にならない
- A_1 以外を 1 個置くごとに A_1 が 1 個はないと過半数にならない
- なので
A_1 < K + SUM(A_2..=A_N)なら0 - ここで諦めた
- https://scrapbox.io/procon-kirokuyou/ARC134_C_-_The_Majority_(500) を見た
- ここまで過半数と箱を埋める条件は満たせている
A_1をA_1 - K - SUM(A_2..=A_N)にする- あとは
A_iをそれぞれ K 個の箱に割り当てる組み合わせをかけあわせれば良い - それぞれ
(A_i + K - 1) C (K - 1)とすれば良い K - 1個の仕切りを加えて並び替える- これは
O(K)で求められる - 全体で
O(NK) ModIntが意外と遅かったのか 1 TLE を出した
bouzuya/rust-sandbox its 0.18.0 をつくった。
its issue update-title を追加した。特に新しい要素はないので作業。
2022-W21 あたりから子どものお絵かきボード (ブギーボードの大きいようなもの) をメモに使っていたのだけどやめた。
紙の場合は「書いたものを残したままもう一枚」ができるもののお絵かきボードだと消してしまわないといけない。写真などを撮って……とするのが正しいのは分かるのだけど実際問題不便だった。
今日のコミット。