見出し画像

611_Div2:3枚カードの組み合わせ=bit全探索だと考えてしまい、問題BでACできずに終わったので、問題Bの反省をする

海外の競技プログラミング「Codeforces」に参加している。1月5日にCodeforces Round#612(Div. 2)に参加した。

【今回の結果】
順位は約5984人中2891位(上位48%くらい)
レート:1370(前回1378、前回比 -8)

全 7 問出題されて、問題 A だけACが取れた。しかし、問題 B で AC が取れなかった。何回か提出したが TLE や WA を繰り返している最中に終わってしまった。今回は問題 B の反省をする。

問題 B の概要

S, E, T の 3 種類の文字で構成される k 文字(最大30文字)の文字列が書かれたカードが n 枚(最大1500枚)与えられる。
n 枚のカードのうち同じ文字列が書いてあるカードはない。
n 枚のうち 3 枚のカードのセットを作りたい。
しかし、3 枚のカードそれぞれの i 番目の文字がすべて異なるか、すべて同じ文字でなければらない。
3 枚のカードのセットを作ることができる組み合わせの数を求めよ。

例えば、

SET
ETS
TSE

の 3 枚のカードがあるとすると、この 3 枚のカードは 1 文字目から 3 文字目まですべて異なる文字なので、条件を満たす組み合わせとなる。

問題 B になぜハマったのか?

例えば、100 枚カードがあったとしたら、以下のようにたくさんの 3 枚セットを作ることができる。
・1 枚目のカード、2 枚目のカード、3 枚目のカード
・1 枚目のカード、2 枚目のカード、4 枚目のカード
・1 枚目のカード、2 枚目のカード、5 枚目のカード
...以下、たくさん。

これらの考えられる 3 枚セットの組み合わせを全部調べる必要があると思ってしまい、3 枚セットのパターンをbit 全探索で作ろうとしていた。
全体的な流れはこう。

bit 全探索でカードの枚数を桁数として 0 と 1 の組み合わせを全部作る。
そのうち、1 が 3 つあれば組み合わせとして採用する。
採用された組み合わせで、1 がある位置のカードを得る。1 は 3 つあるはずなのでカードは 3 枚になる。
この 3 枚のカードで、それぞれの i 番目の文字がすべて異なるか、すべて同じ文字かを調べる。

しかし、

1500桁の2進数どうすればいいんだ?
2の1499乗か...無理だな。

ここで詰まる。
この方法では無理があった。
すべての組み合わせが必要ということは、bit全探索が必要と考えしまっていたので、新たな発想を考えることができず、時間がすぎる。


問題 B を解くポイント

結局のところ、根本的な考え方間違っていたのだが、重要なポイントは次の 2 点だったと思う。

1. 2 枚カードを選んだ時点で、3枚目のカードで欲しい文字は 1 つだけである。
2. その 1 つの文字列が書かれたカードを、調べ終わったカードの一覧から探す。

まず、「1. 2 枚カードを選んだ時点で、3枚目のカードに書かれている文字は 1 つだけである。」について。
例えば、

STT
ETS

とカードが 2 枚決まったら、3枚目のカードに書かれている文字は、以下のように必ず 1 つだけ決まる。

1 文字目は、1 枚目と 2 枚目のカードで異なる文字だから、全部異なるパターンで T になる。
2 文字目は、1 枚目と 2 枚目のカードで同じ文字だから、全部同じパターンで T になる。
3 文字目は、1 枚目と 2 枚目のカードで異なる文字だから、全部同じパターンで E になる。

すなわち、TTE しかセットにならない

カードは最大で 1500 枚でカードの最大文字数 30 なので、ざっと 1500 × 1500 * 30 で、確認ができると見積れる。(結構多いが、この問題 B は 制限時間が 3 秒と若干長くなっている。)

次に、「2.その 1 つの文字列が書かれたカードを、調べ終わったカードの一覧から探す。」について。

STT
ETS
TTE

と 3 枚のカードがあるときを考える。
あらかじめ、答え用の変数(初期値 0 )で作っておく。
そして、まず、STT と ETS が決まり、3枚目になるべきカードは TTE となる。TTEは 3 枚目にあるので、答え(組み合わせの数)に 1 加える
次に、STT と TTE が決まり、3枚目になるべきカードは ETS となる。 ETS は 2枚目にあるが、この組み合わせはすでに確認済みの組み合わせになるので、答えに加えることができない
ここで、答え(組み合わせの数)に 1 加えていいのか、加えることができないのかをどう判断したらいいのか?で悩む。

しかし、調べ終わったカードの一覧から探せば、うまくいく。

すなわち、以下のように考える。
あらかじめ、答え用の変数(初期値 0 )と調べ終わったカード一覧用の配列(初期値空)を作っておく。
STT と ETS が決まり、3 枚目になるべきカードは TTE となる。TTE は調べ終わったカード一覧用の配列には無いので、答え用の変数へは何もしない。
STT と TTE が決まり、3 枚目になるべきカードは ETS となる。ETS は調べ終わったカード一覧用の配列には無いので、答え用の変数へは何もしない。
ここで、STT は調べ尽くしたので、調べ終わったカード一覧用の配列に STT を追加する。
ETS と TTE が決まり、3 枚目になるべきカードは STT となる。STT は調べ終わったカード一覧用の配列にあるので、答え(組み合わせの数)に 1 加える
ここで全パターン調べ終わるので、終了。

以上の反省を踏まえて、実装したところACが取れた。

問題 B で AC が取れたコード

#include <bits/stdc++.h>
using namespace std;

int main() {

 int n, k;
 cin >> n >> k;

 // 全てのカードを入れておく配列
 vector<string> card(n);

 for (int i = 0; i < n; i++) {
   cin >> card[i];
 }

 // 調べ尽くしたカードを保持するためのset
 set<string> st;

 // 答えとなる組み合わせの数
 long long answer = 0;

 // 最初のカードは set が空なので、
 // 調べる必要はなく、調べ尽くしたカード一覧に追加
 st.insert(card[0]);
 
 // 2 枚目のカードから順番に調べていく。
 for (int i = 1; i < n; i++) {
   for (int j = i + 1; j < n; j++) {

     // 3 枚目のカードの希望文字列
     string current = "";

     // 3 枚目のカードの希望文字列を作る
     for (int k_ = 0; k_ < k; k_++) {
       if (card[i][k_] == card[j][k_]) {
         current += card[i][k_];
       } else {
         if (card[i][k_] != 'S' && card[j][k_] != 'S') {
           current += 'S';
         }
         if (card[i][k_] != 'E' && card[j][k_] != 'E') {
           current += 'E';
         }
         if (card[i][k_] != 'T' && card[j][k_] != 'T') {
           current += 'T';
         }
       }
     }

     // 希望文字列が調べ尽くしたカード一覧にあれば、答えに1追加
     if (st.count(current)) {
       answer++;
     }

   }
   
   // 調べ尽くしたカード一覧に追加
   st.insert(card[i]);

 }

 cout << answer << endl;

}

この問題 B の難易度 1500 とのこと。
2020年は難易度 1500 の問題はさらっとできるようになりたい。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

ありがとうございます!
三重県伊勢市でiOS・AndroidアプリのUX設計・UIデザイン・実装、Webサイト、Webアプリの情報設計、UIデザイン、実装を行なっています。また、競技プログラミングに参加したり、読書をしたり、2羽の文鳥と遊んだり、写真を撮ったり、洋菓子を作ったりしています。
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。