エイジング プログラミングコンテスト 2020 振り返り
D - Anything Goes to Zero
popcount(n)をnを2進数表記した時の'1'の個数とする.
n %= popcount(n)としたとき,nが0になる回数をf(n)とする.
あるNについて,Nを二進数表記した後,一つの桁のビットを反転させたものについてf(n)を求めよ.
解法:
単純に変換し愚直に計算するとTLE
一回の操作で大体NがlogNに変化することを考えると,各操作はせいぜい5~6回.
X1,X2,..., XNにたいしてpopcountで割る際,初回のコストが特に高いので,これを高速に実行する.
popcount(Xi) = popcount(X)±1 であることを考えると,X mod(popcount(X)+1 ),X mod(popcount(X)-1) を事前に計算しておき,同じく事前に計算した 2**i mod(popcount(X)+1 )や 2**i mod(popcount(X)-1 )
を足せばよい
(ただし操作回数0回の場合に注意)
E - Camel Train
N頭のラクダを並べる.
i頭目のラクダについて,Ki 番目以内にいればうれしさがLi,それ以外はRiである.
嬉しさが最大の時の嬉しさを求めよ.
(このようなケースがT個ある.)
解法:
最初に全体でL,Rの最小値の合計を求めた後,可能な限り答えを大きくしていく.
L>RのラクダとL<Rのラクダに分ける.(L=Rのラクダはどこにいてもいいので,都合の良いところに置けばよい)
この時,最適解において,L<Rのラクダが常にL>Rのラクダより右側に存在する解がある.(そうでない場合,これを満たすように並べ変えても嬉しさが変化しない)
つまり,別々に最適解を求めればよい.
L>Rのラクダについてリスト camels を作成し,(L-R)をK番目のリストにappendする.
camels のすべての要素について,数えたラクダの合計がラクダのいる番号を越えないようにする.
具体的にはheapqを使用して,
とすればよい.これにより,最小値からHに放り込まれた後,超過する分について再び最小値が削られていく.
L>Rのラクダについても同様に右側から計算してやることで答えが求まる.
Submission #15195468 - AIsing Programming Contest 2020
F - Two Snuke
解法:
まずはs1,n1,u1,k1,e1が0の場合について考える.
この場合、掛け算の和はcombで表すことができる.
N個のボールに5個の仕切りを入れ,先頭から順に割り振る.掛け算の和は,仕切られた中から選ぶ方法の数と対応している.
これはN-5個のボールに(5+5)個の仕切りを入れる方法と同値である.
次に, s1,n1,u1,k1,e1が0出ない場合について考える.
Δs = s2-s1, s = 2s1, ...
と設定すると,
s+n+u+k+e + Δs+Δn+Δu+Δk+Δe ≦ Nを満たせばよいことになる.
これはN-5個のボールに(5+5+5)個の仕切りを入れることに対応する(最初5つのセグメントは偶数).
前半5個は偶数,後半11個は奇数か偶数.
2個セットの偶数で扱えば,前半5個はすべて偶数になる.
後半11個も扱うために,後半11個の偶奇の可能性を全探索し,奇数のところには1個追加すればよい.Nとの偶奇を合わせるために,奇数は 1,3,5,7,9,11個 か 2,4,6,8,10 個である.