po

反省😭

今回のテストはね、反省。 次がんばろう。

I - Platoon Match

I: Platoon Match - CODE FESTIVAL2015チーム対抗早解きリレー | AtCoder

参加者をAチームとBチームに分けたとき、Aチームの(参加者たちの合計の)kill数がBチームのdeath数に等しければ矛盾しないのでvalid。そうでなければinvalid。しかし、

Aチームのkill数=全体のkill数-Bチームのkill数

なので、結局全体の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となります。この配列を埋めるには、 i番目の参加者をBチームに追加するとどうなるかを考えます。 i番目の参加者のkill数を K、death数を D、追加する前のBチームの(kill+death)数を sBとすると、

  • dp[sB]==1

dp[sB]==1ならば追加後のBチームの(kill+death)数 sB+K+Dについてもdp[sB+K+D]=1と更新できます。

  • dp[sB]==0

dp[sB]==0のときは、 i番目の参加者をBチームに追加しても、Bチームの(kill+death)数= sB+K+Dは達成できないのでdp[sB+K+D]は更新されません(0に更新されるわけではない)。*1

また、端っこの条件はdp[0]=1です。なぜなら、どんな入力を与えられても、参加者の中から一人もBチームに入れなかった場合Bチームの(kill+death)数は0となるからです。

解答例

ソースコードの例は以下のようになります。 内側のfor文をfor(int sB=0; sB<=sk; sk++)とすると、たとえば同一の iに対して、まず、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に更新され・・・となってしまいます。これは、一つのチームに i番目の参加者を複数人入れてしまうようなことなのでだめです。*2
forの範囲が0からskまでなのは、そうしないとdp[sk]が更新される機会すらなくなるから(?)です。sk-1でもいいかもしれません。

おわりに

何か奇跡が起きない限り予選通過できないと思うんですが……。

参考

CODE FESTIVAL 2015 チーム対抗早解きリレー · うさぎ小屋

*1:???

*2:ダメ