naoya_t@hatenablog

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

AtCoder Beginner Contest 103

7/21 21:00-22:40
起きてたので出ました

続きを読む

〈ARC埋め〉ARC 064 E, 067 E, 071 E

AtCoder Performances (thanks to Noiminさんfuurinさん)
f:id:n4_t:20180719224910p:plain:w500

パフォーマンス上げていきたいので600点問題も(それ以上も)埋めます

続きを読む

TCO18 Algorithm Round 3B

Round 3Aはれじったけど寝倒したし今度こそ
iwashi31たんとかcafelierたんとか同室

続きを読む

〈過去問埋め〉技術室奥プログラミングコンテスト #3

技術室奥プログラミングコンテスト #3(出てないやつ)
https://beta.atcoder.jp/contests/tkppc3
の問題を見てみた

続きを読む

中央値の中央値 (median of medians)

ABC100の解説で触れられていた「中央値の中央値 (median of medians)」のことを調べたメモ。

厳密なmedian値でなくていいのでそれっぽい値をO(n)で求める方法。少なくとも上下に\frac{3}{10}n個ずつ、それより小さい(or 大きい)値が存在することが示せる。

真のmedianの近似として、適当なpivotの選択に使える。
(配列の中でk番目に小さい値を選ぶときに使える。k=n/2とすれば当然真のmedianも求まる。quicksortのpivotにも使えるけど乱数でやったほうが速いとか。最悪計算量は減らせるけど)

原理は割と簡単

続きを読む

〈AGC埋め〉AGC 500点問題 (AGC 001 B, 002 C, 010 B, 013 B, 014 B)

日課
400点まで埋めてしまったので500点を埋めた
f:id:n4_t:20180718131810p:plain

続きを読む