ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Codeforces Round #515 参加記録＆解説（A～E）

Codeforces プログラミング競技プログラミング

Dashboard - Codeforces Round #515 (Div. 3) - Codeforces

結果は5完で、Virtualの参加者を除くと121位。悪くはないですが、上を目指すなら全完したいところですね…

f:id:betrue12:20181013142347p:plain

5問振り返ります。

A. Vova and Train

Problem - A - Codeforces

問題概要

以下の問題 $t$ 個に答えよ。

1から $L$ までの整数のうち、 $v$ の倍数であり、区間 $\lbrack l, r \rbrack$ に含まれないものの数を求めよ。

制約

$1 \le t \le 10^{4}$
$1 \le L, v \le 10^{9}$
$1 \le l \le r \le L$

解法

1から $L$ までの整数のうち $v$ の倍数は $\lfloor\frac{L}{v}\rfloor$ 個あります。

区間 $\lbrack l, r \rbrack$ に含まれる $v$ の倍数のうち、（存在する場合）最小のものは $\lceil\frac{l}{v}\rceil v$ 、最大のものは $\lfloor\frac{r}{v}\rfloor v$ です。その間に含まれる $v$ の倍数の個数は $\lfloor\frac{r}{v}\rfloor - \lceil\frac{l}{v}\rceil + 1$ です。これを総数から引けばよいです。

※区間 $\lbrack l, r \rbrack$ に $v$ の倍数が1つもない場合がありますが、そのときは $\lfloor\frac{r}{v}\rfloor - \lceil\frac{l}{v}\rceil + 1 = 0$ になるので、同じ計算で答えが求められます。

ACコード

（C++）Submission #44190437 - Codeforces

B. Heaters

Problem - B - Codeforces

問題概要

長さ $n$ のマスのうち、いくつかのマスにヒーターがある。マス $i$ のヒーターが動作している場合、区間 $\lbrack i-r+1, i+r-1 \rbrack$ のマスが暖かくなる。

できるだけ少ない数のヒーターを動作させて、全てのマスを暖かくしたい。そのようなヒーターの数を求めるか、全てのマスを暖かくすることが不可能であることを判定せよ。

制約

$1 \le n, r \le 1000$
$a_{i}$ は0または1。1のときマス $i$ にヒーターが置かれている。

解法

左から右にマスが $1, ..., n$ と並んでいるとします。

「マス $i$ が暖かくなっているかどうか」を管理しながら、左から順番にマスを見ていきます。暖かくないマスを見つけた場合、そのマスを暖かくできるヒーターの中で最も右にあるものを動作させるのが最適です。これを一番右まで行えばよいです。

計算量は $O(nr)$ で十分間に合います。

ACコード

（C++）Submission #44234507 - Codeforces

本番はDPで解きました。「マス $i$ までが全て暖かくなっているために必要なヒーターの最小数」を $dp\lbrack i \rbrack$ としています。これでも解けます。

C. Books Queries

Problem - C - Codeforces

問題概要

横に十分な長さを持つ本棚に、以下のクエリに従って本を置いていく。合計 $q$ 個のクエリを処理せよ。

L id : 一番左にある本の左に番号 id の本を置く。
R id : 一番右にある本の右に番号 id の本を置く。
? id : 既に置かれてある番号 id の本について、「その本の左にいくつ本があるか」と「その本の右にいくつ本があるか」のうち小さいほうを出力する。

制約

$1 \le q \le 2\times 10^{5}$
$1 \le$ id $\le 2\times 10^{5}$
既に置かれた本と同じ番号の本は置かれない。
? id クエリでは既に置かれた本の番号が指定される。

解法

座標を考えると見通しが良くなります。一番最初に置かれる本を座標0として、最左の本の座標と最右の本の座標を管理しておきます。そうすると、本を追加したときにその本の座標が分かるので、それを番号 id をインデックスとする配列などで記録します。

? id クエリに答える際には、番号 id の本の座標、最左の本の座標、最右の本の座標が分かっていれば、左右それぞれにある本の数を求められます。

ACコード

（C++）Submission #44235751 - Codeforces

本番コードはこちら。上のほうがスマートです。

D. Boxes Packing

Problem - D - Codeforces

問題概要

サイズが $a_{1}, ..., a_{n}$ である $n$ 個の物品と、容量 $k$ の箱 $m$ 個がある。

物品を、以下の手順で箱に詰める。

空箱を持つ。物品を前から見ていって、その空箱に詰められるだけ詰める。詰められなくなったら、新しい空箱に切り替えて物品を詰める。（物品は必ず前から順に詰める。詰められない物品をスキップしたり、後回しにすることはできない。）

もしこの手順で全ての物品を詰められない場合は、番号の最も若い物品を捨て、最初からやり直す。

捨てたもの以外の物品を $m$ 個の箱に全て詰められたとき、そのときの物品の数を求めよ。

制約

$1 \le n, m \le 2\times 10^{5}$
$1 \le k \le 10^{9}$
$1 \le a_{i} \le k$

解法

問題文の読解が最難関です。

「物品 $i, (i+1), ..., n$ を前から処理したとき、 $m$ 個以下の箱に全て詰められる」という条件を満たす最小の $i$ を求めれば良いです。単調性があるので、二分探索をすることができます。

二分探索のYes/No問題においては、素直に固定した開始地点から物品を詰めてみて $m$ 個以内に収まるかチェックすればよいです。1回のYes/No問題が $O(n)$ で解けるので全体計算量は $O(n \log n)$ です。

ACコード

（C++）Submission #44204869 - Codeforces

E. Binary Numbers AND Sum

Problem - E - Codeforces

問題概要

2進数で整数 $a, b$ が与えられ、それぞれのビット長は $n, m$ である。

以下の操作を行ったときの答えの値を求め、998244353で割った余りを出力せよ。

$a, b$ のビットAND a&b の値を答えに加算する。
$b$ を右に1ビットシフトする。
$b=0$ なら終了、そうでなければ1に戻る。

制約

$1 \le n, m \le 2 \times 10^{5}$
$a, b$ はそれぞれビット長 $n, m$ の2進数であり、最左ビットは1

解法

$a$ の中で1となっているビットに注目します。このビットが（一番右を0桁目として） $k$ 桁目だとすると、このビットが1回加算されるごとに答えは $2^{k}$ 増加します。

ではこのビットが何回答えに加算されるかというと、それは $b$ の中で $k$ 桁目以上に存在する1の個数に対応します。この個数は $b$ のビットについて累積和を取っておけば、累積和同士の差を取ることで求められます。

f:id:betrue12:20181013144544p:plain

これを $a$ の立っているビット全てについて計算します。 $b$ の最大桁より大きい桁は $a$ についても見なくて良いので、計算量は $O(m)$ となります。

ACコード

さいごに

Fを復習します…Div3は全完を目指したい。