ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC - A,B埋め(042~)

番外編

こちらの続きになります。
42以降のA,B問題のうち既に埋まっていたものもいくつかありますが、その残りをすべて解きました。
ということで、また印象に残った問題についてつらつら記録していこうと思います。
A問題は省略し、B問題についてのみ書いていこうと思います。

ABC046 B - AtCoDeerくんとボール色塗り / Painting Balls with AtCoDeer

問題
提出コード
N個のボールがすべて色が被らないようにするのか、と思い込んでいてWAを連発しました。
結果的には、最初のボールだけ好きな色を選び、その後は残ったK-1色の中から好きな色を選んでいけばいいことになります。
ということで、K×(K-1)^{N-1}になります。


ABC051 B - Sum of Three Integers

問題
提出コード
蟻本の25ページにもさらっと載っているような、基本的でかつ重要(だと個人的に思っています)な計算量を落とすテクニックを使用します。
x,y,zについてそれぞれ0~kの範囲で全探索して、x+y+zがsになるかを調べるとTLEします。
ですが、実はxとyを決めると、足すとsになるようなzは一意に決まり、
z = s - x - y
となります。
なので、xとyについて全探索をし、(s-x-y)が0~kの範囲に入っているかどうかで判断すれば、for文のループを1つ減らすことができます。

ABC064 B - Traveling AtCoDeer Problem

問題
提出コード
気づくと簡単系です。
好きな場所からスタートし、好きなところで終了できるので、座標が昇順(または降順)となるように進んでいけばいいです。
ということで、結局は最大値から最小値を引いたものを求めれば、答えとなります。

ABC079 B - Lucas Number

問題
提出コード
フィボナッチ数を求めるのと同じことをすればいいです。
O(N)が間に合うので、Nの要素数の配列Lを用意し、L_{i} = L_{i-1}+L_{i-2}という漸化式を利用して動的計画法を適用すると答えがL_{N}に入っています。
今となっては基本中の基本ですが、昔はこれもできなかったのかと思うと成長を実感できる…んですかね？


001~040のときと比べて、あまり印象に残る問題が少なかったですね…すらすらと解けるようになったのでしょうか？
実際は誤読をしたりサンプルを通さず出していたのでWAを連発したりしていたのでまだまだという感じもしたのでまた精進していこうと思います。
ということで、ABCのA及びB問題を埋め終わりました！わーい。