trsing’s diary

勉強、読んだ本、仕事で調べたこととかのメモ。

diverta 2019 Programming Contest参加メモ

AtCoder

企業主催？よくわからんが参加だ。数をこなせｳｨｯﾋｰ! 配点的にABとCかDクリアを目標で。

atcoder.jp

結果

A,B,C問題はAC。D問題は提出にもいたらず。E以降は問題文すら見れてねえ。

C：AB Substrings

連結してABができるか。変に被ったりしないので文中にあるABのほか、頭としっぽに注目すればよいことにはすぐ気づいた。 すると

  1. 頭がB、しっぽがAの文字列
  2. 頭がB、しっぽがA以外の文字列
  3. 頭がB以外、しっぽがAの文字列

の場合でちょいと調整が必要であることがわかるから簡単な例を並べて調整方法を見つければよい。

追記
1.を全部くっつける。2.、3.から1個ずつ持ってきて1.にくっつける。残りの2.、3.をくっつける。みたいな感じ。

D：DivRem Number

最大10^{12}だから全探索じゃとても間に合わないよねえということで高速化が必要。で止まった。 modなんでとりあえずN=km+lと置いてみりゃ解説の方法思いついたかも。約数求める高速なアルゴリズム思いつかないから結局無理だったかな。いやググればすぐ出てくるからいけるか。

追記
N=km+lとして計算したらいいだけみたいだ。

N=km+l,\,l<mとおく。

\displaystyle{ \lfloor \frac{N}{m} \rfloor=\lfloor \frac{km+l}{m}\rfloor=k,\\ N\mod m = (km+l)\mod m=l }
\lfloor \frac{N}{m} \rfloor=N\mod mより k=l
\displaystyle{ N=km+k=k(m+1)>k^{2}\\ \sqrt{N}>k }

[1,\sqrt{N})でkを探索、mを算出すればよい。 \sqrt{N}は10^{6}なので間に合う。ACできた。

所感

B問題を読み間違えて無駄に時間使っちゃった。問題文は落ち着いてちゃんと読もう。 約数を高速に求める方法とか定石的なものは一通り見ておこう。