水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder 700 点問題

AtCoder Regular Contest 102:D - All Your Paths are Different Lengths

問題 解法 解答 問題 beta.atcoder.jp 解法 0 ~ L - 1 の長さのパスを作りたいのだから,とりあえず長さ 2^0, 2^1, 2^2, ... , 2^20 の辺を張っておきたいと考える(2^20 までなのは,2^20 > 10^6 であるから)(log2(10^6) が大体 20 なので制約から察する…

AtCoder Regular Contest 101:D - Median of Medians

問題 解法 解答 問題 D - Median of Medians 長さ N の数列 a の全ての連続する部分列の中央値を集めた数列の中央値を求める問題. 解法 以下の2つの条件を満たす x は数列の中央値になる: 数列の中に x 以上の要素が半分以上含まれる x は 1. を満たす整…