buyoh.hateblo.jp

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

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

atcoder

本番の時は N = A+B or N+1=A+B で考察してWAでした．

問題文

最長増加部分列の長さがA，最長減少部分列の長さがBとなるようなN要素から構成される順列を印刷せよ．

提出

Submission #2751681 - AtCoder Regular Contest 091

解説を殆ど*1見ずにACした．

*1:コンテスト終了直後に目を通したような通してないような

続きを読む

AtCoder Chokudai Contest 001 高橋君の山崩しゲーム

参加はしていましたが，改めて解いてみた．

問題概要

30x30のグリッドがあり，各マスに自然数が書き込まれている．次の一連の流れを1手とする．手数を最小化せよ．

  1. 1つのマスを選ぶ
  2. デクリメントする．
  3. ４近傍のうち，デクリメント後のマスの数と一致したマスがあれば，そのマスを改めて選び，ステップ2に戻ることができる．

補足

リンク付けはされていないが，公式解説がある．

https://www.slideshare.net/chokudai/chokudai001

続きを読む