スクリーンショット_2020-03-01_23

ABC157【C問題の反省とD問題の復習】まだまだ、そこらへんもなんとなくわかる程度でごまかしている

3月16日に、競技プログラミングサイトAtCoderで開催された競技プログラミングコンテスト「AtCoder Beginner Contest 157」に参加した。

【今回の結果】
     順位:2743 位(参加者:約 6597 名 上位 42 %くらい)
    レート:654(前回:641 前回比:+13)
パフォーマンス:765(前回:449)

全6問出題され、A問題、B問題、C問題はACできた。しかし、C問題では3WAを出してしまった。C問題は解説PDFの解法2に近い考えで解いていた。解いている最中に「あれ、この問題は0から順番に確認した方がいいんじゃないか?」と解説PDFの解法1のような発想が生まれたが、すでに2WAを出していて、残り2つのテストケースをクリアすればよかったという状況。

「全探索でやりなおすか?」
「いや、引き続き、ちょっと修正したらなんとかなるだろう」

両者で迷ったが、引き続きコードを修正してなんとか3WAでACを取れた。
今回は、以下の2つを反省・復習する。

1.【C問題の反省】解法1と解法2で解いた場合について少し考える。
2.【D問題の復習】UnionFindもわかなかったが、他の悩んだのでその辺をすこし復習する。

【C問題の反省】問題と解法の概要

問題文は以下のリンクをご確認ください。

解説PDFには、以下の2つの解法を紹介しています。

【解法1】0以上10のN乗未満の整数を全て調べます。...(以下、省略)
【解法2】M個の条件について、矛盾が存在しないかを前から順に確かめつつ解の候補を絞り...(以下、省略)。

解法1は、まず答えを想定しておいて、これは答えの条件を満たすのかをチェックするという方法で、解法2は、矛盾する条件を排除し、条件から答えを作り出す方法と解釈している。以下、解説PDFだけを見て解法1の考えをもとに実装しACしたコードと、コンテスト中にACしたコード(解法2の考えに近いと思う)を比較する。

【C問題の反省】解法1をもとに実装し、ACしたコード

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

int main() {

 int N, M;
 cin >> N >> M;

 vector<pair<int,int>> sc(N);
 for (int i = 0; i < M; i++) {
   cin >> sc[i].first >> sc[i].second;
 }

 // N=1のときは、答えは0から9まで
 // N=2のときは、答えは10から99まで
 // N=3のときは、答えは100から999まで
 int start[3] = {0,10,100};
 int end[3] = {9,99,999};

 // Nに合わせて可能性がある答えを小さい数から順番に確認する。
 for (int i = start[N - 1]; i <= end[N - 1]; i++) {

   // 文字列にしておく
   string str = to_string(i);

   // 答えが存在するか(true)しないか(false)
   bool flg = true;

   // 1桁ごと確認する。
   // 見ている桁とs_iが同じだったら、
   // その桁の値とc_iが同じかチェックする。
   // 値とc_iが異なると答えは存在しない。
   for (int j = 0; j < N; j++) {
     for (int k = 0; k < M; k++) {
       if (j + 1 == sc[k].first) {
         if (sc[k].second != str[j] - '0'){
           flg = false;
         }
       }
     }
   }

   // flaがtrueのままfor文が終わった最初のiが答え。
   if (flg) {
     cout << i << endl;
     return 0;
   }

 }
 cout << -1 << endl;
 return 0;
}

【C問題の反省】解法2をもとに実装し、ACしたコード

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

int main() {

 int N, M;
 cin >> N >> M;
 vector<pair<int,int>> sc(N);
 for (int i = 0; i < M; i++) {
   cin >> sc[i].first >> sc[i].second;
 }

 // keyを桁,valueをその桁の値で管理するmap。
 // 見ていない桁は値を-1(初期値)とする。
 map<int,int> v;
 for (int i = 1; i <= N; i++) {
   v[i] = -1;
 }

 // 答えになる整数があるか(ture)、ないか(false)
 bool flg = true;

 // mapに桁と値を入れる。
 // 一度値を入れた桁については、同じ値じゃないとダメ。
 for (int i = 0; i < M; i++) {
   int i_ = sc[i].first;
   if (v[i_] == -1) {
     v[i_] = sc[i].second;
   } else if (v[i_] != sc[i].second){
     flg = false;
     break;
   }
 }

 // mapの1桁目の値が0の場合は、
 // Nが1以外の場合はダメ。
 if (v[1] == 0) {
   if (N != 1) {
     flg = false;
   }
 } else if (v[1] == -1) {
   // 1桁目の値が-1の場合は、
   // Nが1の場合は0、それ以外は1にする。
   if (N == 1) {
     v[1] = 0;
   } else {
     v[1] = 1;
   }
 }

 int answer = -1;

 if (flg) {
   // 答えを作る。
   answer = 0;
   for (int i = 1; i <= N; i++) {
     if (v[i] != -1) {
       answer += v[i] * pow(10, N - i);
     }
   }
 }

 cout << answer << endl;

 return 0;
}

【C問題の反省】解法1と解法2の両方をやってみた感想とか

・解法1は、コードが少ないので、(思いつけば)スピードは早そう。
・実際にWAをたくさん出したせいかもしれないが、解法2は「〇〇の場合は...」が多いため、ミスしやすい気がし、条件をずっと見落とすという可能性もある。
・早くACされている方々が提出されたコードを見ても(といっても、全部見ていないし、さらにC++しか見ていないが)、解法1の方が多かった。
・動画解説も解法1だった(と思う)。

いろいろ考えたが(自分の実装方法が悪いかもしれないし、後半の感想は実装したコードとは関係ないが)、問題を読んだ時に「解法1のような発想もできないといけないよね」という結論になった。

【D問題の復習】問題の概要

問題文は以下のリンクをご確認ください。

【D問題の復習】この問題をUnionFindを使うと解きやすいという発想にならなかった

UnionFindは、先週くらいにやったABC120-Dで初めて見た。

でもまぁ、1回しかやっていないし、しかも1回は動画解説を見ながらの実装。まだまだ自分で使えるレベルにはなっておらず、UnionFindがこの問題で使えるという発想にならなかった。前回のUnionFindのコードや動画解説を見ながらACしたのが以下のコード。

【D問題の復習】なんとか実装してACしたコード

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

class UnionFind {
public:
 // 親の番号
 // 自分が親の場合は-1とする
 vector<int> Parent;

 // 最初はParentの値をすべて-1にしておく
 // -1は誰ともつながっていないことを示す
 UnionFind(int N){
   Parent = vector<int>(N, -1);
 }

 // Aがどのグループに属しているかを調べる
 int root(int A)
 {
   // -1の場合は自分が親
   if (Parent[A] < 0) {
     return A;
   }
   // 自分が属する親を再帰で探す
   return Parent[A] = root(Parent[A]);
 }

 // AとBをつなぐ
 bool connect (int A, int B) {

   // AとBを直接つなぐのではなく、
   // root(A)にroot(B)をつなぐ
   A = root(A);
   B = root(B);
   if (A == B) {
     // すでにつながっているので、必要ない
     return false;
   }

   // 大きい方に小さい方をつなげる
   if (Parent[A] > Parent[B]) {
     swap(A,B);
   }

   // サイズを加える
   Parent[A] += Parent[B];
   
   // つなぐ
   Parent[B] = A;
   return true;

 }

 // A と B が同じグループかを返す
 bool same(int A, int B) {
   return root(A) == root(B);
 }

 // Aが属するグループのサイズを返す
 int size(int A) {
   return -Parent[root(A)];
 }

};

// 友達の数
int AB[100010];

// ブロック関係
vector<int> CD[100010];

int main() {

 int N, M, K;
 cin >> N >> M >> K;

 // 友達関係を管理するために、
 // AとBをつなぐ。
 UnionFind uf(N);
 for (int i = 0; i < M; i++) {
   int A, B;
   cin >> A >> B;
   A--;
   B--;
   AB[A]++;
   AB[B]++;
   uf.connect(A,B);
 }

 // ブロック関係を配列に入れる。
 for (int i = 0; i < K; i++) {
   int C, D;
   cin >> C >> D;
   C--;
   D--;
   CD[C].push_back(D);
   CD[D].push_back(C);
 }

 for (int i = 0; i < N; i++) {

   // 答え(友達候補) = 属するグループのサイズ - 友達の数 - 自分。
   int answer = uf.size(i) - AB[i] - 1;

   for (auto item: CD[i]) {
     // ブロック関係にあって、同じグループに属している場合は、
     // 答えからさらに1引く。
     if (uf.same(i, item)) {
       answer--;
     }
   }
   cout << answer << " ";
 }

 cout << endl;
 return 0;
}

UnionFindの部分はなんとか理解できたが、理解できなかったのが以下の部分。

// ブロック関係を配列に入れる。
for (int i = 0; i < K; i++) {
 int C, D;
 cin >> C >> D;
 C--;
 D--;
 CD[C].push_back(D);
 CD[D].push_back(C);
}

for (int i = 0; i < N; i++) {

 // 答え(友達候補) = 属するグループのサイズ - 友達の数 - 自分。
 int answer = uf.size(i) - AB[i] - 1;

 for (auto item: CD[i]) {
   // ブロック関係にあって、同じグループに属している場合は、
   // 答えからさらに1引く。
   if (uf.same(i, item)) {
     answer--;
   }
 }
 cout << answer << " ";
}

Nの上限が10の5乗。
Kの上限も10の5乗。
ということは、forの2重ループになっているところは、N × K だから間に合わないんじゃないのか?って思っていました。よく考えるとそうならないことはわかったが、「じゃぁどれくらいの計算量なのか」はパッと出ない。
まだまだ、そこらへんもなんとなくわかる程度でごまかしている。
そんな感じの、ごまかし対応で良しとしている論点が多いからまぁレートもほぼ真横に進んでいる。
そのうちきちんと理解します。

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

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