freee プログラミングコンテスト2023（AtCoder Beginner Contest 310）

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

freee プログラミングコンテスト2023（AtCoder Beginner Contest 310） D~
Fどれも苦戦したがFまで。
D 答えの最大値が小さそうなので雑にDFS書いたら間に合った。
E ランレングス圧縮してメモ化再帰で解いた。もっと簡単な方法がありそうだけど分からず。
F 今までに現れた和の種類2^10個をもってDP

— titia (@titia_til) July 15, 2023

G - Takahashi And Pass-The-Ball Game

　解説を読んだけど、ダブリングの解法がすぐには理解できず、解説放送も参考にしてAC。

　ダブリングでいけそうということは分かっても、実装するのが難しい問題だった。

　ダブリングでさくっと求められるのは、「xさんのボールがy回の操作後どこにあるか？」だが、ダブリングの途中で二回の操作を一回にまとめていかねばならないため混乱しやすい。

　ダブリングをこういう風に使ったことがなかった気がするので、ちょっと新鮮だった。

　コンテスト中は行列累乗なんかを考えたりしていて的外れでした。

Ex - Negative Cost

　解説放送を見てAC。

・ナップザック問題で重みが大きいときどうするか？

　という問題の解法を知っていないと解くのが厳しかったと思う。

　最大効率に着目するのは直感にも合致していて、確かにそうだな、という感じ。

　この問題に帰着しようと思えたのなら、帰着する部分は思いつけなくはなさそう。