AOJ2510 Twin book report (JAG Domestic 2013 C)
まず本を読み終わる時間を最短にするには一人目が所要時間の長い順に本を読み、二人目の子供は二冊目から同様に読めば良い。一人目が一冊目を読む間に、二人目が二冊目以降を読み終わらない場合は最適性は明らか。全て読み終わったあとに仲良く感想文を一緒に書けば、最短終了時間も明らか。
二人目が二冊目以降を読み終わってしまう場合にも、とりあえず本を読み終わる時間は最短であることが分かる。二人目は一冊目以外を読み終えたあとに一人目が一冊目を読み終えるまでの間で最も長い時間を作文に費やすのが最適となるので、これはDPで求められる。
確かに分かってしまえば簡単だが、長い順に読むというのも自明というほどではないのでC問題にしては難しいと思う。
