【AtCoder ABC039】C - ピアニスト高橋君【丁寧な解法】

こんにちは、こふです。

C - ピアニスト高橋君を解いていて、引っかかってしまったので解説を書いてみます

丁寧な解説記事がなかった＋高レートのコード読んでも理解しづらい処理がある、効率的に実装できて正しいのはわかるけど難しい・・・

なんとなく解いてしまうのも良くないと思うので、納得できるよう書きます。

前提条件 → 解法検討 → 解法の順です。

問題文の条件である白い鍵盤にいることを無視して解いています。

与えられた文字列を S とします。

M=WBWBWWBWBWBW とします。これは ドレ〜ラシ の鍵盤の色の白黒の表記です。

Sの長さは 20 で、M の長さは 12 です。

S の中に M が存在するなら、単にその位置（インデックス）を求めて何とかなりそうです。

M の 12 文字の並び順は唯一であり、これが S の中に存在すると確定するか判断します。

S は 20 文字なので M との組み合わせなどの文字列としての存在可能性は、12+8, 11+9, 10+10, 1+12+7, 2+12+6... 文字の連結となります。

よって、12 文字である M 全体が存在しない場合（11+9, 10+10）が確実にあります。

つまり、S の中に M が存在するとは限りません。この方針は無理そうです。

逆に、M をいくつか連結した文字列の中に S が存在するか を判定することを検討します。

M を 2 つ連結した文字列を MM とします。

MM の中に S が必ず存在するかを判定します。

MM の長さは 24 で S の長さは 20 です。

S について 20=7（M の末尾 7 文字）+12（M）+1（M の先頭 1 文字） を例に考えます。つまり、3 つの部分に分かれうるのです。4 つ以上には絶対に分かれません。4 つに分かれうるのは 1+12+12+1 であり 26 文字だからです。

MM は 12（M）+12（M） なので MM の中に上記 S は存在しない場合があるため、これはダメそうです。

逆に 26 文字以上なら・・・ということです。

M を 3 つ連結した文字列を MMM とします。

MMM の中に S が必ず存在するかを判定します。

MMM の長さは 36 で S の長さは 20 です。

S については 20=7（M の末尾 7 文字）+12（M）+1（M の先頭 1 文字） を例に考えます。最大で 3 つの分割しかできません。

MMM は 12（M）+12（M）+12（M） なので上記 S は必ず存在します。どうやっても S を上手に存在させられます。

解法検討より文字列検索としての解法は分かったので、具体的にどうするかです。

S が MM のとき、MMM の開始位置に S が存在します。インデックスは 0 です。

S が ?（2 文字）M（12 文字）?(6 文字) のとき、MMM の ?（10 文字）?（2 文字）M（12 文字）?(12 文字) となり、インデックスは 10 となりますが、これが鍵盤の順番の位置そのままです。

また、その位置は S=20=11（M の末尾 11 文字）+9（M の先頭 9 文字） の場合だとしてもインデックスは 11 です。そのため、インデックスは 12 を超えない 0~11 になります。

あとはドレミのローマ字表記の鍵盤順の配列・ベクトルを用意します。

M・S は解法検討で示した文字記号のままです。

main.cppコピー
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5  vector<string> sounds = {"Do", "Do", "Re", "Re", "Mi", "Fa",
6                           "Fa", "So", "So", "La", "La", "Si"};
7  string S;
8  cin >> S;
9  string M = "WBWBWWBWBWBW";
10  string MMM = M + M + M;
11  int index = MMM.find(S);
12  cout << sounds.at(index) << endl;
13  return 0;
14}

こういう考え方より単にリストアップする方が効率的でもあるので、どうやって解くべきかまだつかめていない。