情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

AtCoder Regular Contest 099

AtCoder Regular Contest 099に参加しました！
ABC101 beta:
https://beta.atcoder.jp/contests/abc101/beta.atcoder.jp
ARC099 旧版:
arc099.contest.atcoder.jp
ARC099 beta:
https://beta.atcoder.jp/contests/arc099/beta.atcoder.jp

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 101 / Regular Contest 099
rated 1200 / 2800
6/23(土) 21:00 ～ 22:40 (100分)
100-200-300-500-700-1200 (6問)
ペナルティ: 5分

方針

3完、できれば早解きしたい！

A - Eating Symbols Easy

愚直にシミュレーションすると良いです。
実際に値0から始めて、+が出てきたら+1、-が出てきたら-1すれば値が求められます。

B - Digit Sums

S(N)はNに対して次のような操作をすることで求められます。
求めた結果をaとします。最初、a=0です。

  • aにNを10で割った余りを追加する
  • Nを10で割る

この操作により、毎回aには各桁の値が追加されるので最終的にa=S(N)になります。
後は割れば求まります。

C - Minimization

まず、数列の全ての値を同値にすることと、選択した全ての値は最小値になることから、最終的に全ての値が1になることが分かります。
ここで、まずあるiに対しA_iとA_{i+1}の両方を含むような選択の仕方をしないと仮定します。
この時、A_1からA_iの間に最小値があると仮定するとA_{i+1}からA_Nまでの間には最小値は存在しないので、全ての値を同値にすることはできません。
逆も同様なので、つまり任意のiに対しA_iとA_{i+1}の両方を含むような選択の仕方をしています。
ここで、同じ範囲を何度も選択するのは無駄なので、なるべく重複要素が無いようにすると、例えばN=10, K=4の時は1-4、4-7、7-10のように重複部分は1個までにしたいです。
また、この選択を行う時、常に最小値が入っている範囲を最優先に操作を行っていけば全ての値が最小値になるので、これが最適です。
ということは、この問題は次のように置き換えられます。

長さKのテープが何枚かある。
テープ同士を長さ1の糊しろで繋いでいくとき、繋がったテープの長さがN以上になるためには最低何枚のテープが必要か？
これはテープ1枚でK、2枚でK+(K-1)、3枚でK+(K-1)+(K-1)…とx枚でK+(x-1)(K-1)=x(K-1)+1の長さになります。
ということは、これを解くと\lceil \frac{N-1}{K-1} \rceilより、切り上げ処理を加えて\frac{N-1+(K-2)}{K-1}=\frac{N+K-3}{K-1}が答えになります。

結果

oxxx 1完(300点) 32:34(2WA)
800位 パフォーマンス: 1083
レート: 1847→ 1789(-58)

感想

Cが数学、Dが全く解けない問題で泣くしかなかったです。
ちなみにDですが、N番目のすぬけ数をf(N)とするとき、f(N+1)は2f(N)-f(N-1)か11f(N)-10f(N-1)のどちらかです。
なので愚直に解ける……らしいのだが証明が全く分からない！
無理！