OMC230F 思考過程

公式解説と本質的には変わらないだろうが、数学初心者の競プロerなりに考えた方法を書き留めておく。私はこちらの方が考えやすかった。

A と B を 0 に、C を 1 に置き換えた文字列を考える。たとえば、ACBAC は 01001 となる。定義より、0 が隣り合うことがあっても、1 が隣り合うことはない。

このようにしたとき、操作は以下のように置き換えられる。

• 0 と 1 の間には、0 を挿入する。
• 1 と 0 の間には、0 を挿入する。
• 0 と 0 の間には、1 を挿入する。

以下のようなDPを考える。

• $D{P}_s[i]=$ 00 に
  $i$ 回操作を行ったときの、1 の個数
• $D{P}_d[i]=$ 01 または 10 に
  $i$ 回操作を行ったときの、1 の個数

明らかに、

$D{P}_s[0]=0,D{P}_d[0]=1$ である。

また、

$1\le i$ のとき、DPの値は以下のようになる。

• $D{P}_s[i]=2D{P}_d[i-1]-1$
  • 00 に
    $1$ 回操作すると 010 になるので、01 と 10 に対して
    $i-1$ 回操作を行うことになる。真ん中に挿入した 1 が重複して数えられることに留意。
• $D{P}_d[i]=D{P}_s[i-1]+D{P}_d[i-1]$
  • 01 に
    $1$ 回操作すると 001 になるので、 00 と 01 に対して
    $i-1$ 回操作を行うことになる。10 の場合でもほぼ同様。

DPの様子をある程度手計算してみることにする。

$i$	$D{P}_s[i]$	$D{P}_d[i]$
$0$	$0$	$1$
$1$	$1$	$1$
$2$	$1$	$2$
$3$	$3$	$3$
$4$	$5$	$6$
$5$	$11$	$11$
$6$	$21$	$22$
$7$	$43$	$43$

こう見ると、

$i$ が奇数のとき

$D{P}_s[i]=D{P}_d[i]$ になりそうである。これを帰納法で証明しておこう。(なお本番中は証明していない)

• $i=1$ のとき、明らかに正しい。
• $3\le i$ かつ
  $i$ が奇数のとき、
  • $D{P}_s[i]=2D{P}_d[i-1]-1=2D{P}_s[i-2]+2D{P}_d[i-2]-1$
  • $D{P}_d[i]=D{P}_s[i-1]+D{P}_d[i-1]=2D{P}_d[i-2]-1+D{P}_s[i-2]+D{P}_d[i-2]$
• $D{P}_s[i-2]=D{P}_d[i-2]$ より、
  $D{P}_s[i]=D{P}_d[i]$

重要なのは

$D{P}_s[2023]$ と

$D{P}_d[2023]$ である。以降、

$X=D{P}_s[2023]=D{P}_d[2023]$ とする。

基本的に 1 の数は

$2022X$ になりそうだが、これらは両端以外の文字を重複して数えているため、その数だけ引かれることになる。

1 の個数の最大化を考えると、明らかに

$2$ 文字目から

$2022$ 文字目はすべて 0 にするのがよいことになる。

$1$ 文字目と

$2023$ 文字目はどちらでもよいので、結局以下の

$4$ 通りになる。

• 00000...00000
• 10000...00000
• 00000...00001
• 10000...00001

これらに対応する文字列は各

$2$ 通りである (最も左の 0 を A と B のどちらにするかを決めると、その他も一意に定まる) から、

$m=8$ である。

また、

$M=2022X$ である。

1 の個数の最小化を考えると、

$2$ 文字目から

$2022$ 文字目の 1 の個数を最大化すればよいことになる。この区間の長さは奇数なので、01010...01010 のみに対応する。

0 の個数は

$\lceil \frac{2023}{2}\rceil =1012$ であり、すべての 0 を独立に A または B に対応させることができるので、これに対応する文字列は

$2^{1012}$　通りである。よって、

$n=2^{1012}$ である。

また、1 の個数は

$2023-1012=1011$ 個なので、

$N=2022X-1011$ である。

$m,n$ が求まったので、あとは

$X$ を求めれば、

$M,N$ が求まり問題が解ける。

先ほどのDPテーブルの、奇数のところだけを取り出したものを考える。そして、それらを

$2$ 進数表記してみる。(だいたい倍々に増えているので規則性がありそうと踏んでいる)

$i$	$D{P}_s[i]$	$D{P}_s[i]$ の $2$ 進数表記
$1$	$1$	$1$
$3$	$3$	$11$
$5$	$11$	$1011$
$7$	$43$	$101011$

こうしてみると、どんどん

$10$ が増えてきそうな気持ちになる。試しに

$i=9$ などを計算してみるとなおさら正しそうである。実際、これは以下のように証明できる。(なおこれも本番中は証明していない)

$D{P}_s[i]=2D{P}_d[i-1]-1=2D{P}_s[i-2]+2D{P}_d[i-2]-1=4D{P}_s[i-2]-1$

より、

$2$ 進数表記では末尾の

$1$ を

$0$ にして

$11$ を付け加えるといえる。

こうすると、

$D{P}_s[i]=\frac{2^i-2}{3}+1$ と表すことができる。よって、

$X=\frac{2^{2023}-2}{3}+1$ となる。

これらの値を

$503$ で割った余りを求めよう。以降、

$mod503$ を省略する。

Fermatの小定理より、

• $X\equiv \frac{2^{2023}-2}{3}+1\equiv \frac{2^{15}-2}{3}+1\equiv \frac{32766}{3}+1\equiv 10923\equiv 360$
• $n\equiv 2^{1012}\equiv 2^8\equiv 256$

これらより、答えは

$2022X+8+(2022X-1011)+256\equiv 727920+8+726909+256\equiv 1455093\equiv \mathbf{417}$