Codeforces Round #767 (Div. 1)

　D1まで四完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #767 (Div. 1) pretestはD1まで。
A 後ろからのMEXをもっておき、それと一致した時点で答えに加える
B xが回文、もしくはx+yが回文
C 証明はよく分からないけど、貪欲でOK。上下左右を使っていないマスを埋めて行く。
D1 実験エスパーしたらパスカルの三角形みたいなのが出てきた。

— titia (@titia_til) January 22, 2022

D2. Game on Sum (Hard Version)

　D1は実験エスパーといえばそうなんだけど、正しい漸化式を使って実験していた（漸化式を導いていたのに、それを使って二分探索で答えを探していた）。エスパーといいつつほぼ正しい解法通りやっていたので、まあ。

　D2は、それを高速化する。

　パスカルの三角形っぽいのだから、経路数に帰着できるのでは？　と考えれば良かった。

　

        0

      0   1

    0   1   4

  0   1   5   12

0   1   6   17   32

　という三角形の各数字は、右端の数字たちが何回か足されることによって成り立っている。

　三行目の右端の数字は4だけど、一つ上の数字との差分3がここに書いてあったと考える。

　このとき、五行目の三つ目の数字「６」は、この3と、その上の1からの和で成り立っている。二行目の「１」からの経路は3C1=3。なので、この和が6と求められる。