Codeforces Round #580(Div.2) A～C解説

Codeforces Round #580 (Div.2)のA～Cまでの解説です。
コンテスト中はA～Cの3完でした(Div.1共催の回であったためD問題以降の難易度が高く、結果的にCの早解きができるかが鍵のコンテストでしたが、Cで手間取りレートを少し落としてしまいました…)。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1206
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/69158

A問題:

制約が小さいため、全探索することを考えます。
すべてのi(1<=i<=n),j(1<=j<=m)について、ai+bjがAにもBにも含まれないようなi,jを求め、ai,bjを出力すればよいです。
ai+bjがA,Bに含まれるかどうかの判定は、A,Bの要素をset型などで持っておくことでO(logN+logM)で行うことができます。
以上のことから、この問題をO(NM(logN+logM))で解くことができました(A問題にしては易しめの印象でした)。

B問題:

明らかに、元の値が負であれば-1にし、元の値が正であれば+1にするのが最善です。
したがって、まずこの操作のコストを求めます。
次に、元の値に0があるかどうかで場合分けし、操作終了後のすべての要素の積が1になるように調整するためのコストを求めます。
元の値に0がないとき、元の値が負であるような数が偶数個あれば、調整を行わずともすべての要素の積は1となります。
一方、元の値が負であるような数が奇数個あれば、1回だけ-1または1の符号を反転させる必要があり、このときコストは2増加します。
元の値に0があるとき、すべての0を-1または1にする必要があるためコストは0の個数だけ増加します。
さらに、元の値が負であるような数が偶数個であれば、すべての0を1にしてしまえばよく、元の値が負であるような数が奇数個であれば、0を1つだけ-1にし、それ以外の0を1にしてしまうことですべての要素の積が1になります。
したがって、元の値に0があるとき、元の値が負であるような数の個数に関わらずコストは0の個数だけ増加します。
以上の場合分けを実装すればよく、この操作の計算量はO(N)となります。

サンプルコード(Python):
https://codeforces.com/contest/1206/submission/59010270

n=int(input())
arr=list(map(int,input().split()))
move=0
cnt=0
pcnt=0
ncnt=0
for i in range(n): #各要素について、-1または1に変更するコストを求める
  if arr[i]>0: #要素が正のとき
    move+=(arr[i]-1)
    arr[i]=1
    pcnt+=1
  elif arr[i]<0: #要素が負のとき
    move+=(-1-arr[i])
    arr[i]=-1
    ncnt+=1
  else: #要素が0のとき
    cnt+=1
if pcnt+ncnt==n: #配列に0がないとき
  if ncnt%2==0: #負数の数が偶数個であれば調整は必要ない
    print(move)
  else: #負数の数が奇数個であれば-1を1つ増やす必要があり、コストが2増加する
    print(move+2)
else: #配列に0がないとき
  if ncnt%2==0: #負数の数によらず、0の個数だけコストが増加する
    print(move+cnt)
  else:
    print(move+cnt)

C問題:

まず、どのようなnについて構成が可能かを考えます。
n個の連続する和を2n個作るとき、1から2nまでの値はそれぞれn回現れるので、それらの総和はn*2n*(2n+1)/2=n^2(2n+1)となります。
この値は、nが偶数のとき偶数となり、nが奇数のとき奇数となります。
総和が偶数のとき、これを2n個の和に分割すると、すべての和が等しくなるか、もしくはそれぞれの和の差が2以上になります。
それぞれの和の差が2以上になるとき、明らかに条件に反し、またすべての和が等しくなるとき、同じ値を使う必要がありますが、これも条件に反します。
したがって、nが偶数のときには解を構成することはできません。
逆に、nが奇数のときは必ず解を構成することができます。
以下、このことを示します。
まず、前提として、任意のi(1<=i<=2n)についてai+a(i+1)+…+a(i+n-1)とa(i+1)+…+a(i+n-1)+a(i+n)を考えると、条件より|(ai+a(i+1)+…+a(i+n-1))-(a(i+1)+…+a(i+n-1)+a(i+n))|<=1⇔|ai-a(i+n)|<=1を満たすことがいえます(ただしakについて、k>2nとなるときは、a(k-2n)を指すものとします)。
nが奇数のとき、総和が奇数となり、これを条件を満たすように2n個の和に分割すると、n個の値がk、残りn個の和がk+1となるようなkを取ることができます。
簡単のため、a1=1、a(n+1)=2と仮定します。
このとき、a1+a2+…+anがkでなければ、a2+a3+…+an+a(n+1)がk+1より大きくなってしまい、条件に反します。
したがって、a1+a2+…+anはk、a2+…+an+a(n+1)はk+1となります。
これを続けていくと、a3+…+an+a(n+1)+a(n+2)はkとなり、a4+…+an+a(n+1)+a(n+2)+a(n+3)はk+1となり、…と続いていきます。
これから、a2=a(n+2)+1,a3=a(n+3)-1,a4=a(n+4)+1,…,a(n)=a(2n)+1(nが偶数)、a(n)=a(2n)-1(nが奇数)と表すことができ、またこの条件を満たすようにa2,…,an、a(n+2),…a(2n)を定めると、上記の関係よりn個の和がk、残りn個の和がk+1となることが分かります。
したがって、この条件を満たすように適当にa2,…,an、a(n+2),…a(2n)を定めることで、この問題を解くことができます。
このようなa2,…,an、a(n+2),…a(2n)の決め方としては、2nから3までの数を以下のように互い違いに並べていき、各行をそれぞれa2,…,an、a(n+2),…a(2n)とすることで決めることができます。
例えば2n=10から3までの数を並べるときには、
10 7 6 3
9 8 5 4
というふうにならべ、10,7,6,3をa2,…,a5、9,8,5,4をa8,…a12と定めればよいです。
以上の操作はO(N)で行うことができるため、この問題を解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1206/submission/59058325

n=int(input())
if n%2==0: #nが偶数のときは構成は不可能
   print('NO')
else: #nが奇数のときは上記の方法で構成が可能
   print('YES')
   arr1=[]
   arr2=[]
   for i in range(2*n,2,-1):
       tmp=i%4
       if tmp==2 or tmp==3: #4で割ったあまりが2または3のときは1行目、それ以外のときは2行目に書かれる
           arr1.append(i)
       else:
           arr2.append(i)
   ans=[1]+arr1+[2]+arr2 #答えはa1=1,a2,…,an=arr1,a(n+1)=2,a(n+2),…,a(2n)=arr2となる
   print(*ans)