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