ARMERIA

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

Codeforces Round #515 参加記録&解説(A~E)

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 個のクエリを処理せよ。

  1. L id : 一番左にある本の左に番号 id の本を置く。
  2. R id : 一番右にある本の右に番号 id の本を置く。
  3. ? 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で割った余りを出力せよ。

  1.  a, b のビットAND a&b の値を答えに加算する。
  2.  b を右に1ビットシフトする。
  3.  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コード

Codeforces

さいごに

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