歯科医の前にN(<=4000)人の子供たちが行列を作っていて各子供には1から順番に数字がふられている。子供iには、治療の際の泣き声の大きさv[i]、逃げ出すときの泣き声の大きさd[i]、自信p[i]の3つの値が設定されている。i番目の子供は治療されるときに大きさv[i]の声で泣く。泣き声は行列の先頭からの距離に対して減衰していく。ある大きさの泣き声を聞いた子供はその分だけ自信を減らす。自信が0を下回った子供jは大きさd[j]の声で泣きながら、出口へと走り去っていく。このとき、子供jより後ろにいたすべての子供の自信はd[j]だけ減る。逃げ出す子供がいなくなるまでこれが繰り返される。行列が詰められるのは逃げ出す子供がいなくなってからとする。このような条件下で歯科医は何人の子供を治療できるか。その人数と治療できる子供の番号を答えよ。単純にループを回して愚直にシミュレーションするだけで解ける。ある子供は治療されるか逃げ出すかのどちらかなので、各治療の際に逃げ出す子供をすべてシミュレーションしてもO(N2)となる。以下の解法はpythonだがpypyで投げないと間に合わないので注意。ans))まとめ設定が面白い問題。本番はcnt==v[i]のところをcnt==vとしていてバグらせていた。読者になるリンクTopCoderCodeforcestwitterGitHubQiitaはてなブログをはじめよう!roiti46さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。