見出し画像

613_Di2:問題Cの反省。やっぱり参加者の半分以上の方がACした問題はAC必須。

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

【今回の結果】
順位は約7790人中4847位(上位62%くらい)
レート:1330(前回1370、前回比 -40)

全 6 問出題されて、問題 A と B でACが取れた。しかし、問題 C で AC が取れなかった。問題 B で何回か WA を取っしまい、問題 C は 1 回だけ提出できたが WA で終わってしまった。今回は問題 C の反省をする。

問題 C はこちら

問題 C の概要

整数 X(1 ≦ X ≦ 10 の 12 乗) が与えられる。LCM(a,b) = X を満たし、max(a,b) が最小の値になる a と b の組み合わせを出力せよ。LCMは最小公倍数をいい、組み合わせが複数ある場合はどれか 1 パターンを出力すればいい。

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

解答までの基本的な流れを、以下のように考えていた。

1. X の約数を配列で取得する
2. 約数の配列のすべての組み合わせの最小公倍数を求め X と等しい場合は、その組み合わせを出力する

終わり。

つまり、問題文の「max(a,b) が最小の値になる」を取りこぼしていた。時間が少なかったので焦っていたんだろうな。

問題 C を解くポイント

解答までの基本的な流れは、上記の流れに問題文の「max(a,b) が最小の値になる」を組み込めばいいから、以下のような感じになる。

1. X の約数を配列で取得する
2. a と b の最小値を保持するための変数(a > bを想定)を用意する(初期値はX+1とか大きい数字)
3. 約数の配列のすべての組み合わせの最小公倍数を求める
4. X と等しい場合は、その組み合わせの大きい方の値が、最小値用の変数の値より小さい場合は、最小値の変数の値を更新する。

終わり。

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

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

// 最大公約数
long long gcd(long long a, long long b) {
 if (b == 0) {
   return a;
 }
 return gcd(b, a % b);
}

// 最小公倍数
long long lcm(long long a, long long b) {
 return a / gcd(a, b) * b;
}

// Nの約数を配列で返す
vector<long long> divisor(long long N) {
 vector<long long> res;
 for (long long 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() {

 long long X;
 cin >> X;

 // X の約数一覧
 vector<long long> v = divisor(X);
 
 // 約数が 1 だけだったら 1 と 1 を出力
 if(v.size() == 1) {
   cout << 1 << " " << 1 << endl;
   return 0;
 }

 // 解答用
 long long minA = X+1;
 long long minB = X+1;
 
 // 約数を 1 個ずつチェックしていく。
 for (int i = 0; i < v.size(); i++) {
   long long a = v[i];
   long long b = X / v[i];
   if (X == lcm(a, b)) {
     if (max(a, b) < minA) {
       minA = max(a, b);
       minB = min(a, b);
     }
   }
 }

 cout << minB << " " << minA << endl;

}

実際に提出したコードは以下のリンクから。

このくらいの問題は、20 分くらいで 1 発 AC じゃないとダメだよなぁ。レート下がって当然の結果。次回もがんばろう。

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

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