ABC145 感想
ABC145 問題
A
r * r
B
s[i]とs[i+n/2]をi=[0,n/2)で順に調べていく
C
グラフで考えると、枝の総数は本。各
!通りの経路について、１つの経路に使用される枝の本数は
本。
よって、経路の総和の
が１つの経路に使われていることがわかるから、対称性より、求める値は、全経路
。
D
と
を連立して、
,
これらが非負整数の時、
で求めた。
二項係数は、
このサイトを参考にした。MAXが小さいと正しい答えが出ないっぽい(要確認)
E
ナップザック問題をどう変えればいいかわからなかった。最初は各dp[i][j]について選んだものを保持し、最後に選んでないものの中から一番価値の高いものを選ぼうとしたが、できなかった。
左右からのdpやソートしてからのdpでできるらしい...。要精進。
レート
894 Highest!!
