AtCoder Grand Contest 010 - D言語で競プロ

参加しました、Ａだけの１完でした
AtCoder Grand Contest 010 - AtCoder Grand Contest 010 | AtCoder

A.o
B.xxx

公式の解説
https://atcoder.jp/img/agc010/editorial.pdf

A - Addition

A: Addition - AtCoder Grand Contest 010 | AtCoder

問題概要

N個の整数{A[1], A[2], ..., A[N]}が与えられ、次の操作が出来る

偶奇の等しい２つの整数A[i], A[j]の和A[i] + A[j]を新たに加えて、元のA[i], A[j]を消す

与えられた{A[1], A[2], ..., A[N]}について、この操作を繰り返し、最終的に１つだけに出来るかどうか判定せよ

制約

2 <= N <= 10^5

感想

偶奇の等しい整数同士を足すと、その結果は必ず偶数になります
なので、奇数の２つのペアは足して１つの偶数にできます
なので、{A[1], A[2], ..., A[N]}に含まれる奇数の個数を数えて、それが偶数個あれば全て偶数にでき、最終的に１つにできます
一方奇数個なら、必ず１つ奇数が余りますから、最終的に{奇数、偶数}となってしまい、１つにできません
N = 1があるならコーナーケースがありますが、今回はN >= 2なのでコーナーケースが無いですね

これをコードにすると以下のようになります、計算量はO(N)です
実際はもっと何か冗長に書いちゃってますが……

def solve():
    N = int(input())
    A = [int(i) for i in input().split()]
    yes = 'YES'
    no = 'NO'

    num_od = 0

    for a in A:
        if a % 2 == 1:
            num_od += 1

    if num_od % 2 == 1:
        print(no)
    else:
        print(yes)

それで解説を聞くとsum(A)の偶奇分けだけでよかったみたいです
確かに奇数が奇数個あるか偶数個あるかということとsum(A)が奇数か偶数かという問いは同値ですね。
コンテスト中はどんな方法でもいいからなるべく早く解く、っていうのを意識してるのでより簡潔な表現はなかなか追い求める時間が無いものですが気づけるといいですよね。

def solve():
    N = int(input())
    A = [int(i) for i in input().split()]
    yes = 'YES'
    no = 'NO'

    if sum(A) % 2 == 0:
        print(yes)
    else:
        print(no)

B - Boxes

B: Boxes - AtCoder Grand Contest 010 | AtCoder

問題概要

N個の箱が円環状に並んでおり、i番目の箱にはA[i]個の石が入っている
このとき、次の操作を繰り返して、最終的に全ての箱を空に出来るかどうか判定せよ

i番目の箱を選び、j = 1 ~ N に対して、i + j番目の箱から石をj個取り除く。ただしi + jがNを超えるとき、mod Nで同一視すること。

上記の操作は取り除きたい個数の石が無い箱が存在するとき、その操作を行えないことに注意せよ。

制約

1 <= N <= 10^5
1 <= A[i] <= 10^9

感想

いやあ、難しかったですね……残りの100分全てこの問題に費やしたんですけど結局解けませんでした。
一応コードは何度か提出したんですが最後までWAが取れませんでした、嘘解法でしたね。

まずすぐに分かることとして（私は全然すぐに分からなかったですが）、１回の操作で全体からN*(N+1)/2個の石が減るという事実があります。
よって、sum(A)がN*(N+1)/2の倍数になっていなければ、答えはNOになります。
では、sum(A)がN*(N+1)/2の倍数であれば、答えは必ずYESになるのか、ということですがこれはもちろんNOです。
例えば、N = 3, A = [1, 3, 2] という反例があります。

じゃあどうすれば必要十分なんだってとこが問題ですよね。
実際私はここからなかなか先に進みませんでした。
なんか具体例を作って列挙してみたり、ということをしたりして何とかヒントを掴もうとしてました。

N = 3, A = [1, 3, 2]は無理だけど、 A = [1, 2, 3]は明らかに可能なのでどうやら向きが関係してそうだということが分かります。
この辺でようやく隣合う２項の差を取ってみる、という発想に至ります。前のCodeforcesで解けもしないEに取り組んでたのが微妙に生きてるなと思いました。
それで元の数列から引いていくんじゃなくて、全部空の状態から+1, +2, ..., +Nってしていってその数列になるかっていう風に考えました。
すると+1, +2, ..., +Nって1 - N = 1 mod N であることも含めて隣との差がmod N で考えると全部1なんですよね、なのでこの操作を１回するごとに隣との差が1ずつ増えることになります。
ということはK回+1, +2, ..., +Nってやると、隣との差が全てK mod Nになってるはずなんですよね。
この操作の回数のKっていうのはsum(A) / (N(N+1)/2)ですぐに求められます。
だから与えられたAに対して全ての隣合う２項の差を取って、その差が全てK mod NになってればYES、そうでなければNOだ、と考えました。

……っていう罠（？）にはまりました。
「与えられたAに対して全ての隣合う２項の差を取って、その差が全てK mod Nになっている」
これって確かに「全ての箱の石が取り除ける」ことの必要条件ではありますが、十分条件になってるかが全く考慮されていないのでダメでした。
そもそも「K回+1, +2, ..., +Nってやると」っていう仮定が「全ての箱の石が取り除ける」ことを仮定していることと同じなので。

Aの隣り合う２項の差を取るってとこまではよかったみたいですね。d[i] = A[i + 1] - A[i]として、元の数列ではなく、差の世界で考える。
すると１回の操作で-1, -2, ..., -Nと石を引いていくという操作は、差の世界では各iについてd[i]を-1するということに対応している。
ただし、唯一の例外として-N, -1の間では逆に差が増えることになるのでそこではd[i]が+(N-1)されるということになる。
つまり差の世界では１回の操作はあるjを選んで
d[i] = d[i] - 1 (i != j)
d[j] = d[j] + N - 1
という操作をすることに等しい、ということですね。
そして、K回操作をして全ての石を取り除けるか、という問いは差の世界では「K回上の操作をしたときに全てd[i] = 0とできるかどうか」に等しいことになります。

それで、まず1回の操作で-1するか+(N-1)されるかなので、各iについてd[i] <= Kが成り立っていなければどうやってもd[i] = 0になりません。
次に各iについてd'[i] = d[i] - K と置き直してやると、上の操作はあるjを選んで、他のd'[i]は変化させずに
d'[j] = d'[j] + N
とすることに等しくなります。この操作をK回繰り返して全てのd'[i]をd'[i] = 0と出来るか、という問題になります。
これを確かめるには各d'[i]がNの倍数になっていることが必要十分条件です。

「これに加えて、sum(d'[i]) // N = -Kであることも確かめなきゃいけないのでは？」

と思いますが、もともとのd[i]の定義がd[i] = A[i + 1] - A[i]だったので、sum(d'[i]) = sum(d[i] - K) = -NK なので上のことは確かめなくても成り立っているというわけですね。

長々書きましたが、コードはこんな感じでO(N)で解けますね。

def solve():
    N = int(input())
    A = [int(i) for i in input().split()]
    K, r = divmod(sum(A), N * (N+1) // 2)
 
    if r != 0:
        print('NO')
        return None
 
    dif = [A[(i + 1) % N] - A[i] for i in range(N)]
 
    for i in range(N):
        if dif[i] > K or (K - dif[i]) % N != 0:
            print('NO')
            return None
 
    print('YES')
 
if __name__ == '__main__':
    solve()

でも前半に書いた嘘解法に対するシンプルな反例が見つけられないんですよね