結果
順位 297th / 5299 パフォーマンス 1889 レーティング 1906 → 1904(-2)
まぁこんなもんだろうという成績。しかしとうとうmorio__氏にぶち抜かれてしまったので、時間は流れているなぁという感じ。
A - Circle
素直。
B - Echo
普通に番目と
番目を比較していった。
substr使うのは思い浮かばなかった。
C - Average Length
賢くやる方法がありそうだとは思いつつ、制約が愚直にやっていいよと言ってくれているのでそのままやった。next_permutationを使うのが久しぶりで不安になりながらの実装だったけど、基本的にdo{}while();を使うのってここしかないしな。解説PDFの解法2はいやなるほどですね。
D - Knight
ちょろっと図を描いてみたらパスカルの三角形が出てくるのでコンビネーションのライブラリを持ってきて終了。
E - All-you-can-eat
最初は「一番最後に食べる料理を全探索」という方針で考えていたが、やっぱりここで取られるのがつらいので考え直してみると、美味しさが最大の料理は絶対採用して良いのだなということに気づく。採用する場合、末尾かそうでないかの二通りだが、末尾じゃない場合は先頭に置けば良く、そうするとその最大料理を食べた状態で同じ問題を解くことになるのでこれでほぼ解法が見える。美味しさでソートしておいて、大きい順に末尾or先頭に置いていけば良い。末尾に置く場合は直前までの料理で時間ギリギリになる最大の美味しさをDPで求めておけば良いので。2番目以降を末尾に置く場合もこのDPテーブルが使いまわせるのすごいなぁと思った。綺麗な問題だ。
解説PDFの解法1（前後で2つDPテーブルを作る）のは思い浮かばなかった。解法2が自分のやつと一緒……ってあれ、所要時間の方でソートするのか？ ん、でも美味しさ最大は絶対採用も間違ってはないよな。ほぼどちらでも大丈夫なのか。ふーん？
F - Laminate
の場合の数え方すら全然わかってなくてさっぱりダメでしたね。そこが見えたとしてもDPに帰着して、
、高速化すれば
ですか。こういうの全然できないなぁ。
