ブログ名

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

AtCoder Beginner Contest 158 解法

コンテストページ:https://atcoder.jp/contests/abc158

結果

f:id:ngtkana:20200307225512p:plain

51:47 全完、21 位(最高順位更新)です!

keymoon さんを順位表の 1 ページ目から追い出せて嬉しかったので、茶化してみたのですが、

現実は非情でした。

反省

keymoon さんの呪いによって、順位表の 1 ページ目はのがしてしまいましたが、最高順位をとることができました。得意セットです。

少し詰まった箇所がありましたが、実力相当です。 いつもは序盤はかなり安定側に倒していたのですが、今回はかなり攻めてみました。 今後もそうするかは未定なのですが、攻めると案外速いものですねということがわかりました。

もうライブラリを縛る気はありませんから、Vimスニペットを移植したいところです。

A - Station and Bus (00:01:29)

すべて同じ文字かどうかをチェックです。s[0]!=s[1] || s[1]!=s[2] です。

B - Count Balls (00:02:49)

まず周期的な部分を処理して、そのあとは余りと A の min です。

C - Tax Increase (00:05:26)

税抜価格を全探索です。

いくつか細かい間違いですこし出遅れてしまいました。 戦略的に正しいかはさておき、前半を攻めるとこのあたりが明るみにでて良いですから、続けても良いかもしれません。

D - String Formation (00:09:36)

リバースクエリで実際にリバースをせず、フラグで管理です。 間違えずに実装ができました。

E - Divisible Substring (00:24:10 + (1))

まず、p が 2, 5 の場合は特別扱いです。 そうでないときには 10 と互いに素ですから、x が p で割り切れることと 10x が p で割り切れることは同じです。

たとえば 12345 の部分列 23 を考えましょう。これが割り切れることを、2300 が割り切れることに言い換えましょう。 さらに、2300 は 2345 - 45 とですから、2300 を p で割ったあまりと 45 を p で割った余りが等しいと言い換えましょう。

すると、すべての suffix について p で割った余りを計算して、それの重複度付き集合を計算すると良いことがわかります。

ながたかな戦いの歴史

ところで私は初めこれを、普通の桁和だと思っており、なんですか? E に自明をやめましょう!(どやぁ)をしていました。 幸いサンプル 3 が通りませんでしたから、事なきをえました。ありがとうサンプル 3 さんです。

そして正しい道に戻ってきたは良いのですが、suffix の余りを求めるところで間違えてしまいました。 こういうのは前から見ていけば良くてですね、10 を書けて足していけばよいのです。(どやぁ)をしていたのですが、 みなさんお気づきでしょうか。これは prefix です。(はい!?)

そしてなぜか通るサンプル 3 さんです。頼りにしていたのですが……

F - Removing Robots (00:46:47)

始点でソートして、後ろから見ていきます。 今見ているもの以降だけが存在すると思ったときの場合の数を、DP です。

2 通りに分けられます。まず、今見ているものが動かないときには、一つ右の値です。 動くときには、動かしたときにどこまで波及するのかを見て、波及しなかった最小の場所の値です。 これらをたし算です。

さて問題は、波及しなかった最小の場所の計算の仕方です。 直接波及する範囲は、始点の配列上で Lower Bound をすることで計算ができます。 間接的なものは、この範囲にあるすべてのロボットの波及範囲の合併です。 ですから、各ロボットを動かしたときにどこまで波及するのかを、計算するたびに Max - セグメント木に入れておくことで、取得することが出来ます。

セグメント木を使わない方法も考えようと思ったのですが、思いつきませんでした。逆向きの累積 max ですし、難しそうな雰囲気もあります。

タイムラインのご様子です。

A

わかります。

D

後ろから見る、かなり天才を感じます。

E

たしかにです。ま、まさか、素数はこのために!?(いいえ)

F

https://twitter.com/drken1215/status/1236292206106828800

たしかに解けそうな雰囲気です。

真相です。

キレイな実装です。