AtCoder Beginner Contest 387（Promotion of AtCoderJobs）E,F問題メモ

AtCoder Beginner Contest 387（Promotion of AtCoderJobs）

新年1発目にちなみ、$2025$ という数が持つ性質や巳年のヘビを発想の起点としたような問題が多くて面白かった。

C問題は何故Cに置いたしというくらい難しかったな。。。

E - Digit Sum Divisible 2

• 正整数 $n$ の桁和を、$n$ を $10$ 進法で表したときの各桁の和と定義します。例えば $2025$ の桁和は $2 + 0 + 2 + 5 = 9$ です。
• 正整数 $n$ が $n$ の桁和で割り切れる時、$n$ を 良い整数 と呼びます。例えば $2025$ はその桁和である $9$ で割り切れるので良い整数です。
• 正整数の組 $(a, a+1)$ であって $a$ と $a+1$ が共に良い整数であるものを 双子の良い整数 と呼びます。例えば $(2024, 2025)$ は双子の良い整数です。
• 正整数 $N$ が与えられます。$N \leq a$ かつ $a + 1 \leq 2N$ であるような双子の良い整数 $(a, a + 1)$ を発見してください。そのような $(a, a + 1)$ が存在しない場合はそのことを報告してください。

• $N$ は $1$ 以上 $10^{100000}$ 未満の整数

はじめ、異なるmodの連立式とか、$a$ を1増やした時の余りの差分更新とか考えてたけど、どうにもこうにも上手くいかない。

1つ発見すれば良いので、「シンプルな形になるパターンをいくつか用意しておいて、$N～2N$ の範囲にあるやつを出力する」という方法が採れそう。 シンプルな形で表せる「良い整数」はどんな数か？

以下のように桁和が小さいものは倍数の判定がしやすかったり、 3や9のように桁和と倍数に関係のあるものが多く、調整しやすそう。

• $1$: どんな数でも割り切れる
• $2$: 末尾が偶数でありさえすればよい
• $3$: 桁和が3の数は必ず3の倍数という法則があるので、桁和が3になった時点でOK
• $4$: 下2桁が4の倍数ならよい
• $5$: 末尾が0か5であればよい
• $8$: 下3桁が8の倍数ならよい
• $9$: 桁和が9の数は必ず9の倍数という法則があるので、桁和が9になった時点でOK

ほとんどの場合、隣り合う整数の桁和は1だけ異なる。つまり $(aの桁和)+1=(a+1の桁和)$ となる。
末尾が'9'で繰り上がりが発生する場合は当てはまらないが、その場合 $a$ の桁和が（2桁以上を想定する場合）10以上となっているため、とりあえず考慮から外す。
$a$ の桁和が1～8であれば、必ず $a+1$ の桁和は $(aの桁和)+1$ となる。

その前提では、例えば1や5などは、それ単独ではよくても隣り合う数を考慮した時に上手くいかない。

隣り合った中では $(aの桁和,a+1の桁和)=(2,3),(8,9)$ あたりが作りやすそう。
（実際に愚直な実験で桁和が小さいケースを出力すると、この2組が大量に出てくる）

$a$ の最初の1～2桁の和が2や8となるようにし、その後は“0”を敷き詰めると（ある程度の桁数であれば）2や8の倍数となる。
また、自動的に $a+1$ の桁和が3や9となり、$a+1$ についても条件を満たすようになる。

• $(2,3)$ の組の例
  • 1100…000 と 1100…001
  • 2000…000 と 2000…001
• $(8,9)$ の組の例
  • 1700…000 と 1700…001
  • 2600…000 と 2600…001
  • 3500…000 と 3500…001
  • :
  • 7100…000 と 7100…001
  • 8000…000 と 8000…001

$(8,9)$ の例において $a$ が8の倍数となるには、この構成方法では少なくとも末尾3桁が'000'である必要がある。
$N$ が小さいとそれが保証されないので、小さい場合（6桁以下程度）は愚直に探す。
$N$ が大きい場合、上記の例の中から $N～2N$ の間にあるものは必ず存在し、先頭の1～2桁を確認するだけで決定できる。

Python3

F - Count Arrays

• 正整数 $N,M$ および、各要素が $1$ 以上 $N$ 以下の整数である長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
• 各要素が $1$ 以上 $M$ 以下の整数である長さ $N$ の数列 $x=(x_1,x_2,\dots,x_N)$ のうち、以下の条件を満たすものの数を $998244353$ で割った余りを求めてください。
  • 全ての $i\ (1\leq i\leq N)$ について、$x_i \leq x_{A_i}$

• $1\leq N,M \leq 2025$
• $1\leq A_i\leq N$
• 入力は全て整数

大小関係を $N$ 頂点のグラフに見立て、$i→A_i$ に有向辺を張ったものは、Functional Graphとなる。
つまり、全ての頂点からちょうど1つだけ辺が出ているグラフとなる。

○→○→○→○←○←○←○    ○→○┐
        ↑  ↓      ↑↖          ↑│
        ○←○      ○  ○        └┘

このようなグラフの各頂点に、小→大 となるように $1～M$ の整数値を割り振る方法の数が答えとなる。

グラフは複数の連結成分からなる場合もあるが、 異なる連結成分の決め方は互いに干渉しないので、各連結成分について独立に答えを求め、掛け合わせればよい。
Functional Graph の1つの連結成分は「1つの閉路とそこに向かう枝」からなる。

最後の閉路に含まれる頂点は、大小関係がループしているので必ず同じ値にしなければならない。
閉路を縮約して1つの頂点と見なし、これを根とした木を考える。

    ◎縮約した頂点
  ↗  ↖
○      ○
↑      ↑
○      ○
      ↗↑↖
    ○  ○  ○

葉から順に、以下の木DPをする。

• $\mathrm{DP}[v,k]:=$ 頂点 $v$ に $k$ 以下 の値を割り振る、$v$ の部分木の値の決め方の個数

葉頂点については、$\mathrm{DP}[v,k]=k$ となる。

葉以外の頂点 $u$ は、子を $v_1,v_2,...$ として、まず以下の補助的な値を求めて、

• $\mathrm{DP}'[v,k]:=$ 頂点 $v$ に ちょうど $k$ の値を割り振る、$v$ の部分木の値の決め方の個数
• 以下のように求められる
  • $\mathrm{DP}'[u,k]=\mathrm{DP}[v_1,k] \times \mathrm{DP}[v_2,k] \times ...$

最後に累積和を取ることで、$\mathrm{DP}[u,k]$ が求まる。

最終的に $\mathrm{DP}[根,M]$ がその連結成分の答えとなる。

Python3