buyoh.hateblo.jp

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

データアクセスに制限のある 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 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

続きを読む

codingame: Code of Kutulu 参加記録

codingame

問題概要

KutuluのMinionの攻撃を回避して最後の1人になることが目標．

sanity(SAN)の減少

  • 何もしなくても勝手に下がる．近くに味方が居ると下がりにくくなる．
  • Minionの攻撃を受けると-20．

手段

  • 敵を遠ざけるLight*1
  • 周囲の味方を回復するPlan
  • 一度だけ周囲の敵を騙すYell

戦績

今回は打ち込める時間があったためか，初Legendary．33/2092位．

前半，仕様が滅茶苦茶だったのでやり込む人少ないかなとは思いましたが，そんなことは無かった．

*1:遠ざからないこともある．Lightは最短のプレイヤーを探すためのテーブルのみに影響がある．Minionは常に最短経路を移動する．

続きを読む