東京海上日動 プログラミングコンテスト2021（AtCoder Regular Contest 122) A,C,D,E問題メモ

東京海上日動 プログラミングコンテスト2021（AtCoder Regular Contest 122)

A - Many Formulae

• 長さ $N$ の非負整数列
• $N-1$ 箇所の各項間に演算子 '+' または '-' を入れて1つの式を作る
• 演算子の入れ方は $2^{N-1}$ 通りあるが、そのうち '-' が2回以上連続で登場しない式を「良い式」とする
• 全ての良い式の答えの総和を $\mod{10^9+7}$ で求めよ
• $1 \le N \le 10^5$

主客転倒。

良い式のうち、$A_i$ が正で寄与する式の個数を $p_i$、負で寄与する式の個数を $q_i$ とすると、 $A_i \times (p_i-q_i)$ を各 $i$ について総和をとったものが答え。

$p_i,q_i$ は、自身の左右に、記号を自由に決められる箇所がそれぞれ何個連続しているかで決まる。
'-' を置くとその両隣は '+' を置くしかないので、自由に決められる箇所は左右それぞれ1ずつ短くなる。

               3 1 4 1 5 9 2
                    ^
+を置いたとき  左2  右3 ... p3 = f(2)*f(3)
-を置いたとき  左1  右2 ... q3 = f(1)*f(2)

※ f(x)は長さx+1の良い式の個数

$f(x)$ は以下のDPで求められる。

• $DP[i][j:0/1]=i$ 番目の演算子まで考えて、最後($i$ 番目)が+/-だったときの良い式の個数

そしてこれは、遷移式を作るとわかるがフィボナッチ数列となる。

以下の、末端部分に関する処理に留意する。

• $A_1$ は必ず正で寄与する
• 最左の演算子置き場は、左で自由に決められる箇所は '+' でも '-' でも0箇所
• 最右も同様

Python3

C - Calculator

• 変数 $x,y$ があり、最初はどちらも0
• 以下の4種類の操作を好きな順で好きな回数行う
  • 1: $x←x+1$
  • 2: $y←y+1$
  • 3: $x←x+y$
  • 4: $y←x+y$
• 130回以下の操作で $x$ の値を $N$ にする操作方法の一例を示せ
  • そのときの $y$ の値は問わない
• $1 \le N \le 10^{18}$

$(x,y)$ の組を頂点として、$(0,0)$ から4つの操作の通りに遷移するBFSなどは、 頂点数がアホほど多くなるので無理。

ならばと $(N,y)$ という最終状態から逆にたどることもできるが、 その場合 $y$ には何の値が入っていてもよく、何が最適なのか決められない。

どうも最短経路的に解くのは難しそう。

$N$ の上限は $10^{18}$ とやたら大きいが、どんなに大きくても130回以内でできるらしい。 そのためまずはとにかく大きくする操作方法を考える。

$x$ や $y$ が1以上なら、1を足すより操作3,4でもう一方を足した方がよいので、 はじめに操作1と2で $(1,1)$ にした後は3と4を交互に行うのがよさそう。
その場合、$x,y$ はフィボナッチ数列の項を交互にたどる。

x   y   x   y   x   y   x   y   x   y   x   y  ...
1   1   2   3   5   8  13  21  34  55  89 144  ...

と、だいたい88項目くらいで $10^{18}$ を超えるので、 数を大きくするのはこの方法で大丈夫そう。

あとはフィボナッチ上に現れない $N$ の場合にどう調整するかだが、 $N$ をいくつかのフィボナッチの項の和にすることはできそう。

140 = 89 + 34 + 13 + 3 + 1

• これができるということに名前が付いているらしい
  • ゼッケンドルフの定理

操作3,4を繰り返す中の適当なタイミングで $x$ や $y$ に1足してやれば、 そこからもまたフィボナッチ数列が始まる。
（見た目上は一緒くたになった数字だが、個々のフィボナッチに分解できる）

x   y   x   y   x   y   x   y   x   y   x   y  ...
1   1   2   3   5   8  13  21  34  55  89 144  ...
        1   1   2   3   5   8  13  21  34
                1   1   2   3   5   8  13
                            1   1   2   3
                                    1   1
                                      ====
                                      140
(見た目上のx,y)
1   1   2   4   7  12  20  32  53  86 140
       ↓      ↓          ↓      ↓
        3       8          33      87

$N$ がフィボナッチ数列の $c_1,c_2,...$ 項目の和で表現できる場合、

• 一番大きい $c_{\max}$ が(0-indexedで)偶数なら上記の通りで良い
• 一番大きい $c_{\max}$ が奇数なら、上記のままだと $N$ になるのは $y$ になってしまう
  • →操作を $x,y$ 逆にしたものに読み替える

• $c_{\max}$ 以外の各 $c_i$ について、$c_{\max}$ 項目でちょうど希望の値にするためにはどこで1を足しておく必要があるか
  • $d_i=c_{\max} - c_i$
• 操作3,4を交互に行う中で、$d_i$ 回目の操作タイミングで、操作を行った方に +1 する

と、できあがり。

Python3

フィボナッチのように、直前の2項を足す数列の隣り合う項の比は、黄金比 $=1.618...$ に近づいていく。

操作3,4を繰り返すのが手っ取り早く値が増加して、その比が黄金比になるとしたら、最終状態の $(N,y)$ は $N:y=1.61803398874989484820...:1$ に近くなっているはず。

操作を逆からたどることを考えると、交互に引き続けることで、ちょうどいい具合にこの比が保たれる（黄金比なので）。

勿論、$x,y$ は整数であるため誤差が蓄積されるので調整は必要となる。

大きい方から小さい方を引いてもまだ大きい方が大きい、ということがあり得るが、 連続になってしまってもよいので「大きい方から小さい方を引く」のルールで操作する。

また、一方がゼロになったら、もう一方は操作1,2で1ずつ足していって作る。

これらの状態になるのは値が相応に小さくなってからのはずなので、必ず間に合うという保証が難しいが、いけるらしい。

D - XOR Game

• $2N$ 個の整数 $A_1,A_2,...,A_{2N}$
• AliceとBobがゲームをする
• 手順とルール
  • 以下を $N$ 回繰り返す
    • Aliceが残っている整数を1つ選び、消す（$x$ とする）
    • Bobが残っている整数を1つ選び、消す（$y$ とする）
    • $x \oplus y$ をノートに記録する
  • 最後にノートに記録された $N$ 個の整数のうち、最大値をゲームのスコアとする
  • Aliceはスコアを最大化、Bobは最小化したい
• 両者が最適に行動したときのスコアを求めよ
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \lt 2^{30}$

まず、こういうのは高位のbitから決めていくのがよさそう。

後攻のBobに圧倒的に利がある。

$A_i$ の中での最高位bitを '10000' とする。
ここが立った $A_i$ の個数を数える。

• Aliceが '10000' が立った整数を選んできたら、Bobも立った整数を選ぶ
• Aliceが '10000' が立ってない整数を選んできたら、Bobも立ってない整数を選ぶ

ことで、絶対にスコアの '10000' は立たせないことができる。

なので、以下の2つの問題に分割でき、その大きい方となる。

• '10000' が立った整数の中での答え（'10000' のbitは寝かせてしまうとやりやすい）
• '10000' が立ってない整数の中での答え

必ずどこかでは '10000' が立ってる1つと立ってない1つをペアにすることになる。
従って、スコアにおいて '10000' のbitは立ってしまう。

Bobは「立ってる1つと立ってない1つのペアで、XORが最小のもの」を見つけることになる。

このペア以外の整数をAliceが選んできたら、 Bobも '10000' の立ってる/立ってないが同じ、ペア以外の整数の中から適当に1つ選べばよい。

このペアの整数をAliceが選んできたら、 すかさずBobはペアのもう一方を選べばよい。

これでBobは最小値を達成できる。

見つけ方だが、なるべく '1000' 以下の高位bitから見たときに接頭辞が長く共通している2数を選べばよい。
そのようなものがない （たとえば '10000' が立ってる整数の中では '100' が立ったものしか無く、 '10000' が立ってない整数の中では '100' が立ってないものしか無い）場合は、 仕方ないので '100' は立てて、さらに下位のbitを共通させられるか調べていく。

たかだか深さが30程度なので、再帰関数で実装した。

EditorialではTrie木を構築するとあった。なるほど。
Trie木なら、多対多からなるべく共通させられるようなものを探すのに適している。

Python3

E - Increasing LCMs

• $N$ 個の整数 $A_1,A_2,...,A_N$（互いに異なる）
• これらの整数を、以下の条件を満たすように並べ替える
  • 先頭からの累積LCMが狭義単調増加
• 可能か判定し、可能なら一例を示せ
• $1 \le N \le 100$

素因数分解とかしてしまいそうになるが、気付けば意外と簡単。

末尾から考えるとよい。

基本的に一番制約がきついのは末尾の数で、そこに置ける数があるなら貪欲に置いていってよい。
複数個候補があるならどれでもよい。

末尾に $A_i$ を置けるかどうかの判定は、 残っている整数から $A_i$ を除いた項の総LCMを $l$ とすると、$l$ が $A_i$ の倍数で無ければよい。

64bit Intの制約の中で解くなら、まず他の残っている全ての整数と $A_i$ とのGCDをそれぞれとり、その総LCMを取ればよい。
GCDを取ることで余計な素因数にフィルターをかけている感じなので、総LCMは $A_i$ を超えない。総LCMが $A_i$ と等しくなってしまったらNG、未満ならOK。

Python3

やけにPythonでACしてる人が多くて一瞬驚いたが、 多倍長を使える言語が有利な問題なため、 この問題だけPythonを使っていた、みたいな人が一定数いたためだった。