Div.4に参加しましたが、結果はさんざんでした(大反省)
コンテストURL:https://codeforces.com/contest/1352
A. Sum of Round Numbers
問題概要
左端(一番大きい桁)以外が0の数(例:4000、1、9、800)を「丸められた数」とします。クエリ数と正の整数
が与えられるので、「丸められた数」の和で
をあらわすとき、必要な「丸められた数」の最小の個数と「丸められた数」を求めてください。
考え
「を10で割ったあまり」をvectorに格納しつつ、
が0になるまで10で割っていきます。そのあと、格納された数が0でない場合は桁数を見て10を掛けて出力します(とは書いたけどとてもバグらせました……)。
B. Same Parity Summands
問題概要
正の整数が与えられます。数列
がすべて奇数、またはすべて偶数である場合に、その和を
にすることが可能か判定してください。可能な場合はそのような数列を1つ出力してください。
考え
全部奇数にする場合は最後以外1、全部偶数にする場合は最後以外2にして、一番最後の数で帳尻を合わせればいいです。どちらでも帳尻を合わせられない場合は和をにすることができません。
全部奇数にするときは個の1で
を埋めて、
に入れる
が正の奇数になる必要があります。全部偶数にするときには
個の2で
を埋めて、
に入れる
が正の偶数になる必要があります。
C. K-th Not Divisible by n
問題概要
正の整数が与えられるので、
で割り切れない正の整数のうち
番目のものを出力してください。
考え
「小さいほうから個見た場合、
で割り切れない数は
個含まれる」
上記はが大きくなるほど
も大きくなる(=単調性がある)ので二分探索で求めることができるみたいです。「
で割り切れない数の個数」を求めるには、
個の数の中から
の倍数だけを抜けばいいので、
ということになります。
D. Alice, Bob and Candies
問題概要
飴が個並んでいて、左から
番目の飴の大きさは
です。アリスは左から、ボブは右から、交互に飴を食べるゲームをします。自分の番の時、(一番最初のアリスの時以外は)「直前に相手が食べた飴の大きさの合計」より大きくなるように、1つ以上の飴を食べる必要があります。飴がなくなったら終了です。ゲームの総ターン数と、アリスとボブそれぞれが食べる飴の個数を出力してください。
E. Special Elements
問題概要
数列が与えられます。
であるような
の個数を求めてください。
考え
連続する部分数列の和と等しいはいくつありますか?ということなので、まずは累積和をします。lとrの位置をそれぞれ全探索して一通り部分数列の和を求めた後、
と等しい数があるか見ます。
8000*8000なので、TLEはしなくてもメモリが不安な気持ちになるようなならないような(?)が最大でも
であることから、vector
で十分です。じゅぴろさんありがとうございました……。
F, G なんもわからん(就寝……)