ganmo::cout

競技プログラミング始めました

CADDi 2018 for Beginners

25分で全完したら🥉3位🥉/1314位でした
いくらrated(緑以下)のみ参加OKのコンテストとはいえrated内1桁、しかも3位だったので解き終わってから順位表観てたまげました

A - 12/22

問題: A - 12/22
コンテスト中は10で割ったあまりが2かどうかを見ては2で割って、というのを0になるまで繰り返してあまりが2だった回数を出力すればいい、というふうに解いた。
今考えれば入力が4桁だけなので入力をstringで受け付けて各桁2かどうかでやってもよかったかもしれない

拙解1 (コンテスト中, C++): Submission #3837598 - CADDi 2018 for Beginners
拙解2 (コンテスト後, C++): Submission #3851486 - CADDi 2018 for Beginners

B - AtCoder Alloy

問題: B - AtCoder Alloy
向きを変えられない、ということは単純に{H\le A_i \land W\le B_i}を満たすiの数を数えるだけ。

拙解 (C++): Submission #3838320 - CADDi 2018 for Beginners

C - Product and GCD

問題: C - Product and GCD
a_iはすべて正の整数になるので、Pの素因数分解の指数を各a_iに分配する問題に帰着できる。
なので、Pを因数分解して指数をNで割った商をまた底の上に乗せれば、\mathrm{gcd}\{a_i\}の素因数分解が求まる。
つまり、
{\displaystyle\begin{eqnarray*} P&=&2^{p_{1}} \times 3^{p_{2}} \times 5^{p_{3}} \times \cdots,\\ a_i&=&2^{p_{i1}} \times 3^{p_{i2}} \times 5^{p_{i3}} \times \cdots,\\ \end{eqnarray*}}
というふうに素因数分解したとすると
{\displaystyle\begin{eqnarray*} P&=&a_1 \times a_2 \times \cdots \times a_N \\ &=&\prod_{i=1}^N 2^{p_{i1}} \times 3^{p_{i2}} \times 5^{p_{i3}} \times \cdots \end{eqnarray*}}
とするときに、\{a_i\}の最大公約数を最大にしたいなら、それぞれのjについて\mathrm{min}_i\{p_{ij}\}を大きくする必要がある。
なので、なるべく均等に分配すると、その最大値は{\lfloor \frac{p_j}{N} \rfloor}となる。よって、
{\displaystyle\begin{eqnarray*} \mathrm{max}\{\mathrm{gcd}\{a_i\}\}=2^{\lfloor \frac{p_1}{N} \rfloor} \times 3^{\lfloor \frac{p_2}{N} \rfloor} \times 2^{\lfloor \frac{p_3}{N} \rfloor} \times \cdots \end{eqnarray*}}
これで解けた。コード読んで頂いたほうが分かりやすいと思う。

拙解 (C++): Submission #3840604 - CADDi 2018 for Beginners

D - Harlequin

問題: D - Harlequin
木が多いと問題が難しく思えるが、1本だけだった場合を考えると、自分が先攻で固定なので、最初のりんごを食べる前に木になっているりんごの数が奇数だと勝ち、偶数だと負けとわかる。
木が複数本ある場合に拡張すると、奇数個のりんごがなっている木をすべて選んでりんごを食べるのが最適戦略になる。なぜならば、そうすれば相手の選択肢はすべて偶数個のりんごがなっている木となり、最後のひとつ*1を食べることができず、相手は絶対に勝てない。よって、自分が先に食べ始めるのが決まっているので、最初に食べたときにすべての木のりんごの個数を偶数にできれば勝ちが確定する。
よって、最初木になっているりんごの数がすべて偶数ならばルンルンの勝ち、ひとつでも奇数があれば自分の勝ち。なので、これを実装すればいい。あまりに実装が軽くてコンテスト中はWAを覚悟したが無事通ったのでよかった。

拙解 (C++): Submission #3842019 - CADDi 2018 for Beginners

まとめ

Beginner(緑以下限定コンテスト)とはいえ3位でしかも賞金出るのはうれしすぎる、CADDiさんに感謝するしかない
上限パフォでしたがすでに緑上位なのでギリギリ水色に行きませんでした
書いてる現在は完全に図に乗ってます（緑コーダーなのに）、chokudaiさんの学部1年の時の経験のミニチュア版みたいなものが体験できました
参考：（大学時代の前半のところ）
chokudai.hatenablog.com

*1:１は奇数