ferinの競プロ帳

競プロについてのメモ

yukicoder

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まで…