AtCoder ABC215
ABC215参加しました。
A - Your First Judge
解説 - AtCoder Beginner Contest 215
文字列の比較をすればいいです。公式解答が頑張っていろんな言語で書いてるのに驚いた。
C#で解きましたが、入力文字列=="Hello, World!"で問題なし。
B - log2(N)
解説 - AtCoder Beginner Contest 215
(long)Math.Log2(N)だと、精度不足でした。公式解答でも指摘されてますね。
C#だとdecimal使えばいいのかも知れませんが、decimalはlogを取れないようです。
そもそも入力例にあるように、 $ 10^{18} $ でも2のべき乗だと59という小さな値で収まる以上、for文でNを超えない範囲で2倍したほうが、小数も使わないですし楽でした。
やっぱり競プロで小数問題は要注意ですね。
C - One More aab aba baa
解説 - AtCoder Beginner Contest 215
提出 #25260855 - AtCoder Beginner Contest 215
D - aab aba baa という問題をより簡単にしたものだと思いました。辞書式順序問題です。
NextPermutationで解きました。
文字列の長さが8である以上、Kも$8! = 40320$程度で、NextPermutationでK回回しても問題なかったです。
D - Coprime 2
解説 - AtCoder Beginner Contest 215
gcd()と聞くとどうしても苦手な問題きたか、と思ってしまいますが、今回はそうでもなかった。
発想としてはgcd(a,b)=1なら、a,bは互いに素なはずで、今回求めるkは全部素数なのではないかという点から考えました。で、1~Mまでの素数を全部求めて、ただしAに入っている素数だけは除外する、みたいな。
ただ、これだとA={6,1,5}のとき、k=2,3とかが入ってしまうため、どうにかならないかと他の入力例とかを考え始めて、A=(1,5,25)を考えついたときピンときました。
Aに含まれる数のすべての素因数の集合P(hashsetで保持、つまり、同じ要素を2つ含まない)を持っておきます。
あとは、1~Mまでの数で、Pの要素の倍数を除外していきます。
例えばA=(1,5,25)だとP={5}で、1~Mの中で5の倍数は除外します。
素因数を求めるアルゴリズムはライブラリ化してあると楽。
E - Chain Contestant
解説 - AtCoder Beginner Contest 215
提出 #25260829 - AtCoder Beginner Contest 215
bitDP... まだ学習前でした。 なのでここに書けることはほぼない... 一応解説を見て書いたACコートは上げておきます。
まとめ
手元のライブラリに助けられた回でした。 DPはもっと練習が必要。
