作問の振り返り

意図

過去に競プロの世界において出題側を複数回経験しました．

しかし，それらの解説や作意は「はてなブログ」に書いていたり，ICPCのOB/OG会に置いているため，外部サービスに依存して散逸している印象があります．

そこで，思い出深いものに関しては git を用いつつ手元に集約しておきたいと考えました．

すべてのことを記事にすることはできませんが，少しずつ増やしていこうと思います．

問題集

1. Dinner

個別記事へ

  • 与えられる要素は整数 $N, P, Q$ と長さ $N$ の数列 $C$ である．
  • この問題では $N$ 日間の夕食の計画を立て，各日の幸福度の合計を最大化したい．
  • 各日の行動の選択肢は2つあり，「自炊する」か「食堂に行く」ことである．
    • $i$ 日目の行動が「食堂に行く」である場合，この日の幸福度として $C_i$ を得る．
    • $i$ 日目の行動が「自炊する」である場合，この日の幸福度として $P \times y_i$ を得る．
  • なお，数列$y$は次のように決まる :
    • $y_1 = Q$
    • $i$ 日目の行動が「自炊する」である場合， $y_{i+1} = y_{i} + 1$ が成立する．
    • $i$日目の行動が「食堂に行く」である場合， $y_{i+1} = y_{i} - 1$ が成立する．
  • 本質的な制約
    • $N \leq 5 \times 10^5 $

( Japan Alumni Group Summer Camp 2014 Day 4 Problem D, 2014/9/15 )

ジャッジ