yukicoder No.698 ペアでチームを作ろう
yukicoderもやりはじめました.
No.698 ペアでチームを作ろう - yukicoder
という制約をみておおっ...と思い, とりあえず全探索の計算量を見積もりました.
まず人いたときの二人組の作り方の場合の数について考察します.
が偶数ということなので, そのときの場合に限り考察します.
人を2人組に分けるときの場合の数
は次の漸化式を満たします.
少し説明を入れると, 人いて,
人で二人組を分けるときの数
がわかっているとき, 新たにそこに2人A,Bを加えます. このときの2人組の場合の数は, AとA以外の誰かを組ませる場合の数とそれ以外の人々の二人組の組み合わせの積となり, 結果上の式が導かれます.
上の式に従っての場合を計算すると,
となり, 全探索をしても間に合いそうです(ほんとか？).
しかし, 実装においてsetやvectorを使って要素を増やしたり消したりしていると, あっという間にTLEしました. 実際には上の組み合わせの数より多くのループが回っているからだと思われます.
ここで, 全探索において, 同じ計算を何度もしていることに気がつきました. 組み合わせについてbitで管理しておき, 計算結果を保持しておくことで高速化を図りました. 結局, bitDPのようなものができました. bitDPもどきを実装するのは初めてだったので勉強になりました.
#277981 No.698 ペアでチームを作ろう - yukicoder
ABC 105 反省
バッチェ冷えました...unratedで正直助かりました.
A - AtCoder Crackers
が
で割り切れるとき0, そうでないとき1です.
Submission #2983810 - AtCoder Beginner Contest 105
B - Cakes and Donuts
オイオイ互除法か？と思いましたが制約をみて全探索. B問題ということもありますから...
Submission #2984808 - AtCoder Beginner Contest 105
ここから時間内に解けず;;
C - Base -2 Number
−2の基数変換. ググったりするもよくわからず, お手上げでD問題へ行きました.
結論からいうと正の基数変換と同じように-2で割ったあまりr(r>=0)を順次文字列につけたしていくことで求められるようです... 負の数の余りはめんどくさそうであるとかいう先入観も入ってあまり考察が捗りませんでした.
Submission #2994168 - AtCoder Beginner Contest 105
D - Candy Distribution
ずっとしゃくとり法にこだわってみるも解けそうになく, 累積和をMで割った余りをmapにいれてカウントするところまで気づいてタイムアップ.
右に要素を加えていくと考えたとき, そのときの累積和をMで割った余りが左の累積和のなかで等しい要素の数だけ条件を満たす列が増えるので, 順次それを足しこめば答えです.
Submission #2994015 - AtCoder Beginner Contest 105
ABC 066 D-11
D - 11
個の数列の中で1組のみ等しいものがあり, それ以外は互いに異なる要素であることがポイントです.
問題を少し簡単にして, この等しいもの2つの中から１つのみを取り除いて個の数列について, k個の部分列の個数を考えてみます. この数列において要素はそれぞれ異なっているため, k個の部分列の個数はこの要素の中からk個取り出す場合の数と一致します. よってこのときの答えは
となります.
もとの問題に戻り, この数列に対してもを考えてみましょう. このとき, この組み合わせの数には重複が存在します. なぜならば, 等しい要素が存在しているために全く同じ数列を複数回カウントしてしまうからです.
の組み合わせの中から重複しているものを取り除く方法について考察します. そもそも, 重複するような組み合わせはどのようなものでしょうか.
等しい組の左の方を, 右の方を
とします. 重複して数えてしまう組み合わせは, このどちらかを含んでいます . 重複して数えてしまうものは, この
と
の数列上の順番に対し, どちらの数字の場所を選んでも成立するようなものです.
具体的に言うと, の左側の数列と
の右側の数列から
個を選ぶとき, 数列内の等しい組の
または
のどちらかを選んで加えることができます. このような要素が重複となっているので, これを一回分引いてあげれば答えです.
と
の中間の要素を含む部分列が存在すると,
と
のどちらの要素を使っているかが特定できるので重複にはなりません.
実装には逆元ライブラリを用いました. パスカルの三角形で組み合わせを求める方法だと空間も足りず, 時間も間に合いません.
ABC 060 D-Simple Knapsack
D - Simple Knapsack
ナップザック問題ときたら真っ先に重みでDPか価値でDPか半分全列挙かどれかだろうなあと思って制約を見たらも
も
も大きくてDPできず, さらには
の値も100と半分全列挙するには多すぎます. しかし, 特殊な制約
というものがあります. この制約からの取りうる数値は4種類しかないことがわかります. あとは入力をこの4種類に分類したあと価値順にソートします. 4種の重さからそれぞれいくつ取り出すかを全探索し, 価値の大きいものから貪欲に選び, その重みの和が
より小さければ, 最小値を更新します. すべてのパターンを探索すると答えが得られます.
POJ No.3276 Face The Right Way
3276 -- Face The Right Way
蟻本問題です.
左から牛を見ていき, 後ろを向いていた牛がいたらその牛を左端としたK個の区間の牛の前後をひっくり返し, 右へと見ていく. 左端からK個の区間がとれなくなるまで繰り返し, 残った区間の牛がすべて前を向いているかを確認し, 条件を満たしていればKを記録し, Mを更新する. Kを1~Nまで試して答え.
実装において, 牛をひっくり返すたびにBとFを交換していると面倒で, 計算量も大きくなります. そのために, 各要素についてその番号の牛を左端としたときにひっくり返す操作をしたかどうかを記録する配列を用意しておきます(ひっくり返したら1,ひっくり返していなかったら0).
i番目の要素を見ている時は, i-K+1~ i-1番目までの要素を何回ひっくりかえしたかがわかればi番目が今BかFか確定できます. いちいちi番目の要素をみるときにi-K+1~i-1番目を見ると, 計算量がかさみます. これを防ぐために, i-K+1~i-1 番目の和を格納する変数を用意しておき, iをインクリメントしたときにi-K+1番目の要素を引き, i-1番めの要素を足すしゃくとり和（？）をすることで定数時間でこの和を計算することができます.
POJ No.3320 Jessica's Reading Problem
3320 -- Jessica's Reading Problem
蟻本の問題です.
全要素を満たすまでページをめくり続け, 満たしたら答えの値を更新して左のページを減らし, 全要素を満たさなくなったらページをめくり...とすることで最適解が得られます. 区間の単調性からしゃくとり法ができる例です.
提出
http://poj.org/showsource?solution_id=19033183
ABC 034 D-食塩水
D - 食塩水
問題を見ると, とてもDPがしたくなります. 入力のアルファベットがNとKでそれぞれ制約1000以下, 解説でO(NK)で解けます!と書いてあるところまで想像しDPを考えました. しかし, 食塩水の濃度をテーブルにもたせるとすれば, 水の重さも共に持たせなければ遷移が考えられません. そのためDPは挫折し, あっさり解説を見ました.
適当にK個容器を選んだときの濃度pは
と記述できます. ここで, 『ある濃度pを与えたとき, その濃度より大きい食塩水を作れるか？』という問題を考えます. つまり,
を満たすようにpをK個選べるかどうか(True or False)という問題です. この式を変形すると,
という式になります. pは固定されているので, できるだけが大きいようなものを取ってくることで, この式が実現可能かどうかが決定します. この問題は各iについて
のソートがネックとなり,
で解くことができます.
上の問題に対し, あるpが作成可能であったとき, それより大きな濃度の食塩水が作れることが期待できます. 不可能だったときはpを下げて再び実行...と考えていくと, 二分探索が適用できることがわかります.
このpを十分な回数二分探索することで, 解を求めることができます. 繰り返し一回につき誤差が半分となるため, 100回も繰り返しておけば十分すぎると思います. 繰り返し回数Qとすると全体の計算量はとなります.
