京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200)
記念すべき200回ということで、200に因んだ問題が多かった。
実装は割と素直だが、以下/未満などの境界でバグらせがち。
並び順のルールの上から順に、それ未満になる組合せを数えて、答えを確定させていく。
たとえば「3値の合計が 24 以下となる組合せが 99 個で、25 以下となる組合せが 125 個なら、K=100~125 番目の3値の合計は 25」という感じ。
パラメータの範囲として 1~N は少し扱いづらいので、0~N−1 の値を取るものとして考える。
まず、合計が X となるパラメータの組み合わせ数を求める。
上限が N−1 ということを一旦無視すると、 合計値 X を3パラメータに振り分けるので XH3=X+2C3 となる。
これを 0 から合計すると、X “以下”となるのは f(X)=(X+1)(X+2)(X+3)6 となる。
ここから、どれかが N−1 を超えてしまうものを除外する。
(※1) 1辺の長さ N の立方体を x+y+z=X となる平面で切断し、 原点側にある立体の中の格子点の数を数える問題と考えると、 はみ出ているのは1辺が X−N の三角錐3つ分
これで、合計が X 以下となるパラメータの組み合わせ数を O(1) で求められる。
これが K 未満なら、答えの合計値は X より大きい。
たとえば合計が 4 以下となる組み合わせが 35 個の時、
36 番目からは合計値が 5 であるということになる。
二分探索などで、O(logN) で求められる。
合計値がわかったので、綺麗さを0から順番に増やして調べる。
まず、T′ が固定されていたら、部分問題自体は典型である。
「範囲フリップの操作は、'0'と'1'の境界を最大2個消す操作と言い換えられる」ことを利用すると、'0'と'1'が隣り合う箇所を数えて2で割ればよい。
000110000111100 ↑↑ ↑ ↑ 2回の操作で2個ずつ境界をなくせる
ここに'?'が絡んでくるが、各箇所、独立に考えてよいので、主客転倒のテクニックが使える。
これを合計すればよい。
先頭と末尾が異なる文字だった場合、'0'と'1'の境界が奇数個になり、 切り上げて考えないといけない点が少しややこしくなるが、 便宜的に先頭の1文字を末尾にくっつけて考えると上手くいく。
000110000111100011 このままでは切り替わり位置が5回(奇数個)で、 ↑↑ ↑ ↑ ↑ 合計値を2で割ると異なった結果となってしまう 000110000111100011 0 先頭と合致しているかもカウントに加えることで偶数回が保証され、 ↑↑ ↑ ↑ ↑↑ 合計値を2で割っても正しい結果となる
|S|=1 や K=1 の時のコーナーケースに注意。