ARC189 A問題の思考過程

AtCoder Regular Contest 189のA問題「[Reversi 2](https://atcoder.jp/contests/arc189/tasks/arc189_a)」の解法について説明します。[ARCのDivision制](https://atcoder.jp/posts/1364)導入後、最初のコンテストでした。

コンテスト本番では最初に挑み、40分でACすることができました。
本記事では、コンテスト本番中の自分の思考過程を時系列順に説明します。多少の試行錯誤がありました。

## タイトル
"Reversi 2"とあります。オセロゲームの要素がありそうです。

## 問題の概要

:::note info
元の問題では「$N$個のマスに整数が書かれている」とありますが、この記事では書かれている整数を順に並べた「文字列」として扱います。
:::
長さ$N$の文字列があり、初期状態では1, 0が交互に並んでいます（例：1010101, 1010101010）。以下の操作が可能です：

```
部分文字列が100...01あるいは011...10になるように、区間[l,r]を選び

その間の区間[l+1,r-1]の値をすべて反転させる
```

目標の文字列が与えられるとき、その文字列に到達可能な操作手順の総数を求めます。

### 入力例1
初期状態：101010 → 目標：111110

可能な操作手順は3通り：
1. 101010 → 111010 → 111110
2. 101010 → 101110 → 111110
3. 101010 → 100010 → 111110

### 入力例2
初期状態：1010101010 → 目標：1111101110

このケースは、以下のように分解して考えられます：
- 前半部分：10101 → 11111（3通りの方法）
- 後半部分：101 → 111（1通りの方法）

前半部分は入力例1で観察したように必ず2操作必要で、後半部分の操作（1回）は前半部分の2操作の前・間・後のどこかで実行できます。よって：
- 総数 = 3（前半の方法）× 1（後半の方法）× 3（挿入位置）= 9通り

## 問題解決へのアプローチ

### 1. 初期の考察

入力例に対しての観察で、以下を考えました。

1. **単調性**
    ・効率よく数え上げられるはずなので、何らかの単調性を期待します

2. **成分への分解**の可能性
    ・入力例2のように、問題を部分問題に分解できそうです

3. 各成分について解くべき部分問題：
    ・操作手順の数え上げ
    ・必要な操作回数の計算

4. 最後の総合：
    ・各成分の解をどう組み合わせるか
    ・操作順序の数え上げ

### 2. 単調性を見出す

操作の性質を詳しく見ていきます。

1. 以下の具体例で検討：
    ・101 → 111 の変換
    ・110011 → 111111 の変換

2. Run Length Encoding（RLE）での表現：
    ・101は[1,1,1]（各数字が現れる回数）
    ・110011は[2,2,2]

3. 重要な発見：
    ・1回の操作は「連続する3つの成分の合併」に相当
    ・例：1010101 → 1110101 → 1111101
    　[1,1,1,1,1,1,1] → [3,1,1,1,1] → [5,1,1]

4. 単調性の特定：
    ・操作で合併した成分は、その後に分裂することはありません
    ・1回の操作で数列の長さが2減少します

### 3. 付随する重要な性質

分析を進めると、以下の制約が明らかになりました：

1. 両端の値の保存
    ・元の数列の両端と、操作後の数列の両端は一致する必要がある
    ・例：101...010 → 111...111 は不可能

2. 繰り返し回数の性質
    ・初期状態では全て1回
    ・3つの成分を合併していくので、常に奇数回になる
    ・例：10101010 → 11000010 は不可能

### 4. 操作列が存在する条件

上記の分析から、操作列が存在する必要条件：
1. 元の数列の両端と目標の数列の両端が一致
2. 目標の数列の各値の連続出現回数が全て奇数

これらの条件を満たせばこの後の数え上げの考察が成立するため、結果的に必要十分条件となりました。

### 5. 各成分の部分問題の分析

成分ごとの変換方法の数を考察：

1. 基本ケース：
    ・単一文字（0 or 1）：操作不要
    ・3文字（101 or 010）：1回の操作、1通り
    ・5文字（10101 or 01010）：2回の操作、3通り

2. より長いケースの考察：
    ・7文字の場合は3回の操作が必要
    ・操作順序の数え上げには工夫が必要
    ・帰納的に見出す必要がある

### 6. 括弧列アプローチの試行

最初に試みたアプローチ：

1. 操作を括弧列で表現する試み
    ・例：[1,0,1,0,1] → [1,1,1,0,1] → [1,1,1,1,1] を `()()` と表現
    ・例：[1,0,1,0,1] → [1,0,0,0,1] → [1,1,1,1,1] は `(())` と表現

2. 問題点の発見：
    ・括弧列と操作手順が1対1対応しない
    ・操作順に従って括弧に番号を振る必要性（内側の括弧から順に番号を振る）
    ・帰納的な手続きが複雑になりそう

3. 具体例での検証：
    ・`()()`から派生：`()()()`、`(()())`、`(())()`、`()(())`
    ・`(())`から派生：`(())()`、`()(())`、`((()))`
    ・`()()()`に番号を振る：`(1)(2)(3)`、`(1)(3)(2)`、`(2)(1)(3)`、`(2)(3)(1)`、`(3)(1)(2)`、`(3)(2)(1)`
    ・`(())()`に番号を振る：`((1)2)(3)`、`((1)3)(2)`、`((2)3)(1)`
4. このアプローチは断念：
    ・関係性が複雑で、帰納的な考察が困難

括弧列は諦め、他のアプローチを探すことにした

### 7. 新しいアプローチの発見

シンプルな考え方に立ち返り：

1. 操作を「連続する3つの成分の、右2つを消去して左に合併する」と捉え直し、操作できる場所を数え上げる：
    ・101(RLEでは[1,1,1])の操作：3-2=1通り (左端のみ)
    ・10101([1,1,1,1,1])の操作：5-2=3通り (左側3つ)
    ・1010101([1,1,1,1,1,1,1])の操作：7-2=5通り (左側5つ)

2. 帰納的な考察：
    ・長さkの数列に対して
    ・最初に操作できる場所：k-2通り。操作後の数列の長さはk-2。
    ・次に操作できる場所：k-4通り。操作後の数列の長さはk-4。
    ・以降同様。kは奇数なので1で終わる

3. 検証：
    ・7文字の場合：5×3×1=15通り
    ・実際に数え上げて確認

<details><summary>実際の数え上げ</summary>
    
`()()()`→`(1)(2)(3)`、`(1)(3)(2)`、`(2)(1)(3)`、`(2)(3)(1)`、    `(3)(1)(2)`、`(3)(2)(1)` 6通り
`((()))`→`(((1)2)3)` 1通り
`(()())`→`((1)(2)3)`、`((2)(1)3)` 2通り
`(())()`→`((1)2)(3)`、`((1)3)(2)`、`((2)3)(1)` 3通り
`()(())`→`(())()`と同様で 3通り
    
合計 15通り！もっと長くなるとムリ！
</details>

### 8. まとめあげの方法

最後に、各成分の操作をどう組み合わせるかを考察：

1. 簡単な例：[5,1,3]の場合
    ・操作回数：2,0,1回
    ・順序："113","131","311"の3通り

2. より複雑な例：[7,5,1,3]の場合
    ・操作回数：3,2,0,1回
    ・多項係数での計算：6!/(3!2!0!1!)=60

<details><summary>説明</summary>
    
"1"が3個、"2"が2個、"3"が0個、"4"が1個あるとき、これらを順に並べるやり方は何通りあるか。
合計は3+2+0+1で6個。6個全てを区別すれば6!通り。
"1"の3個を区別しなくすれば6!/3!通り。さらに"2”の2こを区別しなくすれば6!/(3!2!)通り。
</details>

一般に、各成分ごとの操作数がx1,x2,...,xkであれば、手順の数は(x1+x2+...+xk)!/(x1!x2!...xk!)

## 最終的な解法

以下の手順で解を求めます：

1. 操作可能性のチェック
    ・両端一致の確認
    ・繰り返し回数の奇数性確認

2. 各成分ごとの操作手順の数え上げ
    ・長さkの成分：(k-2)(k-4)×3×1通り

3. 操作順序の数え上げ
    ・多項係数による計算
    ・(x1+x2+...+xk)!/(x1!x2!...xk!)

4. 全ての積が答え

## 実装例

コンテスト中の提出コードは[こちら](https://atcoder.jp/contests/arc189/submissions/60588118)です。
Juliaで実装していますが、基本的なPythonの知識があれば理解できる内容になっています。