buyoh.hateblo.jp

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

Code Festival Team Relay (Parallel) - D 数直線

雑でごめんなさい

問題

cf18-relay-open.contest.atcoder.jp

数直線上に N 個の点があり、i 番目の点の座標は x_i です。また、N 個の整数 w_i が与えられます。

次の条件を満たす点 p の座標を求めてください。条件を満たす点が複数ある場合は、最も座標が小さいものを求めてください。

条件: 「1≤i≤N を満たす整数 i に対する (p から点 i までの距離) × w_i の最大値が最小になる。」

続きを読む

COLOCON -Colopl programming contest 2018- D すぬけそだて――トレーニング――

この程度の愚直DPが間違ってたのダメ

問題文

beta.atcoder.jp

  • スタミナとよばれる概念があり,0で空,Xで満タンである.時刻1単位でスタミナは1回復する
  • 時刻0にてスタミナはXである
  • T_1..T_NからK個のタイミングを選んで,スタミナを0にして,スタミナを減らした分だけ経験値がたまる
  • 全てのK∈1..Nについて,獲得できる経験値の最大値を計算する.
続きを読む

ハル研究所プログラミングコンテスト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

続きを読む

定数倍高速化

アルゴリズムとはほぼ無関係.

スタート地点

遅いコード 2797 ms Submission #3108991 - AtCoder Regular Contest 025

namespace Twoを修正します.

一番早いantaさんを見て絶対届かないと思いました.

続きを読む

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

解説とは違う方法なので

問題

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

キーワード

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