ARC055

Atcoder Programming

writerでした。
AtCoDeerくんというシカが主人公です。公式キャラに定着させたい・・・

ちなみにシカではないらしい

A:数え上げ

やるだけ。けっこうすき

B:せんべい

案外難しかったみたいです。
dp[i][j][k] = i枚見てj枚食べていて,"ここまでのmaxを食べているか"=k です。
Nを食べたかどうか という絶対的なものではなく,これまでのmaxを食べたかどうか という相対的な気持ちになると解きやすいと思います。
ちなみにK=1の時はN ->∞ で 1/eに近づきます。

ちなみにN,K<=1e6でも解けます。


C:ABCAC

名前的にABCかと思ったんですがどう考えてもABCには出せないですね・・・

ABC/ACの切れ目を決め打つのが良い選択です。
こうするとN^2では解けて、速くするにはSA + lcp + RMQ もしくは SA + ローリングハッシュ + にぶたん もしくはZ-algorithm というもの(
文字列の頭良い感じの線形アルゴリズムたち３ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
を参照) を使うと良いです。

はじめはYes/No問題でしたがO(N^2)が爆速になってしまったので数え上げになりました。

ちなみに元ネタは解説でりんごさんが言っていた「たかいたい」です。

D:隠された等差数列

SRM div1hardのつもりの問題でした。
発想自体は上位陣にはそんなに難しくないと思いますが、細かい部分がかなり難しかったみたいです。
発想:とりあえず与えられた桁が1桁目になるように10^Xで割っておきます.すると整数部分がわかるので、条件が ほげ<=A+B*i<ほげ+1 の形になります。これを二次元平面に落とすと、縦の線分たちをとおるような直線 という条件になります。
あとは傾きの範囲を求める(有理数を推奨しますがdoubleでも通るっぽい(通らないやり方もあるのかもしれません))のですが、これは先に上下の条件たちの必要なものだけを考えて凸にしておくと簡単に求まるようになります。

あとは見てるのは何桁目だったかを1から探索すれば解けます。

答えはO(N^2)くらいになります.
900.....001 というケースを試してみてください。(図に書くと傾きの条件がかなり厳しいことがわかります)
結構テストケースは強いです(例えば,傾きが10^x/hoge みたいなのは結構条件が厳しくなります)

元ネタですが、餃子屋さんのメニューで、
餃子1個 1|
餃子2個 3|ここが隠れている
餃子3個 4|
餃子4個 6|

みたいに上の桁だけが見えてるのを見て思いつきました。

まとめ

難しかったっぽいですが、良い問題が揃ったと思います。参加or問題を見てくださった方々ありがとうございます。