naoya_t@hatenablog

いわゆるチラシノウラであります

ARC077(タイムシフト参加)

昨夜爆睡中に開催されたAtCoder Regular Contest 077にvirtual参戦。

時間内(1時間40分だよね?)に解けたのはDまで。Eは計算が合わず、食事後に修正して提出。
f:id:n4_t:20170702233732p:plain
↑始めたのが20:45過ぎ

C - pushpush

dequeで前後に交互に追加していくやつ
偶数か奇数かで前後どちらから始めるかを変える(あるいはどちらから読むかを変える)。
→AC
Submission #1399441 - AtCoder Regular Contest 077 | AtCoder

D - 11

n+1枠にn種類入る→同じ種類で2箇所に入るやつが1つだけある(鳩の巣原理)
全部違う種類だったら、{}_{n+1}C_1\cdots{}_{n+1}C_{n+1} を列挙するだけだけど
同じ種類のうち1つだけが使われるケースに重複が発生するので、重複分を削りたい

同じ種類のやつを a_u=a_v=p とすると
a_0,a_1,\cdots,a_{u-1},p,a_{u+1}\cdots,a_{v-1},p,a_{v+1},\cdots,a_n
で、2つの p を境に
(u-1個) p (v-u-1個) p (n+1-v個)
の3グループに分けることができる。それぞれをα, β, γ としよう。
αpβγとαβpγで共通な物を列挙、なんだけど
複数回出現する唯一の数字pを抜いてあるので、α, β, γ 3グループを通じてすべての数字は互いに異なる。という事から、β部分からは選ばれていないので、αpγ が何種類あるか列挙する問題になる。
k個の数字を選ぶとすると、αpγからpを抜いたαγからk-1個を選ぶ問題、即ち{}_{(u-1)+(n+1-v)}C_{k-1}={}_{n-(v-u)}C_{k-1} の計算問題。(剰余演算を二項係数の隣りからインクリメンタルにやるやつ)
→AC
Submission #1399516 - AtCoder Regular Contest 077 | AtCoder

E - guruguru

min(next-prev, next-fav) の折れ線グラフを微分していもす法
時間内に計算が合わなくて提出せず
→晩飯後に修正してAC
Submission #1399621 - AtCoder Regular Contest 077 | AtCoder