Codeforces Round #515 参加記録&解説(A~E)
Dashboard - Codeforces Round #515 (Div. 3) - Codeforces
結果は5完で、Virtualの参加者を除くと121位。悪くはないですが、上を目指すなら全完したいところですね…
5問振り返ります。
A. Vova and Train
問題概要
以下の問題 個に答えよ。
- 1から までの整数のうち、 の倍数であり、区間 に含まれないものの数を求めよ。
制約
解法
1から までの整数のうち の倍数は 個あります。
区間 に含まれる の倍数のうち、(存在する場合)最小のものは 、最大のものは です。その間に含まれる の倍数の個数は です。これを総数から引けばよいです。
※区間 に の倍数が1つもない場合がありますが、そのときは になるので、同じ計算で答えが求められます。
ACコード
(C++)Submission #44190437 - Codeforces
B. Heaters
問題概要
長さ のマスのうち、いくつかのマスにヒーターがある。マス のヒーターが動作している場合、区間 のマスが暖かくなる。
できるだけ少ない数のヒーターを動作させて、全てのマスを暖かくしたい。そのようなヒーターの数を求めるか、全てのマスを暖かくすることが不可能であることを判定せよ。
制約
- は0または1。1のときマス にヒーターが置かれている。
解法
左から右にマスが と並んでいるとします。
「マス が暖かくなっているかどうか」を管理しながら、左から順番にマスを見ていきます。暖かくないマスを見つけた場合、そのマスを暖かくできるヒーターの中で最も右にあるものを動作させるのが最適です。これを一番右まで行えばよいです。
計算量は で十分間に合います。
ACコード
(C++)Submission #44234507 - Codeforces
本番はDPで解きました。「マス までが全て暖かくなっているために必要なヒーターの最小数」を としています。これでも解けます。
C. Books Queries
問題概要
横に十分な長さを持つ本棚に、以下のクエリに従って本を置いていく。合計 個のクエリを処理せよ。
L id
: 一番左にある本の左に番号id
の本を置く。R id
: 一番右にある本の右に番号id
の本を置く。? id
: 既に置かれてある番号id
の本について、「その本の左にいくつ本があるか」と「その本の右にいくつ本があるか」のうち小さいほうを出力する。
制約
-
id
- 既に置かれた本と同じ番号の本は置かれない。
? id
クエリでは既に置かれた本の番号が指定される。
解法
座標を考えると見通しが良くなります。一番最初に置かれる本を座標0として、最左の本の座標と最右の本の座標を管理しておきます。そうすると、本を追加したときにその本の座標が分かるので、それを番号 id
をインデックスとする配列などで記録します。
? id
クエリに答える際には、 番号 id
の本の座標、最左の本の座標、最右の本の座標が分かっていれば、左右それぞれにある本の数を求められます。
ACコード
(C++)Submission #44235751 - Codeforces
本番コードはこちら。上のほうがスマートです。
D. Boxes Packing
問題概要
サイズが である 個の物品と、容量 の箱 個がある。
物品を、以下の手順で箱に詰める。
- 空箱を持つ。物品を前から見ていって、その空箱に詰められるだけ詰める。詰められなくなったら、新しい空箱に切り替えて物品を詰める。(物品は必ず前から順に詰める。詰められない物品をスキップしたり、後回しにすることはできない。)
もしこの手順で全ての物品を詰められない場合は、番号の最も若い物品を捨て、最初からやり直す。
捨てたもの以外の物品を 個の箱に全て詰められたとき、そのときの物品の数を求めよ。
制約
解法
問題文の読解が最難関です。
「物品 を前から処理したとき、 個以下の箱に全て詰められる」という条件を満たす最小の を求めれば良いです。単調性があるので、二分探索をすることができます。
二分探索のYes/No問題においては、素直に固定した開始地点から物品を詰めてみて 個以内に収まるかチェックすればよいです。1回のYes/No問題が で解けるので全体計算量は です。
ACコード
(C++)Submission #44204869 - Codeforces
E. Binary Numbers AND Sum
問題概要
2進数で整数 が与えられ、それぞれのビット長は である。
以下の操作を行ったときの答えの値を求め、998244353で割った余りを出力せよ。
- のビットAND
a&b
の値を答えに加算する。 - を右に1ビットシフトする。
- なら終了、そうでなければ1に戻る。
制約
- はそれぞれビット長 の2進数であり、最左ビットは1
解法
の中で1となっているビットに注目します。このビットが(一番右を0桁目として) 桁目だとすると、このビットが1回加算されるごとに答えは 増加します。
ではこのビットが何回答えに加算されるかというと、それは の中で 桁目以上に存在する1の個数に対応します。この個数は のビットについて累積和を取っておけば、累積和同士の差を取ることで求められます。
これを の立っているビット全てについて計算します。 の最大桁より大きい桁は についても見なくて良いので、計算量は となります。
ACコード
さいごに
Fを復習します…Div3は全完を目指したい。