社会人になったので真面目に競技プログラミングをやることにした v0.8
社会人になったので、競技プログラミングを真面目に始めることにした。
自分の身の振り方にいろいろ思うことがあったので。
なにするの
・毎週コンテストに参加(今のAtCoderのシステム知らないけど、ABCもしくはARC)して知見を一定の規則で出力する。
出力規則も書いたんだけどめちゃめちゃ意識高くなったので恥ずかしくなって消した。
・週2問くらい解いてやっぱり知見を一定の規則で出力する。水色 と緑色 をループする感じなので、最初のうちはここ(https://nizi26i26.hatenablog.com/entry/2018/04/01/200247)から持ってこようかなあと思う。
社会がしんどくなることも見越したこの数字なんだけれども、社会がもっとしんどくなる可能性もある。ならないといいなあ。
ARC095/ABC094 C/D
C
問題概要
N個の数が与えられた時、i番目の数を除いた集合の中央値を答える問題。
取った方針
Nが10**5なので、ソートして二分探索してそれが真ん中より左だったら元の中央値を答えればいいし、右だったら元の中央値の一個右を答えればよい。これでソートがO(NlogN)、二分探索*NがO(NlogN)で通る。
と思っていたらTLEした。なぜ。
よく考えたら「ソートして真ん中より左かどうか」というのは「元の集合の中央値より小さいかどうか」なので、元の集合の中央値を求めてあれば二分探索するまでもなく求まってO(1)。でもソートがO(NlogN)だと思うんですけど(名推理)
得られた知見
中央値より小さいならばソートした時中央より左にあるし、大きいなら右にある。(あたりまえ体操)
解くのに必要な要素
計算量的にソートしてもいいときはとりあえずソートしてみる。
中央値より小さいならばソートした時中央より左にあるし、大きいなら右にある。(あたりまえ体操)
周辺調査によって得られた知見
特になし
D
問題概要
N個の数の集合が与えられて、nCrが最大となるn,rの組を見つける。Nは10**5。
取った方針
なんとなくnは集合の最大値を取っておけばいいような気がする。ならnは固定してrを全探索すればO(N)で通るような気がした。(通らない)
なぜならnCrはO(1)では計算できないため。
nCrのnを固定してrを整数とするとf(r)=nCrは中央が高い山型になるので、多分n/2に一番近いrを選べばいいんだろうなあ、と思いながらなぜか高速にnCrを計算する方法を探し始めて時間切れ。
終了後に上記のアルゴリズムを書いてAC。(その前に10**9と10**8を打ち間違えて大量のWA)
得られた知見
・nCrはO(1)では計算できない。
・a<bの時、aCr < bCr。
・nCrのnを固定してrを整数とするとf(r)=nCrは中央が高い山型になる。
・n乗を書ける言語ならゼロを横にたくさん並べるべきではない。(typo してWA するため)
解くのに必要な要素
・a<bの時、aCr < bCr。
・nCrのnを固定してrを整数とするとf(r)=nCrは中央が高い山型になる。
周辺調査によって得られた知見
nCr = (n-1 C r-1) + (n-1 C r) みたいな漸化式があるので、DPに持ち込むことができる。大学受験で見るヤツだ……！
nCrを何度も計算しないといけなくて、空間計算量がO(nr)でもよくて、計算量O(nr)で間に合うタイプの問題なら使えるかもしれない。(そんなシチュエーションあるのか？)
出典:http://tubo28.me/algorithm/comb-dp/
反省
方針が固まりきらないうちに手を動かして迷走しがち？コンテスト序盤に早解きしようとして焦りすぎかもしれない。
社会
がんばったら1.5h くらいでこれがかけたので、社会がつらくなってもがんばって書きたい。
