久しぶりの20時開催という日本人に優しいスケジュールと逃すわけにはいかないと、前日からの風邪を押して*1参加。
DIV1 250 Fox Plaing Game
方針
またウサギ回だ。全部試すと 100 choose 50 でとんでもない組み合わせ数になるので無理。DP だろうなぁ。しかし、dp[n個決まった][その時の値] でやろうとすると、「その時の値」がすごい組み合わせになるし、実数だから、話にならない。
サンプルを読むと、全部足してから掛ける、(0に掛けることで)nB を全部消費してから足す、B を1つ潰して積部分を正にしてから足す、など、いろいろあるらしい。A, B について、-1, 0, 1 との大小関係で場合分けしたらよさそうだが、場合分けしたら絶対ミスしそう。しかも、それで十分だと証明できない……
実装
なんか可能性のある式が8通りくらいに絞り込めたので、これら全部試して、max を選ぶことにしよう(場合分け回避の術)。書いた。サンプル通った。自信ないけど、これ以上できそうにないので提出。時間かかりまくって、125点。
DIV1 500 Fox Average Sequence
方針
あれ? こっちの方が簡単じゃない? DP[1つ前の値][今の値] を更新していく感じで……。8割書いたところで、平均値についての制約を忘れていたことに気づく。DP[1つ前][今の値][これまでの和]は状態数 41 x 41 x 1600 で、これを 40 回更新すると……ちょっと無理だね。
Challenge
DIV1 250 で、あるパターンをコメントアウトすると、テストケースは通るけど、3, 3, -10, -10 が通らなくなることを発見。これは Challenge に使えそう。
他の人のコードを見る。ん? DPしてる。あー、やっぱり、私の解法じゃダメなのかな? もう余計なことをするのはやめよう。ログアウトして、公式配信の俺の後輩が(ry を見に行った。
結果
なんと 250 通る。1261→1299。
考察・感想
250は、DP[Aを使った回数][Bを使った回数] だった。これに気がつかないのは、ダメダメだった。これって、方眼紙の上で、左下からスタートして右上に到達するまでの組み合わせとかを求める典型的なDPじゃん(最大値・最小値を覚えておく必要があるのが変則的か)。通ったとはいえ、大反省。
500は、DP[2つ前と1つ前の大小関係(0 or 1)][1つ前の値(0-40)][これまでの和(0-1600] でやればよかったみたい。これも気が付きたいところだよなぁ。
ただ、前回の SRM 500 みたいな自力では全く解ける気がしない回に比べると、こういう反省点が見える回のほうが好き。
*1:この漢字であってる?
