りにゅうしょく

競技プログラミング 日常

Codeforces Round #640 (Div. 4) DETAYO~~~~~~~~

Div.4に参加しましたが、結果はさんざんでした(大反省)
コンテストURL:https://codeforces.com/contest/1352

A. Sum of Round Numbers

問題概要

左端(一番大きい桁)以外が0の数(例:4000、1、9、800)を「丸められた数」とします。クエリ数tと正の整数nが与えられるので、「丸められた数」の和でnをあらわすとき、必要な「丸められた数」の最小の個数と「丸められた数」を求めてください。

考え

nを10で割ったあまり」をvectorに格納しつつ、nが0になるまで10で割っていきます。そのあと、格納された数が0でない場合は桁数を見て10を掛けて出力します(とは書いたけどとてもバグらせました……)。

B. Same Parity Summands

問題概要

正の整数n, kが与えられます。数列A_1, A_2, A_3, ..., A_kがすべて奇数、またはすべて偶数である場合に、その和をnにすることが可能か判定してください。可能な場合はそのような数列を1つ出力してください。

考え

全部奇数にする場合は最後以外1、全部偶数にする場合は最後以外2にして、一番最後の数で帳尻を合わせればいいです。どちらでも帳尻を合わせられない場合は和をnにすることができません。
全部奇数にするときはk-1個の1でA_1~A_{k-1}を埋めて、A_kに入れるn-(k-1)が正の奇数になる必要があります。全部偶数にするときにはk-1個の2でA_1~A_{k-1}を埋めて、A_kに入れるn-2 \times (k-1)が正の偶数になる必要があります。

C. K-th Not Divisible by n

問題概要

正の整数n, kが与えられるので、nで割り切れない正の整数のうちk番目のものを出力してください。

考え

「小さいほうからa個見た場合、nで割り切れない数はb個含まれる」
上記はaが大きくなるほどbも大きくなる(=単調性がある)ので二分探索で求めることができるみたいです。「nで割り切れない数の個数」を求めるには、a個の数の中からnの倍数だけを抜けばいいので、 b = a-(a \div n)ということになります。

算数(数学)orエスパーでO(1)もできます(本番中はこっちだった)

D. Alice, Bob and Candies

問題概要

飴がn個並んでいて、左からi番目の飴の大きさはa_iです。アリスは左から、ボブは右から、交互に飴を食べるゲームをします。自分の番の時、(一番最初のアリスの時以外は)「直前に相手が食べた飴の大きさの合計」より大きくなるように、1つ以上の飴を食べる必要があります。飴がなくなったら終了です。ゲームの総ターン数と、アリスとボブそれぞれが食べる飴の個数を出力してください。

考え

dequeを使って、アリスのターンの時は前から、ボブのターンの時は後ろから飴を取っていけばいいです。

E. Special Elements

問題概要

数列a_1, a_2, ..., a_n( 1 \leq a_i \leq n )が与えられます。a_i = a_l + a_{l+1} + ... + a_{r}(1 \leq l < r \leq n)であるようなa_iの個数を求めてください。

考え

連続する部分数列の和と等しいa_iはいくつありますか?ということなので、まずは累積和をします。lとrの位置をそれぞれ全探索して一通り部分数列の和を求めた後、a_iと等しい数があるか見ます。8000*8000なので、TLEはしなくてもメモリが不安な気持ちになるようなならないような(?)a_iが最大でもnであることから、vectorのサイズはn+1で十分です。じゅぴろさんありがとうございました……。

F, G なんもわからん(就寝……)