ferinの競プロ帳

競プロについてのメモ

yukicoder

yukicoder No.922 東北きりきざむたん

問題ページ これは を最小化するように空港を設置する問題である.もし と が同じ木の頂点であれば,どのように空港を配置しても2点間の距離は変化しない.木の2点間の距離はLCAなどを用いることによって で求めることができる. ここからは と が違う木に属…

yukicoder No.924 紲星

問題ページ が の中央値のとき は最小になる.Wavelet Matrixを用いると数列のある連続する区間のk番目の数を求めることができるので,各クエリに対して中央値を求めることができる. 未満の要素の個数 未満の要素の和 以上の要素の和 以上の要素の個数 が答…

yukicoder No.878 Range High-Element Query

問題ページ 解法 マージソートの過程をセグ木に保存する方法(蟻本 p171)と同じ要領で,各頂点にその区間に対応する「高い要素」の列を保存しておく.左の子と右の子の2つの列をmergeするときには,左の子の列はそのままで,右の子の列の要素のうち左の子の列…

yukicoder No.877 Range ReLU Query

問題ページ 解法 区間]により大きい要素しかないのであれば を計算すればよい.逆に以下の要素しかなければ0を出力するだけである.区間]の和,以下の要素の個数,以下の要素の和が求まればより大きい要素と以下の要素に場合分けしてそれぞれ計算すればよい…

yukicoder No.776 A Simple RMQ Problem

問題ページ 解法 この記事(Maximum Subarray Sum in a given Range - GeeksforGeeks)のセグメント木を使って解いた。このセグ木では区間[l,r)の連続した部分列の区間和のmaxを求めることができる。セグ木の各頂点に「区間和」「maximum prefix sum」「maximu…

yukicoder No.235 めぐるはめぐる (5)

問題ページ No.235 めぐるはめぐる (5) - yukicoder 解法 HL分解の練習として解いた。クエリ0は街Xから街Yに対してC[i]*Zを加算するクエリ、クエリ1は街Xから街Yの値の和を求めるクエリになる。区間に対しての加算と区間和を求めるものなので遅延セグメント…

yukicoder 710 チーム戦

問題ページ No.710 チーム戦 - yukicoder 考えたこと 二人でスケジューリング問題をしましょうみたいな問題 どうせ貪欲かDP 制約小さいしとりあえずDPを考える dp[i問目][男がj秒][女がk秒] = (この条件が可能か) のDP 状態数が多すぎる dp[i問目][男がj秒] …

yukicoder 709 優勝可能性

問題ページ No.709 優勝可能性 - yukicoder 考えたこと 各パラメータで一番大きい値とその人を持てばいいだけでは?と思って書く サンプルで落ちる 冷静に読むと同じ値が複数出てくる 各パラメーターjで一番大きい値を取る人の集合cnt[j]を持っておきたくな…

yukicoder No.685 Logical Operations

問題ページ No.685 Logical Operations - yukicoder 考えたこと bitだし2進数で考える x AND y, x XOR y, x OR y を書いてみる X 01001 Y 11101 & 01001 ^ 10100 | 11101 x,yのi桁目を(x_i,y_i)と表す AND < XOR を満たすためには1が出てくる最初の桁が(0,1)…

yukicoder No.669 対決!!! 飲み比べ

問題ページ No.669 対決!!! 飲み比べ - yukicoder 考えたこと 取れる石の数の上限がK個のNim grundy数を使えという雰囲気を感じる 実験をすると「0 1 2 3 … k 0 1 2 3 … k …」みたいな周期になる つまり a[i]%(k+1) でそれぞれの山のgrundy数が求まる あとは…

yukicoder 595 登山

問題ページ No.595 登山 - yukicoder 考えたこと ARC067 D - Walk and Teleportを思い出す 同じように貪欲にできないかなとか考える 間を開けて歯抜けの状態で先に進んだほうがいいことはなさそう ワープして戻るときは単調増加しているできるだけ先のに進ん…

yukicoder No.58 イカサマなサイコロ

No.58 イカサマなサイコロ - yukicoderモンテカルロ法をはじめて使ったのでその記録です。 モンテカルロ法とは乱数を用いてシミュレーションを行う方法です。この問題では次郎君の試行として1から6までの範囲の乱数をN回求め、太郎君の試行として4から6まで…