京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）E,F問題メモ

京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）

記念すべき200回ということで、200に因んだ問題が多かった。

E - Patisserie ABC 2

• ABC洋菓子店のケーキはそれぞれ $1～N$ の値で表される3つのパラメータ「綺麗さ」「おいしさ」「人気度」をもつ
  • 全部で $N^3$ 通りのパラメータの組み合わせがある
• パラメータの異なる $N^3$ 個のケーキを以下の順で並べる
• 並び順
  • 3つのパラメータの合計が小さい方が左
  • 合計が同じなら、綺麗さの小さい方が左
  • それでも同じなら、おいしさの小さい方が左
• 左から $K$ 番目のケーキのパラメータを求めよ
• $1 \le N \le 10^6$
• $1 \le K \le N^3$

実装は割と素直だが、以下/未満などの境界でバグらせがち。

並び順のルールの上から順に、それ未満になる組合せを数えて、答えを確定させていく。
たとえば「3値の合計が $24$ 以下となる組合せが $99$ 個で、$25$ 以下となる組合せが $125$ 個なら、$K=100～125$ 番目の3値の合計は $25$」という感じ。

パラメータの範囲として $1～N$ は少し扱いづらいので、$0～N-1$ の値を取るものとして考える。

まず、合計が $X$ となるパラメータの組み合わせ数を求める。

上限が $N-1$ ということを一旦無視すると、 合計値 $X$ を3パラメータに振り分けるので ${}_XH_3={}_{X+2}C_3$ となる。

これを $0$ から合計すると、$X$ “以下”となるのは $f(X)=\dfrac{(X+1)(X+2)(X+3)}{6}$ となる。

ここから、どれかが $N-1$ を超えてしまうものを除外する。

• $0 \le X \le N-1$ のとき、1つもはみ出る心配は無い
• $N \le X \le 2(N-1)$ のとき、1つだけはみ出ることがある
  • $3 \times f(X-N)$ を除外する(※1)
• $2(N-1)+1 \le X$ のとき、全体 $N^3$ から引くことを考えると、1つめのパターンに帰着できる

(※1) 1辺の長さ $N$ の立方体を $x+y+z=X$ となる平面で切断し、 原点側にある立体の中の格子点の数を数える問題と考えると、 はみ出ているのは1辺が $X-N$ の三角錐3つ分

これで、合計が $X$ 以下となるパラメータの組み合わせ数を $O(1)$ で求められる。

これが $K$ 未満なら、答えの合計値は $X$ より大きい。
たとえば合計が $4$ 以下となる組み合わせが $35$ 個の時、 $36$ 番目からは合計値が $5$ であるということになる。

二分探索などで、$O(\log{N})$ で求められる。

合計値がわかったので、綺麗さを0から順番に増やして調べる。

Python3

def get_pattern(x):
    if x <= n * 2 - 2:
        cur = (x + 1) * (x + 2) * (x + 3) // 6
        if x > n - 1:
            cur -= (x - n + 1) * (x - n + 2) * (x - n + 3) // 2
    else:
        cur = n ** 3
        cur -= (n * 3 - 3 - x) * (n * 3 - 3 - x + 1) * (n * 3 - 3 - x + 2) // 6
    return cur


def solve(n, k):
    l, r = -1, n * 3 - 2
    while l + 1 < r:
        m = (l + r) // 2
        cur = get_pattern(m)

        if cur < k:
            l = m
        else:
            r = m

    remain = k - get_pattern(l)
    for a in range(min(r + 1, n)):
        if r - a > (n - 1) * 2:
            continue
        if r - a > n - 1:
            b = r - a - (n - 1)
            cnt = n - b
            if cnt >= remain:
                return a + 1, b + remain, r - a - b - remain + 2
            remain -= cnt
        else:
            cnt = r - a + 1
            if cnt >= remain:
                return a + 1, remain, cnt - remain + 1
            remain -= cnt


n, k = map(int, input().split())
print(*solve(n, k))

# def check(n, k):
#     buf = []
#     for a in range(1, n + 1):
#         for b in range(1, n + 1):
#             for c in range(1, n + 1):
#                 buf.append((a + b + c, a, b, c))
#     buf.sort()
#     return buf[k - 1][1:]
#
# n = 9
# for k in range(1, 9 ** 3 + 1):
#     s = solve(n, k)
#     c = check(n, k)
#     print(k, s, c, s == c)

F - Minflip Summation

• '0','1','?'からなる文字列 $S$ が与えられる
• これを $K$ 個連結したものを $T$ とする
• $S$ に含まれる'?'の個数を $q$ とすると、'?'を全て'0'か'1'へ置き換える方法は $2^{Kq}$ 通り
• その全てについて、以下の問題を解いて、その答えの和を $\mod{10^9+7}$ で求めよ
• 問題
  • '?'を置き換えた後の文字列を $T'$ とする
  • $1 \le l \le r \le |T'|$ なる整数 $l,r$ を選び、$T'_l～T'_r$（両端含む）の各文字をフリップする
  • 全てを同じ文字にするのに必要な最小の操作回数は何回か？
• $1 \le |S| \le 10^5$
• $1 \le K \le 10^9$

まず、$T'$ が固定されていたら、部分問題自体は典型である。

「範囲フリップの操作は、'0'と'1'の境界を最大2個消す操作と言い換えられる」ことを利用すると、'0'と'1'が隣り合う箇所を数えて2で割ればよい。

000110000111100
  ↑↑  ↑  ↑    2回の操作で2個ずつ境界をなくせる

ここに'?'が絡んでくるが、各箇所、独立に考えてよいので、主客転倒のテクニックが使える。

• '0'と'1'が隣り合う箇所
  • '?'の置き換え方 $2^{Kq}$ 通りの全てで1回ずつカウントされる
• '?'と（'0'または'1'）が隣り合う箇所
  • '?'が、隣と異なる数字に置き換えられたとき、1回カウントされる
  • 他の'?'の置き換え方 $2^{Kq-1}$ 通りの全てで1回ずつカウントされる
• '?'同士が隣り合う箇所
  • 4通りの置き換えパターンのうち2通りでカウントされる
  • 他の'?'の置き換え方 $2^{Kq-2}$ 通りの全てで2回ずつカウントされる

これを合計すればよい。

先頭と末尾が異なる文字だった場合、'0'と'1'の境界が奇数個になり、 切り上げて考えないといけない点が少しややこしくなるが、 便宜的に先頭の1文字を末尾にくっつけて考えると上手くいく。

000110000111100011    このままでは切り替わり位置が5回（奇数個）で、
  ↑↑  ↑  ↑ ↑     合計値を2で割ると異なった結果となってしまう

000110000111100011 0  先頭と合致しているかもカウントに加えることで偶数回が保証され、
  ↑↑  ↑  ↑ ↑↑   合計値を2で割っても正しい結果となる

$|S|=1$ や $K=1$ の時のコーナーケースに注意。

Python3

def solve(s, k):
    MOD = 10 ** 9 + 7

    if len(s) == 1:
        if k == 1:
            return 0

        if s == '?':
            return k * pow(2, k - 2, MOD) % MOD
        else:
            return 0

    c_fix = 0
    c_one = 0
    c_both = 0
    q = 0

    for a, b in zip(s, s[1:] + s[0]):
        if a == '?':
            if b == '?':
                c_both += k
            else:
                c_one += k
            q += 1
        else:
            if b == '?':
                c_one += k
            elif a != b:
                c_fix += k

    p1 = pow(2, k * q - 1, MOD)
    p0 = p1 * 2 % MOD
    inv2 = pow(2, MOD - 2, MOD)

    ans = (p0 * c_fix + p1 * (c_one + c_both)) * inv2 % MOD
    return ans


s = input()
k = int(input())

print(solve(s, k))