見出し画像

ABC150:問題Dについて、なんとか自分なりに理解できたので、自分なりの解釈を整理した。

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

【今回の結果】
順位は約4479人中1946位(上位43%くらい)
レート:598(unretedのため変化なし)

今回も前回同様、問題 A、問題 B、問題 C は正解でき、上位50%に入れたのでよかった。前回のようなしょうもない WA もなかったが、問題 C を解くのに30分くらい使ってしまった。仮の話だが、30分かかったのが10分短いだけで、順位は数百変わる。特に、今回は問題 D を正解した方が 提出者の 15% ほどしかいない難しい問題だったので、問題 C のスピードが重要だったなぁ。

問題 C を早く解くポイント

問題 C を早く解くポイントは、N! 通りある大きさ N の順列をサッと用意できるかだったと思う。C++の場合だと、

map<vector<int>, int> mp;
do {
   // 順列のパターンを mp に入れていく。
   mp[v] = mp.size();
 } while (next_permutation(v.begin(), v.end()));

こんな感じで、next_permutation 関数を使うのが楽。しかしながら、next_permutation 関数は抑えておらず、調べながらたどり着いたので時間がかかってしまった。

自分なりの問題 D の解釈

問題 D をやっていて何回か WA を出している最中に終わってしまったので、問題 D の反省を解説PDF解説動画を見て復習した。コンテスト中も何個か AC があったので、基本的な考え方は間違えてないんだろうなぁと思って、復習したのですが、コンテスト中の考え方は的外れすぎのたまたまACがあっただけの話で、なかなかの難問だった。

問題文はこちら

解説の動画を見て、なんとか理解しようといろいろ考えた解釈のメモが以下の文章です。

まず、
X = a_k × (p + 0.5) について「0.5」は扱いにくいので、
X = (a_k / 2) × (2p + 1) に整理する。

確かに「0.5」は扱いにくい。整理しようという姿勢はこれ以外の問題でも使えそうな考え方。

X = (a_k / 2) × (2p + 1) の (a_k / 2) を a' とすると、
X = a' × (2p + 1) となる。
(2p + 1) は奇数なので、以下の 2 つの条件がわかる。

1. X は a' の奇数倍である
2. X が 2 で割り切れる回数と a' が 2 で割り切れる回数は同じ

1.は、特に問題はない。
2.は、少しピンと来ない。

例えば、以下の 2 つの式は条件を満たしている。

30 = 6 * 5
30 = 10 * 3
30 = 30 * 1

30 は 2 で 1 回割り切れる。6 も 2 で 1 回割り切れる。
30 は 2 で 1 回割り切れる。10 も 2 で 1 回割り切れる。
30 は 2 で 1 回割り切れる。30 も 2 で 1 回割り切れる。
それぞれの式で 2 で割り切れる回数が 1 で同じなので、奇数側を調整することで、同じ X にすることができる。

X = a' × (2p + 1) の (2p + 1) は奇数だから、2 で割り切れる回数は 0 である。
したがって、X と a' は 2 で割り切れる回数が同じでないと X を求めることができない。そして、すべての a' について、2 で割り切れる回数が同じじゃないと奇数側 (2p + 1) をどれだけがんばっても、共通する X は求めることができない。

2 で割り切れる回数を t とすると、解説ではさらに、X と a'、そして M を 2 の t 乗で割っている。

30 = 6 × 5
30 = 10 × 3
30 = 30 × 1

で考えると、30 ÷ 2 の 1 乗、6 ÷ 2 の 1 乗、10 ÷ 2 の 1 乗を計算して、

15 = 3 × 5
15 = 5 × 3
15 = 15 × 1

となる。

以下の 3 つの式でも条件を満たす。

45 = 3 × 15
45 = 5 × 9
45 = 15 * 3

すなわち、2 の t 乗で割ることで、すべての (a' ÷ 2 の t 乗) の最小公倍数の奇数倍であれば、X になりうる

最小公倍数の奇数倍の値が M を超えたらダメと考えたいが、X は 2 の t 乗で割っているので、M も 2 の t 乗で割ったもの(M')を超えたらダメとなる。
ちなみに、最小公倍数の奇数倍の値の個数は、(M') を最小公倍数で割った値を 2 で割った値(切り上げ)となる。

問題 D で ACがとれたコード

以上の解釈から実装して AC が取れたコードは以下の通りです。

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

// 2 で割り切れる回数を返す
int f(int x) {
 int res = 0;
 while (x % 2 == 0) {
   x /= 2;
   res++;
 }
 return res;
}

// 最大公約数を返す
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;
}

int main() {

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

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

 // 入力を 2 で割る
 for (int i = 0; i < N; i++) {
   if (a[i] % 2 == 1) {
     cout << 0 << endl;
     return 0;
   }
   a[i] /= 2;
 }

 // 2 で割り切れる回数が a[0] から a[N - 1] まで、全部同じじゃないとダメ
 // 同じ場合は、2^t で割る
 int t = f(a[0]);
 for (int i = 0; i < N; i++) {
   if (f(a[i]) != t) {
     cout << 0 << endl;
     return 0;
   }
   // a[i] /= 2^t
   a[i] >>= t;
 }

 // M /= 2^t
 M >>= t;

 // 2^t で割った a[0] から a[N - 1] までの lcm を求める。
 // lcm が M を超えるとダメ
 long long lcm_ = 1;
 for (int i = 0; i < N; i++) {
   lcm_ = lcm(lcm_, a[i]);
   if (M < lcm_) {
     cout << 0 << endl;
     return 0;
   }
 }

 // 2^t で割った M = lcm * answer を満たす必要があり、
 // answer は奇数じゃないとダメなので、奇数の個数が答えになる
 M /= lcm_;
 int answer = (M + 1) / 2;
 
 cout << answer << endl;
 
 return 0;

}

これで AC とれたが、「X が 2 で割り切れる回数と a' が 2 で割り切れる回数は同じ」あたりから急に難しい。

まぁでも、解説PDFとか解説動画をそのまま写しただけといえばそうかもしれないが...。


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

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

この記事が入っているマガジン

コメントを投稿するには、 ログイン または 会員登録 をする必要があります。