コンテストページ:https://atcoder.jp/contests/abc158
結果
51:47 全完、21 位(最高順位更新)です!
ひどいことをする方がいるものです。 https://t.co/jXDLI12nKN
— ながたかな (@ngtkana) March 7, 2020
keymoon さんを順位表の 1 ページ目から追い出せて嬉しかったので、茶化してみたのですが、
とか言ってたら追い出されてますね、お疲れさまです。 人を呪わばなんとやら
— keymoon (@kymn_) March 7, 2020
現実は非情でした。
反省
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
いやA読解難わかるなサンプルエスパーで事なきを得たけど
— のいみ(競プロ) (@noimi_kyopro) March 7, 2020
わかります。
D
左右の string 持つと末尾に追加だけでいけます (writer 解は後ろから解くでしたが)
— 不養生 (@satashun) March 7, 2020
後ろから見る、かなり天才を感じます。
E
今日のE、10をかける代わりに逆元をかければ前からでも解けるけど、普通に後ろからやるほうが楽そう
— かいとccs (@tran0826) March 7, 2020
提出 #10645320 - AtCoder Beginner Contest 158 https://t.co/Czjq4o9IpC
たしかにです。ま、まさか、素数はこのために!?(いいえ)
F
https://twitter.com/drken1215/status/1236292206106828800
たしかに解けそうな雰囲気です。
Fのstack/木の解法、多分こんな感じ pic.twitter.com/DHFmyM2ZMj
— keymoon (@kymn_) March 7, 2020
真相です。
解法としては stack で管理しながら implicit に木DPをしています
— ぽかーん懐古DP@259家(桃音モモ) (@259_Momone) March 7, 2020
キレイな実装です。