dwacon 2017 予選

リンク

問題 https://dwacon2017-prelims.contest.atcoder.jp/
解説 なし

概要

Aはやるだけ。
Bは/([2?][5?])+/にマッチする最長部分列の長さを求める問題なのだが、オーバラップがあるためたとえばPythonの標準ライブラリreだけでは単純に記述することは出来ない（はず）。
具体的には、入力例4を見てみると2???5????に対して225252525とはてなを埋めたときに長さ8の最長列を得られることが分かるが、オーバラップが扱えないと

$ echo '2???5????' | grep -Po '([2?][5?])+'
2???
????

と欲しい部分を見つけることが出来ない。
ここで少し考えると、最長の列を得られるような埋め方というのは「先頭から奇数文字目のはてなは2、偶数文字目は5」またはその逆、のどちらかであることが分かる。
これを使って、この2種類の埋め方で得られる2つの文字列から最長の列を探すだけで全体の最長の列を見つけることが出来る。
Cは貪欲にやる（という言い方であっているのかな）。つまりある搬器にあと2人乗せられる状況で1人乗せるか2人乗せるか迷う必要はなく、常に多い方を乗せればよい。
したがって、各時点で乗せられる限り大人数の団体を優先的に乗せる、というのを繰り返すだけで解ける。
Dは時間内に思いつける気がせず撤退してしまったが、解説している人のツイートなどを見て理解した。
問題は、短くまとめるとn個の寿司を順番に食べるとき、各寿司に「少しスコアが得られる食べ方」と「たくさんスコアが得られる食べ方」があり、「たくさんスコアが得られる食べ方」は全体でm回しか使えず、m回使ったあとに出てくる寿司はどちらの食べ方でも食べられない、というルールでスコアを最大化する問題。限られたm回の使い所を選ぶ方法を考える必要がある。
i皿目まででちょうどm回の権利を使い切るとして最大のスコアはいくつか？というのを前から順番に考えていくと、i + 1皿目を食べるときに「i + 1皿目でm回目の権利を使い切る」ために今までに食べた「たくさんスコアが得られる食べ方」を1回諦める、というのを繰り返して更新していけばよいが、ではどれを諦めるのが良いか？というと2つの食べ方によるスコアの差が一番小さかったものを諦めるのがよい。
これは優先順位付きキューを使うことで効率よく実装できる。
このiの結果を使ってi + 1を求めていく感じ、DPっぽいけどそう呼ぶのかどうかはわからない。
Eはわからず。