buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

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

解説ACしてから理解しようとしたら辛かった

https://yukicoder.me/problems/no/75

https://yukicoder.me/submissions/285676

問題概要

  • さいころを振って,でた目を累積する.これを1手とする.
  • 累積値がKになったら終了.超えたら0にリセットする.

手数の期待値を求めたい.

キーワード

巡回するDP

おすすめ解説サイト

garnacha.techblog.jp

garnacha.techblog.jp

yukicoder No.75 - 回数の期待値の問題 - ゲームにっき(仮)別館(仮)

典型力高すぎてちょっと分からない

因幡めぐる@競技プログラミング(@meguru_comp)/「【yukicoder No.75】」の検索結果 - Twilog

続きを読む

AtCoder Regular Contest 027 - D ぴょんぴょんトレーニング

解説とは違う方法なので

問題

N個の石があって,i番目の石はi+1..i+H\[i\]にジャンプ出来る. 次のD個のクエリに答えたい:s番目の石からt番目の石へ移動する方法の数を答えよ.

キーワード

  • 行列演算表現を用いた動的計画法
  • 行列が乗ったセグメントツリー
続きを読む

データアクセスに制限のある 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:コンテスト終了直後に目を通したような通してないような

続きを読む