ABC114回参加記
A,B一発、C 2WA, D, 1WAでした。
特別なアルゴリズムを必要とする問題はなかったので、点を稼ぎやすかった回だったのではと思います。
A問題
nが3 or 5 or 7かどうかを判定する問題です。
cinとif文がかければ行けると思います。計算量O(1)
注意:NoなのかNOなのかは気をつけましょう。それを間違えて5分のペナルティを食らうのは痛いです(戒め)。
B問題
数列の部分を取り出して、543との差を比べる問題です。
intで入力するよりもstringで入力して、charでループする方法がおすすめです。
charで3つの連続する数字を持ってきて、x100, x10, x1をしてint化します。
キャストは(int)ch[i]をやってしまうと、ASCIIコードになってしまうので (int)(ch[i]-'0')でキャストしてあげると良いです。計算量O(n)
3桁なので手打ちしてますが、桁が増えるとpowとかを使ってループさせます。
C問題
ビット全探索の拡張問題です。
ビット全探索は0 or 1ですが、この問題は0, 3 ,5 7を考えてあげる必要があります。
charとかintの配列を使って3or 4進数を自作し、全探索する問題です。
計算量はだいたいO(4^log(n))だと思います。
(僕は) whileを使って書いたので終了条件のところでbugらせて2WAです。whileを使うときは境界に気をつけましょう。
356とかで1が出力されたりしてました。
あと、-1を0に当てないほうがいいと思います。(実装中に気づいたため、無理やり-1を0に当ててます)
D問題
なかなか形容し難い問題です。
やることはn!を素因数分解して、素数の数の積が75にできるな数を探すという作業です。
75=5*5*3なので、作れる組み合わせが少ないののですべてのパターンを記述する方法で解きました。
これはソース読んだ方が絶対早いです。
39行目までが、mapを使って素因数分解をしているところ
その次が単一の素因数で75個以上あるケースの探索をして、
その次が2つの素因数のペアで3*25か5*15が作れるかを探し、
最後が3つの素因数のペアで3*5*5が作れるかを探しています。
3*5*5の時は5が二回出てくるので、重複なく数えるために、3パターンのif文を使っています。
お疲れ様でした。
明日以降に加筆します。