AtCoder Regular Contest 189のA問題「Reversi 2」の解法について説明します。ARCのDivision制導入後、最初のコンテストでした。
コンテスト本番では最初に挑み、40分でACすることができました。
本記事では、コンテスト本番中の自分の思考過程を時系列順に説明します。多少の試行錯誤がありました。
タイトル
"Reversi 2"とあります。オセロゲームの要素がありそうです。
問題の概要
元の問題では「$N$個のマスに整数が書かれている」とありますが、この記事では書かれている整数を順に並べた「文字列」として扱います。
長さ$N$の文字列があり、初期状態では1, 0が交互に並んでいます（例：1010101, 1010101010）。以下の操作が可能です：
部分文字列が100...01あるいは011...10になるように、区間[l,r]を選び
その間の区間[l+1,r-1]の値をすべて反転させる
目標の文字列が与えられるとき、その文字列に到達可能な操作手順の総数を求めます。
入力例1
初期状態：101010 → 目標：111110
可能な操作手順は3通り：
- 101010 → 111010 → 111110
- 101010 → 101110 → 111110
- 101010 → 100010 → 111110
入力例2
初期状態：1010101010 → 目標：1111101110
このケースは、以下のように分解して考えられます：
- 前半部分：10101 → 11111（3通りの方法）
- 後半部分：101 → 111（1通りの方法）
前半部分は入力例1で観察したように必ず2操作必要で、後半部分の操作（1回）は前半部分の2操作の前・間・後のどこかで実行できます。よって：
- 総数 = 3（前半の方法）× 1（後半の方法）× 3（挿入位置）= 9通り
問題解決へのアプローチ
1. 初期の考察
入力例に対しての観察で、以下を考えました。
-
単調性
・効率よく数え上げられるはずなので、何らかの単調性を期待します -
成分への分解の可能性
・入力例2のように、問題を部分問題に分解できそうです -
各成分について解くべき部分問題：
・操作手順の数え上げ
・必要な操作回数の計算 -
最後の総合：
・各成分の解をどう組み合わせるか
・操作順序の数え上げ
2. 単調性を見出す
操作の性質を詳しく見ていきます。
-
以下の具体例で検討：
・101 → 111 の変換
・110011 → 111111 の変換 -
Run Length Encoding（RLE）での表現：
・101は[1,1,1]（各数字が現れる回数）
・110011は[2,2,2] -
重要な発見：
・1回の操作は「連続する3つの成分の合併」に相当
・例：1010101 → 1110101 → 1111101
[1,1,1,1,1,1,1] → [3,1,1,1,1] → [5,1,1] -
単調性の特定：
・操作で合併した成分は、その後に分裂することはありません
・1回の操作で数列の長さが2減少します
3. 付随する重要な性質
分析を進めると、以下の制約が明らかになりました：
-
両端の値の保存
・元の数列の両端と、操作後の数列の両端は一致する必要がある
・例：101...010 → 111...111 は不可能 -
繰り返し回数の性質
・初期状態では全て1回
・3つの成分を合併していくので、常に奇数回になる
・例：10101010 → 11000010 は不可能
4. 操作列が存在する条件
上記の分析から、操作列が存在する必要条件：
- 元の数列の両端と目標の数列の両端が一致
- 目標の数列の各値の連続出現回数が全て奇数
これらの条件を満たせばこの後の数え上げの考察が成立するため、結果的に必要十分条件となりました。
5. 各成分の部分問題の分析
成分ごとの変換方法の数を考察：
-
基本ケース：
・単一文字（0 or 1）：操作不要
・3文字（101 or 010）：1回の操作、1通り
・5文字（10101 or 01010）：2回の操作、3通り -
より長いケースの考察：
・7文字の場合は3回の操作が必要
・操作順序の数え上げには工夫が必要
・帰納的に見出す必要がある
6. 括弧列アプローチの試行
最初に試みたアプローチ：
-
操作を括弧列で表現する試み
・例：[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] は(())と表現 -
問題点の発見：
・括弧列と操作手順が1対1対応しない
・操作順に従って括弧に番号を振る必要性（内側の括弧から順に番号を振る）
・帰納的な手続きが複雑になりそう -
具体例での検証：
・()()から派生：()()()、(()())、(())()、()(())
・(())から派生：(())()、()(())、((()))
・()()()に番号を振る：(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) -
このアプローチは断念：
・関係性が複雑で、帰納的な考察が困難
括弧列は諦め、他のアプローチを探すことにした
7. 新しいアプローチの発見
シンプルな考え方に立ち返り：
-
操作を「連続する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つ) -
帰納的な考察：
・長さkの数列に対して
・最初に操作できる場所：k-2通り。操作後の数列の長さはk-2。
・次に操作できる場所：k-4通り。操作後の数列の長さはk-4。
・以降同様。kは奇数なので1で終わる -
検証：
・7文字の場合：5×3×1=15通り
・実際に数え上げて確認
実際の数え上げ
()()()→(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通り！もっと長くなるとムリ！
8. まとめあげの方法
最後に、各成分の操作をどう組み合わせるかを考察：
-
簡単な例：[5,1,3]の場合
・操作回数：2,0,1回
・順序："113","131","311"の3通り -
より複雑な例：[7,5,1,3]の場合
・操作回数：3,2,0,1回
・多項係数での計算：6!/(3!2!0!1!)=60
説明
"1"が3個、"2"が2個、"3"が0個、"4"が1個あるとき、これらを順に並べるやり方は何通りあるか。
合計は3+2+0+1で6個。6個全てを区別すれば6!通り。
"1"の3個を区別しなくすれば6!/3!通り。さらに"2”の2こを区別しなくすれば6!/(3!2!)通り。
一般に、各成分ごとの操作数がx1,x2,...,xkであれば、手順の数は(x1+x2+...+xk)!/(x1!x2!...xk!)
最終的な解法
以下の手順で解を求めます：
-
操作可能性のチェック
・両端一致の確認
・繰り返し回数の奇数性確認 -
各成分ごとの操作手順の数え上げ
・長さkの成分：(k-2)(k-4)×3×1通り -
操作順序の数え上げ
・多項係数による計算
・(x1+x2+...+xk)!/(x1!x2!...xk!) -
全ての積が答え
実装例
コンテスト中の提出コードはこちらです。
Juliaで実装していますが、基本的なPythonの知識があれば理解できる内容になっています。