AtCoder Grand Contest 014 Task A - Cookie Exchanges 考察メモ

問題

本文

高橋君と青木君とすぬけ君はそれぞれクッキーを A,B,C 個持っています。 この 3 人はお互いにクッキーを交換することにしました。具体的には、以下の操作を繰り返します。

• 3 人は同時に、各々が持っているクッキーを半分ずつに分けて、残りの 2 人にそれぞれ一方を渡す。

ただし、誰かの持っているクッキーの個数が奇数個になったら、そこで操作を繰り返すのをやめます。 さて、クッキーの交換は何回行うことができるでしょうか。 ただし、無限に続けられる場合もあることに注意してください。

制約

• $1\leqq A,B,C \leqq 10^9$

普通の考え方

普通に解くと$O(\log N)$で捌けるので、その場合は特に難しくない。 $A,B,C$がともに等しい値で、かつ偶数のときにこの操作は無限ループとなる。

if a==b==c and a%2==0:
  print(-1)

そうでない場合は、単純に操作を繰り返してあげればよい。

else:
  res=0
  while a%2==b%2==c%2==0:
    a,b,c=(b+c)/2,(c+a)/2,(a+b)/2
    res+=1
  print(res)

コンテスト本番ならこの解き方でまったく問題ないと思うが、時間無制限で解くのであれば実力をつけるために$O(1)$で解けるようになりたいと思った次第である。

Python での最短解答

AtCoder の良いところは、強い人達の提出コードが読み放題なことである。 基本的に良質な情報というのはお金を払わなければ手に入らないものだが、競プロは無料で良質なコードをいくらでも閲覧することができる。控えめに言って最高である。

さて、私が愛してやまない Python による最短解答が以下であった。

a,b,c=map(int,input().split())
e=a-b|c-b
print(len(bin(e&-e))-3or~c%-2)

単純に 2 で割り切れる回数、ではない

これは、公式の入出力例からもわかる。

入力例

4 12 20

出力例

3

ここで 2 数の和の偶奇性を考えよう。 偶数になるケースを考えると、そのパターンは XNOR だ。すなわち、2 数がともに奇数、あるいは、ともに偶数であれば再び偶数に戻る。

すなわち元の数を単純に割っていって 2 で割り切れる回数 ：x&-xの最小値というわけにはいかない。

補足：x&-xについて

ビット演算に慣れていない人のために補足すると、x&-xにより 2 進数における最も下位の 1 が立っているビットの桁位置を知ることができる。

#適当な2進数を考える
+x = 0b010100

#負数にする（ビット反転して1を足す）
-x = 0b101100

#足し合わせればちゃんと0になる
+x = 0b010100
-x = 0b101100
 0 = 0b000000

#論理積（&）を取ってみる
+x = 0b010100
-x = 0b101100
 & = 0b000100

#一般化しても同じ
+x = 0bXXXXXX100000...  #最下位の1より上をXとする
~x = 0bYYYYYY011111...  #ビットを反転させるY=~X
-x = 0bYYYYYY100000...  #1が続くので繰り上がって揃う
 & = 0b000000100000...  #必ず最下位の1が取り出せる

3 行目から分解して考える

パッと見、すぐには理解できないがデカルト先生にならって困難は分割する。

また、求めるアウトプットから逆算したほうが経験的に早く紐解けることが多いので最後の 3 行目から分解していこう。

print()の中身を取り出すと、len(bin(e&-e))-3or~c%-2である。

さらに注意深く見るとlen()-3と~c%2がorで連結されていることが見えてくる。

前半の len 節

len()の中身はといえば、これが先ほど紹介したx&-xの形である。bin()は文字列を返すので、len()-3の節で求めているのは、eが 2 で何回割り切れるかということであるのがわかる。

後半の%節

負数が序数になる場合の剰余の性質はプログラミング言語ごとに異なるケースもあるが、Python では除数の正負と剰余の正負が必ず一致するように出力される。

すなわち、いま注目している~c%-2によって出力されうるのは、0か-1のどちらかに絞られる。

Python の真偽値と論理演算子

ここでしっかりと Python の真偽値や論理演算子の挙動を把握しておく必要がある。

Python だと真偽値bool型はint型のサブクラスであり、以下の対応になっている。

>>> True==1
True

>>> False==0
True

>>> True==-1
False

しかし、if節の中ではそれ以外でも真偽の判定がなされる。 具体的には0や空のオブジェクトがFalseと判断される。

>>> True if -1 else False
True

>>> True if [] else False
False

詳しくは、外部サイト¹を参照されたい。

そして、Python では論理演算子はショートサーキットである。

3 行目の分解結果

len(bin(e&-e))-3or~c%-2

ということは、eが 2 で 1 度も割り切れないときのみ前半部分がFalseになるということがわかる。

ショートサーキットなので、前半部分でTrueが返ると後半部分は評価されない。

つまりeが奇数なら、cが偶数のときに-1、奇数のときに0を返す文になっていることがわかる。

2 行目を分解する

e=a-b|c-b

パッと見ではわからなかった 2 行目だが、これまでの結果を元にここで必要な条件を逆算してみよう。

基本に立ち返って、「普通」の解答を思い出すと、

if a==b==c and a%2==0:
  print(-1)

$A=B=C$かつ$A$が偶数のときに-1を返している。

ここで、$A=B=C$であれば、互いに等価なので「$A$が偶数のとき」という条件は、「$C$が偶数のとき」として問題ない。

また、$A=B=C$かつ$A$が奇数のときを考えれば、1 度も操作が行えないのだから0を返すという挙動が正しい。

この挙動をよく見てみると、前項で紐解いたショートサーキットと~c%-2のなす挙動に当てはまっていることがわかる。

すなわち、$A=B=C$のとき、len(bin(e&-e))-3がFalseとなり、かつ$A=B=C$を満たさない場合にはelse節のwhileと同じ値を返すというのがeに求められる条件である。

$A=B=C$を満たす場合

以下では==を等号として用いる。

# a==b==cのとき、
e == a-b|c-b
e == a-a|a-a
e == 0|0
e == 0

# e==0より
e&-e == 0&0
e&-e == 0
bin(e&-e) == 0b0
len(bin(e&-e)) == 3

# 以上より、a==b==cのとき0を返す
len(bin(e&-e))-3 == 0

#何度も書くのが大変なので以下ではf()とする
f=lambda x:len(bin(x&-x))-3

$A=B=C$を満たさない場合

これは、すぐには意図が理解できないので、具体例でまず検証してみる。

先ほどの入力例で考えてみよう。

4 12 20

e = a-b|c-b
e = 4-12|12-20
e = -8|-8
e = -8
e = -0b1000
# 上で定義したf()を用いて表せば、
f(e) == 3

ここで、x-yのビット表現について以下が成り立つ。

• xとyのビットを下位からたどったときに互いに共通する桁まで0が連続するビットとなる
• ただし、x==yのときは 0 が返る

# Cは下位から連続してビットが共通する部分
  x = 0b???????XCCCCC
  y = 0b???????YCCCCC
x-y = 0b???????100000  #CでないのでX^Yは必ず1

漸化式もどきを考える

今回、$A,B,C$は等価なので、$A$のみに注目して考えてみると、以下のように推移している。

• $A_0=A$
• $A_1=\cfrac{B+C}2$
• $A_2=\cfrac{A_0+A_1}2=\cfrac{A_0}2+\cfrac{B+C}4$
• $A_3=\cfrac{A_1+A_2}2=\cfrac{A_1}2+\cfrac{A_0}4+\cfrac{B+C}8$

ここで、$A_n$の操作が行われているということは、$A_{n-1}$までを含む分数はすべて偶数である。 ということは$A_n\equiv\cfrac{B+C}{2^n}\equiv1\pmod2$となる$n$を求めればよいということがわかる。

つまり、$\cfrac{B}{2^n}\not\equiv\cfrac{C}{2^n}\pmod2$である必要がある。これは、剰余は除算以外は結合則が成り立つので、$\cfrac{B+C}{2^n}\equiv\cfrac{B}{2^n}+\cfrac{C}{2^n}\pmod2$であるからだ。

つまり、$B$と$C$を下の桁から見ていって、はじめてビットが一致しなくなる桁数$n$が求めたい$A_n$となっている。

これを$A,B,C$それぞれについて考えると、e=a-b|c-bの妥当性が見えてくる。

仮に$A=B$などが含まれていたとしても、最終的にorを取るので、$A,B,C$を相互に見たときに求めたい最小の桁数$n$が取得できることがわかる。

まとめ

問題を読むと、$A,B,C$のそれぞれが単純に 2 で割り切れる回数$f(x)$を求めればよいように感じるが、$f(A)=f(B)=f(C)$のケースでは、すべてが同時に奇数になった際に、操作の対象性と偶奇性から$A_n$が再び偶数に戻る点が注意点である。

さらに、e=a-b|c-bとおくことで、$A=B=C$の判定と、ビット共通部の判定をまとめて行うことができるという非常に優れた工夫が光るコードだった。

しかし、これをどのように導出したのか、その点が謎である。 もっとシンプルな思考経路で導いただろうことが予想されるが、現時点の私には、このようにこねくり回してコードが確からしいことを確認することしかできなかった。

もし、もっと簡潔な導出ができるという方がいれば、ぜひ Twitter 等からご連絡いただけると幸いである。