'4'を選択したら、max(H-C, 1)時間が必要ですか？

0で帰還することも可能です。

D問題の難易度も同程度となっております
と書かれていますが本当なのでしょうか？

順位表を見た限り、本当ではないかもしれません。

sample4_EF.txt は部分点E の条件M = 1 を満たしていない気がするのですがどうでしょうか. 

間違っていました。サンプルを全てFとしてリジャッジします。

j!=k ならば idol_{i,j} != idol_{i,k} であることは保証されますか

保証されています。

「当確率で航路が選択される」は「等確率」ですよね？

等確率です。訂正します。

問題文、サンプルより「一度戦闘を行い、勝利した海域においては、再度その海域に進軍したとしても戦闘は発生しない」という理解でよろしいでしょうか？明記されていませんでしたので、質問させて頂きます。

一度勝利した海域においても、何度でも戦闘は発生します。

すべてのアイドルを集めることができることは保証されていますか

保証されています。

部分点の設定が間違ってませんか？

間違っておりました。訂正します。
点数自体には変わりがありませんが、採点される順番が変わっていますのでご確認ください。
（なお、上から順番に部分点を獲得する必要はありません）

sample3ですが、手元のRuby 1.8.7/1.9.3/2.0.0ではいずれも0を出力できるにも関わらず、REになってしまいます。

改行が余計に入っておりました。リジャッジを行います。

同じ種類のくじを何回も引くことは可能ですか

可能です。