AtCoder ABC162 D問題 RGB Triplets

Question

#はじめに
閲覧ありがとうございます。前回同様、AtCoderさんの過去問から質問です。

#問題文
ABC162-D問題です。

#自分が立てた方針
①文字列のn文字目がR、G、Bのいずれかを判定し、Rの配列、Gの配列、Bの配列にnをpush_back
②Rの配列、Gの配列、Bの配列から1つずつ選ぶ全探索により条件に合致する組み合わせの個数を数える

#コード

#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ll long long 

int main() {
  int n;
  string s;
  cin >> n >> s;
  
  //配列の宣言
  vector<int> r, g, b;
  r.reserve(4000); g.reserve(4000); b.reserve(4000);
  
  //方針①の操作
  rep(i, n) {
    char c = s[i];
    if(c == 'R') r.push_back(i);
    else if(c == 'G') g.push_back(i);
    else if(c == 'B') b.push_back(i);
  }
  
  
  int result = 0;
  int rsize = r.size();
  int gsize = g.size();
  int bsize = b.size();
  
  //方針②の操作
rep(i, rsize) {
  rep(j, gsize) {
    rep(k, bsize) {
      int R = r[i];
      int G = g[j];
      int B = b[k];

      int large = max(R, max(G, B));
      int small = min(R, min(G, B));
      int medium = R + G + B - large - small;

      if(large - medium != medium - small) ++result;
      }
    }
  }

  
  cout << result << endl;
  return 0;
}

#その他
テストケース1は通りましたが、2は通りませんでした。
解説生放送とは方針がちょっと違ったので、このコードの間違えを探す術がないのです(泣)

#追記・編集
5/27 19:40 !=の件を編集しました
5/27 21:11 方針②において、ijkの大小関係について編集しました

Comments

[fana]

> 解説生放送とは方針がちょっと違ったので、このコードの間違えを探す術がないのです(泣)

何を言っているのか，全く意味がわかりません．

[shibahama]

プログラミング初心者には｢模写｣という最後の砦があるのですが、それが使えないという意味です()
そんなに大した意味は込めてません、ごめんなさい????

[fana]

> 模写
の是非等には触れませんが，
せっかくご自身で方針を打ち立てたのですから，
・実装したコードがその方針通りの動作をしているか？　という動作確認
・その方針で問題を解けるのか？　という話の内容自体の確認
をするところまで取り組まれると良いのではないかと考えます．

せめて，上記の「どちら側に問題があるのか」という切り分けをすべきです．（他者にはその判断はつきませんし）

[shibahama]

ありがとうございます。今回ですと下の「その方針で問題を解けるのか」に問題があったようです。

Answer 1

//方針②の操作
rep(i, rsize) {
rep(j, gsize) {
rep(k, bsize) {
if(b[k] - g[j] == g[j] - r[i]) ++result;
}
}
}

ここが
題意に沿った判定を行っているように見えないのですが…？
どこが間違っているか？　と問うには，
「何故この処理でやれる（と考える）のか？」という，あなたの考え（アルゴリズム）を説明する必要があるのではないでしょうか．
例えば，問題文に記載された条件全てを何の工夫もなく愚直に実装するとしたら，以下のようになると思いますが，このような愚直な状態と比較して「どのような工夫を行っているのか？」という話が．

//※入力がめんどくさいので代替
const std::string S = "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB";
const int N = (int)S.size();

//愚直なカウント
unsigned int Ans = 0;
for( int i=0; i<N-2; ++i )
{
    for( int j=i+1; j<N-1; ++j )
    {
        if( S[i] == S[j] )continue;
        int dij = j - i;
        for( int k=j+1; k<N; ++k )
        {
            if( k-j == dij )continue;
            if( S[i]==S[k] || S[j]==S[k] )continue;
            ++Ans;
        }
    }
}
std::cout << Ans << std::endl;

Comments

[shibahama]

愚直なカウントだと4000C3≒10^10通りの全探索が必要なので、制限時間に間に合わないと思いました。よって、これよりも少ない数の全探索で終わるように、方針②を考えたのですが。。。。

①で作った配列からそれぞれ1つずつ選び、その数の組でi、j、kを作ればR、G、Bが1つずつの組になるので、愚直なカウントより計算量が少なくなると考えました。
このとき、

ーーーーーーーーーーーーーー

iとjとkの大小関係を意識していないのが原因...!?

ーーーーーーーーーーーーーー

これが原因でした。

```C++
//方針②の操作
rep(i, rsize) {
rep(j, gsize) {
rep(k, bsize) {
int R = r[i];
int G = g[j];
int B = b[k];

int large = max(R, max(G, B));
int small = min(R, min(G, B));
int medium = R + G + B - large - small;

if(large - medium != medium - small) ++result;
}
}
}
```

[shibahama]

失礼、これだとTLEが2件でてしまいました。方針を立て直してみます。

Answer 2

問題点1
j-i != k-j な組の数を求めなければいけません。j-i == k-j ではありません

---

以下追記
問題点2
i, j, k は i < j < k という関係ですが、それぞれ R, G, B であるとは決まっていません。
なので、i = r[i] と置き換えるのは誤りです。
r[x], g[y], b[z] で3重ループにするのはいいですが、それぞれを i < j < k となるように並べ替える必要があります。

---

追記2
問題点3
n <= 4000 なので、char では入りません

  vector<char> r, g, b;

Comments

[fana]

質問コードの問題点は，そんな簡単な話ではないと思う．

[shibahama]

ごめんなさい、(失敗した)改良コードの1部が残ってました…。
正しいコード(正しいけど上手くいかないコード)は仰る通り!=です。

[shibahama]

毎度申し訳ない、後者の件もfanaさんとの返信欄で解決し、実装しましたが、1部のテストケースでWAが改善されませんでした…。
まだじっくり考える必要があるようです…????‍♂️

[shibahama]

>>問題点3
なんでchar型にしていたのかも、なんでchar型で半分以上ACとってたのも謎なんですが、これでTLE以外はACになりました...!!

[yuki23]

TLEまで解決するのは、そもそも3重ループで全探索するという方針に無理があるので、これ以上は難しいです。解説の方針に倣ってくださいとしか。

[shibahama]

そうですよねぇ ...。計算量を再計算したら10^9超えてたんで、どうもがいてもこの方針だと最悪ケースでTLE以外は免れないようです...。お騒がせしました！ミスを見つけてくださってありがとうございます！

Answer 3

AtCoderはテストケースを公開しているのでそこから確かめられるかなと思います。

https://atcoder.jp/posts/20

Answer 4

【質問者です】

最大4000文字の文字列から3つを選ぶ場合、4000C3=10^10通り以上のループを回さなければならないのでら今回のような方針を取って探索回数を削減しようと考えました。しかし、後からもう一度計算してみると、4000文字のうちRとGとBがそれぞれ同じ数出現するとした場合、この方針でも(4000/3)^3=2×10^9以上のループが必要で、制限時間に間に合わないことが分かりました。(多少は改善されてるのですが…。)

今回は質問時点で私の考えた方針を実装する上でのコードバグが何ヶ所かあったのですが、それをご指摘頂き改善したところで、この質問の解決とさせて頂きます。

・立てた方針に沿うコードが実装できていなかった→ご指摘頂き改善された。
・方針について見直したところ、この方針では制限時間に間に合わないことが分かった。

yuki23さんに数か所バグをご指摘いただきましたので、質問本文にはそれを反映させてあります。

Comments

[fana]

本件の「解決」とは何なのか？　という点に関しては色々な考え方があるとは思いますが…

「考えていた方針ではダメだった」というのを「解」として締めるのであれば，
各コメント欄に書かれた「どうダメなのか？」「なぜダメなのか？」ということを纏めるような方向だと良いのかもしれません．

質問時点では「自身の方針」の実装としてもバグっていた
→最終的に，「方針」通りの実装に直すことはできた？
→その結果の動作としては，計算時間を除いては問題なく動くところまで行きついた？

「どこかにある解説をパクればACだから，もうそれで」とかいう話では読み手にとっては無価値ですし．

[yuki23]

最低限、ベストアンサーは寄せられた回答の中から解決に最も役に立ったと思われるものを選んでください。私だけでなく、fanaさん、nnenn0さんも善意から時間を割いて回答しておりますので。
目の前のコードを直してほしいのではなく、TLEにならない方針まで考えてほしい、と読み取れなかったのは、私にも落ち度があったことは認めます。

[fana]

元々は
> テストケース1は通りましたが、2は通りませんでした。
ということで，「TLEがどうの」というのは当初の問題が解消された後から新しく出てきた（全く別の）話だと見えます．
なので，
> 計算時間を除いては問題なく動くところまで行きついた
のであれば，そこがひとまずの着地点であろうと個人的に考えます．

[shibahama]

>fanaさん
今回は、自分が考えた方針が合っているのか、又は合っているが実装に不備があるのか、自分の稚拙さも故に分からない状態で、とても曖昧な質問をしてしまいました。申し訳ないです。
とりあえずコードのバグを指摘してもらい、自分の立てた方針通りの実装が出来たので、この問題は解説の手法を吸収して次に活かすという方向で行こうと思っています。

>yupi23さん
仰る通り、お時間を割いて回答くださった皆さんからBAを選ぶべきですね。自己解決回答をもう少し充実させた上で、yupi23さんにご指摘いただいたことでコードが改善されたことは事実なのですが、プログラミングに対する姿勢について深く考えさせて頂いたfanaさんを改めてBAとして選ばせていただきます。御二方ともありがとうございました。