123に参加したときに書いたソースコードの振り返りです。D問題は解けなかったのでA,B,C問題のみです。AtCoderよりご確認ください。問題の制約より、アンテナ同士の距離が最長となるのはアンテナAとアンテナEの組です。よって、アンテナAとアンテナEの距離だけを見て判定すれば良いことになります。その場合、ソースコードは以下のようになるかと思われます。コンテスト参加中に私がとった解法は、「各アンテナについて、自身よりも東側に位置するアンテナ全てとの距離を求め、直接通信不可能な組み合わせを探す」というものです。具体的には、アンテナAとB,C,D,Eとの距離を計算し、直接通信不可能な組み合わせを探すアンテナBとC,D,Eとの距離を計算し、直接通信不可能な組み合わせを探すアンテナCとD,Eとの距離を計算し、直接通信不可能な組み合わせを探すアンテナDとEとの距離を計算し、直接通信不可能な組み合わせを探すという作業を行っています。明らかに無駄な処理を行っていますが、一応これでもACできます。B問題1回目の注文を時刻0に行うことと、料理が届いたとき、注文可能になったらすぐに注文することは自明でしょう。問題となるのは、どのような順番で料理を注文するのがベストかです。ここで、「注文は10の倍数の時刻にしかできない」という制約に注目しましょう。この制約があるため、最後に注文する料理以外は料理が届いた後に無駄な待ち時間が発生してしまいます。料理が届いても、時刻が10の倍数になるまでは料理を注文できずに待たなければならないので、その時間が無駄となるのです。上の図からもお分かりいただけるかと思いますが、最後に注文する料理以外は(調理時間以上となる最小の10の倍数-調理時間)だけ無駄な待ち時間が発生します。この例では、料理Aは無駄な待ち時間が20-20=0分、料理Bは同20-13=7分、料理Cは同20-15=5分となります。最後に注文する料理については無駄な待ち時間を気にしなくて良いので、無駄な待ち時間が最大となる料理を最後に注文すれば、すべての料理が届くまでの時間を最小にできます。(残りの料理については、どのような順番で注文しても無駄な待ち時間の総和は変化しません。)この例では、無駄な待ち時間が最大となる料理Bを最後に注文することで、3つの料理が届くまでの時間を最小化できます。いうわけで、ソースコードは以下のようになります。調理時間の1の位の数字は、調理時間を10で割った余りです。これが0の場合は無駄な待ち時間が0となりますが、それ以外の場合は(10-調理時間を10で割った余り)が無駄な待ち時間となります。そのため、調理時間を10で割った余りが0以外で最小となる料理が無駄な待ち時間が最大となる料理です。無駄な待ち時間を考慮した調理時間(料理を注文してから次の料理を注文できるようになるまでの時間)は、無駄な待ち時間が0の場合を除けば(調理時間の10の位の数字+1)×10分です。C言語では整数同士の割り算を行うと小数部分は切り捨てられます。よって、調理時間の10の位の数字は単純に調理時間を10で割ることで求められます。C問題C問題は、「全員の移動時間はボトルネックとなる(一度に運べる人数が最少の)交通機関に依存する」ことに気づくことができれば攻略できます。求める移動時間は、都市iからi+1まで移動する交通機関がボトルネックであり、それで一度に移動できる人数がX人であるとすると、以下の3項を足し合わせたものとなります。(N÷Xの小数点以下を切り上げた値)+4分です。ソースコードは以下のようになります。→このブログを応援する・寄付する当ブログでは暗号通貨による寄付を募っております。