AtCoder Grand Contest 073 A,B問題メモ

AtCoder Grand Contest 073

ついにAGCでもChatGPTでそのまま解けたという例が現れたらしい。すごいねぇ（他人事）

A - Chords and Checkered

• 整数 $L,K$ 及び長さ $N$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます．
  • ここで，$2K \lt L$ 及び $0 \leq A_1 \lt A_2 \lt \cdots \lt A_N \lt L$ が保証されます．
• 周の長さが $L$ の円を考えます．
• この円の適当な点を基準点としてとり，そこから円周上を距離 $x$ だけ時計回りに進んだ場所を座標 $x$ の点と呼ぶことにします．
• また，各 $i$ ($1 \leq i \leq N$) について， 座標 $A_i$ の点と座標 $A_i+K$ の点を結ぶ弦を考え，これを弦 $i$ と呼ぶことにします．

• 弦の集合 $s$ に対して，以下の手順で スコアを定めます．
  • $s$ に含まれる弦をすべて描く．描いた弦によって円がいくつかの領域に分かれるので，それらを白と黒で塗る．
  • まず円の中心が含まれる領域を白く塗り，残りの領域は，(長さ正の線分で)隣接する領域の色が異なるように塗る．
  • このような塗り方は常に一意に存在することが証明できる．
  • ここで黒く塗られた領域の個数をスコアとする．

• $s$ としてあり得る集合は $2^N$ 通りあります．
• これらすべてに対するスコアの総和を $998244353$ で割ったあまりを求めてください．

• $1 \leq K$
• $2K \lt L \leq 10^9$
• $1 \leq N \leq 250000$
• $0 \leq A_1 \lt A_2 \lt \cdots \lt A_N \lt L$
• 入力はすべて整数

まず、各 $i=1,2,...,N$ について、$1～i-1$ の採用有無が決まっている状態で弦 $i$ を採用することの寄与（採用することで新たに増える黒の領域の個数）を考えてみる。

少し実験すると、弦 $i$ と「端以外の交点を持たない弦の採用可否」は関係せず、 「端以外の交点を持つ弦（$A_j \lt A_i \lt A_j + K$ なる $j$）」の、特に「個数」のみが重要であることが分かる。
この個数を $x$ とする。$x$ は二分探索で簡単に分かる。

$x$ 個のうち採用したのが $y$ 個である状態に弦 $i$ を引くと、交点は必ず $y$ 個でき、弦 $i$ は $y+1$ 個の区間に分かれる。
これを、$A_i+K$ に近い方から順に区間 $1,2,...,y+1$ と名付ける。

問題の制約から、区間 $1$ が通る領域は弦 $i$ を引く前は必ず白であった。
その後は交互に白と黒を通過するので、区間 $1,3,5,...$ が白、$2,4,6,...$ が黒を通過することになる。

白の領域をぶった切ると、白と黒が1つずつになり、黒の領域の個数が1増える。
黒の領域をぶった切っても、白と黒が1つずつになるが、この時は黒の領域の個数は増えない。
よって、$\lceil \frac{y+1}{2} \rceil$ 個、黒が増えることになる。

$x$ 個中、$y$ 個を採用する方法の個数は二項係数を使って ${}_x \mathrm{C}_y$ である。
$\displaystyle f(x) = \sum_{y=0}^{x} {}_x \mathrm{C}_y \left\lceil \frac{y+1}{2} \right\rceil$ が求まればよい。

これは、二項係数の偶数番目と奇数番目の和が等しいことを利用すると、以下のように変形できる。
または、最初の方を愚直に求めてOEISで検索すると A045623 が見つかる。

• $f(0)=1$
• $f(x)=(x+3)2^{x-2}$（$x \ge 1$）

ここに、交点を持たない弦 $N-x-1$ 本の採用の自由度 $2^{N-x-1}$ を乗じたものが、 弦 $i$ を採用したときの寄与となり、各 $i$ についての合計が答えとなる。

ただし、$A_i \lt K$ となる $i$ については、ループを考慮して1周前から来て交点を持つものも $x$ に含めておく必要がある。

Python3

from bisect import bisect


def solve(l, k, n, aaa):
    aaa = aaa + [a + l for a in aaa]
    ans = 0
    MOD = 998244353
    for i in range(n, n * 2):
        a = aaa[i]
        l = bisect(aaa, a - k)
        r = bisect(aaa, a) - 1
        x = r - l
        if x == 0:
            ans += pow(2, n - 1, MOD)
            ans %= MOD
        elif x == 1:
            ans += 2 * pow(2, n - 2, MOD)
            ans %= MOD
        else:
            ans += (x + 3) * pow(2, x - 2, MOD) * pow(2, n - x - 1, MOD)
            ans %= MOD
    return ans


l, k, n = map(int, input().split())
aaa = list(map(int, input().split()))
ans = solve(l, k, n, aaa)
print(ans)

B - Cyclic Jump

• 長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます．
• あなたは今，数直線上の座標 $0$ の位置に立っており，今から以下の操作を好きな回数行います．
  • $A$ の好きな要素 $A_i$ を自由に選ぶ．また，正負のうち好きな方向を選ぶ．
  • 選んだ方向に距離 $A_i$ だけジャンプする．

• あなたは以下の条件を満たす操作列に興味があります．
  • 操作を $1$ 回以上行い，最終的に座標 $0$ に戻ってくる．
  • 途中で座標が負の領域に入らない．
  • 連続して同じ距離かつ異なる方向にジャンプすることがない．

• 条件を満たす操作列のコストを，その操作列に従って動いた際に訪れる座標の最大値とします．
• 条件を満たす操作列のコストとしてあり得る最小値を求めてください．
• なおこの問題の制約より，条件を満たす操作列は必ず存在します．
• $1$ つの入力につき，$T$ 個のテストケースを解いてください．

• $1 \leq T \leq 125000$
• $2 \leq N \leq 250000$
• $1 \leq A_1 \lt A_2 \lt \cdots \lt A_N \leq 10^{18}$
• $1$ つの入力における $N$ の総和は $250000$ を超えない
• 入力はすべて整数

公式Editorialを読むと非常に簡単な実装で解けるにも関わらず、その実装に至る発想と証明がなかなか難しい。

「実は、最適な操作で使うのは限られた2～3個の要素だけでした」とかだったら考えやすいなと思い、 何となく「特定の2要素 $A_i, A_j$ だけを使う」という限定を入れてみるとどうなるか考える。

この場合、どちらかは常に + で使い、どちらかは - で使うことになる。

略証

その前提で実験すると、答えは $A_i+A_j-\gcd(A_i,A_j)$ となりそう。

Ai = 7    Aj = 11    7+11-gcd(7,11) = 17

  +7   +7    -11   +7    +7    -11   +7    -11   +7   +7
0    7    14     3    10   [17]    6    13     2    9    16  ↙

   -11   +7    -11   +7   +7    -11   +7    -11
16     5    12     1    8    15     4    11     0

だがここで、例えば3つめの要素として $A_k=12$ があったとすると、上記の操作列を「最大値を超えた途中」から開始できる。
この場合、最大値は $15$ となり、上記より良くなる。

  +12    -11   +7   +7    -11   +7    -11
0     12     1    8    15     4    11     0

また、$13,14$ の2要素があったとしても、

  +14    -13   +7   +7    -11   +7    -11
0     14     1    8    15     4    11     0

このように、$1$ を作ってそこから開始することができ、最大値を減らせる。
（この例では $+7,+7,-14$ とした方がさらに安くなるが、まぁ、2個以上の要素を使う例がいくらでも作れる例として）

なので、限られた少数の要素のみを使えばよいという解法では無さそう。
そうなるとお手上げであった。

• 解説 - AtCoder Grand Contest 073

答えを $f(A_1,A_2,...,A_N)$ とする。一般性を失わず、$A_1=\min(A)$ とする。

この時、$f(A_1,A_2,...,A_N) = A_1+f(A_1,A_2-A_1,...,A_N-A_1)$ が成立する。
つまり「$A_1$ と、それ以外から $A_1$ を引いた要素からなる多重集合」で同じ問題を解き、$A_1$ を加えたものと等しくなる。
この時、引数の中身には同じ要素があってもよく、$i \neq j$ であれば $A_i=A_j$ であっても $(+A_i, -A_j)$（同じ距離だけ行って戻る）操作は可能とする。

「おいおい、そんな $A_1$ を引いて各要素を小さくしちゃうと、 小回りが利きすぎて実際より小さいコストが求まってしまうんじゃないのかい？」と直感的に思ってしまうが、、、

「元の問題の制約を満たす操作列」↔「変換後の問題の制約を満たす操作列」間を、 最大値（$+A_1$ のオフセット付き）を変化させずに相互に変換できることを示せばよい。

「元の問題の最適解の操作列は、変換後の問題を解くことで必ず見つかる」し、 「変換後の問題で見つかった最適解は、必ず元の問題に復元できる」ことが言える。

               ／\
          /＼／   \           変換後の操作列は、元の操作列の累積値の遷移の
___/＼___/_________\___  A1   A1以上の部分を再現するものと考えられる。
  /   ＼/           \
 /                   \

初手とラストは、$A_1$ を使ったなら単に省略すれば良く、 そうでないなら $A_i-A_1$ を使ったことにすると変換後の問題に対応づけられる。

途中の手は、累積値が $A_1$ を下回らない限りは、$A_i-A_1,A_1$ を順に使ったことにするとよい。

途中で累積値が $A_1$ を下回る場合は、変換後の問題で $0$ を下回ることになってしまう。

ただし、この場合、必ず $A_1以上→A_1未満→A_1以上$ という変化をしている。
（$A_1$ が最小値であるため、$A_1$ 未満から続けて負の方向に移動することはできない）

元の問題でこの部分の操作列が $(-x,+y)$ だったとすると、 変換後は $(-(x-A_1),+(y-A_1))$ という操作に対応づけることで、$0$ を下回ることを回避できる。

だいたい、逆のことをすればよい。

変換後の操作列を $A_1$ だけ底上げして、 「$A_1$ から出発して、$A_1$ を下回ること無く、$A_1$ に戻ってくる操作列」だと考える。

初手とラストは、$A_1$ を追加すればよい。

途中に出現する $A_i-A_1$ は、 操作前と操作後の累積値がいずれも $A_1$ 以上であるため、 元の操作列では $0$ を下回ること無く、最大値を増やすこと無く、$A_i$ と $A_1$ の2回の操作に復元できる。

• $+(A_i-A_1)$ の場合は、$(-A_1, +A_i)$ を順に行ったという操作に復元できる
• $-(A_i-A_1)$ の場合は、$(-A_i, +A_1)$ を順に行ったという操作に復元できる

これによって $(+A_1,-A_1)$ が隣り合ってしまった場合、それは削除して問題ない。

これで、変換後の操作列から元の問題の操作列にも復元できることが示された。 （隣り合う操作を復元した結果、絶対に $(+A_i,-A_i)$ が隣り合わないことの証明などは若干甘いが）

$A$ をソートし、小さい方から2つを $a,b$ とする。オフセットを $0$ で初期化する。

$b$ が $a$ で割り切れる場合、答えは $b + オフセット$ である。

そうで無い場合、$b$ を超えない最大の $a$ の倍数を $ka$ とし、オフセットを $ka$ 増やし、$a$ 以外から $ka$ を引く。

以上を繰り返せばよい。

ユークリッドの互除法を、1対多で行っているようなイメージ。
この繰り返しは高々 $O(\log{\max(A)})$ 回しかおこなわれないので、 全体の計算量は $O(N\log{N}\log{\max(A)})$ となる。

$A$ をソートする部分を、最小値2つを検索する線形走査にすればオーダー上は $\log{N}$ は取れるが、 Pythonでは下手な自前実装の $O(N)$ より、組み込みの $O(N \log{N})$ の方が速かったりする。

Python3

def solve(n, aaa):
    offset = 0
    while True:
        aaa.sort()
        a, b = aaa[0], aaa[1]
        if b % a == 0:
            return b + offset
        d = b // a * a
        for i in range(1, n):
            aaa[i] -= d
        offset += d


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    print(ans)