読者です 読者をやめる 読者になる 読者になる

AtCoderやってみた

今回はAtCoderの問題を練習がてら解いてみたよ、という日記です。

部分点しか取れなくてもやもやしてるのでここにあげてみます。

問題はCODE FESTIVAL 2016 Final (Parallel)のB問題、詳細は以下

Exactry N Points

  • N問の問題が与えられる

  • i番目の問題を解くとi点もらえる

  • 問題番号が大きいほど難易度が高い

  • N問のうちいくつかの問題を解き、合計得点がN点になるようにしたい。この時できるだけ簡単な問題を解いてN点にせよ(解答する問題の問題番号の最大値が小さくなるようにせよ)


最初に考えたのはNを2分割していって解を求めると言う分割統治的なアプローチだったんですが、これだと分割していった結果同じ数が現れたときの処理が大変だと思い断念。

とりあえずNが簡単な場合に、和がNになる番号の組み合わせで重複のないものを考えて、N=kの解からN=k+1の解を構成できないか考えます。

f:id:unthocyanidin:20161210091805g:plain:h450

線で結ばれたノードは上位ノードに以下の操作をすることで下位ノードが構成できることを示しています。
- ノードの要素の一つに1を足す
- 要素1を追加する
またピンク色のノードは問題番号の最大値が最も小さいノードを示しています。(つまりピンクのノードがN=kのときの解)

図から、帰納的に解を構成できそうだとわかりました。次にピンクのノードだけ取り出して、解の構成法に規則性がないか見てみます。

f:id:unthocyanidin:20161210092651g:plain:h450

赤字で示したのはN=kの解からN=k+1の解を構成する際に"1"増えた要素です。 図をみるとツリーの層を下るに従って赤字が右から左にずれているのがわかります。これが解の規則性です。 規則性のおかげでN=kのときの解が既知で、N=kの解を構成するときにどの要素に1を加えたかを記録しておけばN=k+1の解も構成することができます。

以上の方法で解答を提出すると部分点がGetできました。しかしNが大きい場合にタイムアウトしてしまう...

せっかく規則性がわかったのだから、そこから一般項を求めることができれば、あるいは一般項とまではいかなくともボトムアップ的な解法を回避できればNが大きい場合でもうまく行くはずです。

そこで、この図を要素数ごとにグループ分けしてみます。 f:id:unthocyanidin:20161210100201p:plain:h450 すると第n群の1番目の組み合わせは{1,2,3,...,n}であるとわかります。このことから第n群のi番目の組み合わせは{1,2,3,...,n}のうち大きいほうから要素をi個選び、それぞれ1を足したものとなります。

というわけで、解法として以下の3ステップで解を構成することができます。 1. 与えられたNが第何群か計算する 2. Nの属する群の初項を求める 3. 初項にたいして適当な数だけ1を加える

この方法では1から解を構成するのではなくN群の属する初項を求めてから解を作るため最初の方法に比べて計算量が少なくなります。

とりあえずこの方法でもう一回、解答なげてみますかね。うまく行けば満点もらえるかと。