けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

メディアン

AtCoder ABC 132 C - Divide the Problems (300 点)

ソートして頑張る。 ソートすればいいと思い至りさえすれば、結構ソートするだけに近い感じの雰囲気の問題で、一瞬罠があるのかなと怖くなった。 問題へのリンク 問題概要 個の整数 が与えられる。 は偶数である。次の条件を満たすような整数 が何通りあるか…

AtCoder ABC 127 F - Absolute Minima (600 点)

超絶苦手系。でもこういうのパッとできるようにせな。 問題へのリンク 問題概要 関数 があります。 はじめ、これは定数関数 です。 個のクエリが与えられるので、順番に処理してください。クエリは 2 種類あり、入力形式とクエリの内容は以下の通りです。 更…

AtCoder AGC 020 C - Median Sum (700 点)

コンテスト中に真剣に考えて解けなかった 700 点問題!!! 問題へのリンク 問題概要 個の整数 があたえられる。 個の整数の部分和は空集合に対応するものを除くと 個ある。 このうちの中央値を求めよ。 制約 考えたこと とりあえず部分和問題みたいなことを…

全国統一プログラミング王決定戦 本選 C - Come Together (300 点)

こういうのを爆速で書けるようになりたい。問題としては マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要) の最小値を与える…

AtCoder ARC 101 D - Median of Medians (700 点)

今更前々回の ARC を見て、噂の 700-D Median of Medians を見てみたけど、これはJOI 2017 予選 F - L番目のK番目の数https://t.co/EEfPlJ18Tkとほぼ同じ問題な気がしたん。— けんちょん (@drken1215) 2018年9月6日 とは言え、完全に一緒ではなくて後半の議…