yukicoder No.75 回数の期待値の問題
解説ACしてから理解しようとしたら辛かった
https://yukicoder.me/problems/no/75
https://yukicoder.me/submissions/285676
問題概要
- さいころを振って,でた目を累積する.これを1手とする.
- 累積値がKになったら終了.超えたら0にリセットする.
手数の期待値を求めたい.
キーワード
巡回するDP
おすすめ解説サイト
yukicoder No.75 - 回数の期待値の問題 - ゲームにっき(仮)別館(仮)
典型力高すぎてちょっと分からない
因幡めぐる@競技プログラミング(@meguru_comp)/「【yukicoder No.75】」の検索結果 - Twilog
続きを読む定数倍高速化
アルゴリズムとはほぼ無関係.
スタート地点
遅いコード 2797 ms Submission #3108991 - AtCoder Regular Contest 025
namespace Two
を修正します.
一番早いantaさんを見て絶対届かないと思いました.
続きを読むデータアクセスに制限のある Binary Indexed Tree () の高速化
タイトルについて
正しくは「データアクセスに制限のある Binary Indexed Tree (と同じクエリに答えるデータ構造) の高速化」です
Binary Indexed Tree とは
以下のクエリに時間O(logN)で答えることが出来るデータ構造.
初期化
- サイズNの配列の要素を0に初期化する.
応答
- add(ptr, val) ptr番目の要素にvalを加算
- sum(ptr) 要素[1..ptr]の総和を求める
本記事で加える制約
- データ構造は「カーソル」を持つ.
- カーソルは1つ右,または1つ左へ移動できる.
- 1番目からカーソル位置までの総和を求める
この場合,addとsumを時間O(1)で答えることが出来る.
続きを読むAtCoder Regular Contest 061 - E すぬけ君の地下鉄旅行 / Snuke's Subway Trip
解説と若干違っていたので
概要
https://beta.atcoder.jp/contests/arc061/tasks/arc061_c
鉄道会社の乗り換えを最小化せよ
かなり雑なブログ記事です
続きを読むAtCoder Grand Contest 026 - B rng_10s
解説を軽く読んだだけでは理解できない脳なので記事書いた.
問題
https://beta.atcoder.jp/contests/agc026/tasks/agc026_b
- 昼:客のsnukeさんがジュースをB個買う
- 夜:rngさんが在庫を確認し,C個以下なら翌日朝までにジュースをD個仕入れる
ある日の朝,ジュースの在庫はA個だった.snukeさんは永遠にジュースを買い続けられるか?
続きを読むAtCoder Regular Contest 091 - E LISDL
本番の時は N = A+B or N+1=A+B で考察してWAでした.
問題文
最長増加部分列の長さがA,最長減少部分列の長さがBとなるようなN要素から構成される順列を印刷せよ.
提出
Submission #2751681 - AtCoder Regular Contest 091
解説を殆ど*1見ずにACした.
*1:コンテスト終了直後に目を通したような通してないような