見出し画像

615_Div3:問題BとCをテキトーに実装したから、最終的にTLEになり、1ACで終わった

海外の競技プログラミング「Codeforces」に参加している。1月22日に開催されたコンテスト「Codeforces Round#615 (Div. 3)」に参加した。

【今回の結果】
順位は約6560人中5330位(上位約81%)
レート:1156(前回1164、前回比 -8)

全 6 問出題されて、問題 A、1問だけ AC が取れた。pretestでは、問題 A、B、C は通ったのだが、問題 B と C は最終的なテストでは TLE(制限時間超過)で不正解となり、結果 AC は 1 問だけ。レートが下がったのは 5 回連続となった。

Codeforces は、ざっくり言うとチェックが 2 回あって、pretest はコンテスト中に行われる簡易版、最終的なテストはコンテスト終了後に行われる詳しい版と考えてよく、当然最終的なテストを通らないと AC とならない。

結果 AC は 1 問だけとなったのは、問題 B と C をテキトーにやっていたからである。問題 B と問題 C について、どうテキトーにしていたのかを振り返る。

問題 B の概要

問題 B の本文は以下のリンクに。

簡単に概要を整理すると、

x 軸と y 軸の二次元のグラフで考える(x、y ともに最大1,000)。
(0,0) にロボットがいる。
ロボットは、上か右にしか進むことができない。
すなわち、(x+1, y) か (x, y+1) にしか進めない。
n 個のパッケージがあって、i 個目のパッケージは、(x_i, y_i) の位置(すべて正の整数)にある。
ロボットがすべてのパッケージを回収できる場合は、YES を出力し、最短の移動パターンを 1 つ出力せよ。
移動パターンは、(x+1, y) の場合は R 、(x, y+1) の場合は U で出力せよ。
回収できない場合は NO を出力せよ。
なお、1 つのテストについて t 個(最大1,000)のテストケースがある。

問題 B になぜ AC できなかったのか?

私が pretest で通ったが、最終的なテストでは TLE になったコードはこんな感じ。

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

int main() {

 int t;
 cin >> t;

 while (0 < t) {

   int n;
   cin >> n;

   map<pair<int,int>, int> mp;
   int maxF = 0;
   int maxS = 0;

   for (int i = 0; i < n; i++) {
     int f_, s_;
     cin >> f_ >> s_;
     maxF = max(maxF, f_);
     maxS = max(maxS, s_);
     pair<int, int> pair = make_pair(f_, s_);
     mp[pair]++;
   }

   string answer = "";
   bool flg = true;
   int currentF = 0;
   int currentS = 0;

   for (int i = 0; i <= maxF; i++) {
     for (int j = 0; j <= maxS; j++) {
       pair<int, int> pair = make_pair(i, j);
       if (mp[pair] == 1){
         if (currentF <= i && currentS <= j) {
           for (int i2 = 0; i2 < i - currentF; i2++) {
             answer += "R";
           }
           for (int j2 = 0; j2 < j - currentS; j2++) {
             answer += "U";
           }
           currentF = i;
           currentS = j;
         } else {
           flg = false;
           break;
         }
       }
     }
     if (!flg) {
       break;
     }
   }

   if (flg) {
     cout << "YES" << endl;
     cout << answer << endl;
   } else {
     cout << "NO" << endl;
   }

   t--;

 }
}

上記のコードは、現在地(最初は0,0)から最も近くにあるパッケージを見つけて、そのパッケージへ上と右の移動だけでいくことができれば OK、いけなければダメという考えで実装した。また、現在地の最も近くにあるパッケージをパッケージ一覧からではなく、まず、考えられる座標を全て指定して、その座標にパッケージがあるかないかを確かめるという方法。

例えば、x と y の値が問題 B での x と y の最大値である 1000 とすれば、1,000,000 (= 1000 × 1000) 個の座標について、1 座標ずつパッケージがあるかないかを確認することになる。1,000,000 個のループならなんとかなるかなと思っていたが、t 個のテストケースがあるのを軽視していた。問題 B だと、1 つのテストでの計算量は最大 1000 の 3 乗だ。無理無理。

なぜ、このような実装になってしまったのか。それは、2 次元配列の並び替えがわからなかったから。
例えば、パッケージの位置情報が以下のように与えられるとする。

(1,3)
(1,2)
(3,3)
(5,5)
(4,3)

これらの位置情報を、

(1,2)
(1,3)
(3,3)
(4,3)
(5,5)

こんな感じに並べ替えることができればと思ったのだが、その方法がパッと出てこなかった。
並べ替え方法を考えずに、座標全探索とも言えるような方法を採用してしまったのが、テキトーな対応(その1)である。

問題 B のポイント

今回の問題の場合 c++ だと、パッケージの位置情報は pair<int,int> を要素にする配列 (vector) で管理すると楽。
pair を要素にした vector を並び替え (sort) すると、まず pair の最初の要素 (first) で並び替えを行い、pairの最初の要素が同じ場合は、2 番目の要素 (second) で並び替えてくれる。
vector<pair<int,int>> の並び替えは pair の最初の要素だけで並び替えると勘違いしていたからダメだった。
並び替えたパッケージを最初から順番に、ロボットの現在地から移動できるか否かを判定すればいい。

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

ということで、AC が取れたコードは以下のようになった。

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

int main() {

 int t;
 cin >> t;

 while (0 < t) {

   int n;
   cin >> n;
   vector<pair<int,int>> xy(n);

   for (int i = 0; i < n; i++) {
     int f_, s_;
     cin >> f_ >> s_;
     pair<int, int> p_ = make_pair(f_, s_);
     xy[i] = p_;
   }

   sort(xy.begin(), xy.end());

   int currentX = 0;
   int currentY = 0;
   string answer = "YES";
   string route = "";

   for (int i = 0; i < n; i++) {
     if (xy[i].first < currentX || xy[i].second < currentY) {
       answer = "NO";
       break;
     } else {
       if (currentX < xy[i].first) {
         for (int j = 0; j < xy[i].first - currentX; j++) {
           route += "R";
         }
       }
       if (currentY < xy[i].second) {
         for (int j = 0; j < xy[i].second - currentY; j++) {
           route += "U";
         }
       }
       currentX = xy[i].first;
       currentY = xy[i].second;
     }
   }

   cout << answer << endl;
   if (answer == "YES") {
     cout << route << endl;
   }

   t--;
 }
}

問題 C の概要

問題 C の本文は以下のリンクに。

簡単に概要を整理すると、

整数 n が与えられる(n は最小2、最大10の9乗)。
この n について、以下の条件を満たす異なる 3 つ整数 a、b、c を探したい。
・a、b、c はいずれも 2 以上である。
・a × b × c = n である。
以上の条件を満たす異なる 3 つ整数 a、b、c があれば、YES を出力し、a、b、c のパターンを 1 パターン出力せよ。
満たすものがない場合は NO を出力せよ。
なお、1 つのテストについて t 個(最大100個)のテストケースがある。

問題 C になぜ AC できなかったのか?

私が pretest で通ったが、最終的なテストでは TLE になったコードはこんな感じ。

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

vector<int> divisor(int N) {
 vector<int> res;
 for (int i = 1; i * i <= N; i++) {
   if (N % i == 0) {
     res.push_back(i);
     if (i != N / i) {
       res.push_back(N / i);
     }
   }
 }
 return res;
}

int main() {

 int t;
 cin >> t;

 while (0 < t) {

   int n;
   cin >> n;

   vector<int> v = divisor(n);
   sort(v.begin(), v.end());

   string answer = "NO";
   vector<int> a(3);

   for (int i = 0; i < v.size(); i++) {
     if (1 < v[i]) {
       for (int j = i + 1; j < v.size(); j++) {
         for (int k = j + 1; k < v.size(); k++) {
           if (v[i] * v[j] * v[k] == n) {
             answer = "YES";
             a[0] = v[i];
             a[1] = v[j];
             a[2] = v[k];
             break;
           }
         }
       }
     }
   }

   cout << answer << endl;
   if (answer == "YES") {
     cout << a[0] << " " << a[1] << " " << a[2] << endl;
   }

   t--;
 }
}

上記のコードは、以下の方針で実装している。
・ n について、約数を探して配列に入れる。
・ 1 以外の約数について 3 個のパターンを全パターン作って、掛けた数が n と同じかをチェックする。

これも問題 B のときと似ていて、以下の部分で闇雲に全パターン試している

問題C での n の最大が 1,000,000,000 で、約数は100個(1含む)。
上記のコードだと、for 文が 3 重になっているところが計算量が多くて、だいたい 1,000,000(= 100 × 100 × 100)
これも問題 B のときと同じ。1,000,000 個のループならなんとかなるかなと思っていたが、t 個のテストケースがあるのを軽視していた。このコードだと、1 つのテストでの計算量は最大 100 の 4 乗。これまた無理無理。

基本は全探索かもしれないが、明らかに効率的な実装ができる場合は全探索で片付けてはいけない。

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

コンテスト後に直して AC が取れたコードは以下の通り。

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

vector<int> divisor(int N) {
 vector<int> res;
 for (int i = 1; i * i <= N; i++) {
   if (N % i == 0) {
     res.push_back(i);
     if (i != N / i) {
       res.push_back(N / i);
     }
   }
 }
 return res;
}

int main() {

 int t;
 cin >> t;

 while (0 < t) {

   int n;
   cin >> n;

   vector<int> v = divisor(n);
   sort(v.begin(), v.end());

   string answer = "NO";
   vector<int> a(3);

   for (int i = 0; i < v.size(); i++) {
     if (1 < v[i]) {
       for (int j = i + 1; j < v.size(); j++) {
         int v_ = v[i] * v[j];
         if (n % v_ == 0) {
           if (n / v_ != 1 && n / v_ != v[i] && n / v_ != v[j]) {
             answer = "YES";
             a[0] = v[i];
             a[1] = v[j];
             a[2] = n / v_;
             break;
           }
         }
       }
     }
   }

   cout << answer << endl;
   if (answer == "YES") {
     cout << a[0] << " " << a[1] << " " << a[2] << endl;
   }

   t--;
 }
}

問題は 3 重になっている for 文である。
例えば、n = 12345 とすると、約数は以下の 8 個である。

1, 3, 5, 15, 823, 2469, 4115, 12345

3 個グループを作りたいが、上記の約数一覧から 1 以外の 2 個抜き出すと、残りの 1 個は上記の約数一覧から探す必要はない。
例えば、

a を 3
b を 5

と抜き出すと、c であってほしい数は、12345 ÷ 3 × 5 で割り切れる数であり、さらに、c は 2 以上で、a と b の両方と異なる数値である必要がある。
12345 ÷ 3 × 5 = 823 で割り切れ、823 は 2 以上であり、3 でも 5 でもないのOK。
この 823 はあまり 0 の商なので、823 も12345の約数である。
したがって、823 は約数一覧には必ず入っているので、改めて探す必要はない
探す必要のない数値をわざわざ約数一覧から探すのは、余計な計算。

以上が問題 C でテキトーに考えていた箇所。

まぁ、こんな感じでテキトーにしているとレートは下がります。
以後、気をつけます。

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

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