ブログ名

競技プログラミングやお歌のお話をする高菜です。

トップ > AtCoder Beginner Contest 156 解法

AtCoder Beginner Contest 156 解法

コンテストページ

https://atcoder.jp/contests/abc156/

解法

✔A - Beginner

引き算の反対をご存知でしょうか。たし算といいます。たし算をしましょう！

✔B - Digits

n が 0 になるまで k で割っていきましょう。回数をカウントです。

✔C - Rally

開催場所を全探索です。

もしくは C 問題の難易度ではありませんが、二次関数の接線の傾きの式を考えると、平均に最も近い場所で開催するのが最適であることがわかるので、そちらで実装しても良いかもしれません。いずれも実装の重さは同じくらいです。易しめの E といったところでしょうか。

✔D - Bouquet

n 元集合の冪集合から、濃度が 0, a, b のものを省いたものの数を数えます。2 冪から二項係数を引き算です。

✔E - Roaming

K 回の移動で達成できるものは、空き部屋が K 個以下であるものです。空き部屋の数 i を全探索です。i を固定すると場合の数は、（空き部屋がどれであるか = binom(n,i)）×（有人のお部屋それぞれの人数の場合の数）です。後者は、n - i 個の袋に「最低 1 個以上」の条件を守りながら n 個を配る場合の数で、これも二項係数で書くことができます。

✔F - Modularness

クエリ (n,x,m) を処理しましょう。 数えたいのは「増加する箇所」ですが、「減少する箇所」の方を数えましょう。

まず、d の代わりにそれを m で割った余りを考えればよいです。すると、数列を m で割った余りが「減少する箇所」は、m で割った商が増加する箇所ですから、初めと終わりの商を見ると良いです。n-1 からこれを引くと答えですね。嘘です。「変わらない箇所」も数えて引きましょう。（忘れていた人です。)

計算したいものが 2 つ（商の増加量と変わらない箇所の個数）ありますが、いずれも周期性を用いて計算をすればよいです。

大小を逆向きにすると直接数えることができますが、逆に大変そうかなと、思いとどまりました。

実装は軽めです。コンテスト中の提出なのですが、29 行です。 ところでクエリ形式である意味はあったのでしょうか。結局なにも前計算しませんでしたから、書いていて不安になりました。

結果

22 位です

f:id:ngtkana:20200222224516p:plain

最高順位、更新です。嬉しいですね。

今までトップ 2 が ARC 級という異常仕様だったのですが、なくなってしまいました。（少し下を見ると AGC 級もあります。（！？）） 波のあるタイプですから、高難易度で上振れを引くと温まりがちです。

f:id:ngtkana:20200222224447p:plain

22 位で最高ということは、まだ順位表の 1 ページ目には載ったことがないということです。悲しいですね。天才ながたかなの菜を知っていただくためにも、20 位以内を取っていきたいところです。

ツイッター

C

上位層の方々でも瞬殺ではなさそうですし、易しめの E というのは嘘かもしれません。

D

0 本の花束作れやわかります！

E

制約からは外されていたものの、コーナーケースがあったようです。私は何も気にしていなかった人です。

どうやら OEIS にあったようです。

K = 1 はともかく N = 2 は気付ける気がしません。言われてもしばらくわかりませんでした……（はい！？）

F

ながたかなタイムロスの様子です。