h_nosonの日記

競プロ、CTFなど

DP

Codeforces Round #363 (Div. 2) E. LRU

問題 Problem - E - Codeforces N個のデータと容量Kのキャッシュがある.キャッシュのアルゴリズムにLRUが使われていて,無限のクエリが飛んできたとき,最後のキャッシュの状態にそれぞれのデータが含まれる確率はいくつか. 解法 簡単に言うと,キャッシュ…

yukicoder No.174 カードゲーム(Hard)

問題 No.174 カードゲーム(Hard) - yukicoder A君とB君がカードでゲームを行う.1から1000までの数字が書かれたカードがあり,その中から枚ずつ配られる.試合は回あり,試合ごとにプレイヤーがカードを出していき,大きい数字を出したほうがその数字…

Topcoder SRM 690 Div 2 Hard WolfHockeyTeamEasy

解くのに10時間ほどかかった... 問題 TopCoder Statistics - Problem Statement 人が横に2列になって写真を撮る.それぞれの人はからまで番号がふられている. この時の並びは"nice"かつ"different"でなくてはいけない."nice"とは,以上の番号がふられた人…

yukicoder No.209 Longest Mountain Subsequence

問題 No.209 Longest Mountain Subsequence - yukicoder 個の整数が与えられる. を地形の高さだと考えた時に,の部分列から構成される山で,麓に近づくにつれて坂が緩やかになるような山の幅の最大値を求める問題.解法 ある地点を頂上だと考えた時にそこか…

yukicoder No.75 回数の期待値の問題

問題 No.75 回数の期待値の問題 - yukicoder 1つのサイコロを繰り返し振り,出た目の合計をにする. もしを上回ったら合計を0にリセットする. サイコロの振る回数の期待値はいくらか.解法1 絶対誤差か相対誤差がに収まればいいので モンテカルロでも正解を…