buyoh.hateblo.jp

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

ハル研究所プログラミングコンテスト2018に参加しました

ハル研究所プログラミングコンテスト2018とは

www.hallab.co.jp

自分にとっては

  • 2度め．
  • 2019年卒なので，今回が最後．

今年の成果

  • 16位．食べられないクッキー獲得！
  • 例年より参加者数が多いらしい．

問題概要

  • 20x20のオーブンと，2つのレーン(SmallLane,LargeLane)がある．
  • 各レーンには8つの生クッキー(Piece)がある．
  • 毎ターン，次のいずれかの行動を取る．
    • 何もしない．
    • レーンからPieceを1つ取り出し，オーブンに載せる*1．レーンのPieceは自動的に補充される．
  • オーブンに載せられたPieceは，Pieceごとに割り当てられる焼きターン数後に自動的に取り出され，Pieceごとに割り当てられるスコアが加算される．
  • 補充されるPieceは完全なランダムではなく，「傾向」がある．
  • 1000ターン以内に焼き上がったPieceのスコアの総和が，そのステージのスコアになる．

強そうな画像

seed = 100 200 300 400 stage 1 turn 686

f:id:m_buyoh:20181018203729j:plain

*1:回転して置くことは出来ない．

続きを読む

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

鉄道会社の乗り換えを最小化せよ

かなり雑なブログ記事です

続きを読む