Help us understand the problem. What is going on with this article?

AtCoderの問題「一次元リバーシ(1D Reversi)」を多色化してみた

 こんにちは、@kanten1990と申します。
 私は今、AtCoder Problemを使って、様々なAtCoderの問題を解いているところですが、「一次元リバーシ(1D Reversi)」という問題を見て、これをもう少し変えてみよう、ということで、様々なことを考えました。今回は、そのことを記事にしましたので、ぜひお読みください。
 「一次元リバーシ」が何かわからなくても、記事内でその問題を取り上げますのでご心配なく。
 ※文中の画像は、全て自作です。gif画像は、バナー工房様のサービスを使用してつくりました。

目次

 次の順で話を進めていきます:

第1章 「一次元リバーシ」とは
1-1 問題
1-2 解法
第2章 リバーシの色の種類をを3色にしてみる
2-1 発案のきっかけ
2-2 出来た問題 ― 「3色で」一次元リバーシ
2-3 解法
2-4 これで「つまらなさ」は解消?
第3章 リバーシの色の種類をN色にしてみる
3-1 これはN色にするしかない!
3-2 できた問題
3-3 解法
3-4 AtCoderでの難易度は?
第4章 最後に
4-1 まとめ
4-2 謝辞

第1章. 「一次元リバーシ」とは

 「一次元リバーシ」という問題を解いたから知っている、という方もいらっしゃるかと思いますが、「その問題を見たことがない」という方のためにも、念のため問題を載せておきます。

1-1. 問題(AtCoder Beginner Contest 047 C問題 - 「一次元リバーシ」)

問題文
きつねの次郎と三郎が一次元リバーシで遊んでいます。一次元リバーシでは、盤面には白か黒の石が一列に並んだ状態となっており、列の右端か左端に新たに石を打っていきます。通常のリバーシと同じように、たとえば白の石を打つことで黒の石を挟むと、挟まれた黒の石は白い石に変わります。
ゲームの途中で三郎に急用ができて帰ってしまうことになりました。このとき、盤面の状態は文字列$S$で表されます。石は $|
S
|$ (文字列の長さ) 個並んでおり、左から $i
(
1

i

|
S
|
)$ 個目の石の色は、$S$の $i$文字目が 'B' のとき黒、 'W' のとき白です。
次郎は現在の盤面に対して、できるだけ少ない個数の石を新たに打つことで全ての石を同じ色にしようと考えました。最小で何個の石を打てばよいかを求めてください。

制約
・$1≦|S|≦10^5$
・$S$に含まれる文字は'B'または'W'のいずれかである
AtCoder Beginner Contest 047 C - 一次元リバーシ より引用)

1-2. 私が考えた解法

 この問題においては、置く石の数をいかに少なくするかがポイントですが、シミュレーションしてしまうとかなりの時間がかかりそうです。そこで、...

解法の続きを見たい方はこちら
 どうしたら効率よく置く石の数を求められるかを考えます。
 リバーシのルールとして、「同じ色Aの石の間に挟まれた違う色の石は全て色Aになる」ことは知っているでしょう。たとえば「黒白白白白」と並んでいるところの右端に黒石を置くと、もちろん黒石と黒石に挟まれた白石が存在します。そして、これらは全て黒石になります。
 このとき、最初は隣り合う石の色が違うところが存在していましたが、右端に黒石を置くことで、存在しなくなります。
 スクリーンショット (38).png
 つまり、「石の色をそろえていく」という動作は、「隣り合う石の色が違うところを1つずつなくしていく」という動作と同じと考えることができます。そこで、与えられた文字列を左端から見ていき、隣り合う石の色が違うところを数えてそれを出力すればよいということになります。
 一応、ソースコードを載せておきますが、見なくても構いません。
reversi.cpp
 #include "bits/stdc++.h"
 using namespace std;
 int main() {
    string S;
    cin >> S;
    long long ans = 0;
    for (int i = 0; i < S.size() - 1; i++) {
        if (S.at(i) != S.at(i + 1)) ans++;
    }
    cout << ans << endl;
 }


第2章. リバーシの色の種類を3色にしてみる

 さて、「一次元リバーシ」を解き終わった後、私は「これだけでは少しつまらないなあ」と思ったので、これを少し変えてみることにしました。

2-1. 発案のきっかけ

 「問題を変えてみよう」とはいえ、作問の経験が少ないので、いいアイデアが出ませんでした。私はよくテレビを見るのですが、時々見ていた、私が好きな番組『水曜日のダウンタウン』という番組を思い出しました。その中に、「三つ巴対決 盛り上がる説」というのがあって、3人でオセロをするというのがあったので、「一次元リバーシを3色にしてみよう」と思ったのです。

2-2. 出来た問題 ― 「3色で」一次元リバーシ

問題文

 A君は、赤、青、白の3色を使って一次元リバーシをして遊ぶことにしました。
 最初の盤面の状態を文字列$S$で表します。石は全部で$|S|$個並べられています。左から$i$番目$(1≦i≦|S|)$の石は、'R'なら赤、'B'なら青、'W'なら白色です。そして、「一次元リバーシ」同様、列の右端か左端に新たに石を打っていきます。現在の盤面から、できるだけ少ない個数の石を新たに打つことで全ての石を同じ色にするには最小で何個の石を打つ必要があるかを求めてください。

制約

  • $1≦|S|≦10^5$
  • Sに含まれる文字は'R', 'B', 'W'のいずれかである

入力

 次のように、標準入力で与えられます。
 S 

出力

 全ての石を同じ色にするために打つ必要のある最小の石の個数を1行で出力してください。

サンプル

入力例1
RBWWBWR
出力例1
2
 例えば、右端に白、右端に赤の順で石を置くと、全ての石の色を赤にすることができます。
 スクリーンショット (39).png

入力例2
WWWWW
出力例2
0
 最初から全ての石の色が白になっています。

入力例3
RBWRBWRBBWRB
出力例3
5
全て赤でそろえることができます。

2-3. 解法

 まずはこの問題をしっかりと眺めてみましょう。
 ここでは、入力例3を使って説明したいと思います。

①なに色でそろえるのか?
 この問題では、「赤」「青」「白」の3色のいずれかでそろえられるので、どの色でそろえるか決める必要があります。
②どうやってそろえるのか?
 ここを考えるのがメインです。入力例3では、赤でそろえるのが一番良いようなので、「赤でそろえる」ことを前提に話を進めていきます。
 まずは次のようにそろえてみましょう:
 「右端(または左端)に、赤、赤以外の色という順で置いていく方法(元の問題同様)」
 この方法だと、赤でそろえると7個の石を置くことになります(右端に、赤、白、赤、白、赤、白、赤の順で置いていく)。これだと、出力例3の値と異なっていますね。
 次の方法を考える前に、入力例3の状態から、5個の石を置いて全部赤でそろえる方法を考えてみましょう。


 考えられましたでしょうか?
 例えば(これ以外にやり方があるのかはわかりませんが)次のようにそろえます(n回目に石を置いた時の状態をnターン後とします):
 完成版.gif
 実は、このそろえ方にはある法則性があるのです。それは、「必ず2色の石の色が変わる」ということです。
 例えば、1ターン後、右端に白を置くと、赤石と青石が一枚ずつ、白になりました(もう一度gif画像を見てみてください)。
 よって、そろえ方は次のようになります:
 「右端(または左端)に、2つの石の色が変わるように石を置く方法」
 よくわからない方は、次の実装のところを見ればわかるかと思います。
 ※ちなみに、この方法で左端に置いていくと、5個で全部がでそろいます。
③実装
 それでは、この問題を解いていきましょう。
 前述の方法でそろえるには、3色がそろっているところで裏返せばよいです。...といっても、わからないでしょう。ここのところは言葉での説明がとても難しくて、つい悩んでしまいます。代わりに、この部分は図を使って説明することにします。
スクリーンショット (50).png
 右端から見ていきます。
- 区間[8, 8]にある石の色の種類数は「1」です。
- 区間[7, 8]にある石の色の種類数は「1」です。
- 区間[6, 8]にある石の色の種類数は「2」です。
- 区間[5, 8]にある石の色の種類数は「3」です。よって、右端に青を置くことで、区間[6, 8]の石が全て青になります。
- 区間[4, 5]にある石の色の種類数は「2」です。
- 区間[3, 5]にある石の色の種類数は「3」です。よって、右端に白を置くことで、区間[4, 8]の石が全て白になります。
- 区間[2, 3]にある石の色の種類数は「2」です。
- 区間[1, 3]にある石の色の種類数は「3」です。よって、右側に赤を置くことで、区間[2, 8]の色が全て赤になります。これですべての石の色がそろいました。

 この手順をみてピンときた方はアルゴリズムの本をよく読んでいらっしゃる方です。そう、「しゃくとり法」!
 実際はそうではないと思いますが、なんとなく似ていますね。
 今回は右端から見ましたが、左端から見た方が置く石の数が少なく済む場合もあります。
 さて、改めてどういうことをすればいいのか、以下にまとめます:
 1. 文字列Sを用意する。まずは右端から見ていく。
 2. End = |S|と初期化する。また、SのなかにはM種類の石があるとする。
 3. |S|回のループを回し、中で次の動作をする(i = |S| - 1と初期化する):
  1. 区間[i, End]にある石の色の種類数を調べる。
  2. もし種類数がMだったら、Endにiを代入する。
 4. もし最後まで見たときにそろっていなかったら、置く石の数を+1する。
 5. 同様に、左端から見ていく。
 6. 右端から見たときと、左端から見たときの置く石の数を比較し、少ない方を出力する。

 これを実装したコードを載せておきます。見なくても構いません。

解答例
Three_Colors.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
    string S;
    cin >> S;
    long long len = S.size();
    vector<char>A;
    for (long long i = 0; i < S.size(); i++) {
        if (A.empty()) A.push_back(S.at(i));
        else {
            bool check = true;
            for (long long j = 0; j < A.size(); j++) {
                if (A.at(j) == S.at(i)) check = false;
            }
            if (check) A.push_back(S.at(i));
        }
    }
    long long End = S.size() - 1, Begin = 0;
    long long ans_right = 0, ans_left = 0, kinds = 1, kinds_max = A.size();
    if (kinds_max == 1) {
        cout << 0 << endl;
        return 0;
    }
    for (long long i = S.size() - 2; i >= 0; i--) {
        if (S.at(End) != S.at(i)) kinds++;
        if (kinds == kinds_max) {
            ans_right++;
            End = i;
            kinds = 1;
        }
    }
    if (kinds != kinds_max) ans_right++;
    for (long long i = 1; i < S.size(); i++) {
        if (S.at(Begin) != S.at(i)) kinds++;
        if (kinds == kinds_max) {
            ans_left++;
            Begin = i;
            kinds = 1;
        }
    }
    if (kinds != kinds_max) ans_left++;
    cout << min(ans_left, ans_right) << endl;
}


 計算量は$O(|S|)$です。(推測)

2-4. これで「つまらなさ」は解消?

 さて、3色にしただけでも、彩はあるし、適した難易度だし、ということで面白くなったなあと思い、しばらくはこれを自慢の問題としていました。しかし、2色、3色とやったのだから、せっかくならN色もやってみないと意味がないと思ったのです。よって、「つまらなさ」は完全に解消したとは言えないでしょう。

第3章. リバーシの色の種類をN色にしてみる

3-1. これはN色にするしかない!

 2-4. でも述べましたが、せっかくならN色バージョンも作ってみたいと思ったので、その問題を次に掲載します。先に行っておくと、いちいち文字を設定するのも面倒なので、色ではなく、N種類の数字が書かれていることにしました。

3-2. できた問題

問題文

 高橋君はいわゆる「一次元リバーシ」をしています。
 高橋君は今、$N$種類の石をもっていて、それぞれに$1, 2, ..., N$という数字が書いてあります。
 最初に、高橋君はこれらのうち$M$個の石を、左から$i$番目($1≦i≦M$)には$A_i$と書かれた石が置かれるように並べました。そして、列の右端か左端に新たに石を打っていきます。現在の盤面から、できるだけ少ない個数の石を新たに打つことで全ての石を同じ色にするには最小で何個の石を打つ必要があるかを求めてください。
 但し、高橋君はどの種類の石も十分に多く持っているものとします。
 ※必ずしも$N$種類の石がすべてあるとは限りません。

制約

  • $1≦N, M≦1000$
  • $1≦A_i≦N(1≦i≦N)$

入力

次のように、2行で標準入力より与えられます。
 N M           
 A[1] A[2] A[3] ... A[M]

出力

全ての石を同じ色にするために打つ必要のある最小の石の個数を1行で出力してください。

サンプル

入力例1
5 10
3 3 5 1 2 4 3 1 1 4

出力例1
2
両端にそれぞれ2を置くことで、すべての石を同じ色2にすることができます。
Screenshot (2).png

3-3. 解法

 それでは、この問題を解いていきましょう!
 ...といっても、これは3色のときとあまり変わりません。
 方針は同じです。
 一応、手順だけ以下に記しておきます:
 1. 文字列Sを用意する。まず右端から見ていく。
 2. End = Mと初期化する。SのなかにK種類の石があるとする。
 3. |S|回のループを回し、中で次の動作をする(i = M - 1と初期化する):
  1. 区間[i, End]にある石の色の種類数を調べる。
  2. もし種類数がKだったら、Endにiを代入する。
 4. もし最後まで見たときにそろっていなかったら、置く石の数を+1する。
 5. 同様に、左端から見ていく。
 6. 右端から見たときと、左端から見たときの置く石の数を比較し、少ない方を出力する。
 これを実装したコードを載せておきます。見なくてもかまいません。

解答例
N_kinds.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    vector<int>S(M);
    vector<int>A;
    for (long long i = 0; i < M; i++) {
        cin >> S.at(i);
        if (A.empty()) A.push_back(S.at(i));
        else {
            bool check = true;
            for (long long j = 0; j < A.size(); j++) {
                if (A.at(j) == S.at(i)) check = false;
            }
            if (check) A.push_back(S.at(i));
        }
    }
    long long End = S.size() - 1, Begin = 0;
    long long ans_right = 0, ans_left = 0, kinds = 1, kinds_max = A.size();
    if (kinds_max == 1) {
        cout << 0 << endl;
        return 0;
    }
    for (long long i = S.size() - 2; i >= 0; i--) {
        if (S.at(End) != S.at(i)) kinds++;
        if (kinds == kinds_max) {
            ans_right++;
            End = i;
            kinds = 1;
        }
    }
    if (kinds != kinds_max) ans_right++;
    for (long long i = 1; i < S.size(); i++) {
        if (S.at(Begin) != S.at(i)) kinds++;
        if (kinds == kinds_max) {
            ans_left++;
            Begin = i;
            kinds = 1;
        }
    }
    if (kinds != kinds_max) ans_left++;
    cout << min(ans_left, ans_right) << endl;
}



計算量は$O(NM)$です。(推測)

3-4. AtCoderでの難易度は?

 考えついた当初はちょっと難しいかなと思いましたが、気づくのも、慣れれば簡単ですし、実装も意外と簡単にできると思います。私の予想点数としては、200~300点くらいです。AtCoder Beginner ContestのB, C問題くらいの難易度だと思っています。

第4章. 最後に

4-1. まとめ

 以上、私が「一次元リバーシ」について考えたことを述べました。
 私がこれを改作してみようと思ったときは、遊び半分でやっていました。しかし、その中で、様々なことを学びました。それらは、作問するときの気持ちや、問題文を書くときの気持ちなど、経験したことのないことばかりです。
 今回を機に、様々な問題を作り、作問者側の立場で考えてみたいです。そうすることも、プログラミング上達のためにはいいことなのかなと思います。

 あと、現実的には「一次元リバーシ」で場を盛り上げるのは難しいこともわかりました。これは、学校のプログラミング仲間たちとのちょっとした息抜きにしたいと思います。

4-2. 謝辞

 この問題を作るにあたり、様々な友達に助言をいただきました。ありがとうございました。

記事紹介 

 次のような記事も書いています:
 AtCoderを使うときに便利な拡張機能(Google Chrome)

 最後までお読みいただき、ありがとうございました。もし、この記事に関して、意見や質問、要望等あればコメントをお願いします。

kanten1990
中2のkanten1990です。よろしくお願いします。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした