ドワコン問題概要AチームとBチームにわかれて対戦するゲームがある。このゲームでは試合終了後に各プレイヤーのリザルトとしてkill数とdeath数が表示される。リザルトは各チームごとにkill数の多いプレイヤーから順に表示される。kill数が同数の場合はdeath数の少ない順になる。ある試合が終わったあとのAチーム(N人)のリザルトとBチーム(M人)のリザルトがkill数のみ表示された状態で与えられるので、ありうるdeath数の組合せが何通りあるか求めよ。AチームのdeathはBチームのkillによってしか起こらず、BチームのdeathはAチームのkillによってしか起こらないものとする。1000解法もし「kill数が同数の場合はdeath数の少ない順になる」という制約がなければ、以下のようなDPで答えを求めることができる。i人目までにj個のdeathを割り当てたときの、deathの配り方DPの遷移は単純にi人目に何個のdeathを配るかということになるので、0~sum(kill数の合計)を総当たりすればよい。このDPの計算量はO(N×sum(kill数)2)でおおよそ108くらいになる。このくらいであればやたら定数倍が重いデータ構造を使うのでもない限り間に合う範疇である(と感覚的には思っている)。次に「kill数が同数の場合はdeath数の少ない順になる」という制約を入れた場合であるが、これも基本的には上のDPと同じ形で解くことができる。そのために必要な考え方は「ある人にdeathを1つ割り当てるとき、後ろに同じkill数の人たちが並んでいるのであれば、その人たちにも必ずdeathを1配ることにする」ということである。このような配り方をすると昇順のルールが崩れず、しかもdeathの割り当てを各人で独立に考えることができるようになる。これを踏まえて上のDPを書き直すと、まずDPの状態は↑と同じである。遷移だけが少し変わっており、配るdeathの数を「自分+自分の後ろにいてkill数が同じ人の数」の倍数に限ることにする(これが「後ろのひとたちにも同じ数deathを配る」に当たる)。sum(kill数))が答えとなる。計算量は前述のものと同様。落ちるDP遷移を教えてもらいました。これだと108が105に落ちるので圧倒的に間に合いますね(というか想定解をブチ抜いている)。詳しく書いていただいたのでぜひコメントの方を見てみてください。数直線の原点上に人が2人いる。長さNの01文字列Sが与えられる。(1)はてなブログをはじめよう!fluffyowlさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。