AtCoder Grand Contest 039 参加記録 問題Aについて 10/08 火
標記のコンテストに参加しました。
結果については、このページをご覧ください。
さて、私は「問題A」しか解けませんでしたが、解いていて「この問題は、よくできているなあ」と感心しながら解いていました。そういう意味では、とても面白かったです。
具体的な問題は、次のとおりです。
■問題文
文字列Sが与えられます。
SをK回繰り返してできる文字列をTとします。
Tの文字をひとつ選んで他の文字に書き換える操作を繰り返すことでTのどの隣り合う2文字も相異なるようにするとき、必要な操作の回数の最小値を求めてください。■制約
1≤|S|≤100
Sは英小文字からなる
1≤K≤10^9
Kは整数である
いろいろやってみたことを、以下にメモします。
まず、S は100文字以下の文字列ですので、たとえば、次のような文字列を用意しました。
S="0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789"
これを、最大で「10の9乗」回、つまり、10億回、繰り返します。そうすると、文字列の長さは、最大で1000億文字になります。1000億の文字が並んでいる文字列というのは、すごい長さだなあと思いました。でも、まあ、つないでみないと始まりませんので、とりあえず10億回連結してみました。
そうすると、コンピュータはとても賢いので、ちゃんと10億回連結してくれるのですが、この時点で時間が1.5秒くらいかかってしまいました。今回の問題では制限時間は2秒です。したがって、対象となる文字をそのまま扱ったのでは問題は解決できないということが分かりました。
ということは、文字列を連結せずに、元の文字のままで解析して、答えを出す必要があります。きっと、いろいろなパターンがあって、それぞれに対してアルゴリズムを考えなくてはならないんだろうなと予想しました。
この時点で、サンプルとして与えられている入力文字（3種類あります）を見てみました。すると、この３種類のサンプルが、とてもよくできていて、回答にたどり着くための誘導問題になっていることがわかりました。
つまり、サンプルと同じように、３つの場合に分ければよいことがわかりました。具体的には、最初に与えられた文字列が、
ア、文字列全体が1種類の文字だけでできている場合
例）aaaaaaaaaaaaaaaaa
イの１、文字列が2種類以上の文字でできていて、しかも最初と最後の文字が異なっている場合
例）aaaaaaaaabbbbbbbb
イの２、文字列が2種類以上の文字でできていて、しかも最初と最後の文字が同じ場合
例）aaaaaaaaabbbbbbba
の３通りです。
この結果をもとに作成したプログラムが、次のようなものです。やっつけ仕事でゴチャゴチャのコードになっています。その点は、ご了承ください。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
int64_t k;
cin >> s;
cin >> k;
int sl = s.size();
char c; // 文字列が「一種類の文字だけでできているか」を調べる
c = s.at(0);
int x1=1;
for (int i=1;i<s.size();i++) {
if (c == s.at(i)) x1++;
}
if (x1 == s.size()) { // 一種類の文字だけでできている場合
int64_t tmp;
tmp = *1 * k) / 2; // 全部つなぐと文字数がわかる。置き換え数は、文字数を2で割れば求められる。
cout << tmp;
} else {
vector <int64_t> aa(s.size()); // それぞれの文字が何個続いているかを格納する配列変数
vector <int64_t> bb(s.size()); // 結果的に何文字置き換えればよいかを格納する配列変数
char c;
int last_i;
last_i = 0;
c = s.at(0); // 最初の文字はこれ
aa.at(0) = 1;
for (int j = 1; j< s.size(); j++ ) {
if (s.at(j) != c) { // もし違う文字が出てきたら次のハコに移動する
last_i++;
c = s.at(j);
}
aa.at(last_i)++; // 連続している文字数をカウントする
}
if ( s.at(0) == s.at(s.size()-1) ) { // 最初と最後が同じ場合
bb.at(0) = aa.at(0) / 2; // 一番最初の部分
for (int i=1; i<last_i; i++ ) {
bb.at(i) = (aa.at(i)/2) * k; // 途中は繰り返しになるので k 倍する
}
bb.at(last_i) = aa.at(last_i) / 2; // 一番最後の部分
bb.at(last_i+1) = *2 / 2) * (k-1); // 最初と最後が同じなので連結すると「長い文字列」ができる。その文字列の長さを 2 で割ると1回あたり置き換え数が出てくる。連結部分は k-1 個あるので、(k-1)倍する
} else { // 最初と最後が違う場合
for (int i = 0; i < s.size(); i++) {
bb.at(i) = (aa.at(i)/2) * k; それぞれの文字数を2で割ると置き換え数が出るので、単純にk倍する。最初と最後の文字が違うので、上のような「連結」は発生しない。
}
}
int64_t tmp;
tmp = 0;
for (int i = 0; i < s.size(); i++) { // 置き換え数をすべて合計する
tmp = tmp + bb.at(i);
}
cout << tmp << endl; // 答えを出力する
}
}
