YSF(J)H006 忘備録

HackerRank

YSF(J)H006

　参加ありがとうございました。本来は部活のメンバーのみで行う予定でしたが、想定以上の人数が参加してくれて驚きでした。
　今回はBとEのWriterをさせていただきました。

A

文字通り実装してください

cout<<"HelloWorld\nLoveNanashi"<<endl;

とかでいいんじゃないでしょうか。

B

配列でi番目のゲートが次いつ開くか、を保存する。というのが想定解でした。
各車両について、入る時間がゲートが開く時間以降であった場合、開くまでの時間を足していく…といった感じです。
また、配列をPriority_queueなどにすると実装が軽くなります。 計算量は前者の場合はO(TN)、後者の場合は挿入にlogNかかるのでO(TlogN)となります。

C

高々5本なので、全通りを試しても構いません。通り数は5C3より20通りです。
また、bit全探索を行うことにより、楽に実装をすることができます。
計算量は25なので十分に間に合います。

D

これ難しくないですか?きれいな解法がわかりません。
差の通りは高々4通りです。
1つ目から各差を足してって、正しいのが4つになったときに残りの一つがおかしい。それがなかったら最初がおかしいという風に説くことができます。

E

DP[i][j]をi回目の操作でMで割った余りがjであるものの通り数、という風に定義します。
1回目の動作にてDP[0][(1~6)%M]+=1とします。
i回目の動作以降、j(0~M)に対してDP[i][(j*(1~6))%M]+=DP[i-1][j]とします。
N回までの動作が終わったとき、DP[N-1][K]が答えとなります。
また、適宜modをとっていってください。計算量はO(NM)です。