脳log[20210912]

2021年09月12日 (日) [AtCoder] 精進。ちょっと前の ABC215-E「Chain Contestant」(水 diff)。当日にこう書いている>「今日の感じだと E 問題 F 問題が解ける世界線はそう遠くないと思えるんだけど、つまりは、解けなかったってことなんだな。E 問題で TLE 解が作れただけ」。実際、日を改めれば解けるんだよ>提出 #25816607。それに、166 ms でだいぶイケてると思う>Ruby によるすべての提出。これを本番でだね……。■調子に乗って考え方を書いておこう。現在の状態をどうクラス分けできるか。これまでに出たコンテストの集合と最後に出たコンテストの種類のペアで分けられる。それだけが区別できれば十分。それが D = Array.new(11){[0]*(1<<10)} の部分。幅 10 のビットフラグが 10+1 個分。コンテストの種類は 10 なんだけど、余分な +1 を 10 個の合計の記録用に確保した(Ds = D[-1])。というのは、最後に出たコンテストの区別は現在のコンテストと同じか異なるかという二値で十分なのに、異なるものが９個に分かれてると集計が面倒だから。あとはコンテストの回を追って、参加した場合参加しなかった場合を数えていくだけ。■これは自分が DP を知らなかった昔に DP と知らずに書いたのと同じ形>20120214p01.02。Project Euler の 191 問目だった。