ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300) F,G問題メモ

ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)

無事に300回を迎えられてよかった。すばら。

F - More Holidays

• o と x からなる長さ $N$ の文字列 $S$ を、$M$ 回繰り返した長さ $NM$ の文字列を $T$ とする
  • $S$ には少なくとも $1$ つの x が含まれることが保証される
• $T$ に含まれる x のうち丁度 $K$ 個を選んで o に変える
• 変更後の $T$ に、o のみからなるできるだけ長い連続部分文字列が含まれるようにしたい
• 達成可能な最大値を求めよ
• $1 \le N \le 3 \times 10^5$
• $1 \le M \le 10^9$

ループをまとめて処理。あと、コーナーケースへの注意が必要。

oに変える $K$ 個のxは、xだけで考えたときに連続しているものを選んだ方がよいのは明らか。

変更する左端 $L$ を固定すると、右端 $R$ は一意に決まり、 さらに $L$ の1つ前、$R$ の1つ後のxの位置により、oが何個連続するかも簡単に計算できる。

S = ooxxoooxo  
M = 3
K = 6

  i 012345678  901234567  890123456
  T ooxxoooxo  ooxxoooxo  ooxxoooxo

→ xの位置
   pos: [ 2, 3, 7, 11, 12, 16, 20, 21, 25 ]
   

例1    L   2     34   5     R         Lは pos[1] に相当
    ooxxoooxo  ooxxoooxo  ooxxoooxo     pos[1-1] は 2 なので、次の3からoが始まる
       |--------------------|           pos[1+6] は 21なので、前の20までoが続く
                                      20-3+1 = 18 個の連続

例2        L     23   4     5R        Lは pos[2] に相当
    ooxxoooxo  ooxxoooxo  ooxxoooxo     pos[2-1] は 3 なので、次の4からoが始まる
        |-----------------------|       pos[7+6] は 25なので、前の24までoが続く
                                      24-4+1 = 21 個の連続

$S$ 1周に登場するxの個数を $C$ として、$K / C = D あまり E$ としたとき、 $D$ 周分はスキップでき、$D$ 周後の同じ位置から $E$ 個分のxをoに変えればよい。

これは、$S$ 2周分のposを求めておき、前半1周分のxを $L$ だと固定して試せばよい。
全通り試した後の最適解に、スキップ分の $DN$ を合わせたものが答え。

ただし、pos[0] を $L$ とする場合、その1つ左のxの位置が取得できない。
本来は1つ前のループの右端のxになるので、posの先頭に便宜的に負のindex（$右端のxの位置 - N$）を入れておくとよい。
その上で、試す $L$ の位置はその次から（下例で“2”から）1周分とすればよい。

N=9
T ooxxoooxo  ooxxoooxo
↓
pos: [-2, 2, 3, 7, 11, 12, 16]
      ~~~
         |------>  ここから1周分のxの位置を L にして試す

（または、試す $L$ の位置を1つ多く、2周目の最初のxまでにする、としてもよいが。まぁお好みで）

基本方針はそれでいいのだが、この方法を使うためには前提が必要。

先述の考え方にはループ数の概念が無く、無限に繰り返されることが前提となっているが、実際は $M$ 回と決まっている。

$T$ の左端や右端で“打ち切り”になる場合を考えないといけない。

制約から、この場合は全てのxをoに変えられる。$NM$ が答え。

これが厄介。

求まった最適解が、ループ数 $M+1$ でないと実現できない場合がある。 p

K=8  M=3  (D=2, E=2)
       L                        R
ooxxoooxo ooxxoooxo ooxxoooxo ooxxoooxo
       |------------------------|

M=3 なのに4ループ必要

この場合は、posを1周分だけでチェックすればよい。あと、両端を表すために $[-1,N]$ で挟む。

N=9
S ooxxoooxo
↓
pos: [-1, 2, 3, 7, 9]
      ~~~          ~

なぜ1周なのか。
$T$ における1周目から $D=M-1$ 周分スキップすると最終ループであり、その周回で $T$ は終わりである。
「スキップした上で、さらに周回をまたぐ」ことができないので、1周分の中から最適な場合を見つけると考えてよい。

これは当初の方法で大丈夫。

$D \le M-2$ のときは、最初の1周目から $D$ 周分スキップしても、スキップ先のループの次に必ずもう1ループ以上ある。

（スキップ元＆スキップ先の1周）と（スキップ先の次の1周）があれば、見つかった解は必ず実現できる。

Python3

G - P-smooth number

• $N$ 以下の正整数のうち、素因数分解した時、$P$ 以下の素数のみで構成されるものの個数を求めよ
• $1 \le N \le 10^{16}$
• $2 \le P \le 100$

まずパッと思いつくのは、Dijkstra的に、条件を満たす数を順番に取り出して1カウントし、 それに $P$ 以下の素数をかけたものを再びキューに入れる、というのがある。

100以下の素数は25個なので、もし最大ケースでも $10^5$ 個くらいで収まるのであれば、 全体の計算量は $2.5 \times 10^6$ にlogがかかった程度で間に合いそう･･････。

しかし、サンプル2を見ると最大ケースの答えが書いてあり、$2 \times 10^9$ 程度あることがわかる。
まぁね、G問題だしそこまで甘くはないよね。わかってた。

（このように、問題文中でなく、入出力サンプルにヒントが隠されていることがある。
出題者側もわざわざヒントになるようなケースを入れているのは（たぶん）意図してのことなので、利用できるなら遠慮無く利用しよう）

ただ、同時に“その程度”であることもわかった。

数え上げで、答えが $10^{10}$ 個くらいに収まるのなら、約 $10^5$ ずつの半分全列挙が使える可能性がある。
（ここのひらめきというか、パターンに対する知識というかが、解けるかどうかに大きい気がする）

1. $P$ 以下の素数を2つのグループに分ける
2. それぞれ同グループ内の素因数のみをもつ $N$ 以下の数を全列挙する（$U,V$ とする）
3. $U$ の各要素 $u$ につき、$V$ の中で、掛け合わせても $N$ 以下になる要素の個数を数える
   • $V$ をソートしておいて、$\lfloor \frac{N}{u} \rfloor$ の二分探索で求められる
4. その合計が答え

実際は最初に素数をグループに分けなくても、$U,V$ を構築していく過程で、 素数 $p$ を追加する時に要素の少ない方に追加していけば、大きく偏ることはない。

Python3