反省😭
今回のテストはね、反省。 次がんばろう。
I - Platoon Match
I: Platoon Match - CODE FESTIVAL2015チーム対抗早解きリレー | AtCoder
参加者をAチームとBチームに分けたとき、Aチームの(参加者たちの合計の)kill数がBチームのdeath数に等しければ矛盾しないのでvalid
。そうでなければinvalid
。しかし、
なので、結局全体のkill数と(Bチームのkill数+Bチームのdeath数)とが等しいかを調べればいいことになります。つまり、参加者の中から適当に何人か選んで、その人たちのkill数とdeath数を全部足して全体のkill数に等しくできればvalid
で、そうでなければinvalid
です。ただし、入力例3のように全体のkill数≠全体のdeath数の場合はあらかじめinvalid
を出力して終わります。
全体のkill数は普通に合計して求めればいいですが、
参加者の中から適当に選んで
の部分は参加者一人一人に対して、「選ぶ」「選ばない」の2通り(もしくは、Bチームに「入れる」「入れない」の2通り、など)考えられるので合計2N通りとなってつらいです。
そこで、添字がBチームの(kill+death)数で、その数を達成できるかどうか(0か1か)を値に持つ配列dp
を考えます。するとdp[全体のkill数]==1
ならばvalid
、そうでなければinvalid
となります。この配列を埋めるには、番目の参加者をBチームに追加するとどうなるかを考えます。番目の参加者のkill数を、death数を、追加する前のBチームの(kill+death)数をとすると、
dp[sB]==1
dp[sB]==1
ならば追加後のBチームの(kill+death)数についてもdp[sB+K+D]=1
と更新できます。
dp[sB]==0
dp[sB]==0
のときは、番目の参加者をBチームに追加しても、Bチームの(kill+death)数=は達成できないのでdp[sB+K+D]
は更新されません(0に更新されるわけではない)。*1
また、端っこの条件はdp[0]=1
です。なぜなら、どんな入力を与えられても、参加者の中から一人もBチームに入れなかった場合Bチームの(kill+death)数は0となるからです。
解答例
ソースコードの例は以下のようになります。
内側のfor
文をfor(int sB=0; sB<=sk; sk++)
とすると、たとえば同一のに対して、まず、sB=0
のときdp[sB]=1
なのでdp[k[i]+d[i]+sB]
(=dp[k[i]+d[i]]
)が1
に更新され、sB
がインクリメントされていきsB=k[i]+d[i]
になると前の結果よりdp[k[i]+d[i]]
は1
なのでdp[k[i]+d[i]+sB]
(=dp[2*k[i]+2*d[i]]
)が1
に更新され・・・となってしまいます。これは、一つのチームに番目の参加者を複数人入れてしまうようなことなのでだめです。*2
for
の範囲が0
からsk
までなのは、そうしないとdp[sk]
が更新される機会すらなくなるから(?)です。sk-1
でもいいかもしれません。
おわりに
何か奇跡が起きない限り予選通過できないと思うんですが……。
参考
https://kimiyuki.net/blog/2015/11/18/code-festival-2015-relay/