きままにものづくり

日々の気付いたことなんかを書いてます。

SRM648Div1Easy

問題

以下の性質を満たす文字列Sを求めよ。

  • 要素はAかB
  • サイズはN個
  • S[i]=A, S[j]=B ( 0 \leq i < j < N) となるペアがK個

解法

Aの数をa、Bの数をBとし、a*b+c=Kとなるようにa,b,cを求める。c(=K-a*b)はAを左から詰めた時に、一番右のAをどれだけ右にずらすかを示す値である。

計算量

 O(N)

コード

広告を非表示にする