[ тarsの記録 ]

ABC150 の振り返りです。

感想

コンテスト開始後しばらく5xx系のエラーで問題を開けなかったり、テストケースに不備があったり？で unrated になりましたが、途中で放棄せずに最後までやりました。結果は3完・・・。D問題はコンテスト中に解けなかった（不備関係なく）のは残念ですが、奇数倍に気が付けたのであとちょっとだったかな？と思っています。

各問題の振り返り

A - 500 Yen Coins

はい。A問題の中でもかなり優しい部類な気がします。

B - Count ABC

脳死でループ書いて全探索しました。（公式Editorialと同じ方法）

最近正規表現の本を読んでいるので、ホントは正規表現でやりたかったですが、C++の正規表現はまだ脳死で書けない（C++は競プロでしか書かず、メインの言語ではない）ので早く書けるほうを選びました。

C - Count Order

next_permutationしました。

std::next_permutation が辞書順かどうかは100%自信がなかったので、コンテスト中に調べました。

Cまでで15分くらいでした。（調べてなければもっと早かったハズ）

D - Semi Common Multiple

難しかったけど、あと一歩で解けそうでした。1時間半くらいこの問題とにらめっこしていました・・・。以下にコンテスト中に考えたことを書きます。

$X= a_k \times (p+0.5)$

について、とりあえず $0.5$ を $\displaystyle \frac{1}{2}$ と置き換え、式を以下のように変形してみました。

$\displaystyle X= a_k \times (p+\frac{1}{2})$

$\displaystyle X= a_k \times (\frac{2p}{2}+\frac{1}{2})$

$\displaystyle X= \frac{a_k(2p + 1)}{2}$

ここで、 $(2p + 1)$ は奇数なので、 $X$ は $\displaystyle \frac{a_k}{2}$ の奇数倍なことに気が付きます。

また、任意の $k$ に対して条件を満たさないといけないので、 $X$ としてあり得るのは全ての $\displaystyle \frac{a_i}{2}$ の最小公倍数の奇数倍だけだと考えました。

ここまで考えた時点で、「最小公倍数をとって、昇順に奇数倍していって上限 $M$ を超えるまでの回数を数えればいけるかな？」と思ってコンテスト中は実装したのですが、以下の考察が抜けていました😅

コンテスト中の考察で抜けていたところ

「全ての $a_i$ について、 $2$ で割れる回数が同じ」という条件が抜け落ちていました。ここまで考えが及んでいればACでした。

解説

$\frac{a_i}{2}$ の奇数倍だけ、ということは、 $p$ をどんな整数にしても $2^n$ を作ることができません。（ここに気が付いてなかった）

なので全ての $\displaystyle a_i$ について、素因数分解したときの $2^n$ の数が同じ、つまり $2$ で割れる回数が同じになっていないと $p$ をどんな値にしようが条件を満たすことができません。

おわりに

年末に引越しなどで忙しくて1~2週間くらい参加できておらず、今回は久しぶりの参加でしたがやっぱりコンテストにでるのは楽しいです。