見出し画像

624_Div3【B問題の反省】pretestは通ったが、system testでWA。難しい問題を悩むより、確証なくpretestを通ったコードを再度検証した方がいいかもしれない

2月24日に、海外の競技プログラミング「Codeforces」で開催された「Codeforces Round#624(Div3)」に参加した。

【今回の結果】
 順位:5184位(参加者:約9289名 上位56%くらい)
レート:1175(前回:1181 前回比:-6)

全6問出題され、A,B,C問題の3問をpretestでACになったが、B問題は最終的なsystem testでWAになった。ということで2AC。コンテスト中でもAとC問題は「これはこう解くといいだろう」と確信を持って回答できたが、B問題は「これでいいのだろうか?」という不安混じりの提出でpretestのACだった。system testでWAになっても、まぁ仕方ないなという感想。今回はB問題の反省をする。

B 問題について

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

簡単に概要を言いますと。n個の数字が並んでいる数列aと、p_1からp_mまでm個の数字がある。a[p_i]とa[p_{i+1}]を何回でも入れ替えることができる。この操作を行うことで、数列aを昇順にすることができるか、という問題。例として、

a = [3,2,1]
p = [1,2]

で考えると。

1. pに[2]があるので、aの2番目と3番目を入れ替えて[3,1,2]となる。
2. pに[1]があるので、aの1番目と2番目を入れ替えて[1,3,2]となる。
3. 入れ替えは何回してもいいので、aの2番目と3番目を入れ替えて[1,2,3]となり、昇順に並び替えることができる。

したがって、答えはYESとなる。

ダメだったコード

このB問題は、解法がよくわからず以下のような方針で実装した。

・数列aについて、二重ループでaを昇順に並びかえる。
・その時、入れ替える箇所、すなわち、a[i] > a[j]の箇所があれば、i + 1 をsetに入れる。
・setに入っている値が全部pにあればYES、1個でもなければNOとなる。

こんな感じで実装したのが、以下のコードです。

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

int main() {

 int t;
 cin >> t;
 
 while (0 < t) {

   int n, m;
   cin >> n >> m;

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

   vector<int> p(n);
   for (int i = 0; i < m; i++) {
     int p_;
     cin >> p_;
     p[p_]++;
   }

   set<int> st;
   // aを昇順に並び替える
   for (int i = 0; i < n; i++) {
     for (int j = i + 1; j < n; j++) {
       // 入れ替えるときに入れ替える場所をsetに入れる。
       if (a[i] > a[j]) {
         swap(a[i], a[j]);
         st.insert(i+1);
       }
     }
   }

   string answer = "YES";

   // set に入れた数値が1個でもpになければNO
   // 全部あれば、YES
   for (auto item:st){
     if (p[item] == 0) {
       answer = "NO";
       break;
     }
   }

   cout << answer << endl;

   t--;
 }
 return 0;
}

並び替えがちゃんとできるかは確認したが、setの内容の確認が甘かった。例えば、以下のa、pで上記のコードを見ると、

a = [5,5,6,6,4,5]
p = [1,4,5,3]

setの中身は

1,3,4

となる。
aに4があり、最小値なので1番目まで移動しないといけない。しかし、setの中に「2」がないので、aの4は1番目まで移動できない。aの中に5が何個もあるからその辺りで処理がうまいこと行っていない。このようなケースに気がつかず、pretestが通ってしまうという結果となった。

方針がまちがっていた

問題文を読んだ直後は「実際にp_1からp_mを使って、数列aを昇順に並び替えることができるか否かを確認したいなぁ」「でも、何回でも入れ替えることができると書いてあった時点で『終わり』を決めることができないなぁー」と思ってしまい、試しもしなかった方針が解説で説明されていた。

「すべてのpについて、a[p_i] > a[p_{i+1}] を満たす場合は a[p_i] と a[p_{i+1}] を入れ替える」を繰り返せば、いつかは終わる。
終わった a が昇順に並んでいればYES、並んでいない場合はNOとなる。

この方針で実装しなおして、ACしたコードは以下の通りです。

ACしたコード

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

int main() {

 int t;
 cin >> t;
 
 while (0 < t) {

   int n, m;
   cin >> n >> m;
   
   vector<int> a(n);
   for (int i = 0; i < n; i++) {
     cin >> a[i];
   }

   vector<int> p(n);
   for (int i = 0; i < m; i++) {
     int p_;
     cin >> p_;
     p[p_ - 1]++;
   }
   
   bool flg = true;
   // すべてのpについて、a[p_i] > a[p_{i+1}] を満たすケースがある限り、
   // a[p_i] と a[p_{i+1}] を入れ替える
   while (flg) {
     bool change = false;
     for (int i = 0; i < n; i++) {
       if (p[i] && a[i] > a[i + 1]) {
         change = true;
         swap(a[i], a[i + 1]);
       }
     }
     if (!change) {
       flg = false;
     }
   }

   string answer = "YES";
   // 入れ替え終わった a が昇順ならばYES
   // そうでない場合はNO
   for (int i = 0; i < n - 1; i++) {
     if (a[i + 1] < a[i]) {
       answer = "NO";
       break;
     }
   }   
 
   cout << answer << endl;
   t--;
 }
 return 0;
}

最初に考え方を固定してしまっていたので、次回以降はその辺りを注意しよう。今回、D問題を手も足も出ない状態で、40分くらいうんうん悩んで終わったのだが、時間によっては、難しい問題を悩むより、今回のB問題みたいに確証なくpretestを通ったコードを再度検証した方がいいかもしれないな。


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

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